武汉工程大学考研《数据结构》考试大纲

凯程考研集训营，为学生引路，为学员服务！武汉工程大学考研《数据结构》考试大纲一、“数据结构”课程的目的和要求《数据结构》在计算机科学中是一门综合性的核心专业基础课，而且正逐渐发展成为众多理工专业的热门选修课。数据结构课程在整个课程体系中处于承上启下的核心地位，它一方面扩展和深化在离散数学、程序设计语言等课程学到的基本技术和方法，一方面为进一步学习其它专业课奠定坚实的理论与实践基础。课程的主要任务是学习数据的逻辑结构，存储结构以及相关的算法设计。本课程的目的是使学生学会分析待加工处理数据的特性，以便选择适当的逻辑结构、存储结构以及进行相应的算法设计。在教给学生数据结构选择和算法设计的同时，培养学生的抽象思维能力、逻辑推理能力和形式化思维方法，增强分析问题和解决问题的能力，更重要的是培养专业兴趣、树立创新意识。二、基本内容第一章数据结构基础知识(一)基本内容：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.4Huffman树和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.4B树及其基本操作、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排序;快速排序;堆排序;排序算法的适用场合和选择。三、关于考试命题的若干规定1、考试方式为笔试闭卷，考试时间为180分钟，满分为150分。凯程考研集训营，为学生引路，为学员服务！2、对不同能力层次要求在试卷中所占比例大致如下：“识记”占20﹪，“领会”占30﹪，“简单应用”占30﹪，“综合应用”占20﹪。3、试卷中难易程度比例大约为：易:较易:较难:难=2:3:3:2。4、题型有：判断题、单项选择题、问答题、应用题、算法设计题。四、主要参考书1、李春葆.数据结构教程(第4版).北京：清华大学出版社，20132、严蔚敏，吴伟民.数据结构(C语言版).北京：清华大学出版社，20113、齐德昱.数据结构与算法.北京：清华大学出版社，20104、王红梅、胡明等.数据结构(C++版).北京：清华大学出版社，20055、DonaldKnuth.TheArtofComputerProgramming.Vol.1:FundamentalAlgorithms,Vol.3:SortingandSearching.Addison-westeyPublishingCompany,Inc.,19736、WilliamFord,WilliamTopp.DataStructurewithC++.PrenticeHall,Inc.,1996。小提示：目前本科生就业市场竞争激烈，就业主体是研究生，在如今考研竞争日渐激烈的情况下，我们想要不在考研大军中变成分母，我们需要：早开始+好计划+正确的复习思路+好的辅导班（如果经济条件允许的情况下）。2017考研开始准备复习啦，早起的鸟儿有虫吃，一分耕耘一分收获。加油！