2015年华科834复试笔试题

简介: 2015年华科834复试笔试题

1685019939096.jpg

答:

一、

1.

最优子结构,重叠子问题

2.

算法在最坏情况下的平均运行时间(模糊)

3.

类似于锦标赛算法,比较log2n向上取整次

4.

遗忘知识点:各类排序算法比较

5.

渐进紧确界,上界函数,下界函数

6.

明白BFS的实现方式即可

7.

0/1背包问题:动态规划

8.

回溯法和分支限界法的区别

在于状态空间树的构造方式不一样,一个是深度优先,一个是广度优先


二、

floyd算法:关键是更新d[i][j] (k)


主要代码块

floyd(A,n)//A是图对应邻接矩阵,n是顶点数
d←A//用二维矩阵d存储最短距离,初始化为A,不存在边定义为无穷
for k←0 to n-1 1 do
   for i←0 to n-1 1 do
       for i←0 to n-1 1 do
         if d[i][j]>d[i][k]+d[k][j]
           then d[i][j]=d[i][k]+d[k][j]


三、

有点类似于树的先序遍历,只不过在遍历的时候先左孩子再左孩子

递归实现比较简单,时间0(n),空间复杂度0(n)

关键在于循环实现,利用一个栈,进入时先进右孩子到底,边进边生成树左孩子,之后右孩子出来看其左分支,循环上述过程

0(n),0(n)

这里对空间复杂度有点小迷糊了


四、

这里可能想考贪心算法,但是题目描述有点问题

1685019971989.jpg


一二它描述不清楚

三题老大题

(1)关键字和记录放在一块,减少I/0次数

(2)检查点操作可以标记事务开始的位置,能很快在日志中找到事务,而且检查点之前完成的事务不用再redo


明白三种情况

丢失修改:是你改我改,修改被覆盖丢失

不可重复读:我读后发生了更新

读脏数据:读后事务被撤销

相关文章
|
存储 程序员 Linux
从软硬件交互的角度去看中断的一生
从软硬件交互的角度去看中断的一生
272 0
|
6月前
|
机器学习/深度学习 人工智能 文件存储
Llama Nemotron:英伟达开源基于Llama架构优化的推理模型,253B参数持平DeepSeek R1!
NVIDIA推出的Llama Nemotron系列推理模型,基于Llama架构优化,包含Nano/Super/Ultra三款,在数学推理、编程和工具调用等任务中展现卓越性能。
177 5
Llama Nemotron:英伟达开源基于Llama架构优化的推理模型,253B参数持平DeepSeek R1!
|
机器学习/深度学习 网络架构
YOLOv8改进 | 2023主干篇 | 利用RT-DETR特征提取网络PPHGNetV2改进YOLOv8(超级轻量化精度更高)
YOLOv8改进 | 2023主干篇 | 利用RT-DETR特征提取网络PPHGNetV2改进YOLOv8(超级轻量化精度更高)
948 1
|
JavaScript 前端开发 UED
探究: 为什么JavaScript要在body标签尾部引入?
探究: 为什么JavaScript要在body标签尾部引入?
169 0
|
SQL 分布式计算 MaxCompute
了解那些“奇葩”SQL写法,快速写出高效率SQL(2)
了解那些“奇葩”SQL写法,快速写出高效率SQL
129 0
了解那些“奇葩”SQL写法,快速写出高效率SQL(2)
|
SQL 网络协议 Oracle
异地使用PLSQL远程连接访问Oracle数据库【内网穿透】
异地使用PLSQL远程连接访问Oracle数据库【内网穿透】
310 0
多线程实践-生产者消费者
多线程实践-生产者消费者
122 0
|
Linux 程序员 Shell
冬季实战营第二期学习报告
针对第二期的Linux操作系统实战入门,通过动手实操的体验写出感受。时间真快,从1月24日到1月28日,参与了五天不同内容的动手实战,从中发现虽然在大学里学过这门课,但是好像没有这期收获很多没有学过的知识点,每一天都在涨知识,不得不感叹,学无止境,感觉真妙,可见大学里学的东西比较浅,还需要自学其它很多新知识点,感谢第二期Linux操作系统实战入门的体验,再接再厉~ 让我们一起向未来。
193 0
冬季实战营第二期学习报告
|
存储 自然语言处理 数据库
Lucene 查询原理
# 前言 Lucene 是一个基于 Java 的全文信息检索工具包,目前主流的搜索系统Elasticsearch和solr都是基于lucene的索引和搜索能力进行。想要理解搜索系统的实现原理,就需要深入lucene这一层,看看lucene是如何存储需要检索的数据,以及如何完成高效的数据检索。
8863 1