中国地质大学研究生院
硕士研究生入学考试《数据结构》考试大纲
Ⅰ. 考试内容及考试要求
一、数据结构的基本概念、算法及算法分析方法
【考试内容】
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）针对线性表上所需要执行的主要操作，知道选择顺序表还是链表作为其存储结构才能取得较优的时空性能。
