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