招收硕士研究生入学考试

807数据结构考试大纲

一、考试总体要求

《数据结构》是一门专业基础课，要求考生理解数据结构的基本概念，掌握数据的逻辑结构、存储结构及其差异，以及各种基本操作的实现；在掌握基本的数据处理原理和方法的基础上，能够对算法进行时间复杂度和空间复杂度分析；能够选择合适的数据结构和方法进行问题求解。具备采用C、C++设计与实现算法的能力。

二、考试内容

本课程主要考试主要包括的内容：基本概念和算法分析、线性表、栈和队列、串、数组和广义表、树和二叉树、图、查找、排序。

1.基本概念和算法分析

本部分主要介绍数据结构的基本概念和常用术语，算法和算法分析方法。重点要求理解数据结构的基本概念、理解抽象数据结构的定义、算法的基本要素和算法分析方法，掌握算法的时间复杂度和空间复杂度分析方法。

2.线性表

本部分主要介绍线性表的逻辑结构和各种存储表示方法，以及运算的实现。重点要求掌握线性表的定义、特点和基本操作，熟练掌握线性表的存储表示，包括顺序存储和链式存储，以及在这两种存储结构上的插入、删除、查找等运算的实现，理解其异同点和优缺点。掌握特殊链表的定义和基本运算的实现，包括循环链表和双向链表，掌握线性表的应用，包括一元多项式的组织和操作以及其它应用等。

3.栈和队列

本部分主要介绍栈和队列的逻辑结构定义，以及在两种存储结构上基本运算的实现。重点要求熟练掌握栈和队列的基本概念，以及栈和队列的两种实现方法（顺序存储结构实现和链式存储结构实现）及其操作的实现。能够掌握栈和队列的基本应用。

4.串

本部分主要介绍串的基本概念、存储结构和运算。重点要求掌握串的基本概念，掌握串模式匹配KMP及改进算法。

5.数组和广义表

本部分主要介绍数组和广义表的定义、存储及运算。重点要求掌握数组的特点及存储表示方法。掌握特殊矩阵的存储表示方法，包括对称矩阵、对角线矩阵、稀疏矩阵。掌握广义表的定义、存储表示方法以及对广义表的分解操作。

6.树和二叉树

本部分主要介绍二叉树的定义、性质、存储结构、遍历、线索化；树的定义、存储结构、遍历、树和森林的转换，赫夫曼树及其赫夫曼编码等内容。要求掌握树与二叉树的定义、性质，掌握二叉树的存储表示，包括顺序存储和链式存储。掌握二叉树的遍历及其应用，包括先序、中序、后序和层次序遍历。理解线索二叉树的定义、存储表示和寻找前驱、后继。掌握树和森林的存储表示、树、森林与二叉树的转换、树和森林的遍历。掌握赫夫曼树和赫夫曼编码及其应用。

7.图

本部分主要介绍介绍图的基本概念、两种常用的存储结构、两种遍历方法以及图的应用算法。重点要求掌握图的基本概念，基本性质。掌握图的存储方法，重点掌握邻接矩阵法和邻接表法。掌握图的两种遍历方法：深度优先遍历和广度优先遍历算法及实现，掌握拓扑排序算法及算法实现。理解基于图的最小(代价)生成树算法、最短路径算法、关键路径算法。

8.查找

本部分主要介绍线性表、树和哈希表的查找方法、算法实现以及各种查找方法的时间性能（平均查找长度）分析。重点要求掌握顺序查找、折半查找、二叉排序树和哈希表查找的基本思想和算法实现。掌握平衡二叉树的基本操作，理解B-树和B+树的基本概念。能够理解各种不同查找算法的特点及其适用情况，分析不同查找算法的性能。

9.内部排序

本部分主要介绍几种内部排序方法的基本思想、排序过程、算法实现、时间和空间性能的分析；并且对各种排序方法进行比较。重点要求掌握直接插入排序、折半插入排序、起泡排序、快速排序、直接选择排序、堆排序、归并排序、基数排序的基本思想和排序过程。掌握各类排序方法的时间/空间复杂度，以及稳定性。