武汉工程大学数据结构研究生入学考试大纲一、 “数据结构”课程的目的和要求数据结构在计算机科学中是一门综合性的核心专业基础课，而且正逐渐发展成为众多理工专业的热门选修课。数据结构课程在整个课程体系中处于承上启下的核心地位，它一方面扩展和深化在离散数学、程序设计语言等课程学到的基本技术和方法，一方面为进一步学习其它专业课奠定坚实的理论与实践基础。课程的主要任务是学习数据的逻辑结构，存储结构以及相关的算法设计。本课程的目的是使学生学会分析待加工处理数据的特性，以便选择适当的逻辑结构、存储结构以及进行相应的算法设计。在教给学生数据结构选择和算法设计的同时，培养学生的抽象思维能力、逻辑推理能力和形式化思维方法，增强分析问题和解决问题的能力，更重要的是培养专业兴趣、树立创新意识。二、基本内容第一章 数据结构基础知识（一）基本内容：1.1 数据结构的兴起和发展。1.2 数据结构的研究对象。1.3 数据结构的基本概念。1.4 算法以及算法分析。（二）基本要求：（1）了解数据结构的兴起和发展。（2）掌握数据结构的基本概念。（3）掌握数据的逻辑结构，存储结构和算法的相互联系和实质。（4）掌握算法以及算法分析。（5）了解数据结构的主要应用领域及发展方向。（三）重点及难点：重点：数据结构的定义，数据的逻辑结构、存储结构的类型，算法的分析方法。难点：算法的概念、特性和算法的分析。第二章 线性表（一）基本内容：2.1 线性表的逻辑结构。2.2 线性表的顺序存储结构及实现。2.3 线性表的链接存储结构及实现。2.4 线性表的其他存储方法。2.4.1 循环链表。2.4.2 双链表。2.4.3 静态链表。2.5 线性表的应用举例。（二）基本要求：（1）理解线性表的逻辑结构。（2）掌握线性表的顺序和链接存储结构及各自的特征。（3）熟练掌握在顺序和链接存储结构上的典型算法实现，并能够尽量提高算法性能。（4）合理运用线性表来解决实际问题。（三）重点及难点：重点：数据结构的定义，数据的逻辑结构、存储结构的类型，算法的分析方法。难点：算法的概念、特性和算法的分析。第三章 栈和队列（一）基本内容：3.1 栈的特征、顺序栈和链栈的实现。3.2 栈的基本应用。3.3 队列的特征、顺序队和链队列的实现。3.4 队列的基本应用。3.5 递归算法的运行过程，递归算法的特征与设计。（二）基本要求：（1）掌握栈和队列与线性表的关系。（2）深入理解栈和队列的结构特性和典型操作。（3）掌握栈和队列在编程中的应用。（4）掌握递归算法的特征与设计方法。（三）重点及难点：重点：栈和队列的结构特性和典型操作。难点：循环队列的设置和操作的实现，栈与队列的编程应用。第四章 字符串（一）基本内容：4.1 字符串的概念与特征；与线性表的区别和联系；字符串的基本操作。4.2 字符串的存储结构以及基本操作的实现。4.3 模式匹配算法及改进。（二）基本要求：（1）了解字符串的概念与特征；与线性表的区别和联系；字符串的基本操作。（2）掌握字符串的存储结构以及基本操作的实现。（3）掌握模式匹配算法及改进。（三）重点及难点：重点：字符串的基本操作在存储结构上的实现。难点：模式匹配的 KMP 算法。第五章 数组和广义表（一）基本内容：5.1 多维数组的逻辑结构和存储方法。5.2 特殊矩阵的逻辑结构，特殊矩阵的逻辑结构到存储结构的映射函数。5.3 稀疏矩阵的特点，利用三元组对及特殊矩阵的压缩及典型操作算法设计。5.4 广义表的基本操作、广义表的存储结构。（二）基本要求：（1）掌握多维数组的行序优先与列序优先存储方法。（2）掌握特殊矩阵的特点和压缩存储。（3）掌握稀疏矩阵的特点和压缩存储。（4）掌握广义表的基本操作、广义表的存储结构。（5）了解广义表的基本操作实现。（三）重点及难点：重点：多维数组的逻辑结构和存储结构，特殊矩阵的结构特性和压缩存储方法，稀疏矩阵的压缩存储，广义表的概念与存储。难点：矩阵的压缩存储以及地址变换，广义表的基本操作实现。第六章 树和二叉树（一）基本内容：6.1 树的基本概念和特征。6.2 二叉树的概念和性质、二叉树的顺序存储结构和链式存储结构、二叉树的遍历及应用、线索二叉树基本概念和构造。6.3 树的存储结构、森林与二叉树的相互转换、树和森林的遍历。6.4 Huffman 树和 Huffman 编码。（二）基本要求：（1）掌握树的逻辑结构与存储结构。（2）熟练掌握二叉树的基本性质、特征和存储结构、二叉树的遍历及应用。（3）掌握线索二叉树的基本概念和构造。（4）掌握树的存储结构、森林与二叉树的相互转换、树和森林的遍历。（5）掌握 Huffman 树和 Huffman 编码。（三）重点及难点：重点：二叉树的概念和性质、二叉树存储结构、二叉树的遍历及应用、线索二叉树及应用、树、森林和二叉树的关系以及相互转换。难点：树和二叉树的相关算法实现。第七章 图（一）基本内容：7.1 图的概念与特征、图的邻接矩阵、邻接表、邻接多重表、十字链表的存储。7.2 图的深度优先和广度优先遍历。7.3 最小生成树的算法与实现。7.4 最短路径的算法与实现。7.5 拓扑排序的算法与实现。7.6 关键路径的算法与实现。（二）基本要求：（1）理解图的逻辑结构与其特征。（2）掌握图的基本存储结构。（3）掌握图的两种遍历方法及其应用。（4）掌握图的多种经典算法及其编码实现。（三）重点及难点：重点：图的基本存储结构；深度优先遍历和广度优先遍历；图的基本应用：最小生成树、最短路径、拓扑排序与关键路径。难点：图的多种经典算法及其编码实现。第八章 查找技术（一）基本内容：8.1 查找的概念，查找算法的性能标准。8.2 顺序查找、折半查找和分块查找。8.3 二叉排序树的概念和查找与操作、平衡二叉树的概念与操作。8.4 B 树及其基本操作、B+树的基本概念。8.5 散列表的概念与构造方法，查找性能。8.6 查找算法的分析及应用（二）基本要求：（1）了解查找的概念，查找算法的性能标准。（2）掌握顺序查找、折半查找和索引顺序表的查找。（3）掌握二叉排序树的概念与操作；平衡二叉树的概念与操作。（4）掌握 B 树及其基本操作；B+树的基本概念。（5）掌握散列表的概念与构造方法，查找性能。（三）重点及难点：重点：各种查找算法及其性能分析。难点：查找算法的时间性能；折半查找的判定树；平衡二叉树的操作；B-树的操作；散列表的构造与性能计算。第九章 排序（一）基本内容：9.1 排序算法的概念与性能评估标准。9.2 插入排序及经典算法。9.3 交换排序及经典算法。9.4 选择排序及经典算法。9.5 归并排序及算法。9.6 基数排序及算法。9.7 外部排序。9.8 各种内部排序算法的比较。9.9 排序算法的应用。（二）基本要求：（1）了解排序算法的概念与性能评估标准。（2）掌握插入排序及经典算法；交换排序及经典算法。（3）掌握选择排序及经典算法；归并排序及算法。（4）掌握基数排序及算法。（5）理解外部排序的基本方法。（三）重点及难点：重点：五大类内排序算法的思路，并对其各自的经典算法的算法步骤和算法性能进行较为详尽的分析。难点：Shell 排序；快速排序；堆排序；排序算法的适用场合和选择。第十章 文件（一）基本内容：10.1 文件的有关概念。文件的逻辑结构及其操作。文件的存储结构（组织方式）分类。评价文件组织效率的标准。10.2 顺序文件的特点及外存种类的适应性。顺序文件上各种查找方法的基本思想及对外存种类的要求。10.3 索引文件的组织方式和特点。索引文件的查询和更新操作的基本思想。10.4 索引顺序文件是最常用的一种文件组织方式的原因。两种最常用的索引顺序文件（ISAM 文件和 VSAM 文件）的组织方式和特点。在 ISAM 文件和 VSAM 文件上查询和更新操作的基本思想。10.5 散列文件的组织方式和特点。散列文件的查询和更新操作的基本思想。10.6 多关键字文件与其它文件的区别。多重表文件和倒排文件的组织方式和特点。多重表文件和倒排文件上查询及更新操作的基本思想。（二）基本要求：（1）了解文件的基本概念。（2）了解顺序文件、索引文件和散列文件的组织方式和特点。（三）重点及难点：重点：顺序文件、索引文件和散列文件的组织方式和特点。难点：ISAM 文件和 VSAM 文件。三、关于考试命题的若干规定1、考试方式为笔试闭卷，考试时间为 180 分钟，满分为 150 分。2、对不同能力层次要求在试卷中所占比例大致如下： “识记”占 20， “领会”占30， “简单应用”占 30， “综合应用”占 20。3、试卷中难易程度比例大约为：易:较易:较难:难=2:3:3:2。4、题型有：判断题、单项选择题、问答题、应用题、算法设计题。四、主要参考书1、李春葆数据结构教程（第 4 版） 北京：清华大学出版社，20132、严蔚敏，吴伟民数据结构（C 语言版） 北京：清华大学出版社，20113、齐德昱数据结构与算法北京：清华大学出版社，20104、王红梅、胡明等数据结构（C+版） 北京：清华大学出版社，20055、Donald KnuthThe Art of Computer ProgrammingVol.1: Fundamental Algorithms, Vol.3: Sorting and SearchingAddison-westey Publishing Company,Inc. ,19736、William Ford, William ToppData Structure with C+Prentice Hall,Inc. ,1996