同等学历加试 081603 地图制图学与地理信息工程《数据结构》考试大纲.doc

中国地质大学研究生院 硕士研究生入学考试《数据结构》考试大纲 Ⅰ. 考试内容及考试要求 一、数据结构的基本概念、算法及算法分析方法 【考试内容】 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）线性表上定义的基本操作，并能利用基本操作构造出较复杂的操作。 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、栈和队列的应用（领会） 栈和队列的特点，什么样的情况下能够使用栈或队列。 四、串 【考试内容】 1、串的定义、空串、空格串、子串、主串、串相等。 2、串的基本操作。 3、串的顺序存储结构及在顺序存储结构下基本操作的实现。 4、串的堆分配存储表示及其在堆分配存储结构下基本操作的实现。 5、串的链式存储表示。 【考试要求】 1、串的有关概念及其基本运算（领会）。 2、串的简单应用：使用串解决与串相关的简单的应用问题。 五、数组和广义表 【考试内容】 1、数组的顺序存储结构。 2、二维数组的按行存储及按列存储和计算数组元素的地址计算公式。 3、矩阵的压缩存储、特殊矩阵的表示。 4、广义表的定义和操作（HEAD和TAIL）。 5、广义表的2种存储结构。 【考试要求】 1、多维数组（领会