资源描述
中国 地质大学研究生 院 硕士研究生入学考试数据结构考 试 大纲 . 考试内容及考 试 要求 一、数据结构的基本概念、算法及算法分析方法 【考试内容】 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 ）线性表上定义的基本操作，并能利用基本操作构造出较复杂的操作。1 2 线性表的顺序存储结构顺序表（综合应用） （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 、栈和队列的应用（领会） 栈和队列的特点，什么样的情况下能够使用栈或队列。 四、串 【考试内容】2 1 、串的定义、空串、空格串、子串、主串、串相等。 2 、串的基本操作。 3 、串的顺序存储结构及在顺序存储结构下基本操作的实现。 4 、串的堆分配存储表示及其在堆分配存储结构下基本操作的实现。 5 、串的链式存储表示。 【考试要求】 1 、串的有关概念及其基本运算（领会） 。 2 、串的简单应用：使用串解决与串相关的简单的应用问题。 五、数组和广义表 【考试内容】 1 、数组的顺序存储结构。 2 、二维数组的按行存储及按列存储和计算数组元素的地址计算公式。 3 、矩阵的压缩存储、特殊矩阵的表示。 4 、广义表的定义和操作（HEAD 和 TA I L ） 。 5 、广义表的 2 种存储结构。 【考试要求】 1 、多维数组（领会） （1 ）多维数组的逻辑结构特征。 （2 ）多维数组的顺序存储结构及地址计算方式。 （3 ）数组是一种随机存取结构的原因。 2 、矩阵的压缩存储（领会） （1 ）特殊矩阵和疏稀矩阵的概念。 （2 ）特殊矩阵和压缩存储时的下标变换方法。 （3 ）稀疏矩阵的三元组表表示方法及有关算法。 3 、广义表（领会） （1 ）广义表的概念、广义表和线性表的联系。 （2 ）广义表表头和表尾的概念及广义表两个特殊的基本运算，取表头和取表尾。 （3 ）广义表的两种存储结构。 六、树和二叉树 【考试内容】 1 、树的定义和术语。 2 、 二叉树 （完全二叉树、 满二叉树） 的定义和性质 （结论） 、 二叉树的存储结构顺序表 示法和链表表示法。 3 、二叉树的三种遍历方法及相应的递归算法。 4 、树的存储表示法孩子表示法、双亲表示法、孩子兄弟表示法。 5 、树和森林及二叉树的转换方法。 6 、树和森林的遍历。 7 、树的路径长度、树的带权路径长度、H u ffm a n 树（最优二叉树）的构造方法。 8 、H u ffm a n 编码方法。 【考试要求】 1 、领会3 （1 ）树的逻辑结构特征。 （2 ）树的不同表示方法。 （3 ）树的常用术语及含义。 （4 ）树和森林与二叉树之间的转换方法。 （5 ）树的各种存储结构及其特点。 （6 ）树的遍历方法。 2 、简单应用 （1 ）二叉树的定义及树与二叉树的差别。 （2 ）二叉树的性质，了解相应的证明方法。 （3 ）二叉树的两种存储结构、特点及适用范围。 （4 ）最优二叉树和前缀编码的概念及特点。 （5 ）H u ffm a n 算法的思想。 （6 ）根据给定的叶结点及其权值构造出相应的最优二叉树。 （7 ）根据最优二叉树构造对应的 Hu f f ma n 编码。 3 、综合应用 （1 ）二叉树的三种遍历算法，理解其执行过程。 （2 ）根据不同的遍历方法，应能得出其相应的结点访问次序。 （3 ）以遍历算法为基础，设计有关算法解决简单的应用问题。 七、图 【考试内容】 1 、 图的定义及术语。 2 、 图的存储结构（邻接矩阵、邻接表） 。 3 、 图的遍历（深度优先、广度优先） 。 4 、 图的最小生成树算法。 5 、 单源点最短路径算法 Dijk sta r 算法。 6 、 拓扑排序、关键路径。 【考试要求】 1 、领会 （1 ）图的逻辑结构特征。 （2 ）图的常用术语及含义。 （3 ）图的存储结构及其特点。 （4 ）图的遍历方法。 （5 ）拓扑排序、关键路径的相关概念及算法思想。 2 、简单应用 （1 ）图的两种存储结构、特点及适用范围。 （4 ）无向连通网求解最小生成树的算法（Pr i me 算法和 Kru r sk a l 算法）思想。 3 、综合应用 （1 ）图的两种遍历算法，理解其执行过程。 （2 ）根据不同的遍历方法，应能得出其相应的结点访问次序。 （3 ）根据 Dijkst ar 算法求解图的最短路径。4 八、排序 【考试内容】 1 、排序的基本概念 2 、插入排序（直接插入排序、折半插入排序） 3 、起泡排序 4 、简单选择排序 5 、希尔排序 6 、快速排序 7 、堆排序 8 、二路归并排序 9 、基数排序 10 、各种内部排序算法的比较 11 、内部排序算法的应用 【考试要求】 1 、领会 （1 ）排序、关键码、稳定排序等术语的含义。 2 、简单应用 （1 ）各种内部排序算法的算法思想。 3 、综合应用 （1 ）各种内部排序算法的特点、应用范围、时空复杂度分析、比较应用等。 九、查找 【考试内容】 1 、查找的基本概念 2 、顺序查找法 3 、折半查找法 4 、二叉搜索树、AV L 树 5 、散列（Hash ）表及其查找 6 、查找算法的分析及应用 【考试要求】 1、领 会 （1 ）查找、平均查找长度等基本概念的含义。 （2 ）二叉搜索树、AV L 树的概念； （3 ）散列的含义。 2 、 简单应用 （1 ）顺序查找、折半查找的算法思想、应用特点。 （2 ）二叉搜索树、AV L 树的特点以及平均搜索长度的分析。 （3 ）常用的散列表的构造方法、冲突处理的方法。 3 、 综合应用 （1 ）二叉搜索树的创建、插入、删除算法。 （2 ）AV L 平衡化旋转的方法。5 . 相关说明 本大纲在 【考试要求】 中， 按照识记、 领会、 简单运用和综合运用等四个层次规定学生通过 学习应该达到的能力层次要求。四个能力层次是递进等级关系，各能力层次的含义是： 1 、 【识记】能够了解有关的名词、概念、知识的含义，并能正确认识和表述、选择和判断。 2 、 【领会】 在识记的基础上， 能够比较全面地把握基本概念、 基本事实、 基本理论模型、 基 本方法， 能把握有关概念、 事实、 理论模型、 分析方法之间的区别和联系。 并能根据考核的不同 要求，做出正确的解释、说明和论述。 3 、 【 简单运用】 在领会的基础上， 能够运用本课程中规定的少量 的知识点， 分析和解释有关 的一般的应用问题。例如，简单的算法设计和时间性能分析。 4 、 【 综合运用】 指在简单运用的基础上， 能够综合运用所学习过的多个 知识点， 分析和解决 较复杂的应用问题，例如，设计较复杂的算法。 . 参考书 1 、 数据结构 （C 语言版） ，严蔚敏 吴伟民 编著，清华大学出版社，20 07 年版。 2 、 数据结构题集 ，严蔚敏 吴伟民 著，清华大学出版社，20 07 年版。 3 、 数据结构（用面向对象方法与 C+ 语言描述） （第二版） ，殷人昆 主编 ，清华大学出版社， 20 07 年版。 . 试卷结构 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 % ）
展开阅读全文