数据结构期末复习提纲ppt课件.ppt

《数据结构期末复习提纲ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第1-3章绪论1复习范围：第一、二、三章所有内容2复习要点：1）数据结构的基本概念逻辑结构：表，树，图存储结构：顺序（静态），链式（动态），索引，Hash2）算法和算法分析计算算法的时间复杂度和空间复杂度的方法第四章线性表、栈、队列1复习范围：第四章所有内容2线性表复习要点：1）线性表的逻辑结构2）线性表的存储结构：顺序：数组，表长表示链式：单链表，循环链表，双向链表，头指针，头结点，首结点，空标志，结束标志3）插入和删除算法遍历方法：i++p=p->next算法实现:元素移动指针调整算法的时间复

2、杂度第四章线性表、栈、队列（续）3栈、队列复习要点：1）栈的定义，特性（LIFO），存储结构2）POP和PUSH算法3）栈的空、满标志4）队列的定义，特性（FIFO）5）链式队列和循环队列的存储结构6）队列的入队和出队算法7）队列的空、满标志8）堆栈应用，举例：表达式求值：A*(B+C)-D1复习范围：PPT2复习要点：1）数组的逻辑结构2）以行或列为主序的存储结构及地址计算3）对特殊矩阵压缩存储的下标变换方法4）稀疏矩阵的三元组表示和十字链表表示方法5）广义表的定义、特点和存储结构（附加）数组与

3、广义表第五、六章二叉树和普通树1复习范围：第五章、第六章2复习要点：1）树的递归形式的定义和其他术语2）二叉树的定义，形态，五条性质及其证明，存储结构3）二叉树的遍历：求遍历序列，遍历算法，由两种遍历序列恢复二叉树4）树与森林：存储结构，与二叉树的转换，先根和后根遍历，由两种遍历序列恢复树或森林5）哈夫曼树：带权路径长度，最优二叉树的定义，构造方法，哈夫曼编码的方法第七章图1复习范围：第七章2复习要点：1）概念术语：图与网（有向、无向），顶点与边（弧），邻接与度，路径，连通，生成树2）图的邻接矩阵

4、或邻接表的表示，求顶点度的算法，求顶点的边或弧的算法3）图的DFS、BFS遍历序列4）无向图的DFS，BFS生成树5）利用Prim算法和Kruskal算法的基本方法求无向网的最小生成树6）利用Dijkstra算法求最短路径第八章内部排序1复习范围：第八章2复习要点：1）概念术语：排序，排序的分类，稳定性2）基本排序算法：直接插入、起泡、简单选择排序的算法实现，效率分析（关键字的比较次数和元素的移动次数）3）先进排序方法：Shell、快速、堆、归并、基数排序的方法和执行过程，堆的调整方法第九、十章查

5、找、索引1复习范围：第九章、第十章2复习要点：1）概念术语：查找表、关键字、查找成功（失败）2）线性表查找：顺序、自组织表、折半算法实现，对存储结构的要求，平均查找长度计算。判定树概念。3）Hash表：Hash函数及其构造方法，冲突及其解决方法，Hash表的查找、插入、删除过程，平均查找长度4）索引查找：线性索引表、分块索引表。5）二叉排序树的定义，查找算法，插入和删除算法，平均查找长度6）AVL树的定义，构造过程，插入删除旋转类型与方法7）2-3树（B-树）的定义，查找、插入、删除的方法考试常见

6、题型(复习提纲)第一部分：概念、线性表、栈和队列----线性结构．算法的五个重要特性?．算法的时间复杂度、空间复杂度?．线性表的元素关系存储时如何体现？．头结点的作用？首结点、头结点、头指针区别？.单链表、双链表、循环链表的插入和删除操作,以及判断链表为空的条件？．循环队列Q[0，n-1]，头、尾位置为f、r，队满、队空的条件？队列元素个数计算？．双端队列、单端受限队列的入队与出队序列关系？.元素进栈与退栈的过程？对已知入栈序列，可能输出结果及不可能输出结果？考试常见题型(复习提纲)第二部分：二叉

7、树与普通树---树形结构．树的表示形式？二叉树的性质？二叉树的存储结构？二叉树的四种遍历？.具有n个结点的二叉树的最小深度？最大深度？．n个结点的完全二叉树顺序存储，叶结点和非叶结点的个数、范围？．遍历方式不同叶结点的相对顺序如何？内结点的相对顺序又如何？.已知二叉树的两种遍历结果（一般必须包含一个中序或层序），请构造这棵二叉树？.树的存储结构有哪些？树和森林与二叉树的相互转换？（即对一棵树或森林给出二叉链表存储？根据二叉链表存储画出该树或森林？）.已知电文，求哈夫曼编码需要位数和具体编码数？对已

8、知序列进行哈夫曼编码？.设二叉树采用二叉链表存储，请编写算法实现求二叉树高度(结点个数，判定是否为平衡二叉树，是否为二叉排序树,AVL树的构造等)？考试常见题型(复习提纲)第三部分：图---图形结构．无向图和有向图的存储方法（主要有2种）？．图的遍历（深度优先和广度优先）？图的遍历结果与存储结构有关！.图的生成树？带权图的最小生成树？.有向图可以进行拓扑排序的条件？对一个图进行拓扑排序？.对已知带权有向图，求关键路径？计算某源点都其余顶点的最短路径？.比如，已知一个无向图的邻接表（