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

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

2、法对被查找表中元素要求。对长度为n表来说，3种查找法在查找成功时平均查找长度各是多少？解：3种方法对查找要求分别以下：1）次序查找法：表中元素能够任意次序存入。2）二分查找法：表中元素必须以关键字大小递增或递减次序有序列且次序表存放。3）分块查找法：表中元素块内元素能够任意次序存放，但块与块之间必须以关键字大小递增（或递减）存放，即前一块内全部元素关键字都不能大（或小）于后一块内任何元素关键字。第2页3种方法平均查找长度分别以下：次序查找法：查找成功平均查找长度为n+1/2。二分查找法：查找成功平均长度为log2（n+1）-1。分块查找法：若用次序查找确定所在块，平均查找长度为：1/2（n/1

3、+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哈希地址空间中对该关键字序列结构哈希表。第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

4、%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

5、）=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)=key MOD 13, 哈希表长为m=16， 设每个统计查找概率相等(1) 用线性探测再散列处理冲突，即Hi=(H(key)+di) MOD mH(55)=

6、3 冲突，H1=(3+1)MOD16=4 冲突，H2=(3+2)MOD16=5H(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=90 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15ASL=(1*6+2+3*3+4+9)/12=2.514 168275519208479231110H(19)=6H(14)=1H

7、(23)=10H(1)=1 冲突，H1=(1+1) MOD16=2H(68)=3H(20)=7H(84)=6 冲突，H1=(6+1)MOD16=7 冲突，H2=(6+2)MOD16=8H(27)=1 冲突，H1=(1+1)MOD16=2 冲突，H2=(1+2)MOD16=3 冲突，H3=(1+3)MOD16=4H(11)=11H(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 14127796855198420231011ASL=(1*6+2*4+3+4)/

8、12=1.75关键字(19,14,23,1,68,20,84,27,55,11,10,79)第8页lowhighmid 1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92找211 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid例5：在下例中，画出折半查找21过程示意图。在画出有序序列查找判定树，计算查找成功ASL（自己做）。第9页92

9、7537138864215801956判定树：1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92ASL=（1X1+2X2+4X3+4X4）/11=第10页1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid找701 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmi

10、d1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid例7：折半查找举例第11页1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhigh因为lowhigh，则查找表中不存在要查找统计，查找失败，返回查找失败信息结束查找。第12页例题8试给出一棵树关键字序列，使AVL树4种调整平衡操作（LL，LR，RR，RL）各最少执行一次，并画出其结构过程。【解】设关键字输入序列为：4、5、7、2、1、3、6，则AVL树结构过程以下列图所表示。第13页 输入结点 插入后

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

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

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 两棵树图v1v2v8v4v5v6v3v8v1

14、v6v2v5v4v3v7v1第19页【解】由连通图定义知：这两个图都是连通图。连通图深度优先搜索方法是：假定图中某个顶点v1为出发点。搜索方法是：首先访问出发点，然后任选未访问过邻接点，再以该邻接点为新出发点继续进行深度优先搜索，直至全部顶点都被访问过。连通图广度优先搜索方法是：从图中某个顶点vi出发，在访问了vi 之后依次访问vi全部邻接点，然后分别从这些邻接点出发按广度优先搜索遍历图其它顶点。重复这一过程，直至全部顶点都被访问到。由此得到如图7.9和图7.10所表示对应深度优先生成树和广度优先生成树。第20页v1v2v4v5v8v6v3v7v1v2v6v5v3v4v7 (a)顶点v1遍历深

15、度优先生成树 (b)顶点v1遍历深度优先生成树 图7.9v1v2v4v5v3v8v7v6v7v4v3v5v2v1v6 (a)顶点v1遍历广度优先生成树 (b)顶点v1遍历广度优先生成树 图7.10第21页例题12对如图7.14所表示有向图,试给出：邻接矩阵 邻接表 逆邻接表 强连通分量 从出发深度优先遍历序列 从出发广度优先遍历序列。653241图7.14 有向图【解】 邻接矩阵以下：第22页12345644652532141邻接表如图7.15所表示。图7.15 邻接表第23页首先改变图7.14中有向边方向得到如图7.16所表示有向图，然后依据图7.16画出邻接表(即图7.14逆邻接表)，如图

16、7.17所表示.653241图7.16 有向图第24页12345625636533251图7.17 图7.14逆邻接表第25页在有向图G中,假如对于每一对vi,vjV(顶点集),且vivj ，从vi 到vi 和从vi vi 都存在路径，则称G是强连通图。有向图中极大强连通子图称作有向图强连通分量。由此得图7.14强连通分量如图7.18所表示。 图7.18 图7.14强连通分量从出发深度优先遍历序列为:。从出发广度优先遍历序列为:。145623第26页例题13有一带权无向图顶点集合为v1，v2，v3，v4，v5，v6，v7，v8，已知其邻接矩阵三元组表如图7.19所表示。画出该无向图邻接表。画出

17、全部可能最小生成树。依据你给邻接表分别写出从v1出发进行深度优先遍历和广度优先遍历顶点序列。写出从v1到v2最短路径。【解】首先依据邻接矩阵三元组表画出带权无向图，如图7.20所表示 。图7.20邻接表如图7.21所表示。第27页 图7.20 带权无向图882012121522112263285348352364438451047851253254106236346777487678257.19 三元组表v1v5v3v6v2v8v4v722847351210第28页图7.21 邻接表0123456745215636115422417030第29页因为存在权值相同边,则最小生成树可能不止一个,此

18、题可能最小生成树如图7.22所表示. （a） （b）图7.22 可能最小生成树v1v5v3v6v2v8v4v72284735v1v5v3v4v7v2v6v82284735第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)且输出之;在有向图中删除该顶点和全部以该顶点为尾弧;v1v2v6v5v4v3第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条边，