《数据结构》部分
（一）绪论
1.识记：（1）数据结构的基本概念：数据、数据元素、数据项、数据对象、数据结构；（2）根据数据元素之间关系的不同特性通常有哪四种基本结构；（3）抽象数据类型的概念；（4）算法、算法的时间复杂度和空间复杂度的定义；
2.理解：（1）算法的时间复杂度的分析；（2）选择合适的数据结构是解决应用问题的关键步骤；
3.运用：对于一般算法能分析出其时间复杂度。
（二）线性表
1.识记：（1）线性结构的特点；（2）线性表的抽象数据类型；（3）链表中的相关概念：头指针、头结点、首结点、尾结点、尾指针；
2.理解：（1）线性表的顺序表示和实现，特别是插入、删除算法的实现，并分析其时间复杂度；（2）线性表的链式表示和实现，特别是建表、插入、删除和查找算法的实现，并分析其时间复杂度；（3）链表如何表示线性表中元素之间的逻辑关系；（4）单链表、双向链表、循环链表的区别；（5）顺序表和链表的优缺点；
3.运用：（1）利用顺序表的结构特征设计算法解决简单的应用问题；（2）利用链表的结构特征设计算法解决简单的应用问题。
（三）栈和队列
1.识记：（1）栈的相关概念：栈、栈顶、栈底、空栈等；（2）队列的相关概念：队、队头、队尾等；（3）循环队列的定义。
2.理解：（1）栈和队列与线性表的异同；（2）栈的逻辑结构特征；（3）顺序栈的实现，特别是进栈和出栈算法的实现；（4）队列的逻辑结构特征；（5）链队列的出队、入队算法的实现；（6）顺序队列（主要是循环队列）的出队、入队算法的实现，溢出的概念及其队空、队满的判定条件；（7）栈和队列的特点，什么样的情况下能够使用栈或队列。
3.运用：（1）利用栈的结构特征设计算法解决简单的应用问题；（2）利用队列的结构特征设计算法解决简单的应用问题。
（四）串
1.识记：（1）串的定义；（2）串的相关概念：长度、子串、空串、位置等。
2.理解：（1）串与线性表的区别；（2）串的抽象数据类型；（3）串的定长顺序存储方式的算法实现；（4）串的模式匹配算法，特别是KMP算法。
3.运用：改进的KMP算法。
（五）树和二叉树
1.识记：（1）树的定义和相关术语；（2）树的逻辑结构特征；（3）二叉树的定义；（4）最优二叉树（赫夫曼树）的相关概念。
2.理解：（1）树的三种表示法；（2）二叉树的性质；（3）二叉树的顺序存储结构和链式存储结构；（4）二叉树的三种遍历算法及其实现：先序遍历、中序遍历、后序遍历，并确定三种遍历所得到的相应的结点访问序列；（5）二叉树线索化的目的及实质；（6）树和森林与二叉树之间的转换；（7）赫夫曼树算法的思想。
3.运用：（1）根据给定的叶子结点及其权值构造出相应的赫夫曼树；（2）根据赫夫曼树构造对应的赫夫曼编码。
（六）图
1.识记：（1）图的定义与术语；（2）图的逻辑结构特征；（3）生成树和最小生成树的相关概念；（4）最短路径的含义；（5）关键路径的含义。
2.理解：（1）图的邻接矩阵和邻接表两种存储结构算法的实现；（2）根据应用问题的特点和要求选择合适的存储结构；（3）连通图及非连通图的深度优先搜索和广度优先搜索算法的实现及时间分析；（4）最小生成树的两种算法：Prim算法和Dijkstra算法的基本思想、时间性能及其各自的特点；（5）拓扑排序的基本思想和步骤；（6）关键路径算法的实现；（7）求单源最短路径的Dijkstra算法的基本思想和时间性能。
3.运用：（1）对给定的连通图，根据Prim和Kruskal算法构造出最小生成树；（2）对给定的有向图，若拓扑序列存在，则写出一个或多个拓扑序列；（3）在AOE网中，求出活动的最早开始时间和最晚开始时间，得到关键活动，求出关键路径；（4）对于给定的有向图，根据Dijkstra算法构造出单源最短路径。
（七）查找
1.识记：（1）查找表以及相关概念；（2）二叉排序树的相关概念；（3）哈希表的相关概念。
2.理解：（1）顺序查找、二分查找的算法实现和查找效率分析；（2）二叉排序树的插入、删除、建立和查找算法的实现及效率分析；（3）哈希表的构造方法和处理冲突的方法。
3.运用：哈希表查找方法的应用。

展开全文