数据期末复习提纲.ppt

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

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

2、要点：1）栈的定义，特性（LIFO），存储结构2）POP和PUSH算法3）栈的空、满标志4）队列的定义，特性（FIFO）5）链式队列和循环队列的存储结构6）队列的入队和出队算法7）队列的空、满标志8）堆栈应用，举例：表达式求值：A*(B+C)-D第四章（附加）串1复习范围：PPT2复习要点：1）串的定义，特性，术语2）串的各种操作的含义3）存储结构：定长顺序存储，堆分配存储4）联接，求子串算法的实现5）基本模式匹配算法6）next函数的定义和求解方法1复习范围：PPT2复习要点：1）数组的逻辑结构2）以行或列为主序的存储结构及地址计算3）对特殊矩阵压

3、缩存储的下标变换方法4）稀疏矩阵的三元组表示和十字链表表示方法5）广义表的定义、特点和存储结构6）广义表的表头和表尾分解方法第四章（附加）数组与广义表第五、六章二叉树和普通树1复习范围：第五章、第六章2复习要点：1）树的递归形式的定义和其他术语2）二叉树的定义，形态，五条性质及其证明，存储结构3）二叉树的遍历：求遍历序列，遍历算法，由两种遍历序列恢复二叉树4）树与森林：存储结构，与二叉树的转换，先根和后根遍历，由两种遍历序列恢复树或森林5）哈夫曼树：带权路径长度，最优二叉树的定义，构造方法，哈夫曼编码的方法第七章图1复习范围：第七章2复习要点：1）概

4、念术语：图与网（有向、无向），顶点与边（弧），邻接与度，路径，连通，生成树2）图的邻接矩阵或邻接表的表示，求顶点度的算法，求顶点的边或弧的算法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-树）的定义，查找、插入、删除的方法