《数据结构》考试大纲
一、考试大纲的性质
数据结构是报考我校软件工程、计算机技术专业学位硕士的考试科目。为帮助考生明确考试复习范围和有关要求，特制定本考试大纲。
二、考试范围和内容
1.数据结构基本概念
(1)数据结构的基本概念：数据、数据元素、数据结构、数据的逻辑结构、物理结构、算法等。
(2)算法时间复杂度和空间复杂度的分析方法。
2.线性表
(1)线性表的定义。
(2)线性表的顺序存储结构和主要算法实现，如查找、插入和删除算法。
(3)线性表的链式存储结构和主要算法实现，如查找、插入和删除算法。
(4)循环链表、双向链表的特点。
(5)从时间和空间复杂度的角度比较两种存储结构的不同特点及其适用场合。
(6)线性表的应用，如线性表的合并算法。
3.栈和队列
(1)栈的定义及特点，栈的顺序存储和链接存储结构，进栈出栈算法，顺序栈栈满和栈空的条件。
(2)栈的应用，如表达式求值算法，借助栈深入理解递归算法。
(3)队列的定义及特点，队列的顺序存储(循环队)和链接存储结构，进队出队算法，循环队列中队满及队空的条件。
4.串和数组
(1)串的定义。
(2)串的古典模式匹配算法。
(3)数组地址的计算方法。
(4)特殊矩阵的压缩存储方法。
5.树和二叉树
(1)二叉树的定义和性质。
(2)二叉树的两种存储结构：顺序存储和链式存储。
(3)二叉树的创建和三种不同遍历算法，利用遍历算法实现二叉树的其他操作，如计算二叉树结点个数、叶子结点个数、二叉树的高度等算法。
(4)线索二叉树的特性及构造方法。
(5)树和森林的定义、存储结构与二叉树的转换方法。
(6)树的应用，哈夫曼树及哈夫曼编码的构造算法、带权路径长度的计算。
6.图
(1)图的定义和性质。
(2)图的两种存储结构：邻接矩阵和邻接表。
(3)图的两种遍历策略：深度优先搜索算法和广度优先搜索算法。
(4)图的基本应用，包括拓扑排序算法、求解最短路径的迪杰斯特拉算法、构造最小生成树的两种算法（普里姆算法和克鲁斯卡尔算法）。
7.查找
(1)线性表的查找：顺序查找和折半查找算法。
(2)树表的查找：二叉排序树的定义，二叉排序树的创建、插入、删除和查找算法。
(3)散列表的查找：两种处理冲突的方法包括开放地址法（线性探测法、二次探测法）和链地址法。
(4)上述三种不同查找算法的分析，平均查找长度ASL的计算方法及时间复杂度分析，不同查找算法的适用场合。
8.排序
(1)排序的基本概念。
(2)插入排序：直接插入排序、折半插入排序和希尔排序。
(3)交换排序：冒泡排序和快速排序。
(4)选择排序：简单选择排序和堆排序。
(5)归并排序：2-路归并排序。
(6)上述各种排序方法的特点和排序过程，时间和空间复杂度的分析，排序方法“稳定”或“不稳定”的含义。排序算法的实现及适用场合。
三、考试方式和时间
考试方式：闭卷笔试。
考试时间：180分钟。
试卷满分：150分。
考试主要题型：选择题、判断题、填空题、应用题、算法设计题（算法实现用C/C++语言）。
四、主要参考书
严蔚敏，李冬梅，吴伟民.数据结构（C语言版）.北京：人民邮电出版社.
