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(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
上一篇: 92.翻转链表
下一篇: 华科2017年计算机学院机试题(c++)