���˸߿�

（二）数据结构考试大纲（100分）

一、考试要求
1、能分析数据的内在逻辑关系。
2、掌握常用数据结构在计算机中的表示方法。
3、理解数据表示和数据处理之间的关系，理解算法效率的分析方法。
4、能利用常见的数据结构，进行算法设计。

二、考试内容
第1章引论
1、了解数据结构的基本概念。
2、了解数据的逻辑结构、存储结构、算法的概念。
3、理解数据类型、抽象数据类型的概念。
4、理解时间复杂度、空间复杂度的概念。
第2章表
1、理解ADT表的概念及基本运算。
2、掌握表的顺序存储结构及其运算的实现。
3、掌握表的链接存储结构及其运算的实现。
4、理解单链表、循环链表、双向链表的特点。
第3章栈
1、掌握栈的定义和基本运算。
2、掌握栈的顺序实现及其运算的实现。
3、掌握栈和队列的链接实现及其运算的实现。
4、掌握栈的应用。
第4章队列
1、掌握队列的定义和基本运算。
2、掌握队列的顺序实现（循环队列）及其运算的实现。
3、掌握队列的链接实现及其运算的实现。
4、掌握队列的应用。
第5章递归
•理解递归的概念。
•了解分治与递归的关系。
•了解用栈模拟递归技术。
第6章排序与选择
•理解排序的基本概念（关键字、内外排序、稳定性、时间效率、空间效率）
•掌握选择排序的方法（简单选择排序、堆排序）
•掌握插入排序的方法（直接插入排序）
•掌握交换排序的方法（冒泡排序、快速排序）
•了解合并排序的方法。
•理解各种排序方法的优缺点。
第7章树
1、掌握树的表示法，包括父亲结点数组表示法、儿子链表表示法、左儿子右兄弟表示法。
2、理解二叉树的定义和术语、性质。
3、掌握二叉树的存储结构，包括顺序存储实现和指针实现。
4、掌握二叉树的遍历算法及其应用。
5、了解线索树的概念。
第8章集合
1、了解以集合为基础的抽象数据类型。
2、了解集合上的基本运算。
3、了解集合的实现（位向量实现、链表实现）。
第9章符号表
•理解抽象数据类型符号表的概念。
•掌握符号表的数组实现。
•掌握开散列表和闭散列表的实现。
•理解散列函数构造方法以及处理冲突的办法。
•掌握线性再散列技术。
第10章字典
•理解抽象数据类型字典及其运算。
•掌握二叉搜索树及其实现。
第11章优先队列
•理解抽象数据类型优先队列及其基本运算。
•理解堆的概念及其实现。
•掌握哈夫曼树及其应用。
第12章图
•解图的概念、术语。
2、掌握图的存储结构（邻接矩阵、邻接表）
3、掌握图的遍历方法（深度优先遍历、广度优先遍历）
4、掌握图的小生成树的算法（prim算法、kruskal算法）。
5、掌握图的单源短路径的dijkstra算法。
•了解所有顶点对之间的短路径floyd算法。

三、考题类型
•选择题（概念、存储表示、算法描述）：24%
•填空题（概念、存储表示、算法描述）：16%
•应用题（综合）：40%
•算法设计题：20%

参考用书：
《数据结构与算法》，王晓东编，高等教育出版社