2019年清华大学伯克利数据科学基础综合真题回忆

清华-伯克利深圳学院数据科学与信息技术（数据科学交叉学科硕士项目清华-伯克利深圳学院数据科学与信息技术（数据科学交叉学科硕士项目）培养方案（2016年6月修订）一、适用学科、专业：数据科学与信息技术（学科代码99J3）数据科学交叉学科作为面向信息技术与跨学科前沿交叉领域的国际化高端人才培养项目，适用学科、专业包括：计算机与数据科学类、电子信息技术类、机械工程类（含仪器仪表）和人文与社会科学类等。

二、培养目标通过课程学习和研究实践，具备数据科学与信息技术相关科技领域较宽广的专业知识，掌握扎实的专业技能，具备在智能传感、信息器件、信息处理、网络技术、数据科学、人机交互等领域开展创新性工作的能力，创办相关高新技术企业的能力和管理全球性产业的能力，培养全球科技、工程领袖和未来企业家，为解决区域和全球性重大挑战输送高素质人才。

三、学习年限与学位设置采用全脱产的培养方式,培养地点在深圳和加州伯克利。

学习年限2～3年，不超过清华大学硕士学位研究生最长修业年限。

按照以下两种方式的一种设置。

1、全程在清华-伯克利深圳学院学习，完成各培养环节，并满足清华大学硕士学位授予要求的学生将被授予清华大学“数据科学与信息技术”学术型硕士学位。

2、第一学年在清华-伯克利深圳学院学习，第二学年到加州伯克利大学学习（9个月），第三学年回到清华学习。

完成各培养环节，并同时满足清华大学和加州伯克利大学硕士学位授予要求的学生，可获得清华大学与加州伯克利大学双硕士学位。

四、培养方式数据科学交叉学科硕士研究生项目采用前沿交叉研究与创新实践紧密结合的教育模式，实行导师组负责制。

培养环节主要包括：基础课程、专业模块、工程领导力、专题研究、企业实践、毕业论文等环节。

五、学位学分要求研究生在攻读全日制的数据科学交叉学科硕士期间，总学分不少于24学分。

具体如下：1、公共必修课 5学分2、专业必修课程不少于15学分3、学术与职业素养课程不少于1学分4、必修环节 3学分攻读全日制的数据科学交叉学科硕士项目的研究生，可以向加州伯克利大学申请攻读工程硕士项目，如获得加州伯克利大学工学院工程硕士项目录取，且修满该校学位要求学分，可向该校申请工程硕士学位。

清华⼤学数据结构试题和答案⼀、单选题（每题 2 分，共20分）1.1.对⼀个算法的评价，不包括如下（B ）⽅⾯的内容。

A．健壮性和可读性B．并⾏性C．正确性D．时空复杂度2.2.在带有头结点的单链表HL中，要向表头插⼊⼀个由指针p指向的结点，则执⾏( )。

A. p->next=HL->next; HL->next=p;B. p->next=HL; HL=p;C. p->next=HL; p=HL;D. HL=p; p->next=HL;3.3.对线性表，在下列哪种情况下应当采⽤链表表⽰？( )A.经常需要随机地存取元素B.经常需要进⾏插⼊和删除操作C.表中元素需要占据⼀⽚连续的存储空间D.表中元素的个数不变4.4.⼀个栈的输⼊序列为1 2 3，则下列序列中不可能是栈的输出序列的是( C )A. 2 3 1B. 3 2 1C. 3 1 2D. 1 2 35.5.AOV⽹是⼀种（）。

A．有向图B．⽆向图C．⽆向⽆环图D．有向⽆环图6.6.采⽤开放定址法处理散列表的冲突时，其平均查找长度（）。

A．低于链接法处理冲突 B. ⾼于链接法处理冲突C．与链接法处理冲突相同D．⾼于⼆分查找7.7.若需要利⽤形参直接访问实参时，应将形参变量说明为（）参数。

A．值B．函数C．指针D．引⽤8.8.在稀疏矩阵的带⾏指针向量的链接存储中，每个单链表中的结点都具有相同的（）。

A．⾏号B．列号C．元素值D．⾮零元素个数9.9.快速排序在最坏情况下的时间复杂度为（）。

A．O(log2n) B．O(nlog2n) C．0(n) D．0(n2)10.10.从⼆叉搜索树中查找⼀个元素时，其时间复杂度⼤致为( )。

A. O(n)B. O(1)C. O(log2n)D. O(n2)⼆、⼆、运算题（每题 6 分，共24分）1. 1.数据结构是指数据及其相互之间的______________。

当结点之间存在M对N（M：N）的联系时，称这种结构为_____________________。

“数据库概论”2019年秋（李红燕）期末考试回忆版Sulley更新：December30,20191填空题1.一百万项记录，阶数n=20的B+树至少需要多少次磁盘读取？2.关系数据库常用的优化技术有哪两种？3.外排序由哪两部分组成？4.数据库故障恢复一般用什么方法？5.关系代数中的θ连接是由哪两个操作组成？6.另外三题不记得了评论这个是真的有点坑，开始助教发邮件说是选择，就没有怎么复习细节，最后竟然是填空，而且考的是比较细微的地方。

好在一分一空，问题不大。

2简答题1.比较嵌套循环连接和块嵌套训练连接对不同内外层分配的代价大小。

数据来自课件db11p.18~24。

2.课件db7p.37~38的例子。

3.证明，若关系模式R不满足BCNF，那么一定存在属性A,B∈R，使(R−AB)→A成立。

4.使用其他关系代数定义关系代数除法，见课件db2p.55~57。

5.XQuery的一个查询。

6.B+树的插入与删除，课件db10p.25~28。

评论都是重点内容，好好复习即可。

在答题的时候把B+树的插入和删除搞反了，我服了。

3并发控制协议写出时间戳协议在什么情况下操作不允许。

时间戳协议存在死锁吗？为什么？举例说明存在活锁的情况。

4关系数据库设计给出了一个课程的关系模式。

第一问要求写出函数依赖集；第二问求一个候选码；第三问求BCNF分解；第四问求3NF分解。

5数据库模型设计给定一个现实背景。

第一问要求画出ER图；第二问根据ER图写出关系模式；第三问到第六问，要求用关系代数或SQL语句进行查询。

评论本次考试总的来说难度不大，但内容很大、考点很细，需要认真准备才能拿高分。

如果不准备拿高分，其实也挺简单的。

[2019初试真题回忆] 2019年河南理工大学数据结构专业真题回忆（941）
2019年真题跟往年的真题题型都不一样了，整张卷子算法设计题占据了85％，河理工院校的真题有时候能找到有时候找不到，这个回忆版或许会帮助到想考河理工计算机学院的学弟学妹们！
1 链表和顺序表有啥区别，各自的优缺点
2 写出带头单链表查找第k个结点的代码
3 写出单链表查找倒数第k个结点的算法
4 给出模式串\\\"ababaabab\\\"，求next值和详细的计算过程（PS:2019的大纲里没提到串的知识，但是居然考了串，所以复习要全面覆盖，不能有遗漏，你觉得不考的可能偏偏会考，所以把它要求的那本书吃透）
5 给出一个无向图，写出邻接矩阵和邻接表（根据它给出近3年真题，这个每年都考了）
6 用prim求最小生成树的生成过程的具体步骤
7 设计一个算法求十个数中第5大的数（ps:1-10中第5大的数是6），还问算法时间复杂度能否达到O（N）？
8 怎么用一维数组存储满二叉树写出代码过程
其他暂时有点模糊，记不大清晰了，总之，复习要全面，复习要尽早，所有的成功都不是空穴来风，你要相信自己的努力终将有迹可循，加油研儿们，向前冲鸭！。