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

五
明白三种情况
丢失修改：是你改我改，修改被覆盖丢失
不可重复读：我读后发生了更新
读脏数据：读后事务被撤销