【盛世清北】清华大数据工程考研经验笔记

2022考研随着五一小长假的到来，才发现考研已悄无声息的过了三分之一。随着时间的推移，报考清华考研的同学们，无论是寻找资料，向前辈请教还是报班的途径，终将选择最适合自己的考研路。而盛世清北为了帮助同学们少走弯路，特整理相关清华大数据工程考研经验笔记，与大家分享。

【招生目录】

自动化系

085400 电子信息

方向：

01(全日制)大数据工程

考试科目：①101 思想政治理论②201 英语一③301 数学一④827 电路原理

深圳国际研究生院

085400 电子信息

04(全日制)大数据工程

科目：①101 思想政治理论②201 英语一③301数学一④962数学-数据方向基础综合

【分数线】

962 数学-数据方向基础综合

《数据结构》(C语言版) 清华大学出版社 严蔚敏、吴伟民

827 电路原理

《电路原理》（第2版） 清华大学出版社，2007年3月 江辑光 刘秀成

《电路原理》 清华大学出版社，2007年3月 于歆杰 朱桂萍 陆文娟

《电路》（第5版） 高等教育出版社，2006年5月 邱关源 罗先觉

【考试大纲】

962数学-数据方向基础综合：

1.1什么是数据结构

1.2基本概念和术语

1.3抽象数据类型的表示与实现

1.4算法和算法分析

1.4.1算法

1.4.2算法设计的要求

1.4.3算法效率的度量

1.4.4算法的存储空间需求

2线性表

2.1线性表的类型定义

2.2线性表的顺序表示和实现

2.3线性表的链式表示和实现

2.3.1线性链表

2.3.2循环链表

2.3.3双向链表

2.4一元多项式的表示及相加

3栈和队列

3.1栈

3.1.1抽象数据类型栈的定义

3.1.2栈的表示和实现

3.2栈的应用举例

3.2.1数制转换

3.2.2括号匹配的检验

3.2.3行编辑程序

3.2.4迷宫求解

3.2.5表达式求值

3.3栈与递归的实现

3.4队列

3.4.1抽象数据类型队列的定义

3.4.2链队列——队列的链式表示和实现

3.4.3循环队列——队列的顺序表示和实现

3.5离散事件模拟

4串

4.1串类型的定义

4.2串的表示和实现

4.2.1定长顺序存储表示

4.2.2堆分配存储表示

4.2.3串的块链存储表示

4.3串的模式匹配算法

4.3.1求子串位置的定位函数 Index（S，T，pos）

4.3.2模式匹配的一种改进算法

4.4串操作应用举例

4.4.1文本编辑

4.4.2建立词索引表

5数组和广义表

5.1数组的定义

5.2数组的顺序表示和实现

5.3矩阵的压缩存储

5.3.1特殊矩阵

5.3.2稀疏矩阵

5.4广义表的定义

5.5广义表的存储结构

5.6m 元多项式的表示

5.7广义表的递归算法

5.7.1求广义表的深度

5.7.2复制广义表

5.7.3建立广义表的存储结构

6树和二叉树

6.1树的定义和基本术语

6.2二叉树

6.2.1二叉树的定义

6.2.2二叉树的性质

6.2.3二叉树的存储结构

6.3遍历二叉树和线索二叉树

6.3.1遍历二叉树

6.3.2线索二叉树

6.4树和森林

6.4.1树的存储结构

6.4.2森林与二叉树的转换

6.4.3树和森林的遍历

6.5树与等价问题

6.6赫夫曼树及其应用

6.6.1最优二叉树（赫夫曼树）

6.6.2赫夫曼编码

6.7回溯法与树的遍历

6.8树的计数

7图

7.1图的定义和术语

7.2图的存储结构

7.2.1数组表示法

7.2.2邻接表

7.2.3十字链表

7.2.4邻接多重表

7.3图的遍历

7.3.1深度优先搜索

7.3.2广度优先搜索

7.4图的连通性问题

7.4.1无向图的连通分量和生成树

7.4.2有向图的强连通分量

7.4.3最小生成树

7.4.4关节点和重连通分量

7.5有向无环图及其应用

7.5.1拓扑排序

7.5.2关键路径

7.6最短路径

7.6.1从某个源点到其余各顶点的最短路径

7.6.2每一对顶点之间的最短路径

8动态存储管理

8.1概述

8.2可利用空间表及分配方法

8.3边界标识法

8.3.1可利用空间表的结构

8.3.2分配算法

8.3.3回收算法

8.4伙伴系统

8.4.1可利用空间表的结构

8.4.2分配算法

8.4.3回收算法

8.5无用单元收集

8.6存储紧缩

9查找

9.1静态查找表

9.1.1顺序表的查找

9.1.2有序表的查找

9.1.3静态树表的查找

9.1.4索引顺序表的查找

9.2动态查找表

9.2.1二叉排序树和平衡二叉树

9.2.2B 树和B+树

9.2.3键树

9.3哈希表

9.3.1什么是哈希表

9.3.2哈希函数的构造方法

9.3.3处理冲突的方法

9.3.4哈希表的查找及其分析

10内部排序

10.1概述

10.2插入排序

10.2.1直接插入排序

10.2.2其他插入排序

10.2.3希尔排序

10.3快速排序

10.4选择排序

10.4.1简单选择排序

10.4.2树形选择排序

10.4.3堆排序

10.5归并排序

10.6基数排序

10.6.1多关键字的排序

10.6.2链式基数排序

10.7各种内部排序方法的比较讨论

11外部排序

11.1外存信息的存取

11.2外部排序的方法

11.3多路平衡归并的实现

11.4置换一选择排序

11.5最佳归并树

12文件

12.1有关文件的基本概念

12.2顺序文件

12.3索引文件

12.4ISAM 文件和VSAM 文件

12.4.1ISAM 文件

12.4.2VSAM 文件

12.5直接存取文件（散列文件）

12.6多关键字文件

12.6.1多重表文件

12.6.2倒排文件

【历年真题】

第一部分数据结构(70分)

1、判断题10×2'

T(n)=T(n/2)+O(1)的解总是T(n)=O(log n)

比较算法CBA的排序与时间复杂度O(nlog n)

2、单选题8×3'

非法表达式+逆波兰式

evaluate()表达式求值算法

3、算法题6'+4'+3'

单峰向量:设计算法

4、算法题6'+4'+3'

最大和区间:设计算法求出一组数的最大和区间

后序遍历中，first()函数和next()函数。(10分)

first()函数是求出后序遍历的第一个点，写出算法思路、伪代码

next()函数是求出当前节点后序遍历中的后一个结点，，写出算法思路、伪代码

由题意可知，通过first和next就能求出树的后序遍历，分析一下，这种方法与正常求后序遍历的方法有什么差异。

利用广度优先遍历的思想，求图中最小的围长，围长就是图中环的权加和，要求空间复杂度为O(n)，时间复杂度为O(ne)，e为边的个数，n为点的个数。(15分)

1.算法思路

2.伪代码

3.时间空间复杂度

我的思路是，对每一个结点都加一个信息，就是该结点父亲的信息。

按照广度优先遍历将所有结点入队，如果图中有环，会出现两个相连信息相同的结点。

找到相邻且相同的结点，根据父亲结点的信息，递归出环的所有结点，结束条件就是两个结点的父亲相同。

求出环的圈长，循环检查所有环，实时更新，最后输出最小圈长。

stl中的归并排序与正常归并排序的代码有些不同，下面给出stl中归并排序的源码(15分)

1.补全上文中确实的代码

2.解释上文划线代码的含义

3.这种归并排序与正常的归并排序相比有什么优缺点

【考研经验】

考研的备战是持久战，需要不断的补充体力和脑力，如果没有一个好的身体，你是没有办法撑完考研全程的，身体不行，毅力就更不行了，别幻想着你毅力强大，硬撑打时间战，不代表考研就能顺利通关，不要假装自己很努力，盛世清北清华考研辅导班根据历年的经验，发现有这样的一批考生，就喜欢熬夜，白天睡不醒，晚上不睡觉，熬夜学习，毕竟考试是在白天，这样熬夜学习效率也并不高，本末倒置。总结一个正确复习状态送给那些需要熬夜的年轻人。

一、调整生活习惯

面对即将到来的考试，同学们复习力度也在逐渐加大，恨不得一天24小时都在学习，这样一来，同学们的睡眠时间必定会减少；睡眠时间不充足，会引起一系列的健康问题。所以考生们不管学习有多紧张，最好在11点之前入睡；不然容易造成免疫力下降，从而引起一系列的健康问题。我们面对即将到来的考试，要及时调节自己的生物钟，让自己的作息时间和考试的时间进行充分的吻合。这么做的主要目的就是让我们考试当天能够以一个良好的状态去面对考试，发挥自己最大的能力。所以最后一个月，大家不要再熬夜了，保持正常的作息才是关键。

二、正确对待错题

现在同学们的复习不要再以每天大量的做题为主了，那样只会浪费现在的宝贵时间，而且部分同学大量做卷子还停留在单纯的对答案阶段，根本起不到什么实质性的的作用。现在盛世清北建议考生要做的就是把之前的那些错题，统统整理出来，让自己再过一遍之前做错的题；并把它研究透彻，知道自己为什么错，是哪个部分没有掌握好，对于没有掌握好的部分要进行进一步的清理，把盲点全部扫除掉，把能拿下来的分数拿下来。错题的整理，既是一种复习巩固，又是一种查缺补漏。对于我们知识的掌握和复习效率的提升都有显著效果。

三、冲刺分清主次

现在各科的复习已经进入最后的收尾工作了，现在基本上就是扫除知识盲区，进行知识点的查缺补漏。政治的复习目前同学们应该把之前做过的那些错题重新进行整理归纳；并且针对各个板块重点多做题，掌握一些答题方法和技巧。还要多多关注时政新闻，对今年的一些时政热点进行全面了解。

英语在这个复习我们同样要进行扫盲，把之前的错题进行再次突击，争取做到考试的时候，错过的题目绝不再错。大家还要抽出一个完整的时间做一套完整的题目，看自己用时多少，根据自己所用的时间和考试的时间进行对比，并作出相关的调整方案。

专业课的复习，同学们对于往年的考试试题做一个汇总，了解出题人的思路，喜欢在那些地方出题。对于出题人喜欢的板块一定要倒背如流。

四、合理饮食，保证身体正常运转

清华考研辅导班建议不用刻意地吃得特别好，如果肠胃不适应的话，反而会收到负效果。考试前既不可空腹，也不可过饱。要忌暴饮暴食，注意饮食卫生。每天定时睡觉、起床，调整好“生物钟”也是保证最佳身体状况的方法。很多身体不适的原因也有心理紧张的因素，可以参照消除紧张感的方法使自己放松，心理上轻松了，身体上的压力也能减轻不少。

五、考前建立自信

考前没有自信，一是对所学的知识掌握不牢，还存在知识空白点，二是太看重考试。针对第一点要做到根据实际情况，尽可能夯实基础；针对第二点，要正确认识考试。知道原因后，我们可在早晨起床时马上暗示自己心情愉快、有信心，能放松情绪。另外要看到自己的优点，多进行提高自信心的心理训练，克服自卑情绪。还有要正确的认识考试，这一次考试并不能决定什么，就算失败，它也能给自己带来经验和阅历，花些时间能弥补回来，并不能让自己产生损失。

身体是革命的本钱，盛世清北清华考研辅导班说的嘴皮都要破了，一定要记住，身体垮了，即使考上研究生也没什么用，大家一定要谨记。