程序编写复习要点.ppt

《程序编写复习要点.ppt》由会员分享，可在线阅读，更多相关《程序编写复习要点.ppt（10页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、复习要点复习要点 绪论绪论 时间和空间复杂性的定义、简单算法的级别的求时间和空间复杂性的定义、简单算法的级别的求法法 求法。求法。时空复杂性的大时空复杂性的大 O表示法、级别好坏的判断表示法、级别好坏的判断 大大 表示法。表示法。串的模式匹配算法串的模式匹配算法 失效函数失效函数的求法的求法和程序实现，及其时间复杂性和程序实现，及其时间复杂性 级别。级别。在主串中寻找模式的算法和程序实现。在主串中寻找模式的算法和程序实现。1复习要点复习要点 线性表线性表 顺序表：顺序表：基本操作：插入和删除、查找实现程序、代价、时间复杂基本操作：插入和删除、查找实现程序、代价、时间复杂 性分析性分析 链接表示

2、和实现：链接表示和实现：单链表基本操作：插入和删除、查找实现程序、代价、时单链表基本操作：插入和删除、查找实现程序、代价、时 间复杂性分析间复杂性分析 静态链表基本操作：插入和删除、查找实现程序、代价、静态链表基本操作：插入和删除、查找实现程序、代价、时间复杂性分析、和动态链表相比的优缺点。时间复杂性分析、和动态链表相比的优缺点。双向链表的基本操作：插入和删除、查找实现的代价、优双向链表的基本操作：插入和删除、查找实现的代价、优 缺点等。缺点等。2复习要点复习要点 栈和队列栈和队列 堆栈的表示和实现：堆栈的性质。堆栈的表示和实现：堆栈的性质。顺序表示：插入和删除实现程序顺序表示：插入和删除实现

3、程序链接表示：插入和删除实现程序链接表示：插入和删除实现程序 队列的表示和实现：队列的性质。队列的表示和实现：队列的性质。链接表示：进出队的基本操作及其实现链接表示：进出队的基本操作及其实现循环队列：进出队的操作及实现、队列元素的计数。操作循环队列：进出队的操作及实现、队列元素的计数。操作 时的注意点，翻转技术的使用。时的注意点，翻转技术的使用。3复习要点复习要点树和二叉树树和二叉树 1、树、森林的定义：树：非空。高度。森林。、树、森林的定义：树：非空。高度。森林。2、二叉树：定义、基本性质、顺序表示、链接表示。、二叉树：定义、基本性质、顺序表示、链接表示。3、遍历二叉树、遍历二叉树 前序、中

4、序、后序的定义和程序实现。前序、中序、后序的定义和程序实现。4、堆、堆定义、实现、最大化堆和最小化堆。定义、实现、最大化堆和最小化堆。堆的插入、删除前序、建堆。堆的插入、删除前序、建堆。建堆和插入删除的代价。建堆和插入删除的代价。4复习要点复习要点 5、树和森林、树和森林 树的存储结构、树和森林同二叉树的转换。树的存储结构、树和森林同二叉树的转换。树的前序、后序遍历。森林的前序、中序遍历。树的前序、后序遍历。森林的前序、中序遍历。树和森林的遍历和相应的二叉树之间的关系。树和森林的遍历和相应的二叉树之间的关系。6、赫夫曼树及其与树的应用、赫夫曼树及其与树的应用 最优二叉树定义、赫夫曼树的构造算法

5、及实现最优二叉树定义、赫夫曼树的构造算法及实现 赫夫曼编码赫夫曼编码 8、树的计数、树的计数前序前序(或后序或后序)中序如何确定一棵二叉树中序如何确定一棵二叉树二叉树和树的计数的推导二叉树和树的计数的推导5复习要点复习要点 图图 图的各种存储形式及适用范围：图的各种存储形式及适用范围：图的各种算法的执行过程及时空复杂性图的各种算法的执行过程及时空复杂性深度、广度优先的定义和实现算法深度、广度优先的定义和实现算法 最小生成树算法、判定。生成最小生成树算法、判定。生成 树。树。Prim 算法和算法和 Kruscal 算法实现。算法实现。AOV 网络的拓扑排序网络的拓扑排序定义、和定义、和有关算法。

6、有关算法。最短路径算法：最短路径算法：Dijktra算法和算法和 Floyd 算法。算法。6复习要点复习要点 集合与搜索集合与搜索 静态搜索结构：静态搜索结构：顺序搜索：成功查找的平均查找长度的分析顺序搜索：成功查找的平均查找长度的分析 平均查找长度（包括成功、非成功）平均查找长度（包括成功、非成功）算法的实现、程序等算法的实现、程序等有序顺序表的搜索：有序顺序表的搜索：折半查找：成功与不成功时的查找长度分析、折半查找：成功与不成功时的查找长度分析、实现、程序等实现、程序等7复习要点复习要点集合与搜索集合与搜索 动态搜索结构动态搜索结构 二叉排序树：定义，生成，结点的数据结构，如何生成二二叉排

7、序树：定义，生成，结点的数据结构，如何生成二叉排序树，实现程序。叉排序树，实现程序。查找的平均查找长度。查找的平均查找长度。插入和删除算法的分析和实现。插入和删除算法的分析和实现。平衡二叉树：定义、平衡因子、插入的实现过程、左改组平衡二叉树：定义、平衡因子、插入的实现过程、左改组和右改组。查找分析。和右改组。查找分析。8复习要点复习要点内部排序：内部排序：排序：定义、稳定与不稳定排序：定义、稳定与不稳定 直接插入排序：实现、时间复杂性。直接插入排序：实现、时间复杂性。快速排序：实现、时空复杂性分析和推导。改进。快速排序：实现、时空复杂性分析和推导。改进。堆排序和选择排序实现。堆的定义。建堆算法

8、和实现。时堆排序和选择排序实现。堆的定义。建堆算法和实现。时 空复杂性级别。空复杂性级别。基数排序：实现时空分析基数排序：实现时空分析 各种排序法的比较和最佳排序速度的分析、判定树各种排序法的比较和最佳排序速度的分析、判定树9复习要点复习要点考试注意事项考试注意事项 程序编写程序编写 2 道、需按时空复杂性要求等进行编写。道、需按时空复杂性要求等进行编写。填空。证明算法的时间复杂性级别、出现的和式不必化简填空。证明算法的时间复杂性级别、出现的和式不必化简。构造构造 数据结构、树形等。判断结构的好坏。按要求给出相应的结果。数据结构、树形等。判断结构的好坏。按要求给出相应的结果。答疑：时间：待定答疑：时间：待定 地点：待定地点：待定10