图结构和查找习题复习(7-8章)

1、例题例题1 1对于给定的关键序列，若哈希函数无冲突，则称其为完备对于给定的关键序列，若哈希函数无冲突，则称其为完备(perfect)(perfect)的。设哈希表长度为的。设哈希表长度为7 7，试为，试为BretBret，JaneJane，MichelleMichelle，HeattherHeatther 设计一个完备的哈希函数设计一个完备的哈希函数H H（提示：（提示：考虑每个字串的第考虑每个字串的第3 3个字符），并写出其个字符），并写出其CC代码。代码。解：解：设计哈希函数设计哈希函数H H如下：如下：H H（keykey）=key=key（第（第3 3个字母的个字母的ASCIIASCI

2、I码码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=6例题例题2 2：试述顺序查找法、二分查找法和分块查找法对被查找的表中元：试述顺序查找法

3、、二分查找法和分块查找法对被查找的表中元素的要求。对长度为素的要求。对长度为n n的表来说，的表来说，3 3种查找法在查找成功时的平均查种查找法在查找成功时的平均查找长度各是多少？找长度各是多少？解：解：3 3种方法对查找的要求分别如下：种方法对查找的要求分别如下：1 1）顺序查找法：表中元素可以任意次序存入。）顺序查找法：表中元素可以任意次序存入。2 2）二分查找法：表中元素必须以关键字的大小递增或递减的次序有序）二分查找法：表中元素必须以关键字的大小递增或递减的次序有序列且顺序表存储。列且顺序表存储。3 3）分块查找法：表中元素块内的元素可以任意次序存放，但块与块之）分块查找法：表中元素块

4、内的元素可以任意次序存放，但块与块之间必须以关键字的大小递增（或递减）存放，即前一块内所有元素间必须以关键字的大小递增（或递减）存放，即前一块内所有元素的关键字都不能大（或小）于后一块内任何元素的关键字。的关键字都不能大（或小）于后一块内任何元素的关键字。3 3种方法平均查找长度分别如下：种方法平均查找长度分别如下：顺序查找法：查找成功的平均查找长度为顺序查找法：查找成功的平均查找长度为n+1/2n+1/2。二分查找法：查找成功的平均长度为二分查找法：查找成功的平均长度为loglog2 2（n+1n+1）-1-1。分块查找法：若用顺序查找确定所在的块，平均查找长度为：分块查找法：若用顺序查找确

5、定所在的块，平均查找长度为：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采用开放定址法的二次采用开放定址法的二次探测再哈希方法解决冲突，试在探测再哈希方

6、法解决冲突，试在0 01818的哈希地址空间中对该关键字的哈希地址空间中对该关键字序列构造哈希表。序列构造哈希表。【解【解】依题意，依题意，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=2

7、3%13=10H H（1414）=14%13=1=14%13=1（发生冲突）（发生冲突）H H（1414）= =（1+11+1* *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+16+1* *1 1）%19=7%19=7（仍发生冲突）（仍发生冲突）H（84）=（6-1*1）%19=5H（27）=27%13=1（发生冲突）（发生冲突）H（27）=（1+1*1）%19=2（发生冲突）（发生冲突）H（27）=（1-1

8、）%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）=1addr（14）=2addr（55）=3addr（68）=4addr（84）=5addr（19）=6addr（20）=7addr（10）=9addr（23）=10addr

9、（11）=11addr（77）=12其他地址为空。其他地址为空。例例 已知一组关键字已知一组关键字(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=(

10、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(

11、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(2) 用链地址法处理冲突用链地址法处理冲突0 1 2 3 4 5 6 7 8 9 10 11 12 14127796855198420231011ASL=(1*6+2*4+3+4)/12=1.75关键字关键字(1

12、9,14,23,1,68,20,84,27,55,11,10,79)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 5：在下例中，画出折半查找：在下例中，画出折半查找2121的过程示意图。在画出有的过程示意图。在画出有序序列的查找判定树，计算查找

13、成功的序序列的查找判定树，计算查找成功的ASLASL（自己做）。（自己做）。927537138864215801956判定树：判定树：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=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 92lowhighmi

14、d1 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：折半查找举例：折半查找举例1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhigh由于由于lowhigh，则查找表中不存在要查找的记录，则查找表中不存在要查找的记录，查找失败，返回查找失败信息结束查找。查找失败，返回查找失败信息结束查找。例题例题8 8试给出一棵

15、树的关键字序列，使试给出一棵树的关键字序列，使AVLAVL树的树的4 4种调整平衡操作（种调整平衡操作（LLLL，LRLR，RRRR，RLRL）各至少执行一次，并画出其构造过程。）各至少执行一次，并画出其构造过程。【解【解】设关键字的输入序列为：设关键字的输入序列为：4 4、5 5、7 7、2 2、1 1、3 3、6 6，则，则AVLAVL树的构造树的构造过程如下图所示。过程如下图所示。 输入结点输入结点 插入后插入后 调整平衡后调整平衡后 4 4 无需调整无需调整 4454575472547547215274134253671527144175362413725RRRR型型无需调整无需调整无

16、需调整无需调整LLLL型型LRLR型型RLRL型型572163图图8.5 AVL树构造过程树构造过程例题例题9 9给定序列给定序列33，5 5，7 7，9 9，1111，1313，1515，1717：按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成后按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成后的二叉排序树，并求在等概率情况下查找成功的平均查找长度。的二叉排序树，并求在等概率情况下查找成功的平均查找长度。按表中元素顺序构造一棵二叉平衡树，并求其在等概率情况下查找成功的按表中元素顺序构造一棵二叉平衡树，并求其在等概率情况下查找成功的平均查找长度，与平均查找长度，与

17、比较，可得出什么结论？比较，可得出什么结论？【解【解】按输入顺序进行插入后的二充满排序树如下左图所示，其在等概率下查找按输入顺序进行插入后的二充满排序树如下左图所示，其在等概率下查找成功的平均查找长度为：成功的平均查找长度为：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+21+2* *2+32+3* *4+54+5）=11/4=11/4。

18、与与相比，可见在同样序列的查找中，二叉平衡排序树比二叉排序树的平均相比，可见在同样序列的查找中，二叉平衡排序树比二叉排序树的平均查找长度要小且查找效率高。查找长度要小且查找效率高。35 57 79 911111313151517179 953 313131515171711117 7图图8.6 二叉排序树二叉排序树图图8.7 二叉平衡树二叉平衡树例题例题1010：线性表关键字集合：线性表关键字集合8787，2525，310310，0808，2727，132132，6868，9595，187187，123123，7070，6363，4747，共有，共有1313个元素，已知哈希函数为：个元素，已知

19、哈希函数为：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

20、=3=68%13=3H（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=133113161332101例题例题1111对如图对如图7.8(a)7.8(a)和和(b)(b)所示的图，试画出其深度优先生成树和广度优先生成所示的图，试画出其深度优先生成树和广度优先生成树。树。 (a) (b)图图7.8 7.8 两棵树图两棵树图v1v2v8v4v5v6v3v8v1

21、v6v2v5v4v3v7v1【解【解】由连通图的定义知：这两个图都是连通图。由连通图的定义知：这两个图都是连通图。连通图深度优先搜索的方法是：连通图深度优先搜索的方法是：假定图中某个顶点假定图中某个顶点v v1 1为出发点。搜索方法是：首先访问出发点，然后任为出发点。搜索方法是：首先访问出发点，然后任选未访问过的邻接点，再以该邻接点为新的出发点继续进行深度优先选未访问过的邻接点，再以该邻接点为新的出发点继续进行深度优先搜索，直至所有顶点都被访问过。连通图广度优先搜索的方法是：搜索，直至所有顶点都被访问过。连通图广度优先搜索的方法是：从图中某个顶点从图中某个顶点v vii出发，在访问了出发，在访

22、问了v vi i 之后依次访问之后依次访问v vii的所有邻接点，然后的所有邻接点，然后分别从这些邻接点出发按广度优先搜索遍历图的其他顶点。重复这一分别从这些邻接点出发按广度优先搜索遍历图的其他顶点。重复这一过程，直至所有顶点都被访问到。过程，直至所有顶点都被访问到。由此得到如图由此得到如图7.97.9和图和图7.107.10所示的相应的深度优先生成树和广度优先生成所示的相应的深度优先生成树和广度优先生成树。树。v1v2v4v5v8v6v3v7v1v2v6v5v3v4v7 (a) (a)顶点顶点v v1 1遍历的深度优先生成树遍历的深度优先生成树 (b)(b)顶点顶点v v1 1遍历的深度优先

23、生成遍历的深度优先生成树树 图图7.97.9v1v2v4v5v3v8v7v6v7v4v3v5v2v1v6 (a)(a)顶点顶点v1v1遍历的广度优先生成树遍历的广度优先生成树 (b)(b)顶点顶点v1v1遍历的广度优先生成树遍历的广度优先生成树 图图7.107.10例题例题12对如图对如图7.14所示的有向图所示的有向图,试给出：试给出：邻接矩阵邻接矩阵 邻接表邻接表 逆邻接表逆邻接表 强连通分量强连通分量 从从出发的深度优出发的深度优先遍历序列先遍历序列 从从出发的广度优先遍历序列。出发的广度优先遍历序列。653241图图7.14 7.14 有向图有向图【解【解】 邻接矩阵如下：邻接矩阵如下

24、：12345644652532141邻接表如图邻接表如图7.157.15所示。所示。图图7.15 邻接表邻接表首先改变图首先改变图7.147.14中有向边的方向得到如图中有向边的方向得到如图7.167.16所示的有向图，然后根所示的有向图，然后根据图据图7.167.16画出邻接表画出邻接表( (即图即图7.147.14的逆邻接表的逆邻接表) )，如图，如图7.177.17所示所示. .653241图图7.16 7.16 有向图有向图12345625636533251图图7.17 图图7.14的逆邻接表的逆邻接表在有向图在有向图G中中,如果对于每一对如果对于每一对vi,vjV(顶点集顶点集),且

25、且vivj ，从，从vi 到到vi 和从和从vi 的的vi 都存在路径，则称都存在路径，则称G是强连通图。有向图中的极大强连通是强连通图。有向图中的极大强连通子图称作有向图的强连通分量。由此得图子图称作有向图的强连通分量。由此得图7.14的强连通分量如图的强连通分量如图7.18所示。所示。 图图7.18 图图7.14的强连通分量的强连通分量从从出发的深度优先遍历序列为出发的深度优先遍历序列为: :。从从出发的广度优先遍历序列为出发的广度优先遍历序列为: :。145623例题例题13有一带权无向图的顶点集合为有一带权无向图的顶点集合为v1，v2，v3，v4，v5，v6，v7，v8，已知，已知其邻

26、接矩阵的三元组表如图其邻接矩阵的三元组表如图7.19所示。所示。画出该无向图的邻接表。画出该无向图的邻接表。画出所有可能的最小生成树。画出所有可能的最小生成树。根据你给的邻接表分别写出从根据你给的邻接表分别写出从v1出发进行深度优先遍历和广度优先遍出发进行深度优先遍历和广度优先遍历的顶点序列。历的顶点序列。写出从写出从v1到到v2的最短路径。的最短路径。【解【解】首先根据邻接矩阵的三元组表画出带权无向图，如图首先根据邻接矩阵的三元组表画出带权无向图，如图7.20所示所示 。图图7.20的邻接表如图的邻接表如图7.21所示。所示。 图图7.20 7.20 带权无向图带权无向图8820121215

27、22112263285348352364438451047851253254106236346777487678257.19 三元组表三元组表v1v5v3v6v2v8v4v722847351210图图7.21 7.21 邻接表邻接表0123456745215636115422417030由于存在权值相同的边由于存在权值相同的边,则最小生成树可能不止一个则最小生成树可能不止一个,此题可能的最小生此题可能的最小生成树如图成树如图7.22所示所示. （a） （b）图图7.22 可能的最小生成树可能的最小生成树v1v5v3v6v2v8v4v72284735v1v5v3v4v7v2v6v82284735根据图根据图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 有向图有向图【解【解】拓扑排序算法的步骤为拓扑排序算法的步骤为:在有向图中选择一个没有前驱的顶点在有向图中选择