下载文档原格式
清华考研辅导班-2020清华大学962数学-数据方向基础综合考研经验真题参考书目清华大学962数学-数据方向基础综合考试科目，2020年初试时间安排为12月22日下午14:00-17:00业务课二进行笔试，清华大学自主命题，考试时间3小时。
一、适用院系及专业清华大学伯克利深圳学院0812J3数据科学与信息技术清华大学伯克利深圳学院0830J2环境科学与新能源技术二、考研参考书目清华大学962数学-数据方向基础综合有官方指定的考研参考书目，盛世清北整理如下：《数据结构》(C语言版) 清华大学出版社严蔚敏、吴伟民盛世清北建议：（1）参考书的阅读方法目录法：先通读各本参考书的目录，对于知识体系有着初步了解，了解书的内在逻辑结构，然后再去深入研读书的内容。
体系法：为自己所学的知识建立起框架，否则知识内容浩繁，容易遗忘，最好能够闭上眼睛的时候，眼前出现完整的知识体系。
问题法：将自己所学的知识总结成问题写出来，每章的主标题和副标题都是很好的出题素材。
尽可能把所有的知识要点都能够整理成问题。
（2）学习笔记的整理方法A:通过目录法、体系法的学习形成框架后，在仔细看书的同时应开始做笔记，笔记在刚开始的时候可能会影响看书的速度，但是随着时间的发展，会发现笔记对于整理思路和理解课本的内容都很有好处。
B:做笔记的方法不是简单地把书上的内容抄到笔记本上，而是把书上的关键点、核心部分记到笔记上，关上书本，要做到仅看笔记就能将书上的内容复述下来，最后能够通过对笔记的记忆就能够再现书本。
三、重难点知识梳理2020年清华大学深圳国际研究生院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倒排文件四、考研真题2009年，教育部出台了严格管理院校自主命题专业考试科目相关资料、限制专业课辅导的规定，很多学校从那时起不再公布和出售真题，并不再提供专业课参考书目。
2020年硕士研究生统一入学考试《计算机专业基础》第一部分考试说明一、考试性质计算机专业基础是计算机科学与技术学科（一级学科）、计算机技术工程领域硕士生入学考试的专业基础课。
考试对象为参加东北大学计算机科学与工程学院2020年全国硕士研究生入学考试的准考考生。
二、考试形式与试卷结构（一）答卷方式：闭卷，笔试（二）答题时间：180分钟（三）考试题型及比例简答题20%综合题80%（四）参考书目《数据结构》，严蔚敏，清华大学出版社，2001年。
《C语言程序设计》（第3版），谭浩强,清华大学出版社,2010年。
第二部分考查要点（一）数据结构考查要点1 绪论1.1 数据结构的基本概念和术语1.2 抽象数据类型的表示与实现1.3 算法和算法分析2 线性表2.1 线性表类型定义2.2 线性表的顺序表示和实现2.3 线性表的链式表示和实现3 栈和队列3.1 栈的类型定义、表示和实现3.2 栈的应用3.3队列的类型定义、表示和实现3.4 队列的应用4 串4.1 串的类型定义、表示和实现4.2串操作应用5 数组和广义表5.1数组的定义、顺序表示和实现5.2特殊矩阵的压缩存储5.3广义表的定义和存储结构6 树和二叉树6.1 树的定义和基本术语6.2二叉树的定义、基本性质和存储结构6.3遍历二叉树和线索二叉树6.4树和森林6.5哈夫曼树及哈夫曼编码7 图7.1 图的定义、基本术语和存储结构7.2图的遍历7.3图的连通性和最小生成树7.4有向无环图、拓扑排序和关键路径。
9 查找9.1 静态查找表9.2 动态查找表9.3 哈希表10 排序10.1 插入排序10.2 快速排序10.3 选择排序10.4 归并排序10.5 基数排序10.6排序方法的比较（二）C语言考查要点1、算法及其描述方法1.1算法的概念、特点1.2算法的描述方法（流程图、N-S流程图）1.3程序设计的三种基本结构；2、数据类型、运算符和表达式2.1变量和常量2.2 预处理命令2.3数据类型（整型、实型、字符型）2.4算术运算符、表达式3、顺序程序设计3.1各种类型数据的格式化输入/输出方法3.2字符数据的非格式化输入/输出方法3.2顺序程序的设计4、选择结构程序设计4.1关系运算符、逻辑运算符和条件运算符4.2 if、switch语句；4.3 if语句的嵌套。
962 《数学-数据方向基础综合》考试大纲为准。
一. 学科概述“数据科学和信息技术”是清华大学自主设置的交叉学科，面向未来的社会发展需求并已按国家有关文件要求完成备案的新型学科.欢迎但不限于以下专业背景的同学报考：电子科学与技术、信息与通信工程、计算机科学与技术、电气工程、动力工程及工程热物理、光学、应用经济学、数学、物理、化学、仪器科学与技术、机械工程、控制科学与工程、土木工程、管理科学与工程、航空宇航科学与技术、社会学等。
二．参考书目：《数据结构》(C语言版) (严蔚敏、吴伟民清华大学出版社)三．考试内容：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倒排文件。
10.4 选择排序
选择排序(Selection Sort)的基本思想是：每一趟在n-i+1(i=1,2, …,n-1)个记录中选取关键字最小的记录作为有序序列中的第 i个记录。
10.4.1 简单选择排序
10.4.2 树形选择排序
10.4.3 堆排序
10.4.1 简单选择排序
假设排序过程中，待排记录序列的状态为：
有序序列R[1..i-1] 无序序列 R[i..n]
从中选出关键字最小的记录第 i 趟
简单选择排序
有序序列R[1..i] 无序序列 R[i+1..n]
简单选择排序的算法描述如下：
void SelectSort (Sqlist &L ) {
// 对顺序表&L作简单选择排序。
for (i=1; i<L.length; ++i) {
// 选择第 i 小的记录，并交换到位
j = SelectMinKey(L, i);
// 在 L.r[i.. L.length] 中选择关键字最小的记录 if (i!=j) L.r[i]←→L.r [j]; // 与第i个记录交换
}
} // SelectSort
算法 10.9
时间性能分析
对 n 个记录进行简单选择排序，所需进行的关键字间的比较次数总计为：
2 ) 1
(
) (
1
1 -
=
-
∑
-
=
n n
i
n
n
i
移动记录的次数，最小值为 0, 最大值为3(n-1) 。
10.4.3 堆排序（Heap Sort）
堆的定义:
堆是满足下列性质的数列{r1, r2, …，r n}：
r i<=r2i r i<=r2i+1
或
r i>=r2i
r i>=r2i+1
(小顶堆) (大顶堆)
例如:
{12, 36, 27, 65, 40, 34, 98, 81, 73, 55, 49} 是小顶堆{12, 36, 27, 65, 40, 14, 98, 81, 73, 55, 49} 不是堆
若将该数列视作完全二叉树，则 r 2i 是 r i 的左孩子； r 2i+1 是 r i 的右孩子。
r i
r 2i r 2i+1
例如:
12 36
27 65
40 34 98 81 73 55 49 是堆
14 不
堆排序即是利用堆的特性对记录序列进行排序的一种排序方法。
以大堆顶为例，若在输出堆顶的最大值之后，使得剩余的n-1个元素的序列重又建成一个堆，则得到n个元素中的次大值，如此反复执行，便能得到一个有序序列，这个过程称之为堆排序。
例如：
{ 40, 55, 49, 73, 12, 27, 98, 81, 64, 36 } 40
55
49 73 98 81 12 27 64 36
初始序列 建大顶堆 { 98, 81, 49, 73, 36, 27, 40, 55, 64, 12 } 98
81 49 73 40 55 36 27 64 12 初始堆 交换 98 和 12
{ 12, 81, 49, 73, 36, 27, 40, 55, 64, 98 } 12 81 49 73 40 55 36 27 64 98 交换98和12 经过筛选 重新调整为大顶堆
{ 81, 73, 49, 64, 36, 27, 40, 55, 12, 98 }
81
73 49 64 40 55 36 27 12 98
重调整为堆
定义堆类型为:
typedef SqList HeapType;
// 堆采用顺序表表示之
两个问题:
1、如何由一个无序序列“建堆”？
2、如何在输出堆顶元素之后，调整剩余元素成为一个新的
堆，即“筛选”？
所谓“筛选”指的是，对一棵左/右子树均为堆的完全二叉树，“调整”根结点使整个二叉树也成为一个堆。
筛
选
堆
堆
例如 98 81 49
36 27 40 55 64 12 是大顶堆
但在 98 和 12 进行互换之后，它就不是堆了，
12 98 因此，需要对它进行“筛选”。
比较 12
81
73
64 12
void HeapAdjust (HeapType &H, int s, int m)
{ // 已知H.r[s..m]中记录的关键字除 H.r [s] 之外均满足堆的定
//义，本函数自上而下调整 H.r[s] 的关键字，使 H.r[s..m] 也
//成为一个大顶堆
rc = H.r[s]; // 暂存 H.r[s]
for ( j=2*s; j<=m; j*=2 ) { // 沿key较大的孩子向下筛选
if ( j<m && H.r [j].key<H.r [j+1].key ) ++j; //j为key较大的 //记录的下标 if ( rc.key >= H.r[j].key ) break; //rc应插入在位置s上
H.r [s] = H.r [j]; s = j;
}
H.r [s] = rc; // 将调整前的堆顶记录插入到s位置
} // HeapAdjust
算法 10.10
if ( j<m && R[j].key<R[j+1].key ) ++j;
// 左/右“子树根”之间先进行相互比较 // 令 j 指示关键字较大记录的位置
if ( rc.key >= R[j].key ) break;
// 再作“根”和“子树根”之间的比较， // 若“>=”成立，则说明已找到 rc 的插 // 入位置 s ，不需要继续往下调整
R[s] = R[j]; s = j;
// 否则记录上移，尚需继续往下调整
void HeapSort ( HeapType &H ) {
// 对顺序表 H 进行堆排序
for ( i=H.length/2; i>0; --i )
HeapAdjust ( H, i, H.length ); // 建大顶堆
for ( i=H.length; i>1; --i ) {
H.r[1]←→H.r[i];
// 将堆顶记录和当前未经排序子序列
// H.r[1..i]中最后一个记录相互交换
HeapAdjust(H, 1, i-1); // 对 H.r[1..i-1] 进行筛选 }
} // HeapSort
算法 10.11
建堆是一个从下往上进行“筛选”的过程。
例如: 排序之前的关键字序列为
40 55 12 98 81 36 81 73 98 49
81
73
55 现在，左/右子树都已经调整为堆，最后只要调整根结点，使整个二叉树是个“堆”即可。
98
49 40 64 36 12 27
堆排序的时间复杂度分析：
1.对深度为 k 的堆，“筛选”所需进行的关键字比较的次数至多为2(k-1)；
2.对 n个关键字，建成深度为h=(⎣log2n⎦+1)的堆，所需进行的关键字比较的次数至多 4n；
3.调整“堆顶”n-1次，总共进行的关键字比较的次数不超过
2 (⎣log2(n-1)⎦+ ⎣log2(n-2)⎦+ …+log22) < 2n(⎣log2n⎦)
因此，堆排序的时间复杂度为O(n log n)。
