第一部分考试说明

　　一、考试性质

　　数据结构是计算机各专业的专业基础课。它的评价标准是高等学校计算机科学与技术各专业本科毕业生能达到的及格或及格以上水平，以保证被录取者具有基本的专业理论基础及程序设计能力，以利于计算机科学与技术各专业的导师择优选拔硕士研究生。

　　考试对象为参加全国硕士研究生入学考试的本科毕业生和具有同等学力的在职人员。

　　二、考试范围

　　各种基本类型的数据结构的概念、特征、操作、存储表示和基本应用；各种基本查找表的概念、特征及其查找方法，基本的内排序和外排序方法；文件在外存储器中的基本表示方法；用C语言（或C ）描述算法和程序设计，算法分析。

　　三、评价目标

　　在考查基本概念、基本知识、基本方法的基础上，注重考查学生运用基本知识来分析和解决实际问题的能力，注重考查算法和程序设计的能力。

　　具体要求见本考试大纲第二部分的“考查要点”。

　　四、考试形式与试卷结构

　　1.答卷方式：闭卷，笔试。

　　2.答题时间：180分钟。

　　3.考查内容及其考查比例

　　基本概念、基本知识、基本方法约占40～50；综合应用、算法和程序设计与算法分析约占60～50.

　　4.试卷结构与考试题型

　　试卷共150分，基本的考试题型有：

　　（1）单项选择题和多项选择题；

　　（2）填空题（基本概念、基本知识、基本方法）；

　　（3）画图题；

　　（4）简答题；

　　（5）应用题（求解问题）；

　　（6）算法和程序设计填空题；

　　（7）算法和程序设计与分析题；

　　（8）其它题型。

　　五、教材和参考书

　　教材：《数据结构》（C语言版），严蔚敏、吴伟民编著，清华大学出版社，1997.4

　　第二部分考查要点

　　1.数据结构和算法

　　数据结构、存储结构的概念；数据类型与抽象数据类型；算法的概念，用C/C 描述算法和程序设计，算法分析初步。

　　2.线性表

　　线性表的定义和基本操作；线性表的抽象数据类型；线性表的顺序存储结构，

　　应用举例；线性表的链式存储结构（单链表，双链表，循环链表），应用举例。

　　3.栈

　　栈的定义和基本操作；栈的抽象数据类型；顺序栈，链式栈；栈和递归算法，算术表达式求值，其它应用。

　　4.队列

　　队列的定义和基本操作；队列的抽象数据类型；顺序队列，链式队列；双端

　　队列的定义和基本操作；应用举例。

　　5.数组和广义表

　　（1）数组

　　数组的定义和基本操作；数组的顺序存储结构，应用举例；特殊矩阵和稀疏

　　矩阵的压缩存储。

　　（2）广义表

　　广义表的定义和基本操作，广义表的抽象数据类型，广义表的存储结构。

　　*广义表运算的实现举例。

　　6.字符串

　　字符串的定义和基本操作，字符串的存储结构，字符串操作的实现举例，字符串和模式匹配。

　　7.树和二叉树

　　（1）树的基本概念和基本操作，树的抽象数据类型。

　　（2）二叉树的概念和性质，特殊二叉树；二叉树的存储结构；

　　（3）二叉树的生成与建立。

　　（4）遍历二叉树：前序遍历，中序遍历，后序遍历，层次遍历。

　　（5）二叉树其它操作实现举例。

　　（6）线索二叉树的概念和存储结构，二叉树的线索化，线索二叉树的遍历。

　　（7）树的存储结构，树与二叉树之间的转换，森林与二叉树之间的转换，树和森林的遍历。

　　（8）树的路径长度和带权路径长度，哈夫曼树（Huffman）的概念，哈夫曼算法，哈夫曼编码树。

　　（9）二叉排序树的的概念和基本操作，二叉排序树的建立，二叉排序树其它操作实现举例。

　　8.图

　　（1）图的基本概念和基本操作，图的抽象数据类型。

　　（2）图的存储结构：数组表示法（邻接矩阵）；邻接表，逆邻接表，十字链表；邻接多重表。

　　（3）图的遍历：深度优先搜索法，宽度优先搜索法，求图的连通分量。

　　（4）生成树、最小生成树的概念；克鲁斯卡尔（Kruskal）算法，普里姆（Prim）算法。