数据结构复习大纲

1、第一章 概论1 数据结构的基本概念和术语n 数据、数据元素、数据项、数据对象、数据结构等基本概念n 数据结构的逻辑结构，存储结构及数据运算的含义及其相互关系n 数据结构的四种逻辑结构及四种常用的存储表示方法n 抽象数据类型的概念及其与数据结构的关系 2算法的描述和分析。n 算法、算法的时间复杂度和空间复杂度的概念n 算法描述和算法分析的方法第二章 线性表1线性表的逻辑结构n 线性表的逻辑结构特征n 线性表上定义的基本运算，并能利用基本运算构造出较复杂的运算2线性表的顺序存储结构n 顺序表的存储方式及它如何映射线性表中元素之间的逻辑关系n 顺序表的存储结构定义（C语言的类型描述）n 线性表基本运

2、算在顺序表上的实现方法及其时间性能分析n 利用顺序表设计算法解决应用问题3线性表的链式存储结构n 链表的存储方式及它如何映射线性表中元素之间的逻辑关系n 链表中头指针和头节点的使用n 单链表、双链表、循环链表在链接方式上的区别n 各种链表的存储结构定义（C语言的类型描述）n 线性表基本运算在链表上的实现方法及其时间性能分析n 循环链表上尾指针取代头指针的作用n 利用链表设计算法解决简单的应用问题4顺序表和链表的比较n 顺序表和链表的主要优缺点n 根据应用问题的时空要求，为线性表选择合理的存储结构第三章 栈和队列1 栈的逻辑结构，存储结构及其相关算法n 栈的逻辑结构特点，栈与栈性表的关系n 顺序

3、栈和链栈的存储结构定义（C语言的类型描述）n 顺序栈和链栈上进栈、退栈等基本运算的实现方法n 栈上的“上溢”和“下溢”的概念及其判别条件n 递归过程中栈的作用n 设计递归程序的原则和方法n 利用栈设计算法解决简单的应用问题2队列的逻辑结构，存储结构及其相关算法 n 队列的逻辑结构特点，队列与线性表的关系n 顺序队列和链队列的存储结构定义（C语言的类型描述）n 顺序队列（主要是循环队列）和链队列上入队、出队等基本运算的实现方法n 队列的“上溢”和“下溢”的概念及其判别条件n 循环队列取代普通的顺序队列的原因n 利用队列设计算法解决简单的应用问题第四章 串1串及其运算n 串的概念及其与线性表的关系

4、n 串上定义的基本运算，并能利用基本运算构造出较复杂的运算2串的存储结构和基本运算的实现n 串的两种主要存储结构顺序串和链串的存储结构定义（C语言的类型描述）n 顺序串上串的基本运算的实现n 朴素的模式匹配算法与KMP算法的算法思想及时间复杂度分析n KMP算法中next和nextval数组的求值方法第五章 数组和广义表1多维数组n 多维数组的逻辑结构特征，多维数组和线性表的关系n 多维数组的顺序存储结构及地址计算方法n 数组是一种随机存取结构的原因2矩阵的压缩存储n 特殊矩阵和稀疏矩阵的概念n 特殊矩阵在压缩存储时的下标变换方法n 稀疏矩阵的三元组表和十字链表表示方法3广义表n 广义表的有关

5、概念及其与线性表的关系n 求给定非空广义表的表头和表尾运算第六章 树1树的概念n 树的逻辑结构特征n 树的常用术语及含义2二叉树n 二叉树的定义，二叉树与树的差别n 完全二叉树和满二叉树的概念n 二叉树的性质n 二叉树的顺序存储结构和链式存储结构的定义（C语言的类型描述）和表示方法3二叉树的遍历n 二叉树的先序、中序、后序、层序遍历算法n 求给定二叉树的先序、中序、后序遍历对应的结点访问序列n 由二叉树的先序和中序、中序和后序、中序和层序的序列确定二叉树n 以遍历算法为基础，设计有关算法解决简单的应用问题4线索二叉树n 二叉树线索化的目的n 线索二叉树存储结构的表示方法n 在线索二叉树中查找给

6、定结点的前趋和后继的方法5树和森林n 树和森林与二叉树之间的转换方法和对应关系n 树的各种存储结构的表示方法及其特点n 树的先序和后序遍历方法n 森林的先序和中序遍历方法6哈夫曼树及其应用n 最优二叉树的概念及特点n 求哈夫曼树的方法n 设计哈夫曼编码的方法第七章 图1图的概念n 图的逻辑结构特征n 图的常用术语及含义2图的存储结构n 图的邻接矩阵的存储结构定义（C语言的类型描述）及表示法和特点n 图的邻接表的存储结构定义（C语言的类型描述）及表示法和特点3图的遍历n 图的深度优先搜索和广度优先搜索遍历算法及时间性能n 确定两种遍历所得到的顶点访问序列n 图的两种遍历与树的遍历之间的关系n 利

7、用图的两种遍历设计算法解决简单的应用问题4生成树和最小生成树n 生成树和最小生成树的概念n 对给定的图画出深度和广度优先生成树或生成森林n Prim和Kruskal算法的基本思想n 对给定的连通图，根据Prim和Kruskal算法构造出最小生成树5有向无环图的应用n 拓扑排序的基本思想和步骤n 拓扑排序不成功的原因n 求给定AOV网的拓扑序列n 关键路径、关键活动的概念n 求AOE网的关键路径的步骤和方法n 对给定的AOE网，求关键路径和工期6最短路径n 最短路径的含义n 求单源最短路径的Dijkstra算法的基本思想和时间性能n 对于给定的有向图，画出根据Dijkstra算法求单源最短路径的

8、过程示意图n 求每一对顶点间最短路径的Floyd算法的基本思想和时间性能n D (k) i,j (0kn-1)的含义n 对于给定的有向图，用Floyd算法求每一对顶点之间的最短路径长度，能写出D(-1) ，D(0) ，D(n-1) 的值第八章 查找1基本概念n 静态查找表和动态查找表的含义n 平均查找长度ASL的定义2静态查找表n 顺序查找、折半查找、分块查找的算法思想、算法实现、ASL的分析计算n 折半查找对存储结构和关键字的要求n 三种查找方法的主要优缺点3动态查找表n 二叉排序树的定义、特点和用途n 二叉排序树的查找方法和算法实现、ASL的分析和计算n 二叉排序树的插入、删除、建树方法n

9、 输入实例对所建二叉排序树形态的影响n 平衡二叉树的定义和作用n 平衡二叉树插入结点及生成过程中的调整方法n B-树的定义n B-树上的查找、插入、删除、生成方法n B+树的定义n B+树上的查找方法4哈希表n 哈希表、哈希函数、哈希地址和装填因子等有关概念n 哈希函数的选取原则及产生冲突的原因n 常用的哈希函数的构造方法n 解决冲突的主要方法n 产生“堆积”现象的原因n 哈希表查找和其它表查找的本质区别。n 采用线性探测法或拉链法解决冲突时，哈希表的建表方法、查找过程以及ASL的分析计算第九章 内部排序1基本概念n 排序方法的稳定性的含义n 排序算法评价标准2插入排序n 直接插入排序的基本思

10、想、算法实现、时空性能n 希尔排序的基本思想和时空性能3交换排序n 冒泡排序的基本思想、算法实现、时空性能n 快速排序的基本思想、算法实现、时空性能n 枢轴记录的选取对快速排序的影响n 针对给定的输入实例，写出快速排序的每趟排序过程4选择排序n 简单选择排序的基本思想、算法实现、时空性能n 锦标赛排序的基本思想和时空性能n 堆的有关概念和定义n 堆的性质及堆与完全二叉树的关系n 堆排序的基本思想、算法实现、时空性能n 针对给定的输入实例，能写出堆排序的排序过程5归并排序n 两路归并排序的基本思想、算法实现、时空性能n 针对给定的输入实例，能写出归并排序的排序过程6基数排序n 基数排序的基本思想、时空性能。n 针对给定的输入实例能写