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

1、图结构和查找习题复习章,1,例题1 对于给定的关键序列，若哈希函数无冲突，则称其为完备(perfect)的。设哈希表长度为7，试为Bret，Jane，Michelle，Heatther设计一个完备的哈希函数H（提示：考虑每个字串的第3个字符），并写出其C代码。 设计哈希函数H如下： H（key）=key（第3个字母的ASCII码MOD 7），则： H（Bert）=101 MOD 7=3 H（Jane）=110 MOD 7=5 H（Shirley）=105 MOD 7 H（Bryce）=121 MOD 7=2 H（Michelle）=99 MOD 7=1 H（Heather）=97 MOD 7=

2、6,图结构和查找习题复习章,2,例题2：试述顺序查找法、二分查找法和分块查找法对被查找的表中元素的要求。对长度为n的表来说，3种查找法在查找成功时的平均查找长度各是多少？ 解：3种方法对查找的要求分别如下： 1）顺序查找法：表中元素可以任意次序存入。 2）二分查找法：表中元素必须以关键字的大小递增或递减的次序有序列且顺序表存储。 3）分块查找法：表中元素块内的元素可以任意次序存放，但块与块之间必须以关键字的大小递增（或递减）存放，即前一块内所有元素的关键字都不能大（或小）于后一块内任何元素的关键字。,图结构和查找习题复习章,3,3种方法平均查找长度分别如下： 顺序查找法：查找成功的平均查找长度

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采用开放定址法的二次探测再哈希方法解决冲突，试在018的哈希地址空间中对该关键字序列构造哈希表。,图结构和查找习题复习章,4,【解】 依题意，m=19，二次探测再哈希的下一地址计算公式为： d1=H（key）；

4、d2j=（d1+j*j）%m；d2j+1（d1-j*j）%m；j=1，2， 其计算函数如下： H（19）=19%13=6 H（1）=1%13=1 H（23）=23%13=10 H（14）=14%13=1（发生冲突） H（14）=（1+1*1）%19=2 H（55）=55%13=3 H（20）=20%13=7 H（84）=84%13=6（发生冲突） H（84）=（6+1*1）%19=7（仍发生冲突）,图结构和查找习题复习章,5,H（84）=（6-1*1）%19=5 H（27）=27%13=1（发生冲突） H（27）=（1+1*1）%19=2（发生冲突） H（27）=（1-1）%19=0 H（68

5、）=68%13=3（发生冲突） H（68）=（3+1*1）%19=4 H（11）=11%13=11 H（10）=10%13=10（发生冲突） H（10）=（10+1*1）%19=11（仍发生冲突） H（10）=（10-1*1）%19=9 H（77）=11%13=12 因此，各关键字的记录对应的地址分配如下： addr（27）=0 addr（1）=1,图结构和查找习题复习章,6,addr（14）=2 addr（55）=3 addr（68）=4 addr（84）=5 addr（19）=6 addr（20）=7 addr（10）=9 addr（23）=10 addr（11）=11 addr（77）=

6、12 其他地址为空。,图结构和查找习题复习章,7,例 已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79) 哈希函数为：H(key)=key MOD 13, 哈希表长为m=16， 设每个记录的查找概率相等,(1) 用线性探测再散列处理冲突，即Hi=(H(key)+di) MOD m,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)

7、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)MO

8、D16=4,H(11)=11,H(10)=10 冲突，H1=(10+1)MOD16=11 冲突，H2=(10+2)MOD16=12,图结构和查找习题复习章,8,(2) 用链地址法处理冲突,ASL=(1*6+2*4+3+4)/12=1.75,关键字(19,14,23,1,68,20,84,27,55,11,10,79),图结构和查找习题复习章,9,例5：在下例中，画出折半查找21的过程示意图。在画出有序序列的查找判定树，计算查找成功的ASL（自己做）。,图结构和查找习题复习章,10,ASL=（1X1+2X2+4X3+4X4）/11=,图结构和查找习题复习章,11,例7：折半查找举例,图结构和查找

9、习题复习章,12,由于lowhigh，则查找表中不存在要查找的记录，查找失败，返回查找失败信息结束查找。,图结构和查找习题复习章,13,例题8 试给出一棵树的关键字序列，使AVL树的4种调整平衡操作（LL，LR，RR，RL）各至少执行一次，并画出其构造过程。 【解】 设关键字的输入序列为：4、5、7、2、1、3、6，则AVL树的构造过程如下图所示。,图结构和查找习题复习章,14,输入结点 插入后 调整平衡后 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

10、,1,3,7,2,5,RR型,无需调整,无需调整,LL型,LR型,RL型,5,7,2,1,6,3,图8.5 AVL树构造过程,图结构和查找习题复习章,15,例题9 给定序列3，5，7，9，11，13，15，17： 按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成后的二叉排序树，并求在等概率情况下查找成功的平均查找长度。 按表中元素顺序构造一棵二叉平衡树，并求其在等概率情况下查找成功的平均查找长度，与比较，可得出什么结论？ 【解】 按输入顺序进行插入后的二充满排序树如下左图所示，其在等概率下查找成功的平均查找长度为：ASL成功=（1+2+2+3+4+5+6+7+8）/8=9/2。

11、构造一棵平衡二叉树如下右图所示，其在等概率下查找成功的平均查找长度为：ASL成功=1/8（1+2*2+3*4+5）=11/4。 与相比，可见在同样序列的查找中，二叉平衡排序树比二叉排序树的平均查找长度要小且查找效率高。,图结构和查找习题复习章,16,3,5,7,9,11,13,15,17,9,5,3,13,15,17,11,7,图8.6 二叉排序树,图8.7 二叉平衡树,图结构和查找习题复习章,17,例题10：线性表关键字集合87，25，310，08，27，132，68，95，187，123，70，63，47，共有13个元素，已知哈希函数为：H（k）=k%13 采用链地址法处理冲突。设计出这种

12、链表结构，并计算该表的成功查找的平均长度。（练习题） 【解】 依题意知： H（87）=87%13=9 H（25）=25%13=12 H（310）=310%13=11 H（08）=08%13=8 H（27）=27%13=1 H（132）=132%13=2 H（68）=68%13=3,图结构和查找习题复习章,18,H（95）=95%13=4 H（187）=187%13=5 H（123）=123%13=6 H（70）=70%13=5 H（63）=63%13=11 H（47）=47%13=8 采用拉链法处理冲突的链表（学生做）。成功查找的平均查找长度： ASL=,图结构和查找习题复习章,19,例题11

13、 对如图7.8(a)和(b)所示的图，试画出其深度优先生成树和广度优先生成树。 (a) (b) 图7.8 两棵树图,图结构和查找习题复习章,20,【解】 由连通图的定义知：这两个图都是连通图。 连通图深度优先搜索的方法是： 假定图中某个顶点v1为出发点。搜索方法是：首先访问出发点，然后任选未访问过的邻接点，再以该邻接点为新的出发点继续进行深度优先搜索，直至所有顶点都被访问过。连通图广度优先搜索的方法是： 从图中某个顶点vi出发，在访问了vi 之后依次访问vi的所有邻接点，然后分别从这些邻接点出发按广度优先搜索遍历图的其他顶点。重复这一过程，直至所有顶点都被访问到。 由此得到如图7.9和图7.1

14、0所示的相应的深度优先生成树和广度优先生成树。,图结构和查找习题复习章,21,(a)顶点v1遍历的深度优先生成树 (b)顶点v1遍历的深度优先生成树 图7.9,(a)顶点v1遍历的广度优先生成树 (b)顶点v1遍历的广度优先生成树 图7.10,图结构和查找习题复习章,22,例题12 对如图7.14所示的有向图,试给出： 邻接矩阵 邻接表 逆邻接表 强连通分量 从出发的深度优先遍历序列 从出发的广度优先遍历序列。,图7.14 有向图,【解】 邻接矩阵如下：,图结构和查找习题复习章,23,邻接表如图7.15所示。,图7.15 邻接表,图结构和查找习题复习章,24,首先改变图7.14中有向边的方向得

15、到如图7.16所示的有向图，然后根据图7.16画出邻接表(即图7.14的逆邻接表)，如图7.17所示.,图7.16 有向图,图结构和查找习题复习章,25,图7.17 图7.14的逆邻接表,图结构和查找习题复习章,26,在有向图G中,如果对于每一对vi,vjV(顶点集),且vivj ，从vi 到vi 和从vi 的vi 都存在路径，则称G是强连通图。有向图中的极大强连通子图称作有向图的强连通分量。由此得图7.14的强连通分量如图7.18所示。 图7.18 图7.14的强连通分量 从出发的深度优先遍历序列为:。 从出发的广度优先遍历序列为:。,1,4,5,6,2,3,图结构和查找习题复习章,27,例

16、题13 有一带权无向图的顶点集合为v1，v2，v3，v4，v5，v6，v7，v8，已知其邻接矩阵的三元组表如图7.19所示。 画出该无向图的邻接表。 画出所有可能的最小生成树。 根据你给的邻接表分别写出从v1出发进行深度优先遍历和广度优先遍历的顶点序列。 写出从v1到v2的最短路径。 【解】 首先根据邻接矩阵的三元组表画出带权无向图，如图7.20所示 。 图7.20的邻接表如图7.21所示。,图结构和查找习题复习章,28,图7.20 带权无向图,7.19 三元组表,12,10,图结构和查找习题复习章,29,图7.21 邻接表,图结构和查找习题复习章,30,由于存在权值相同的边,则最小生成树可能

17、不止一个,此题可能的最小生成树如图7.22所示. （a） （b） 图7.22 可能的最小生成树,图结构和查找习题复习章,31,根据图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)且输出之; 在有向图中删除该顶点和所有以该顶点为尾的弧;,图结构和查找习题复习章,32,重复和,直至图中没有前驱的顶点(不存在有弧相连的顶点)时为止。 由此得到图7.23全部可能的拓扑排序序列如下: 1 5 2 3 6 4 1 5 2 6 3 4 1 5 6 2 3 4 5 6 1 2 3 4 5 1 6 2 3 4 5 1 2 6 3 4 5 1 2 3 6 4,图结构和查找习题复习章,33,例题23 设G为有n个顶点的无向连通图,证明所有具有n-1条边并有n个顶点的无向连通图是树图。 【证