重庆交通大学2016年全国硕士研究生招生考试《数据结构》考试大纲

一、考试总体要求：

1、熟练掌握数据结构的基本概念，包括数据的逻辑结构、存储结构和算法，掌握算法分析的基本概念，能进行算法复杂度的分析。

2、熟练掌握线性表的基本概念以及存储结构的表示和实现，掌握在设定的存储结构下各种类型线性表的算法设计。

3、熟练掌握栈和队列的基本概念与性质，掌握在顺序存储和链式存储结构下对栈和队列的操作，以及利用栈与队列解决实际问题的基本方法。

4、充分理解串的基本概念、熟练掌握串的存储结构和相关的操作算法。

5、掌握数组、广义表和稀疏矩阵的基本概念，存储结构和基本操作的实现

6、充分理解树型结构的基本概念,熟练掌握其逻辑特征，掌握树的各种存储结构的表示方法，能够熟练地进行树与二叉树之间的转换。

7、充分理解二叉树的基本概念、性质；掌握树的数组存储表示和链表存储表示；训练掌握二叉树的各种遍历方法，以及各种遍历的递归和非递归算法，掌握利用二叉树的遍历操作解决实际问题的方法。

8、充分理解线索二叉树的基本概念，掌握其存储结构的表示和实现，掌握线索二叉树的建立和遍历算法；掌握中序线索二叉树的插入和删除算法，掌握前序和后序线索化二叉排序树的方法以及算法；掌握在中序线索二叉树中查找某一结点的前趋和后继结点的算法。

9、掌握堆的基本概念以及其操作。

10、充分理解树的路径长度的概念，熟练掌握Huffman树的概念以及算法,了解Huffman编码方法.

11、充分理解图的基本概念以及其逻辑结构和特点，熟练掌握常用的两种存储方法（邻接矩阵和邻接表）以及在其存储结构上的深度优先和广度优先遍历算法的设计，掌握图的连通分量的算法思想。了解图的其他存储结构。掌握最小生成树的Prim算法和Kruskal算法、掌握非负权值的图的最短路径概念、以及最常见的三种最短路径的算法思想。掌握拓扑排序的算法思想以及其具体求解过程。

12、掌握数据文件的基本概念和数据文件的基本操作。

13、掌握散列表的概念以及散列方法、掌握散列函数的选择(构造)原则、处理散列冲突的方法。

14、掌握查找或搜索的基本概念；掌握静态查找表和动态查找表的概念；掌握线性查找的方法及其算法；掌握在有序线性表上进行折半查找的方法和算法。了解二叉搜索树和AVL树的概念。

15、充分了解各种排序方法的排序特点和排序过程，对于任意给出的数据元素序列，能够熟练地采用指定排序方法进行排序，并且能够对每一种排序方法排序过程中所进行的元素之间的比较次数、相应排序算法的时间、空间、排序的稳定性等性能进行分析。

★ 考试内容

1、数据结构概论

（1）数据结构的基本概念，数据的逻辑结构、存储结构以及数据结构的分类。

（2）算法的定义、算法的性能分析以及算法的度量。

2、线性表

（1）线性表的定义以及线性表的基本操作。

（2） 顺序表的定义和特点；顺序表上的各种操作算法实现以及其性能分析。

（3） 顺序表的应用。

（4） 单链表的定义和各种算法实现以及其性能分析。

（5） 单链表的应用。

3、栈与队列

（1）栈与队列的基本概念、基本性质。

（2）栈与队列的顺序存储结构与链式存储结构定义以及其操作和算法实现。

（3）栈与队列的应用。

（4）递归的概念和递归工作栈。

（5） 双端队列的概念以及其数组和链表表示。

4、串

（1）串的基本概念、串的基本操作和存储结构。

（2）串的模式匹配算法和改进的KMP算法

5、数组和广义表

（1）数组的概念、多维数组的实现。

（2）对称矩阵和稀疏矩阵的压缩存储。

（3）广义表的基本概念、表示和基本操作。

6、树与二叉树

（1）树的定义和性质。

（2）二叉树的概念、性质。

（3）二叉树的存储结构。

（4）二叉树的遍历及其应用。

（5）线索二叉树。

（6）树和森林。

（7）堆的概念（最大堆和最小堆）；堆的建立以及堆的插入和删除算法。

（7）赫夫曼树及其应用。

7、图

（1）图的定义，基本概念，图的分类，常用名词术语。

（2）图的存储结构。邻接矩阵存储表示和邻接表存储表示以及其算法实现。

（3）图的遍历操作概念以及其算法实现。

（4）最小生成树，最短路径，AOV网与拓扑排序。

8、文件及查找

（1）数据文件的基本概念和基本术语，数据文件的基本操作。

（2）顺序文件、索引文件、散列(Hash)文件。

（3）静态查找表和顺序查找。

（4）基于有序表的折半查找以及其性能分析。

（5）散列表和散列方法；散列函数；处理散列冲突的基本方法。

（6）二叉搜索树的概念；AVL树的概念。

9、排序

（1）排序的基本概念，排序方法和分类。

（2）插入排序法(含折半插入排序法)、选择排序法、泡排序法、快速排序法、堆排序法、归并排序、基数排序。各种排序方法排序的原理、规律和特点，各种排序算法的时空复杂度分析。

二、考试形式与试卷结构

（一）考试形式

考试形式为笔试，考试时间为3小时，满分为150分。

（二）试卷结构（题型）

1．单项选择题和多项选择题；

2．填空题(基本概念、基本知识、基本方法)；

3．简答题；

4．应用题(求解问题)；

5．算法和程序设计填空题；

6．算法和程序设计与分析题；

7．其它题型。

三、主要参考书目

1、《数据结构》(第2版).殷人昆. 清华大学出版社

更多学历考试信息请查看学历考试网