课程编号：842课程名称：数据结构

一、 考试的总体要求

掌握常用数据结构的逻辑结构、存储结构和基本操作，灵活运用所学的数据结构解决实际问题。

二、 考试的内容

1．基本概念：数据、数据元素、数据对象、数据类型与抽象数据类型、时间复杂度、空间复杂度、线性结构（线性表、栈与队列）、非线性结构（树与二叉树、图）、查找、排序、哈夫曼树、二叉排序树、二叉平衡树、哈希表、AOV图、AOE网等。

2．常用数据结构的基本内容：

（1）线性表：线性表的特点；顺序表和链表的数据类型描述和基本操作的实现以及时间复杂度；特别是带头结点的单向链表和有序链表，单向循环链表和双向循环链表。

（2）限定线性表：栈和队列的特点；顺序栈、链栈、循环队列和链队列的数据类型描述和基本操作的实现以及时间复杂度。

（3）二叉树与树：基本术语；二叉树和树的特点；二叉树与树、森林的转换；二叉链表、孩子兄弟链表和双亲孩子链表的数据类型描述和基本操作的实现以及时间复杂度。

（4）图：基本术语；图的特点；邻接矩阵和邻接表的数据类型描述和基本操作的实现以及时间复杂度。

3．数据处理技术：

（1）查找：静态查找（顺序查找（带岗哨）、折半查找）；动态查找（二叉排序树、二叉平衡树和B-树的查找、插入和删除）；查找算法的性能分析（ASL）

（2）内排序：插入类排序（直接插入排序、折半插入排序、希尔排序）、交换类排序（冒泡排序、快速排序）、选择类排序（简单选择排序、堆排序）、归并类排序（二路归并排序）的算法思想和一趟排序的过程。

4. 基本应用：

（1）线性表的应用：一元多项式的计算

（2）栈的应用：栈与递归、表达式的计算

（3）队列的应用：二叉树的层次遍历和图的广度遍历

（4）二叉树和树的应用：哈夫曼树及其编码/解码，用遍历算法的框架求解其他问题

（5）图的应用：最小生成树、最短路径、拓扑排序、关键路径

三、 考试的题型

概念解释、问题简答、算法与程序设计、综合应用