中国地质大学研究生院硕士研究生入学考试数据结构考试大纲. 考试内容及考试要求一、数据结构的基本概念、算法及算法分析方法【考试内容】1、 合适的数据结构在解决实际应用问题中的关键性；学习数据结构的意义。2、 数据、数据元素、数据项、数据结构等基本概念。3、 数据结构的四种逻辑结构和两种存储结构表示方法。4、 抽象数据类型的表示和实现。5、 算法的五个特点。6、 算法、算法的时间复杂度和空间复杂度、最坏的和平均的时间复杂度等概念。7、 算法描述和算法分析的方法，对于一般算法能分析出时间复杂度。【考试要求】1、数据结构的基本概念和术语（识记）（1）数据、数据元素、数据项、数据结构等基本概念。（2）数据结构的逻辑结构、存储结构及数据操作的含义及其相互关系。（3）数据结构的四种逻辑结构和两种常用的存储表示方法。2、数据结构在软件系统中的作用（识记） 。（1）数据结构在各种软件系统中所起的作用。（2）选择合适的数据结构是解决应用问题的关键步骤。3、算法的描述和分析（领会）（1）算法、算法的时间复杂度和空间复杂度、最坏的和平均的时间复杂度等概念。（2）算法的时间复杂度不仅仅依赖于问题的规模，也取决于输入实例的初始状态。（3）算法描述和算法分析的方法，对于一般算法能分析出时间复杂度。（4）O 符号的含义及求解渐进时间复杂度的方法。二、线性表【考试内容】1、线性表的类型定义。2、顺序表的含义及特点，顺序表上的插入、删除操作及其平均时间性能分析。3、链式表示和实现，单链表、双链表、循环链表链接方式上的区别。4、单链表上实现的建表、查找、插入和删除等基本算法及其时间复杂度。5、循环链表及双向链表的定义和相关算法。6、顺序表和链表的比较，以及如何选择其一作为其存储结构才能取得较优的时空性能。【考试要求】1、线性表的逻辑结构（识记）（1）线性表的逻辑结构特征。（2）线性表上定义的基本操作，并能利用基本操作构造出较复杂的操作。12线性表的顺序存储结构顺序表（综合应用）（1） 顺序表的含义及特点，即顺序表如何反映线性表中元素之间的逻辑关系。（2）顺序表上的插入、删除操作及其平均时间性能分析。（3）利用顺序表设计算法解决简单的应用问题。3线性表的链式存储结构链表（综合应用）（1）链表如何表示线性表中元素之间的逻辑关系。（2）链表中头指针和头结点的使用。（3）单链表、双链表、循环链表链接方式上的区别。（4）单链表上实现的建表、查找、插入和删除等基本算法，并分析其时间复杂度。（5）单循环链表以及单循环链表上的算法与单链表上相应算法的异同点。（6）双链表的定义及其相关的算法。（7）利用链表设计算法解决简单的应用问题。4、顺序表和链表的比较（领会）（1）顺序表和链表的主要优缺点。（2）针对线性表上所需要执行的主要操作，知道选择顺序表还是链表作为其存储结构才能取得较优的时空性能。三、栈和队列【考试内容】1、栈的抽象数据类型的定义。2、栈的表示和实现。3、栈的简单应用。4、抽象数据类型队列的定义。5、队列的链式表示和实现。6、队列的顺序表示和实现。【考试要求】1、栈的逻辑结构、存储结构及其相关算法（综合应用）（1）栈的逻辑结构特点，栈与线性表的异同。（2）顺序栈和链栈上实现的进栈、退栈等基本算法。（3）栈的“上溢” 和“ 下溢”的概念及其判别条件。（4）利用栈设计算法解决简单的应用问题。2、队列的逻辑结构、存储结构及其相关算法（综合应用）（1）队列的逻辑结构特点，队列与线性表的异同。（2）顺序队列（主要是循环队列）和链队列上实现的入队、出队等基本算法。（3）队列的“上溢” 和“ 下溢”的概念及其判别条件。（4）使用数组实现的循环队列取代普通的顺序队列的原因。（5）循环队列中对边界条件的处理方法。（6）利用队列设计算法解决简单的应用问题。3、栈和队列的应用（领会）栈和队列的特点，什么样的情况下能够使用栈或队列。四、串【考试内容】21、串的定义、空串、空格串、子串、主串、串相等。2、串的基本操作。3、串的顺序存储结构及在顺序存储结构下基本操作的实现。4、串的堆分配存储表示及其在堆分配存储结构下基本操作的实现。5、串的链式存储表示。【考试要求】1、串的有关概念及其基本运算（领会） 。2、串的简单应用：使用串解决与串相关的简单的应用问题。五、数组和广义表【考试内容】1、数组的顺序存储结构。2、二维数组的按行存储及按列存储和计算数组元素的地址计算公式。3、矩阵的压缩存储、特殊矩阵的表示。4、广义表的定义和操作（HEAD 和 TAIL） 。5、广义表的 2 种存储结构。【考试要求】1、多维数组（领会）（1）多维数组的逻辑结构特征。（2）多维数组的顺序存储结构及地址计算方式。（3）数组是一种随机存取结构的原因。2、矩阵的压缩存储（领会）（1）特殊矩阵和疏稀矩阵的概念。（2）特殊矩阵和压缩存储时的下标变换方法。（3）稀疏矩阵的三元组表表示方法及有关算法。3、广义表（领会）（1）广义表的概念、广义表和线性表的联系。（2）广义表表头和表尾的概念及广义表两个特殊的基本运算，取表头和取表尾。（3）广义表的两种存储结构。六、树和二叉树【考试内容】1、树的定义和术语。2、二叉树（完全二叉树、满二叉树）的定义和性质（结论） 、二叉树的存储结构顺序表示法和链表表示法。3、二叉树的三种遍历方法及相应的递归算法。4、树的存储表示法孩子表示法、双亲表示法、孩子兄弟表示法。5、树和森林及二叉树的转换方法。6、树和森林的遍历。7、树的路径长度、树的带权路径长度、Huffman 树（最优二叉树）的构造方法。8、Huffman 编码方法。【考试要求】1、领会3（1）树的逻辑结构特征。（2）树的不同表示方法。（3）树的常用术语及含义。（4）树和森林与二叉树之间的转换方法。（5）树的各种存储结构及其特点。（6）树的遍历方法。2、简单应用（1）二叉树的定义及树与二叉树的差别。（2）二叉树的性质，了解相应的证明方法。（3）二叉树的两种存储结构、特点及适用范围。（4）最优二叉树和前缀编码的概念及特点。（5）Huffman 算法的思想。（6）根据给定的叶结点及其权值构造出相应的最优二叉树。（7）根据最优二叉树构造对应的 Huffman 编码。3、综合应用（1）二叉树的三种遍历算法，理解其执行过程。（2）根据不同的遍历方法，应能得出其相应的结点访问次序。（3）以遍历算法为基础，设计有关算法解决简单的应用问题。七、图【考试内容】1、 图的定义及术语。2、 图的存储结构（邻接矩阵、邻接表） 。3、 图的遍历（深度优先、广度优先） 。4、 图的最小生成树算法。5、 单源点最短路径算法Dijkstar 算法。6、 拓扑排序、关键路径。【考试要求】1、领会（1）图的逻辑结构特征。（2）图的常用术语及含义。（3）图的存储结构及其特点。（4）图的遍历方法。（5）拓扑排序、关键路径的相关概念及算法思想。2、简单应用（1）图的两种存储结构、特点及适用范围。（4）无向连通网求解最小生成树的算法（Prime 算法和 Krurskal 算法）思想。3、综合应用（1）图的两种遍历算法，理解其执行过程。（2）根据不同的遍历方法，应能得出其相应的结点访问次序。（3）根据 Dijkstar 算法求解图的最短路径。4八、排序【考试内容】1、排序的基本概念2、插入排序（直接插入排序、折半插入排序）3、起泡排序4、简单选择排序5、希尔排序6、快速排序7、堆排序8、二路归并排序9、基数排序10、各种内部排序算法的比较11、内部排序算法的应用【考试要求】1、领会（1）排序、关键码、稳定排序等术语的含义。2、简单应用（1）各种内部排序算法的算法思想。3、综合应用（1）各种内部排序算法的特点、应用范围、时空复杂度分析、比较应用等。九、查找【考试内容】1、查找的基本概念2、顺序查找法3、折半查找法4、二叉搜索树、AVL 树5、散列（Hash）表及其查找6、查找算法的分析及应用【考试要求】1、 领会（1）查找、平均查找长度等基本概念的含义。（2）二叉搜索树、AVL 树的概念；（3）散列的含义。2、 简单应用（1）顺序查找、折半查找的算法思想、应用特点。（2）二叉搜索树、AVL 树的特点以及平均搜索长度的分析。（3）常用的散列表的构造方法、冲突处理的方法。3、 综合应用（1）二叉搜索树的创建、插入、删除算法。（2）AVL 平衡化旋转的方法。5. 相关说明本大纲在【考试要求】中，按照识记、领会、简单运用和综合运用等四个层次规定学生通过学习应该达到的能力层次要求。四个能力层次是递进等级关系，各能力层次的含义是：1、 【识记】能够了解有关的名词、概念、知识的含义，并能正确认识和表述、选择和判断。2、 【领会】在识记的基础上，能够比较全面地把握基本概念、基本事实、基本理论模型、基本方法，能把握有关概念、事实、理论模型、分析方法之间的区别和联系。并能根据考核的不同要求，做出正确的解释、说明和论述。3、 【简单运用】在领会的基础上，能够运用本课程中规定的少量的知识点，分析和解释有关的一般的应用问题。例如，简单的算法设计和时间性能分析。4、 【综合运用】指在简单运用的基础上，能够综合运用所学习过的多个知识点，分析和解决较复杂的应用问题，例如，设计较复杂的算法。. 参考书1、 数据结构 （C 语言版） ，严蔚敏 吴伟民 编著，清华大学出版社，2007 年版。2、 数据结构题集 ，严蔚敏 吴伟民 著，清华大学出版社，2007 年版。3、 数据结构（用面向对象方法与 C+语言描述） （第二版） ，殷人昆 主编，清华大学出版社，2007 年版。. 试卷结构1、考试题型及比例分布（1）单项选择题（约 30%）（3）简答及应用（约 40%）（4）算法设计（约 30%）其他可能出现的题型：填空题（约 15%） ，判断题（约 10%） 。2、考试内容及比例分布（1）数据结构基本概念、算法及算法分析方法（约 5%）（2）线性表（约 15%）（3）栈和队列（约 10%）（4）串（约 5%）（5）数组与广义表（约 5%）（6）树和二叉树（约 20%）（7）图（约 10%）（8）排序（约 15%）（9）查找（约 15%）