《数据结构》考试大纲

一、        基本要求

掌握数据结构的基本概念、基本分析方法和基本算法，包括数据结构的基本概念、线性表、栈和队列、树和二叉树、图、查找技术以及排序技术。

二、        考试范围

第1章 绪论

1.1 数据结构在程序设计中的作用（C）

1.2 不作要求

1.3 数据结构的基本概念（B）

1.4 算法及算法分析（A）

第2章 线性表

2.1 线性表的逻辑结构（B）

2.2 线性表的顺序存储结构及其实现（A）

2.3 线性表的链接存储结构及其实现（A）

2.4 顺序表和链表的比较（C）

第3章 栈和队列

3.1 栈

3.1.1 栈的逻辑结构 （B）

3.1.2 栈的顺序存储结构及其实现（A）

3.1.3 栈的链接存储结构及其实现（B）

3.1.4 顺序栈和链栈的比较 （B）

3.2 队列

3.2.1 队列的逻辑结构 （B）

3.2.2 队列的顺序存储结构及其实现（A）

3.2.3 队列的链接存储结构及其实现（B）

3.2.4 循环队列和链队列的比较 （C）

3.3 应用举例

3.3.1 栈的应用—表达式求值 （A）

3.3.2 队列的应用—火车车厢重排（B）

第4章 字符串和多维数组

4.1 字符串（B）

4.2 多维数组（B）

4.3 矩阵的压缩存储（A）

4.4 应用举例（C）

第5章 树和二叉树

5.1 树的逻辑结构（B）

5.2 树的存储结构（C）

5.3 二叉树的逻辑结构（A）

5.4 二叉树的存储结构及实现

5.4.1 顺序存储结构 （B）

5.4.2 二叉链表（A）

5.4.3 三叉链表（C）

5.4.4 线索链表（C）

5.5 二叉树的遍历非递归算法（B）

5.6 树、森林与二叉树的转换（A）

5.7 应用举例

5.7.1 二叉树的应用举例—哈夫曼树及哈夫曼编码 （A）

5.7.2 树的应用举例—八枚硬币问题（C）

第6章 图

6.1 图的逻辑结构（A）

6.2 图的存储结构及实现

6.2.1 邻接矩阵 （A）

6.2.2 邻接表（A）

6.2.3 十字链表（C）

6.2.4 邻接多重表（C）

6.2.5邻接矩阵和邻接表的比较（C）

6.3 最小生成树（A）

6.4 最短路径（B）

6.5 有向无环图及其应用（A）

第7章 查找技术

7.1 概述：查找的基本概念（A）

7.2 线性表的查找技术（B）

7.3 树表的查找技术（A）

7.4 散列表的查找技术（A）

第8章 排序技术

8.1概述：排序的基本概念（A）

8.2 插入排序 （A）

8.3 交换排序 （B）

8.4 选择排序 （A）

8.5 归并排序 （A）

8.6 分配排序 （C）

8.7 各种排序方法的比较 （B）

（上述内容中，A的内容是重点，要求学生掌握；B的内容要求学生熟悉；C的内容要求学生了解。）

三、        参考书目

1. 王红梅等编，数据结构（C++版）（第2版） [M]. 北京：清华大学出版社，2011.06

2. 王红梅等编，数据结构（C++版）学习辅导与实验指导（第2版） [M]. 北京：清华大学出版社，2011.09

3. 严蔚敏，数据结构（C语言）[M]. 北京：清华大学出版社，2015.03

4. 周桂红，数据结构[M]。 天津：南开大学出版社，2016.09