第一章概论
1． 数据结构的基本概念和术语。
数据、数据元素、数据项、数据对象、数据结构等基本概念。
数据结构的逻辑结构，存储结构及数据运算的含义及其相互关系。
数据结构的四种逻辑结构及四种常用的存储表示方法。
第二章算法分析技术。
1．算法的描述和分析。
无穷大阶的几种描述方法的区别。
算法、算法的时间复杂度和空间复杂度的概念。
几种常见复杂度的好坏程度。
就（原）地算法的含义。
算法描述和算法分析的方法。
第三章线性表。
1．线性表的逻辑结构。
线性表的逻辑结构特征。
线性表上定义的基本运算，并能利用基本运算构造出较复杂的运算。
2．线性表的顺序存储结构。
顺序表的存储方式及它如何映射线性表中元素之间的逻辑关系。
顺序表的存储结构定义。
线性表基本运算在顺序表上的实现方法及其时间性能分析。
利用顺序表设计算法解决应用问题。
3．线性表的链式存储结构。
链表的存储方式及它如何映射线性表中元素之间的逻辑关系。
链表中头指针和头节点的使用。
单链表、双链表、循环链表在链接方式上的区别。
各种链表的存储结构定义。
线性表基本运算在链表上的实现方法及其时间性能分析。
循环链表上尾指针取代头指针的作用。
利用链表设计算法解决简单的应用问题。
4．顺序表和链表的比较。
顺序表和链表的主要优缺点。
根据应用问题的时空要求，为线性表选择合理的存储结构。
5. 数组和矩阵。
多维数组的逻辑结构特征，多维数组和线性表的关系。
多维数组的顺序存储结构及地址计算方法。
数组是一种随机存取结构的原因。
对称矩阵和稀疏矩阵的概念。
对称矩阵在压缩存储时的下标变换方法。
稀疏矩阵的三元组表和十字链表表示方法。
稀疏矩阵压缩存储后不能进行随机存取的原因。
第四章栈和队列。
1． 栈的逻辑结构，存储结构及其相关算法。
栈的逻辑结构特点，栈与栈性表的关系。
顺序栈和链栈的存储结构定义。
顺序栈和链栈上进栈、退栈等基本运算的实现方法。
已知入栈序列求可能的出栈序列。
栈上的“上溢”和“下溢”的概念及其判别条件。
递归过程中栈的作用。
设计递归程序的原则和方法。
递归程序改写为非递归程序的方法。
利用栈设计算法解决简单的应用问题。
2．队列的逻辑结构，存储结构及其相关算法
队列的逻辑结构特点，队列与线性表的关系。
顺序队列和链队列的存储结构定义。
顺序队列（主要是循环队列）和链队列上入队、出队、求队列中元素个数等基本运算的实现方法。
队列的“上溢”和“下溢”的概念及其判别条件。
循环队列取代普通的顺序队列的原因。
利用队列设计算法解决简单的应用问题。
第五章字符串与模式匹配。
1．串及其运算。
串的概念及其与线性表的关系。
串上定义的基本运算。
2．串的存储结构和基本运算的实现。
串的两种主要存储结构—顺序串和链串的存储结构定义。
顺序串上串的基本运算的实现。
朴素的模式匹配算法与kmp算法的算法思想及时间复杂度分析。
kmp算法中next和nextval数组的含义和求值方法。
第六章树与二叉树。
1．树的概念
树的逻辑结构特征。
树的常用术语及含义。
2．二叉树。
二叉树的定义，二叉树与树的差别。
完全二叉树和满二叉树的概念。
二叉树的性质。
二叉树的顺序存储结构和链式存储结构的定义和表示方法。
3．二叉树的遍历。
二叉树的先序、中序、后序、层序遍历算法。
求给定二叉树的先序、中序、后序遍历对应的结点访问序列。
由二叉树的先序和中序、中序和后序、中序和层序的序列确定二叉树。
以遍历算法为基础，设计有关算法解决简单的应用问题。
4．线索二叉树。
二叉树线索化的目的。
线索二叉树存储结构的表示方法。
**索二叉树中查找给定结点的前趋和后继的方法。
5．树和森林。
树和森林与二叉树之间的转换方法和对应关系。
树的各种存储结构的表示方法及其特点。
树的先序和后序遍历方法。
森林的先序和中序遍历方法。
利用树/森林设计算法解决简单的应用问题。
6．哈夫曼树及其应用。
最优二叉树的概念及特点。
求哈夫曼树的方法。
设计哈夫曼编码的方法。
7. 并查集。
等价类和并查集的定义。
等价类与树的关系。
几种并操作的方法。
几种查操作的方法。
不同并操作和查操作的时间性能分析。
第七章图。1．图的概念。
图的逻辑结构特征。
图的常用术语及含义。
2．图的存储结构。
图的邻接矩阵的存储结构定义及表示法和特点。
图的邻接表的存储结构定义及表示法和特点。
在特定运算下邻接矩阵与邻接表的时空性能的比较。
有向图的十字链表表示方法。
无向图的邻接多重表表示方法。
3．图的遍历。
图的深度优先搜索和广度优先搜索遍历算法及时间性能。
确定两种遍历所得到的顶点访问序列。
图的两种遍历与树的遍历之间的关系。
利用图的两种遍历设计算法解决简单的应用问题。
4．图的连通性。
强连通分量的求法。
生成树和最小生成树的概念。
对给定的图画出深度和广度优先生成树或生成森林。
prim和kruskal算法的基本思想。
对给定的连通图，根据prim和kruskal算法构造出最小生成树。
5．有向无环图的应用。
拓扑排序的基本思想和步骤。
拓扑排序不成功的原因。
判断有向图是否存在环的几种方法。
求给定aov网的拓扑序列。
关键路径、关键活动的概念。
求aoe网的关键路径的步骤和方法。
对给定的aoe网，求关键路径和工期。
6．最短路径。
最短路径的含义。
求单源最短路径的dijkstra算法的基本思想和时间性能。
对于给定的有向图，画出根据dijkstra算法求单源最路径的过程示意图。
求每一对顶点间最短路径的floyd算法的基本思想和时间性能。
a (k) [i,j] (1≤k≤n)的含义。
对于给定的有向图，用floyd算法求每一对顶点之间的最短路径长度，能写出a(0) ，1) ，n) 的值。
能利用最短路径算法设计算法解决简单应用问题。
第八章查找。
1．基本概念。
静态查找表和动态查找表的含义。
平均查找长度asl的定义。
2．静态查找表。
顺序查找、折半查找、分块查找的算法思想、算法实现、asl的分析计算。
折半查找对存储结构和关键字的要求。
三种查找方法的主要优缺点。
次优查找树的原理和构造方法。
3．动态查找表。
二叉排序树的定义、特点和用途。
二叉排序树的查找方法和算法实现、asl的分析和计算。
二叉排序树的插入、删除、建树方法。
输入实例对所建二叉排序树形态的影响。
平衡二叉树的定义和作用。
平衡二叉树的性质和平衡因子的含义。
平衡二叉树插入结点及生成过程中的调整方法。
平衡二叉树asl的计算。
b-树的定义。
b-树上的查找、插入、删除、生成方法。
b+树的定义。
b+树与b-树的异同点。
b+树上的查找方法。
4．哈希表。
哈希表、哈希函数、哈希地址和装填因子等有关概念（装填因子的计算方法）
哈希函数的选取原则及产生冲突的原因。
常用的哈希函数的构造方法。
解决冲突的主要方法。
产生“堆积”现象的原因。
哈希表查找和其它表查找的本质区别。
采用线性探测法或拉链法解决冲突时，哈希表的建表方法、查找过程以及asl的分析计算。
第九章内部排序。
1．基本概念。
排序方法的稳定性的含义。
排序算法的分类方法。
排序算法评价标准。
2．插入排序。
直接插入排序的基本思想、算法实现、时空性能。
希尔排序的基本思想和时空性能。
针对给定的输入实例，写出插入类排序的排序过程。
3．交换排序。
冒泡排序的基本思想、算法实现、时空性能。
快速排序的基本思想、算法实现、时空性能。
枢轴记录的选取对快速排序的影响。
针对给定的输入实例，写出交换类排序的排序过程。
4．选择排序。
简单选择排序的基本思想、算法实现、时空性能。
锦标赛排序的基本思想和时空性能。
堆的有关概念和定义。
堆的性质及堆与完全二叉树的关系。
堆排序的基本思想、算法实现、时空性能。
针对给定的输入实例，能写出选择类排序的排序过程。
5．归并排序。
两路归并排序的基本思想、算法实现、时空性能。
针对给定的输入实例，能写出归并排序的排序过程。
6．基数排序。
基数排序的基本思想、时空性能。
基数排序和其它几类排序的本质区别。
针对给定的输入实例能写出基数排序的排序过程。
7．各种排序方法的比较。
掌握各种排序的主要特点。
根据实际问题的特点和要求选择合适的排序方法。
利用各种排序方法思想设计算法解决简单应用问题。
第一十章外部排序。
外部排序的两个基本步骤。
外排序时内外存交换次数的计算。
提高外排序效率的两个手段。
利用“败者树”实现多路平衡归并的原因和方法。
通过置换-选择排序生成初始归并段的方法。
最佳归并树的意义和构造方法。
数据结构复习提纲
软件学院数据结构与算法复习提纲。data structures and algorithms 概念 type,类型 一组值的集合。type,简单类型例如整数，因为它的值不含有子结构。aggregate type,复杂类型，一个记录含有多项信息。银行账户含有多项信息如姓名 地址 composite t...
数据结构复习提纲
第一部分试题说明。1 试卷考试时间为90分钟。2 试题类型 选择题 20个，每题2分，共40分 简答题 6个，每题5分，共30分 和算法设计题 2个，每题15分，共30分 第二部分各章知识点。第1章绪论。1 数据结构的概念。2 数据结构的形式化表示方法 ds d，r 要求给定一个形式化表示，能够画出...
数据结构复习提纲
概述。1 数据结构定义 本质。2 数据结构三要素。3 顺序存储方式和链式存储方式优缺点。4 数据结构按关系分类 线性结构 非线性结构 集合结构。5 时间复杂度估计 讲过的例题 线性表。1 顺序栈 特点lifo 存储定义 基本操作 入栈 出栈 入栈时需判栈是否为满 出栈时需判栈是否为空 入栈出栈时to...