3.1 《数据结构》

3.1.1 考试的基本要求

1.理解数据结构的基本概念;掌握数据的逻辑结构、存储结构及其差异，以及各种基本操作的实现。

2.掌握基本数据处理原理和方法的基础上，能够对算法进行基本的时间复杂度与空间复杂度分析。

3.能够选择合适的数据结构和方法进问题求解，具备采用 C 或 C++或 JAVA 语言设计与实现算法的能力。

3.1.2 考试的主要内容与要求

1、数据结构和算法的基本概念

了解数据结构的基本概念，包括逻辑结构、物理结构的基本概念、两者之间的区别与联系。

了解算法的基本概念和性质。

了解算法复杂度的基本概念，掌握对非递归代码的复杂度的计算基本方法。

2、线性表

了解线性表的逻辑结构定义。

掌握线性表的顺序结构实现，以及顺序结构下基本操作的实现，能写出操作代码。掌握线性表的链式结构实现，以及链式结构下基本操作的实现，能写出操作代码。能够设计针对顺序结构和链式结构线性表的一般应用问题的算法，能写出算法代码。

掌握栈的基本概念、栈的性质。

掌握栈的顺序结构和链式结构实现，以及相应操作的实现，能够写出操作代码。了解栈与递归的关系，能够编写递归算法，能够将递归算法转换为非递归形式。掌握队列的基本概念和性质。

掌握队列的顺序结构和链式结构实现，以及相应操作的实现，能写出操作代码。掌握栈和队列的应用方法，能够运用栈和队列解决相关问题，能写出算法代码。掌握串的基本操作实现，能写出算法代码。

掌握串的朴素模式匹配算法和KMP 模式匹配算法，能手工计算KMP 算法中的nextval

向量，能写出算法代码。

掌握稀疏矩阵的三元组表存储方法以及基于三元组表结构的快递转置算法，能写出算法代码。

3、树和二叉树

了解树的定义和性质。了解二叉树的概念。

掌握二叉树的基本性质，并能够进行描述和证明。(包括深度与最大结点数的关系性质、每层最大结点数性质、结点数与最小深度的关系性质、n2=n0-1 性质、完全二叉树序号与结点关系性质等)

掌握二叉树的二叉链结构的实现。

掌握二叉树的前序遍历、中序遍历、后序遍历和层次遍历规则，能够手工计算二叉树的遍历序。

掌握二叉树的遍历性质，能够根据前序+中序或中序+后序还原出二叉树，并能写出

还原算法代码。

掌握二叉树的前序、中序和后序递归遍历算法，能写出算法代码。

了解线索化二叉树的概念。了解哈夫曼树的概念。

掌握哈夫曼算法的思想和步骤，能够手工计算哈夫曼树，能写出算法代码。了解哈夫曼编码的概念，能够手工计算哈夫曼编码。

了解树、森林和二叉树的关系。

能够解决一般性的二叉树应用问题，设计算法并写出算法代码。

4、图

了解图的定义。

掌握图的邻接矩阵、邻接表的实现方法。

掌握图的深度优先和广度优先遍历算法，能够手工计算图的深度优先遍历序和广度优先遍历序，能写出算法代码。

掌握最小生成树计算(Prim 算法和 Kruskal 算法)，能够进行手工计算，能写出算法代码。

掌握最小生成树的 MST 性质，能够进行描述和证明。

掌握拓扑排序和关键路径问题的求解算法，能够进行手工计算，能写出算法代码。掌握单源起点最短路径算法(Dijkstra 算法)和任两点间最短路径算法(Floyd 算法)，

能够进行手工计算，能写出算法代码。

5、查找

掌握静态表的概念和折半查找算法，能够进行手工计算，能写出算法代码。掌握散列表的基本概念，散列函数的基本设计技巧。

掌握二叉排序树的概念，以及二叉排序树上的查找、插入、删除算法，能够进行手

工计算，能写出算法代码。

掌握平衡二叉树的概念，以及平衡二叉树的插入和调整算法，能够进行手工计算。了解 B-、B+树的概念，以及 B-树的插入和删除算法。

6、内排序

掌握简单选择排序、直接插入排序、交换排序、希尔排序、快速排序、堆排序、二路归并排序、基数排序的算法思想和步骤，能够写出排序过程，能写出算法代码。

了解各种排序方法的特点，能够针对特定问题背景选择适当的排序方法。

3.1.3 主要参考书

严蔚敏.数据结构(C 语言版).北京：清华大学出版社，2020