2015年华科834复试笔试题

答：

一、

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）

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

四、

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

一二它描述不清楚

三题老大题

四

（1）关键字和记录放在一块，减少I/0次数

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

五

明白三种情况

丢失修改：是你改我改，修改被覆盖丢失

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

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