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

例题例题1 1对于给定的关键序列，若哈希函数无冲突，则称其为完备对于给定的关键序列，若哈希函数无冲突，则称其为完备(perfect)(perfect)的。设哈希表长度为的。设哈希表长度为7 7，试为，试为BretBret，JaneJane，MichelleMichelle，HeattherHeatther设计一个完备的哈希函数设计一个完备的哈希函数H H（提示：（提示：考虑每个字串的第考虑每个字串的第3 3个字符），并写出其个字符），并写出其CC代码。代码。设计哈希函数设计哈希函数H H如下：如下：H H（keykey）=key=key（第（第3 3个字母的个字母的ASCIIASCII码码MOD 7MOD 7），则：），则：H H（BertBert）=101 MOD 7=3=101 MOD 7=3H H（JaneJane）=110 MOD 7=5=110 MOD 7=5H H（ShirleyShirley）=105 MOD 7=105 MOD 7H H（BryceBryce）=121 MOD 7=2=121 MOD 7=2H H（MichelleMichelle）=99 MOD 7=1=99 MOD 7=1H H（HeatherHeather）=97 MOD 7=6=97 MOD 7=61例题例题2 2：试述顺序查找法、二分查找法和分块查找法对被查找的表中元：试述顺序查找法、二分查找法和分块查找法对被查找的表中元素的要求。对长度为素的要求。对长度为n n的表来说，的表来说，3 3种查找法在查找成功时的平均查种查找法在查找成功时的平均查找长度各是多少？找长度各是多少？解：解：3 3种方法对查找的要求分别如下：种方法对查找的要求分别如下：1 1）顺序查找法：表中元素可以任意次序存入。）顺序查找法：表中元素可以任意次序存入。2 2）二分查找法：表中元素必须以关键字的大小递增或递减的次序有序）二分查找法：表中元素必须以关键字的大小递增或递减的次序有序列且顺序表存储。列且顺序表存储。3 3）分块查找法：表中元素块内的元素可以任意次序存放，但块与块之）分块查找法：表中元素块内的元素可以任意次序存放，但块与块之间必须以关键字的大小递增（或递减）存放，即前一块内所有元素间必须以关键字的大小递增（或递减）存放，即前一块内所有元素的关键字都不能大（或小）于后一块内任何元素的关键字。的关键字都不能大（或小）于后一块内任何元素的关键字。23 3种方法平均查找长度分别如下：种方法平均查找长度分别如下：顺序查找法：查找成功的平均查找长度为顺序查找法：查找成功的平均查找长度为n+1/2n+1/2。二分查找法：查找成功的平均长度为二分查找法：查找成功的平均长度为loglog2 2（n+1n+1）-1-1。分块查找法：若用顺序查找确定所在的块，平均查找长度为：分块查找法：若用顺序查找确定所在的块，平均查找长度为：1/21/2（n/1+sn/1+s）+1+1；若用二分查找确定所在块，平均查找长度为；若用二分查找确定所在块，平均查找长度为loglog2 2（n/s+1n/s+1）+s/2+s/2。其中，。其中，s s为每块含有的元素的个数。为每块含有的元素的个数。例题例题3 3：设有一组关键字设有一组关键字1919，1 1，2323，1414，5555，2020，8484，2727，6868，1111，1010，7777采用哈希函数：采用哈希函数：H H（keykey）=key%13=key%13采用开放定址法的二采用开放定址法的二次探测再哈希方法解决冲突，试在次探测再哈希方法解决冲突，试在0 01818的哈希地址空间中对该关键的哈希地址空间中对该关键字序列构造哈希表。字序列构造哈希表。3【解解】依题意，依题意，m=19m=19，二次探测再哈希的下一地址计算公式为：，二次探测再哈希的下一地址计算公式为：d d1 1=H=H（keykey）；）；d d2j 2j=（d d1 1+j*j+j*j）%m%m；d d2j+12j+1（d d1 1-j*j-j*j）%m%m；j=1j=1，2 2，其计算函数如下：其计算函数如下：H H（1919）=19%13=6=19%13=6H H（1 1）=1%13=1=1%13=1H H（2323）=23%13=10=23%13=10H H（1414）=14%13=1=14%13=1（发生冲突）（发生冲突）H H（1414）=（1+1*11+1*1）%19=2%19=2H H（5555）=55%13=3=55%13=3H H（2020）=20%13=7=20%13=7H H（8484）=84%13=6=84%13=6（发生冲突）（发生冲突）H H（8484）=（6+1*16+1*1）%19=7%19=7（仍发生冲突）（仍发生冲突）4H（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）=15addr（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)=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 1 68 27 55 19 20 84 79 23 11 10H(19)=6H(14)=1H(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=127(2)用链地址法处理冲突用链地址法处理冲突0 1 2 3 4 5 6 7 8 9 10 11 12 14127796855198420231011ASL=(1*6+2*4+3+4)/12=1.75关键字关键字(19,14,23,1,68,20,84,27,55,11,10,79)8lowhighmid 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 5：在下例中，画出折半查找：在下例中，画出折半查找2121的过程示意图。在画出有的过程示意图。在画出有序序列的查找判定树，计算查找成功的序序列的查找判定树，计算查找成功的ASLASL（自己做）。（自己做）。9927537138864215801956判定树：判定树：1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92ASL=ASL=（1X1+2X2+4X3+4X41X1+2X2+4X3+4X4）/11=/11=101 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 92low highmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid例例7 7：折半查找举例：折半查找举例111 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhigh由于由于lowhigh，则查找表中不存在要查找的记录，则查找表中不存在要查找的记录，查找失败，返回查找失败信息结束查找。查找失败，返回查找失败信息结束查找。12例题例题8 8试给出一棵树的关键字序列，使试给出一棵树的关键字序列，使AVLAVL树的树的4 4种调整平衡操作（种调整平衡操作（LLLL，LRLR，RRRR，RLRL）各至少执行一次，并画出其构造过程。）各至少执行一次，并画出其构造过程。【解解】设关键字的输入序列为：设关键字的输入序列为：4 4、5 5、7 7、2 2、1 1、3 3、6 6，则，则AVLAVL树的构造树的构造过程如下图所示。过程如下图所示。13 输入结点输入结点 插入后插入后 调整平衡后调整平衡后 4 4 无需调整无需调整 4454575472547547215274134253671527144175362413725RRRR型型无需调整无需调整无需调整无需调整LLLL型型LRLR型型RLRL型型572163图图8.5 AVL树构造过程树构造过程14例题例题9 9给定序列给定序列33，5 5，7 7，9 9，1111，1313，1515，1717：按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成后按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成后的二叉排序树，并求在等概率情况下查找成功的平均查找长度。的二叉排序树，并求在等概率情况下查找成功的平均查找长度。按表中元素顺序构造一棵二叉平衡树，并求其在等概率情况下查找成功的按表中元素顺序构造一棵二叉平衡树，并求其在等概率情况下查找成功的平均查找长度，与平均查找长度，与比较，可得出什么结论？比较，可得出什么结论？【解解】按输入顺序进行插入后的二充满排序树如下左图所示，其在等概率下查找按输入顺序进行插入后的二充满排序树如下左图所示，其在等概率下查找成功的平均查找长度为：成功的平均查找长度为：ASLASL成功成功=（1+2+2+3+4+5+6+7+81+2+2+3+4+5+6+7+8）/8=9/2/8=9/2。构造一棵平衡二叉树如下右图所示，其在等概率下查找成功的平均查找长构造一棵平衡二叉树如下右图所示，其在等概率下查找成功的平均查找长度为：度为：ASLASL成功成功=1/8=1/8（1+2*2+3*4+51+2*2+3*4+5）=11/4=11/4。与与相比，可见在同样序列的查找中，二叉平衡排序树比二叉排序树的平均相比，可见在同样序列的查找中，二叉平衡排序树比二叉排序树的平均查找长度要小且查找效率高。查找长度要小且查找效率高。1535 57 79 911111313151517179 953 313131515171711117 7图图8.6 二叉排序树二叉排序树图图8.7 二叉平衡树二叉平衡树16例题例题1010：线性表关键字集合：线性表关键字集合8787，2525，310310，0808，2727，132132，6868，9595，187187，123123，7070，6363，4747，共有，共有1313个元素，已知哈希函数为：个元素，已知哈希函数为：H H（k k）=k%13=k%13采用链地址法处理冲突。设计出这种链表结构，并计算该表的成功查找采用链地址法处理冲突。设计出这种链表结构，并计算该表的成功查找的平均长度。（练习题）的平均长度。（练习题）【解解】依题意知：依题意知：H H（8787）=87%13=9=87%13=9H H（2525）=25%13=12=25%13=12H H（310310）=310%13=11=310%13=11H H（0808）=08%13=8=08%13=8H H（2727）=27%13=1=27%13=1H H（132132）=132%13=2=132%13=2H H（6868）=68%13=3=68%13=317H（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例题例题1111对如图对如图7.8(a)7.8(a)和和(b)(b)所示的图，试画出其深度优先生成树和广度优先生成所示的图，试画出其深度优先生成树和广度优先生成树。树。(a)(b)图图7.8 7.8 两棵树图两棵树图v1v2v8v4v5v6v3v8v1v6v2v5v4v3v7v119【解解】由连通图的定义知：这两个图都是连通图。由连通图的定义知：这两个图都是连通图。连通图深度优先搜索的方法是：连通图深度优先搜索的方法是：假定图中某个顶点假定图中某个顶点v v1 1为出发点。搜索方法是：首先访问出发点，然后任为出发点。搜索方法是：首先访问出发点，然后任选未访问过的邻接点，再以该邻接点为新的出发点继续进行深度优先选未访问过的邻接点，再以该邻接点为新的出发点继续进行深度优先搜索，直至所有顶点都被访问过。连通图广度优先搜索的方法是：搜索，直至所有顶点都被访问过。连通图广度优先搜索的方法是：从图中某个顶点从图中某个顶点v vii出发，在访问了出发，在访问了v vi i 之后依次访问之后依次访问v vi i的所有邻接点，然后的所有邻接点，然后分别从这些邻接点出发按广度优先搜索遍历图的其他顶点。重复这一分别从这些邻接点出发按广度优先搜索遍历图的其他顶点。重复这一过程，直至所有顶点都被访问到。过程，直至所有顶点都被访问到。由此得到如图由此得到如图7.97.9和图和图7.107.10所示的相应的深度优先生成树和广度优先生成所示的相应的深度优先生成树和广度优先生成树。树。20v1v2v4v5v8v6v3v7v1v2v6v5v3v4v7 (a)(a)顶点顶点v v1 1遍历的深度优先生成树遍历的深度优先生成树 (b)(b)顶点顶点v v1 1遍历的深度优先生成树遍历的深度优先生成树 图图7.97.9v1v2v4v5v3v8v7v6v7v4v3v5v2v1v6 (a)(a)顶点顶点v1v1遍历的广度优先生成树遍历的广度优先生成树 (b)(b)顶点顶点v1v1遍历的广度优先生成树遍历的广度优先生成树 图图7.107.1021例题例题12对如图对如图7.14所示的有向图所示的有向图,试给出：试给出：邻接矩阵邻接矩阵 邻接表邻接表 逆邻接表逆邻接表 强连通分量强连通分量 从从出发的深度优出发的深度优先遍历序列先遍历序列 从从出发的广度优先遍历序列。出发的广度优先遍历序列。653241图图7.14 7.14 有向图有向图【解解】邻接矩阵如下：邻接矩阵如下：2212345644652532141邻接表如图邻接表如图7.157.15所示。所示。图图7.15 邻接表邻接表23首先改变图首先改变图7.147.14中有向边的方向得到如图中有向边的方向得到如图7.167.16所示的有向图，然后根所示的有向图，然后根据图据图7.167.16画出邻接表画出邻接表(即图即图7.147.14的逆邻接表的逆邻接表)，如图，如图7.177.17所示所示.653241图图7.16 7.16 有向图有向图2412345625636533251图图7.17 图图7.14的逆邻接表的逆邻接表25在有向图在有向图G中中,如果对于每一对如果对于每一对vi,vj V(顶点集顶点集),且且vivj，从，从vi 到到vi 和从和从vi 的的vi 都存在路径，则称都存在路径，则称G是强连通图。有向图中的极大强连通是强连通图。有向图中的极大强连通子图称作有向图的强连通分量。由此得图子图称作有向图的强连通分量。由此得图7.14的强连通分量如图的强连通分量如图7.18所示。所示。图图7.18 图图7.14的强连通分量的强连通分量从从出发的深度优先遍历序列为出发的深度优先遍历序列为:。从从出发的广度优先遍历序列为出发的广度优先遍历序列为:。14562326例题例题13有一带权无向图的顶点集合为有一带权无向图的顶点集合为v1，v2，v3，v4，v5，v6，v7，v8，已知，已知其邻接矩阵的三元组表如图其邻接矩阵的三元组表如图7.19所示。所示。画出该无向图的邻接表。画出该无向图的邻接表。画出所有可能的最小生成树。画出所有可能的最小生成树。根据你给的邻接表分别写出从根据你给的邻接表分别写出从v1出发进行深度优先遍历和广度优先遍出发进行深度优先遍历和广度优先遍历的顶点序列。历的顶点序列。写出从写出从v1到到v2的最短路径。的最短路径。【解解】首先根据邻接矩阵的三元组表画出带权无向图，如图首先根据邻接矩阵的三元组表画出带权无向图，如图7.20所示所示。图图7.20的邻接表如图的邻接表如图7.21所示。所示。27 图图7.20 7.20 带权无向图带权无向图882012121522112263285348352364438451047851253254106236346777487678257.19 三元组表三元组表v1v5v3v6v2v8v4v72284735121028图图7.21 7.21 邻接表邻接表012345674521563611542241703029由于存在权值相同的边由于存在权值相同的边,则最小生成树可能不止一个则最小生成树可能不止一个,此题可能的最小生此题可能的最小生成树如图成树如图7.22所示所示.（a）（b）图图7.22 可能的最小生成树可能的最小生成树v1v5v3v6v2v8v4v72284735v1v5v3v4v7v2v6v8228473530根据图根据图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)且输出之且输出之;在有向图中删除该顶点和所有以该顶点为尾的弧在有向图中删除该顶点和所有以该顶点为尾的弧;v1v2v6v5v4v331重复重复和和,直至图中没有前驱的顶点直至图中没有前驱的顶点(不存在有弧相连的顶点不存在有弧相连的顶点)时为止。时为止。由此得到图由此得到图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 432例题例题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一定是树图。一定是树图。证毕。证毕。33V1V2V3V4V5V6V7V8V9顶点 Ve Vl0645771614180668710161418v9v8v7v6v4v5v3v2v1a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4a1a2a3a4a5a6a7a8a9a10a11活动 e l l-e*00002266046258377077071031616014140033例例14：关键路径的计算：关键路径的计算34此课件下载可自行编辑修改，供参考！感谢您的支持，我们努力做得更好！35