燕山大学2005年研究生入学----数据结构复习大纲
数据结构复习大纲(硕士研究生)
-、选用教材
严蔚敏编 清华大学出版，《数据结构》(第二版)
二、考试大纲
第一章
1．熟悉各名词、术语的含义，深刻理解基本概念。
2．了解抽象数据类型的定义、表示和实现方法。
3． 理解算法的概念及5个特性。
4．掌握算法时间复杂度的估算方法。
第二章
1．了解线性表的逻辑结构特性。
2．熟练掌握在顺序和链式存储上实现查找、插入、删除等基本 操作的算法。
3．能够从时间和空间复杂度的角度综合比较线性表两种存储结构 的特点及其适用场合。
第三章
1．掌握栈和队列这两种抽象数据类型的特点，并能在相应的应 用问题中正确选用它们。
2．熟练掌握栈的两种实现方法、基本操作及其算法。
3．熟练掌握循环队列上的基本操作方法。
4．理解递归算法执行过程中栈的状态变化过程。
第四章
1．熟悉串的定义和基本操作。
2．掌握在串的定长顺序存储结构上实现串的基本操作方法。
第六章
1．熟练掌握二叉树的定义、结构特性，了解相应的证明方法。
2．熟悉二叉树的各种存储结构的特点。
3．熟练掌握二叉树的各种遍历策略的递归和非递归算法，能灵I 活运用遍历算法实现二叉树的某些操作。
4．理解二叉树线索化的实质，掌握线索二叉树上的操作及算法。
5．熟悉树的各种存储及其特点，掌握树和森林与二叉树的转换 方法。
6．学会编写实现树和二叉树的各种操作的算法。
7．了解最优二叉树(哈夫曼树)的特性，掌握建立哈夫曼树和 哈夫曼编码的方法。
8．理解先序序列和中序序列能唯一确定一棵二叉树的道理。
第七章
1．熟悉图及相关定义，图的各种存储结构及其构造算法。
2．熟练掌握图的两种搜索方式和算法。
3．掌握最小生成树、拓扑排序、关键路径、最短路径等问题
的求解算法。
第九章
1．熟练掌握顺序表和有序表的查找方法。
2．熟练掌握二叉排序树的构造方法和查找方法。
3．掌握平衡二叉树的维护平衡的方法。
4．熟练掌握哈希表的构造方法，深刻理解哈希表与其他表的根 本区别。
第十章
1．理解排序的定义和各种排序方法的特点。
2．了解各种方法的排序过程及其依据的原则，了解基于"关键 字的比较'进行排序的方法和分类。
3．理解排序方法"稳定"和"不稳定"的含义。
4．掌握各种排序方法的时间复杂度的分析。
5．熟练掌握直接插入、折半插入、希尔插入、快速、堆选等排 序算法。
6．掌握归并和基数排序算法。
第十二章
理解文件的基本概念，熟悉各类文件的特点、构造方法及其 基本操作。
注：未列章节，不做要求。