《【专业课】数据结构及算法的复习ppt模版课件》由会员分享，可在线阅读，更多相关《【专业课】数据结构及算法的复习ppt模版课件（8页珍藏版）》请在金锄头文库上搜索。
1、1,复习要点,图 图的各种存储形式及适用范围： 图的各种算法的执行过程及时空复杂性 深度、广度优先的算法 最短路径算法 AOE、AOV 网络的有关算法 最短路径算法 最小生成树算法,2,复习要点,查找 静态查找表： 顺序表：成功查找的平均查找长度的分析 平均查找长度（包括成功、非成功） 算法的实现、程序等 有序表： 折半查找：成功与不成功时的查找长度分析、 实现、程序等 插值查找及其实现 索引顺序查找：查找长度分析、实现等,3,复习要点,查找 动态查找表 二叉排序树：定义，生成，结点的数据结构，如何生成二 叉排序树，实现程序。 查找的平均查找长度。 插入和删除算法的分析和实现。 平衡二叉树：定
2、义、平衡因子、插入的实现过程、左改组 和右改组。查找分析。 B 树和B树：定义、插入和删除的实现过程。B树的最大 深度。B 树和B树的异同。,4,复习要点,查找 动态查找表 哈希表：定义，冲突，哈希函数，冲突及其解决办法，装 填因子。随机探测情况下的成功于非成功查找分析。 内部排序： 排序：定义、稳定与不稳定 直接插入排序：实现、时间复杂性。折半插入排序及实现。 SHELL排序：实现、增量序列的选定。 快速排序：实现、时空复杂性分析和推导。改进。 堆排序和选择排序：实现。堆的定义。建堆算法和实现。时 空复杂性分析。,5,复习要点,内部排序： 归并排序：实现 基数排序：实现时空分析 各种排序法的
3、比较和最佳排序速度的分析、判定树。 外部排序： 外存信息的组织、读取。 多路平衡归并法的实现方法，胜者树及败者树的实现。 置换选择排序法的实现。初始归并段的生成。如何生成尽可能长的初始归并段。 最佳归并树。,6,复习要点,文件： 索引顺序文件同顺序文件相比特点，适合的外存。 ISAM 和 VSAM 文件的组织方法特特点、插入、删除的基本 操作等。 B树如何用于组织文件。控制区间和控制区域。 集合 最优二叉查找树算法的实现，时间复杂性。 不相交集的合并算法实现。UNION-FIND 问题的树结构及其 实现。 23树的特性，如何实现插入及删除算法。,7,复习要点,集合 最优二叉查找树算法的实现，时
4、间复杂性。 不相交集的合并算法实现。UNION-FIND 问题的树结构及其 实现。 23树的特性，如何实现插入及删除算法。 字典和优先队列，实现算法。 可并堆，实现算法。 可连接队列，实现算法。 始终四种基本结构允许适用的指令，时间考虑。,8,复习要点,无向图的双连通性： 关节点、双连通成分、各引理的证明。LOW值的定义，关节点 的求法。程序的实现。,考试注意事项,程序编写、需按要求。时空复杂性等。 填空。证明引理。构造数据结构、树形图形等。按要求给出相应 的结果。执行算法的结果。问答题等。 答疑：时间：6月26日 9：00 至 16：30 6月27日 10：00 至 11：30 地点：下院，教师休息室,
