安徽农业大学
研究生入学考试复习大纲
| 科目名称 | 数据结构 | 科目代码 | 829 | ||||
| 参考书目名称 | 编者 | 出版单位 | 版次 | 年份 | |||
| 《数据结构》（c语言版） | 严蔚敏等 | 清华大学出版社 |
|
| |||
| 考试范围及要点 | |||||||
| 一、数据结构基本概念及简单的算法分析 考试内容 (1)数据结构的基本概念，数据的逻辑结构、存储结构。 (2)算法的定义、算法的基本特性以及算法分析的基本概念、算法的性能标准；算法的后期测试；算法的事前估计；空间复杂度度量；时间复杂度度量；时间复杂度的渐进表示法；渐进的空间复杂。 考试要求 建立有关数据结构最基本的概念，包括数据的逻辑结构、存储结构和算法，算法分析的基本概念与基本方法。
二、线性表 考试内容 (1)线性关系、线性表的定义，线性表的基本操作。 (2)线性表的顺序存储结构与链式存储结构(包括单链表、循环链表和双向链表)的构造原理。在以上两种存储结构上对线性表实施的最主要的操作(包括三种链表的建立、插入和删除、检索等)的算法设计。 考试要求 掌握线性表的基本概念以及两种存储结构的构造原理，掌握在各种存储结构下对线性表进行的基本操作的算法设计。
三、栈和队列 考试内容 (1)堆栈与队列的基本概念、基本操作。 (2)堆栈与队列的顺序存储结构与链式存储结构的构造原理。 (3)在不同存储结构的基础上对堆栈与队列实施插入与删除等基本操作对应的算法设计。 考试要求 掌握堆栈和队列的基本概念与特征，掌握在两种存储结构下如何对堆栈和队列进行插入和删除等操作，以及利用堆栈与队列解决实际问题的基本方法。
四、串 考试内容 (1)串的基本概念、串的基本操作和存储结构。 (2)串的模式匹配算法和改进的KMP算法。 考试要求 充分了解串的基本概念、掌握串的存储结构和相关的操作算法。
五、数组和广义表 考试内容 (1)数组的概念、多维数组的实现。 (2)对称矩阵和稀疏矩阵的压缩存储。 (3)广义表的基本概念。 考试要求 掌握数组、广义表和稀疏矩阵的基本概念，物理结构和基本操作的实现。
六、树和二叉树 考试内容 (1)树的基本概念和基本操作,树的抽象数据类型。 (2)二叉树的概念和性质,特殊二叉树；二叉树的存储结构。 (3)二叉树的生成与建立。 (4)遍历二叉树：前序遍历,中序遍历,后序遍历,层次遍历。 (5)二叉树其它操作实现举例。 (6)线索二叉树的概念和存储结构,二叉树的线索化,线索二叉树的遍历。 (7)树的存储结构,树与二叉树之间的转换,森林与二叉树之间的转换,树和森林的遍历。 (8)树的路径长度和带权路径长度,哈夫曼树(Huffman)的概念,哈夫曼算法, 哈夫曼编码树。 (9)二叉排序树的的概念和基本操作,二叉排序树的建立,二叉排序树其它操作实现举例。 考试要求 充分了解树型结构的逻辑特征，掌握各种存储结构的构造原理，能够熟练利用常用的三种遍历方法，掌握利用二叉树的遍历操作解决实际问题的方法，掌握二叉排序树的建立以及在二叉排序树中查找一个结点存在与否的过程。
七、图 考试内容 (1)图的定义，基本概念，图的分类，常用名词术语。 (2)图的邻接矩阵存储方法、邻接表存储方法的构造原理。 (3)图的遍历操作。 (4)最小生成树，最短路径，AOV网与拓扑排序。 考试要求 充分了解图的逻辑结构的特点，掌握常用的两种存储方法，掌握最小生成树(Prim算法和Kruskal算法)、最短路径、拓扑排序的具体求解过程。
八、查找 考试内容 (1)查找的概念,关键字比较次数,平均查找长度。 (2)顺序表的查找:顺序查找,折半查找,分块查找。 (3)树表的查找:二叉排序树,平衡二叉树。 (4)哈希(Hash)表的查找:哈希表的概念,哈希函数构造方法,哈希表的建立和查找,冲突处理方法。 考试要求 充分了解各种顺序文件的结构与相应的查找方法；了解各种查找算法之间时空效率的差异；从结构与操作上了解散列文件的建立、散列函数的选择(构造)原则、处理散列冲突的方法以及在散列文件中查找一个记录存在与否的过程。
九、排序 考试内容 (1)排序的概念；排序的稳定性；比较关键字次数，移动记录次数；顺序表的排序，链接表(单链表)的排序。 (2)内排序方法与算法 (a)交换排序：冒泡排序，快速排序。 (b)插入排序：直接插入排序，2-路插入排序，折半插入排序，希尔排序。 (c)选择排序：直接选择排序，锦标赛排序，堆排序。 (d)归并排序。 (e)基数排序。 (3)各种排序算法的评价和应用。 考试要求 充分了解各种排序方法的排序特点和排序过程，对于任意给出的数据元素序列，能够熟练地采用指定排序方法进行排序，并且能够对每一种排序方法排序过程中所进行的元素之间的比较次数、相应排序算法的时间、空间、排序的稳定性等性能进行简单分析。 | |||||||
| 试题结构： | |||||||
| 一、试卷满分及考试时间 本试卷满分为150分，考试时间为180分钟 二、答题方式 答题方式为闭卷、笔试 三、试卷内容结构 数据结构基本概念及简单的算法分析：5％ 线性表：10％－15％ 栈和队列：10％ 串：5％ 数组和广义表：5－10％ 树和二叉树：15％－20％ 图：15－20％ 查找和排序：15％－20％ 四、试卷题型结构 填空题：10分，占7％ 选择题：10分，占7％ 简答题：30分，占20％ 应用题：60分，占40％ 算法分析与设计题：40分，占27％ | |||||||
