中国传媒大学硕士研究生入学考试
《算法与数据结构》
一、考试的总体要求
《算法与数据结构》不仅是大学本科计算机科学与技术专业的专业基础课，也是其他从事计算机信息处理专业的一门重要的基础课程。它主要考查考生对数据的组织、存储、处理等能力，算法设计以及对算法的分析和评价的掌握程度。要求考生理解数据结构的逻辑结构和物理结构的基本概念，熟练掌握各种数据结构以及有关算法，并具有综合运用所学知识分析和解决实际问题的能力。
二、考试的内容
（一）数据结构的基本概念
1．什么是数据结构
2．逻辑结构
3．存储结构
4．数据运算
5．抽象数据类型的表示与实现
6．算法和算法分析
（二）线性表
1．线性表的基本概念
2．线性表的顺序表示和实现
3．线性链表
4．循环链表
5．双向链表
6．链表的应用
（三）栈和队列
1．栈和队列的基本概念
2．栈的顺序实现
3．栈的链式实现
4．栈的应用
5．栈与递归的实现
6．队列的顺序实现
7．队列的链式实现
（四）串
1．串的顺序存储表示
2．串的堆分配存储表示
3．串的块链存储表示
4．Brute-Force模式匹配算法
5．KMP模式匹配算法
6．串操作的应用
（五）数组和广义表
1．数组的顺序表示和实现
2．特殊矩阵
3．稀疏矩阵
4．广义表的定义
5．广义表的存储结构
6．广义表的运算
（六）树和二叉树
1．树的定义和基本术语
2．二叉树的定义和性质
3．二叉树的顺序存储
4．二叉树的链式存储
5．遍历二叉树
6．线索二叉树
7．树的存储结构
8．森林与二叉树的转换
9．树和森林的遍历
10．树与等价问题
11．赫夫曼树及其应用
（七）图
1．图的定义和基本术语
2．图的数组表示法
3．邻接表
4．十字链表
5．邻接多重表
6．图的深度优先搜索
7．图的广度优先搜索
8．无向图的连通分量和生成树
9．有向图的强连通分量
10．最小生成树
11．拓扑排序
12．关键路径
（八）动态存储管理
1．可利用空间表及分配方法
2．边界标识法
3．伙伴系统
4．无用单元收集
（九）查找
1．查找的基本概念
2．顺序查找
3．二分查找
4．分块查找
5．二叉排序树
6．平衡二叉树
7．B-和B＋树
8．哈希表的构造方法
9．处理冲突的方法
10．哈希表的查找及分析
（十）内部排序
1．直接插入排序
2．希尔排序
3．冒泡排序
4．快速排序
5．简单选择排序
6．树形选择排序
7．堆排序
8．归并排序
9．基数排序
10．各种内部排序方法的比较
（十一）外部排序
1．外部排序的方法
2．多路平衡归并的实现
3．置换－选择排序
4．最佳归并树
（十二）文件
1、文件的基本概念
2、顺序文件
3、索引文件
4、ISAM文件
5、VSAM文件
6、散列文件
7、多重表文件
8、倒排文件
三、考试的基本题型
主要题型可能有：是非题、选择题、填空题、简答题、算法设计题、综合题等。
四、考试的形式及时间
笔试，不需要任何辅助工具。考试时间为三小时。
