图结构和查找习题复习市公开课一等奖省赛课微课金奖课件.pptx

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,例题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=6,第1页,例题2：试述次序查找法、二分查找法和分块查找法对被查找表中元素要求。对长度为n表来说，3种查找法在查找成功时平均查找长度各是多少？,解：3种方法对查找要求分别以下：,1）次序查找法：表中元素能够任意次序存入。,2）二分查找法：表中元素必须以关键字大小递增或递减次序有序列且次序表存放。,3）分块查找法：表中元素块内元素能够任意次序存放，但块与块之间必须以关键字大小递增（或递减）存放，即前一块内全部元素关键字都不能大（或小）于后一块内任何元素关键字。,第2页,3种方法平均查找长度分别以下：,次序查找法：查找成功平均查找长度为n+1/2。,二分查找法：查找成功平均长度为log,2,（n+1）-1。,分块查找法：若用次序查找确定所在块，平均查找长度为：1/2（n/1+s）+1；若用二分查找确定所在块，平均查找长度为log,2,（n/s+1）+s/2。其中，s为每块含有元素个数。,例题3：设有一组关键字19，1，23，14，55，20，84，27，68，11，10，77采取哈希函数：H（key）=key%13采取开放定址法二次探测再哈希方法处理冲突，试在018哈希地址空间中对该关键字序列结构哈希表。,第3页,【解】,依题意，m=19，二次探测再哈希下一地址计算公式为：,d,1,=H（key）；d,2j,=（d,1,+j*j）%m；d,2j+1,（d,1,-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（仍发生冲突）,第4页,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）=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,第5页,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）=12,其它地址为空。,第6页,例 已知一组关键字(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)MOD16=6,冲突，H6=(1+6)MOD16=7,冲突，H7=(1+7)MOD16=8,冲突，H8=(1+8)MOD16=9,0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15,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)用链地址法处理冲突,0 1 2 3 4 5 6 7 8 9 10 11 12,14,1,27,79,68,55,19,84,20,23,10,11,ASL=(,1,*6+,2,*,4,+,3,+,4,)/,12,=1.75,关键字(19,14,23,1,68,20,84,27,55,11,10,79),第8页,low,high,mid,1 2 3 4 5 6 7 8 9 10 11,5 13 19 21 37 56 64 75 80 88 92,找21,1 2 3 4 5 6 7 8 9 10 11,5 13 19 21 37 56 64 75 80 88 92,low,high,mid,1 2 3 4 5 6 7 8 9 10 11,5 13 19 21 37 56 64 75 80 88 92,low,high,mid,例5：在下例中，画出折半查找21过程示意图。在画出有序序列查找判定树，计算查找成功ASL（自己做）。,第9页,92,75,37,13,88,64,21,5,80,19,56,判定树：,1 2 3 4 5 6 7 8 9 10 11,5 13 19 21 37 56 64 75 80 88 92,ASL=（1X1+2X2+4X3+4X4）/11=,第10页,1 2 3 4 5 6 7 8 9 10 11,5 13 19 21 37 56 64 75 80 88 92,low,high,mid,找70,1 2 3 4 5 6 7 8 9 10 11,5 13 19 21 37 56 64 75 80 88 92,low,high,mid,1 2 3 4 5 6 7 8 9 10 11,5 13 19 21 37 56 64 75 80 88 92,low,high,mid,1 2 3 4 5 6 7 8 9 10 11,5 13 19 21 37 56 64 75 80 88 92,low,high,mid,例7：折半查找举例,第11页,1 2 3 4 5 6 7 8 9 10 11,5 13 19 21 37 56 64 75 80 88 92,low,high,因为lowhigh，则查找表中不存在要查找统计，查找失败，返回查找失败信息结束查找。,第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.5 AVL树结构过程,第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=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,第17页,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=,第18页,例题11,对如图7.8(a)和(b)所表示图，试画出其深度优先生成树和广度优先生成树。,(a)(b),图7.8 两棵树图,v1,v2,v8,v4,v5,v6,v3,v8,v1,v6,v2,v5,v4,v3,v7,v1,第19页,【解】,由连通图定义知：这两个图都是连通图。,连通图深度优先搜索方法是：,假定图中某个顶点v,1,为出发点。搜索方法是：首先访问出发点，然后任选未访问过邻接点，再以该邻接点为新出发点继续进行深度优先搜索，直至全部顶点都被访问过。连通图广度优先搜索方法是：,从图中某个顶点v,i,出发，在访问了v,i,之后依次访问v,i,全部邻接点，然后分别从这些邻接点出发按广度优先搜索遍历图其它顶点。重复这一过程，直至全部顶点都被访问到。,由此得到如图7.9和图7.10所表示对应深度优先生成树和广度优先生成树。,第20页,v1,v2,v4,v5,v8,v6,v3,v7,v1,v2,v6,v5,v3,v4,v7,(a)顶点v,1,遍历深度优先生成树 (b)顶点v,1,遍历深度优先生成树,图7.9,v1,v2,v4,v5,v3,v8,v7,v6,v7,v4,v3,v5,v2,v1,v6,(a)顶点v1遍历广度优先生成树 (b)顶点v1遍历广度优先生成树,图7.10,第21页,例题12,对如图7.14所表示有向图,试给出：,邻接矩阵 邻接表 逆邻接表 强连通分量 从出发深度优先遍历序列 从出发广度优先遍历序列。,6,5,3,2,4,1,图7.14 有向图,【解】,邻接矩阵以下：,第22页,1,2,3,4,5,6,4,4,6,5,2,5,3,2,1,4,1,邻接表如图7.15所表示。,图7.15 邻接表,第23页,首先改变图7.14中有向边方向得到如图7.16所表示有向图，然后依据图7.16画出邻接表(即图7.14逆邻接表)，如图7.17所表示.,6,5,3,2,4,1,图7.16 有向图,第24页,1,2,3,4,5,6,2,5,6,3,6,5,3,3,2,5,1,图7.17 图7.14逆邻接表,第25页,在有向图G中,假如对于每一对v,i,v,j,V(顶点集),且v,i,v,j,，从v,i,到v,i,和从v,i,v,i,都存在路径，则称G是强连通图。有向图中极大强连通子图称作有向图强连通分量。由此得图7.14强连通分量如图7.18所表示。,图7.18 图7.14强连通分量,从出发深度优先遍历序列为:。,从出发广度优先遍历序列为:。,1,4,5,6,2,3,第26页,例题13,有一带权无向图顶点集合为v,1,，v,2,，v,3,，v,4,，v,5,，v,6,，v,7,，v,8,，已知其邻接矩阵三元组表如图7.19所表示。,画出该无向图邻接表。,画出全部可能最小生成树。,依据你给邻接表分别写出从v,1,出发进行深度优先遍历和广度优先遍历顶点序列。,写出从v,1,到v,2,最短路径。,【解】,首先依据邻接矩阵三元组表画出带权无向图，如图7.20所表示。,图7.20邻接表如图7.21所表示。,第27页,图7.20 带权无向图,8,8,20,1,2,12,1,5,2,2,1,12,2,6,3,2,8,5,3,4,8,3,5,2,3,6,4,4,3,8,4,5,10,4,7,8,5,1,2,5,3,2,5,4,10,6,2,3,6,3,4,6,7,7,7,4,8,7,6,7,8,2,5,7.19 三元组表,v1,v5,v3,v6,v2,v8,v4,v7,2,2,8,4,7,3,5,12,10,第28页,图7.21 邻接表,0,1,2,3,4,5,6,7,4,5,2,1,5,6,3,6,1,1,5,4,2,2,4,1,7,0,3,0,第29页,因为存在权值相同边,则最小生成树可能不止一个,此题可能最小生成树如图7.22所表示.,（a）（b）,图7.22 可能最小生成树,v1,v5,v3,v6,v2,v8,v4,v7,2,2,8,4,7,3,5,v1,v5,v3,v4,v7,v2,v6,v8,2,2,8,4,7,3,5,第30页,依据图7.21邻接表得到深度优先遍历序列为:v,1,v,5,v,4,v,7,v,6,v,3,v,2,v,8,;广度优先遍历序列为:v,1,v,5,v,2,v,4,v,3,v,8,v,6,v,7,。,从v,1,到v,2,最短路径为v,1,v,5,v,3,v,6,v,2,。,例题20,试列出图7.23中全部可能拓扑排序序列。,图7.23 有向图,【解】,拓扑排序算法步骤为:,在有向图中选择一个没有前驱顶点(入度为0)且输出之;,在有向图中删除该顶点和全部以该顶点为尾弧;,v1,v2,v6,v5,v4,v3,第31页,重复和,直至图中没有前驱顶点(不存在有弧相连顶点)时为止。,由此得到图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,第32页,例题23,设G为有n个顶点无向连通图,证实全部含有n-1条边并有n个顶点无向连通图是树图。,【证实】,必要性：因为含有n个顶点无向连通图最少有n-1条边，因为此处无向连通图为树图，所以它只有n-1条边，假如多于n-1条边就会形成环，少于n-1条边则不连通。,充分性：若G是连通图且只有n-1条边，则G必为树图。设G是连通但不是树图，则G中必定存在回路，所以我们能够从回路中去掉一条边且仍使得G是连通；这时，G则成为n个顶点但只有n-2条边连通图，这显然是错误，故G一定是树图。,证毕。,第33页,V1,V2,V3,V4,V5,V6,V7,V8,V9,顶点 Ve Vl,0,6,4,5,7,7,16,14,18,0,6,6,8,7,10,16,14,18,v9,v8,v7,v6,v4,v5,v3,v2,v1,a2=4,a3=5,a5=1,a6=2,a9=4,a1=6,a4=1,a7=9,a8=7,a10=2,a11=4,a1,a2,a3,a4,a5,a6,a7,a8,a9,a10,a11,活动 e l l-e,*,*,*,*,*,*,0,0,0,0,2,2,6,6,0,4,6,2,5,8,3,7,7,0,7,7,0,7,10,3,16,16,0,14,14,0,0,3,3,例14：关键路径计算,第34页,