图结构和查找习题复习章ppt课件.ppt

例题1对于给定的关键序列 若哈希函数无冲突 则称其为完备 perfect 的 设哈希表长度为7 试为 Bret Jane Michelle Heatther 设计一个完备的哈希函数H 提示 考虑每个字串的第3个字符 并写出其C代码 设计哈希函数H如下 H key key 第3个字母的ASCII码MOD7 则 H Bert 101MOD7 3H Jane 110MOD7 5H Shirley 105MOD7H Bryce 121MOD7 2H Michelle 99MOD7 1H Heather 97MOD7 6 1 例题2 试述顺序查找法 二分查找法和分块查找法对被查找的表中元素的要求 对长度为n的表来说 3种查找法在查找成功时的平均查找长度各是多少 解 3种方法对查找的要求分别如下 1 顺序查找法 表中元素可以任意次序存入 2 二分查找法 表中元素必须以关键字的大小递增或递减的次序有序列且顺序表存储 3 分块查找法 表中元素块内的元素可以任意次序存放 但块与块之间必须以关键字的大小递增 或递减 存放 即前一块内所有元素的关键字都不能大 或小 于后一块内任何元素的关键字 2 3种方法平均查找长度分别如下 顺序查找法 查找成功的平均查找长度为n 1 2 二分查找法 查找成功的平均长度为log2 n 1 1 分块查找法 若用顺序查找确定所在的块 平均查找长度为 1 2 n 1 s 1 若用二分查找确定所在块 平均查找长度为log2 n s 1 s 2 其中 s为每块含有的元素的个数 例题3 设有一组关键字 19 1 23 14 55 20 84 27 68 11 10 77 采用哈希函数 H key key 13采用开放定址法的二次探测再哈希方法解决冲突 试在0 18的哈希地址空间中对该关键字序列构造哈希表 3 解 依题意 m 19 二次探测再哈希的下一地址计算公式为 d1 H key d2j d1 j j m d2j 1 d1 j j m j 1 2 其计算函数如下 H 19 19 13 6H 1 1 13 1H 23 23 13 10H 14 14 13 1 发生冲突 H 14 1 1 1 19 2H 55 55 13 3H 20 20 13 7H 84 84 13 6 发生冲突 H 84 6 1 1 19 7 仍发生冲突 4 H 84 6 1 1 19 5H 27 27 13 1 发生冲突 H 27 1 1 1 19 2 发生冲突 H 27 1 1 19 0H 68 68 13 3 发生冲突 H 68 3 1 1 19 4H 11 11 13 11H 10 10 13 10 发生冲突 H 10 10 1 1 19 11 仍发生冲突 H 10 10 1 1 19 9H 77 11 13 12因此 各关键字的记录对应的地址分配如下 addr 27 0addr 1 1 5 addr 14 2addr 55 3addr 68 4addr 84 5addr 19 6addr 20 7addr 10 9addr 23 10addr 11 11addr 77 12其他地址为空 6 例已知一组关键字 19 14 23 1 68 20 84 27 55 11 10 79 哈希函数为 H key keyMOD13 哈希表长为m 16 设每个记录的查找概率相等 1 用线性探测再散列处理冲突 即Hi H key di MODm H 55 3冲突 H1 3 1 MOD16 4冲突 H2 3 2 MOD16 5 H 79 1冲突 H1 1 1 MOD16 2冲突 H2 1 2 MOD16 3冲突 H3 1 3 MOD16 4冲突 H4 1 4 MOD16 5冲突 H5 1 5 MOD16 6冲突 H6 1 6 MOD16 7冲突 H7 1 7 MOD16 8冲突 H8 1 8 MOD16 9 ASL 1 6 2 3 3 4 9 12 2 5 14 1 68 27 55 19 20 84 79 23 11 10 H 19 6 H 14 1 H 23 10 H 1 1冲突 H1 1 1 MOD16 2 H 68 3 H 20 7 H 84 6冲突 H1 6 1 MOD16 7冲突 H2 6 2 MOD16 8 H 27 1冲突 H1 1 1 MOD16 2冲突 H2 1 2 MOD16 3冲突 H3 1 3 MOD16 4 H 11 11 H 10 10冲突 H1 10 1 MOD16 11冲突 H2 10 2 MOD16 12 7 2 用链地址法处理冲突 ASL 1 6 2 4 3 4 12 1 75 关键字 19 14 23 1 68 20 84 27 55 11 10 79 8 例5 在下例中 画出折半查找21的过程示意图 在画出有序序列的查找判定树 计算查找成功的ASL 自己做 9 ASL 1X1 2X2 4X3 4X4 11 10 例7 折半查找举例 11 由于low high 则查找表中不存在要查找的记录 查找失败 返回查找失败信息结束查找 12 例题8试给出一棵树的关键字序列 使AVL树的4种调整平衡操作 LL LR RR RL 各至少执行一次 并画出其构造过程 解 设关键字的输入序列为 4 5 7 2 1 3 6 则AVL树的构造过程如下图所示 13 输入结点插入后调整平衡后4无需调整 4 4 5 4 5 7 5 4 7 2 5 4 7 5 4 7 2 1 5 2 7 4 1 3 4 2 5 3 6 7 1 5 2 7 1 4 4 1 7 5 3 6 2 4 1 3 7 2 5 RR型 无需调整 无需调整 LL型 LR型 RL型 5 7 2 1 6 3 图8 5AVL树构造过程 14 例题9给定序列 3 5 7 9 11 13 15 17 按表中元素的顺序依次插入一棵初始为空的二叉排序树 画出插入完成后的二叉排序树 并求在等概率情况下查找成功的平均查找长度 按表中元素顺序构造一棵二叉平衡树 并求其在等概率情况下查找成功的平均查找长度 与 比较 可得出什么结论 解 按输入顺序进行插入后的二充满排序树如下左图所示 其在等概率下查找成功的平均查找长度为 ASL成功 1 2 2 3 4 5 6 7 8 8 9 2 构造一棵平衡二叉树如下右图所示 其在等概率下查找成功的平均查找长度为 ASL成功 1 8 1 2 2 3 4 5 11 4 与 相比 可见在同样序列的查找中 二叉平衡排序树比二叉排序树的平均查找长度要小且查找效率高 15 3 5 7 9 11 13 15 17 9 5 3 13 15 17 11 7 图8 6二叉排序树 图8 7二叉平衡树 16 例题10 线性表关键字集合 87 25 310 08 27 132 68 95 187 123 70 63 47 共有13个元素 已知哈希函数为 H k k 13采用链地址法处理冲突 设计出这种链表结构 并计算该表的成功查找的平均长度 练习题 解 依题意知 H 87 87 13 9H 25 25 13 12H 310 310 13 11H 08 08 13 8H 27 27 13 1H 132 132 13 2H 68 68 13 3 17 H 95 95 13 4H 187 187 13 5H 123 123 13 6H 70 70 13 5H 63 63 13 11H 47 47 13 8采用拉链法处理冲突的链表 学生做 成功查找的平均查找长度 ASL 18 例题11对如图7 8 a 和 b 所示的图 试画出其深度优先生成树和广度优先生成树 a b 图7 8两棵树图 19 解 由连通图的定义知 这两个图都是连通图 连通图深度优先搜索的方法是 假定图中某个顶点v1为出发点 搜索方法是 首先访问出发点 然后任选未访问过的邻接点 再以该邻接点为新的出发点继续进行深度优先搜索 直至所有顶点都被访问过 连通图广度优先搜索的方法是 从图中某个顶点vi出发 在访问了vi之后依次访问vi的所有邻接点 然后分别从这些邻接点出发按广度优先搜索遍历图的其他顶点 重复这一过程 直至所有顶点都被访问到 由此得到如图7 9和图7 10所示的相应的深度优先生成树和广度优先生成树 20 a 顶点v1遍历的深度优先生成树 b 顶点v1遍历的深度优先生成树图7 9 a 顶点v1遍历的广度优先生成树 b 顶点v1遍历的广度优先生成树图7 10 21 例题12对如图7 14所示的有向图 试给出 邻接矩阵 邻接表 逆邻接表 强连通分量 从 出发的深度优先遍历序列 从 出发的广度优先遍历序列 图7 14有向图 解 邻接矩阵如下 22 邻接表如图7 15所示 图7 15邻接表 23 首先改变图7 14中有向边的方向得到如图7 16所示的有向图 然后根据图7 16画出邻接表 即图7 14的逆邻接表 如图7 17所示 图7 16有向图 24 图7 17图7 14的逆邻接表 25 在有向图G中 如果对于每一对 vi vj V 顶点集 且vi vj 从vi到vi和从vi的vi都存在路径 则称G是强连通图 有向图中的极大强连通子图称作有向图的强连通分量 由此得图7 14的强连通分量如图7 18所示 图7 18图7 14的强连通分量 从 出发的深度优先遍历序列为 从 出发的广度优先遍历序列为 1 4 5 6 2 3 26 例题13有一带权无向图的顶点集合为 v1 v2 v3 v4 v5 v6 v7 v8 已知其邻接矩阵的三元组表如图7 19所示 画出该无向图的邻接表 画出所有可能的最小生成树 根据你给的邻接表分别写出从v1出发进行深度优先遍历和广度优先遍历的顶点序列 写出从v1到v2的最短路径 解 首先根据邻接矩阵的三元组表画出带权无向图 如图7 20所示 图7 20的邻接表如图7 21所示 27 图7 20带权无向图 7 19三元组表 12 10 28 图7 21邻接表 29 由于存在权值相同的边 则最小生成树可能不止一个 此题可能的最小生成树如图7 22所示 a b 图7 22可能的最小生成树 30 根据图7 21邻接表得到的深度优先遍历序列为 v1 v5 v4 v7 v6 v3 v2 v8 广度优先遍历序列为 v1 v5 v2 v4 v3 v8 v6 v7 从v1到v2的最短路径为v1 v5 v3 v6 v2 例题20试列出图7 23中全部可能的拓扑排序序列 图7 23有向图 解 拓扑排序算法的步骤为 在有向图中选择一个没有前驱的顶点 入度为0 且输出之 在有向图中删除该顶点和所有以该顶点为尾的弧 31 重复 和 直至图中没有前驱的顶点 不存在有弧相连的顶点 时为止 由此得到图7 23全部可能的拓扑排序序列如下 152364152634156234561234516234512634512364 32 例题23设G为有n个顶点的无向连通图 证明所有具有n 1条边并有n个顶点的无向连通图是树图 证明 必要性 由于具有n个