2016年华科834复试笔试题

答：

一

1.上界函数:一个算法时间复杂度的渐进紧确上界

2.最优性原因：原问题的最优解包含子问题的最优解

3.分治法：将一个问题划分为规模更小，互不重叠的子问题求解的方法

二

1.01背包问题：动态规划，分支限界，回溯法等

2.最优二分检索树问题：动态规划

3.深度优先数：未知知识点

三

Floyd算法寻找最短路径过程

动态规划： d[i][j](k）表示考虑前k个结点的所有松弛操作

有些遗忘的知识点：最短路径问题中各种方法对比

四

由题意，应该用贪心算法求出max和min，（猜测题目是正数情况）

简单计算（（（a*b+1）c+1）*d+1）=abcd+cd+d+1

可见要使这个值小则就使cd+d小

先将数组排序好

求最小时：每次先选最大的两个数

求最大时：每次先选最小的两个数

类似于Huffman编码求解过程

时间复杂度O（nlg（n））空间O（n），可以用优先队列实现

五

双指针遍历法，时间复杂度O(k),空间复杂度O（1）

伪代码略

数据库

答

一

1.笛卡尔积，差，投影

2.正确性（完备性是F+中所有函数依赖可由amstrong公理推出）

3.物理结构设计阶段（模糊不清楚）

4全选（模糊不清楚）

5.首先AC可以排除，意向锁具有一定粒度，感觉应该选B（模糊不清楚）

二

题目描述不是很清楚，我假设一个教练对应一堂课

1.

会员号、课程号是码，由于又存在课程号决定教练号，非主属性存在部分依赖，所以只能是1NF，存在数据冗余、更新异常、插入异常、删除异常。

2.

select id 
from pi 
where time>20
group by id 
having count(id)>1

select id
from pi_fin
where time=studytime
group by id 
having count(id)>1

三、

这里不好画图，但是实际我在计算时，确实有失误，需要补充这部分的知识

四、

知识模糊点

五

二段锁协议可以保证可串行调度，但是可串行调度不一定符合二段锁协议

六

分析题目是系统故障，REDO+UNDO，需要日志文件，找到最近一次备份的日志文件先正向扫描，将已经执行好的事务写入redo队列， 未执行完的写入undo队列；对redo队列，正向扫描日志，执行对应操作，直到事务结束；对undo队列，逆向扫描日志文件，执行对应操作的逆操作直到事务开始

这张试题暴露的问题还挺多。需要再开一篇文章来讲解

https://blog.csdn.net/qq_36684096/article/details/105943586