华科2015复试算法和数据库笔试题（不完全回忆版）

emptybottle123

前天签了录取协议，被录取的事应该是没问题了。说好考上了发帖的~今准备写考研经历，一看怎么没人发今年的笔试题呢？明明前几年都有人发的，前人栽树后人乘凉的优良传统不能丢啊。于是我先来发题目回忆版吧，考研经历以后再写。不过过了这么久，我也只记得一部分了，希望有人能帮忙补全。


算法原理
一，名词解释（3小题，每题3分）
1、上界函数；
2、最优性原理；
3、分治法；
二、填空（2分/空*5，只记得两个，还记不清具体值了。。）
1、0/1背包问题，背包中物品质量为w={w1,w2,w3,w4}，收益p={p1,p2,p3,p4},背包容量为M，问最大收益以及此时的解向量{x1,x2,x3,x4}。
2、二分检索树，有5个结点，求最小的代价和此时检索树的路径长度。3.已知结点的深度优先数，求某两个结点的最低深度优先数（这是双连通分量里面的知识点）。
三、一个有4个结点的有向图，提供了图的邻接矩阵，模拟floyd算法寻找最短路径的过程。（10分）
四、黑板上有一个数组，每次擦掉两个数a和b，再把a*b+1写回黑板上，直到黑板上只剩下一个数。设最后剩下的数最大为max，最小为min，求极差s=max-min。用贪心策略设计算法求s，描述你所设计的算法，并写出你所设计算法的时间复杂度和空间复杂度。（12分)
五、有两个数组中分别有m和n个元素，分别按非降序排列。设计算法求出两个数组中第k小的元素，用伪代码写出你设计的算法，并写出算法的时间复杂度。(9分)
数据库
一、选择题（10题、每题1分，我并没有全部记得）
1、代数运算中的除运算可以分解成哪几种基本运算（）
2、由F出发根据Armstrong原理推导出来的函数依赖一定在F+中是指Armstrong原理的（）。
3、一个数据库在试运行前，管理员正在考虑分区问题，问此时处在数据库设计的（）阶段。
4、哪个优化需要用到数据字典（）
四个选项为查询优化、代数优化、物理优化三选二或全选
5、以下封锁中并行性最强的是（）
A、一次申请全部封锁；B、二段锁；C、按次序申请封锁；D意向锁；
二、有一个关系模式含有两个表，PI(会员号，课程号，课时，教练号)，PI_FIN（会员号，课程号，时间，学习时间）;(15分，每问5分)
问：（1）、该关系模式最多满足第几范式，还要求说明关系模式PI存在的问题，也就是低级范式的缺点，总之要求会判断，也要会说明相应第x范式的优缺点；
（2）、用SQL求至少选修了两门课时为30小时的课程会员；
（3）、用SQL求至少完成了两门课所有课时的会员号；
三、某学术期刊中包含如下关系：一个学术主题包含多篇文章，每个文章只能投给一个主题；每篇文章有多个作者，作者中只有一个投稿者；每个学术主题有多个审稿人，每篇文章有多个审稿人对其进行审稿，每个人都给出审稿意见。学术主题包含主题名和主题编号，作者包含作者名和作者编号，文章包含文章名和文章编号，审稿人包含审稿人编号和名字。对以上关系画出E-R图并设计关系模式，注意标明主码和外码。（10分)
四、B+树索引和hash索引在存取时有什么区别？应用背景上有什么区别？(5分)
五、二段锁协议与冲突可串行化调度有什么关系；(5分)
六、一个学校的数据库每周日12点进行一次全盘备份，每日12点进行一次差异备份，每小时进行一次日志备份。机器在2015年3月11日凌晨3:31出了系统故障，请问怎么恢复能使损失最小。(5分)

yocooo

还有经验吗？继续分享哈

来自Android客户端

wumengchao1234

哇咔咔多谢师兄

wumengchao1234

想请教一下师兄。华科复试笔试除了算法和数据库还会考什么？