圖結構和查找習題復習(7-8章)

1、例題例題1 1對于給定的關鍵序列，若哈希函數(shù)無沖突，則稱其為完備對于給定的關鍵序列，若哈希函數(shù)無沖突，則稱其為完備(perfect)(perfect)的。設哈希表長度為的。設哈希表長度為7 7，試為，試為BretBret，JaneJane，MichelleMichelle，HeattherHeatther 設計一個完備的哈希函數(shù)設計一個完備的哈希函數(shù)H H（提示：（提示：考慮每個字串的第考慮每個字串的第3 3個字符），并寫出其個字符），并寫出其CC代碼。代碼。解：解：設計哈希函數(shù)設計哈希函數(shù)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）分塊查找法：表中元素塊內(nèi)的元素可以任意次序存放，但塊與塊之）分塊查找法：表中元素塊

4、內(nèi)的元素可以任意次序存放，但塊與塊之間必須以關鍵字的大小遞增（或遞減）存放，即前一塊內(nèi)所有元素間必須以關鍵字的大小遞增（或遞減）存放，即前一塊內(nèi)所有元素的關鍵字都不能大（或小）于后一塊內(nèi)任何元素的關鍵字。的關鍵字都不能大（或?。┯诤笠粔K內(nèi)任何元素的關鍵字。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為每塊含有的元素的個數(shù)。為每塊含有的元素的個數(shù)。例題例題3 3： 設有一組關鍵字設有一組關鍵字1919，1 1，2323，1414，5555，2020，8484，2727，6868，1111，1010，7777采用哈希函數(shù)：采用哈希函數(shù)：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，其計算函數(shù)如下：其計算函數(shù)如下：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（發(fā)生沖突）（發(fā)生沖突）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（發(fā)生沖突）（發(fā)生沖突）H H（8484）= =（6+16+1* *1 1）%19=7%19=7（仍發(fā)生沖突）（仍發(fā)生沖突）H（84）=（6-1*1）%19=5H（27）=27%13=1（發(fā)生沖突）（發(fā)生沖突）H（27）=（1+1*1）%19=2（發(fā)生沖突）（發(fā)生沖突）H（27）=（1-1

8、）%19=0H（68）=68%13=3（發(fā)生沖突）（發(fā)生沖突）H（68）=（3+1*1）%19=4H（11）=11%13=11H（10）=10%13=10（發(fā)生沖突）（發(fā)生沖突）H（10）=（10+1*1）%19=11（仍發(fā)生沖突）（仍發(fā)生沖突）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) 哈希函數(shù)為：哈希函數(shù)為：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種調(diào)整平衡操作（種調(diào)整平衡操作（LLLL，LRLR，RRRR，RLRL）各至少執(zhí)行一次，并畫出其構造過程。）各至少執(zhí)行一次，并畫出其構造過程?！窘狻窘狻吭O關鍵字的輸入序列為：設關鍵字的輸入序列為：4 4、5 5、7 7、2 2、1 1、3 3、6 6，則，則AVLAVL樹的構造樹的構造過程如下圖所示。過程如下圖所示。 輸入結點輸入結點 插入后插入后 調(diào)整平衡后調(diào)整平衡后 4 4 無需調(diào)整無需調(diào)整 4454575472547547215274134253671527144175362413725RRRR型型無需調(diào)整無需調(diào)整無

16、需調(diào)整無需調(diào)整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個元素，已知哈希函數(shù)為：個元素，已知

19、哈希函數(shù)為：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)所示的圖，試畫出其深度優(yōu)先生成樹和廣度優(yōu)先生成所示的圖，試畫出其深度優(yōu)先生成樹和廣度優(yōu)先生成樹。樹。 (a) (b)圖圖7.8 7.8 兩棵樹圖兩棵樹圖v1v2v8v4v5v6v3v8v1

21、v6v2v5v4v3v7v1【解【解】由連通圖的定義知：這兩個圖都是連通圖。由連通圖的定義知：這兩個圖都是連通圖。連通圖深度優(yōu)先搜索的方法是：連通圖深度優(yōu)先搜索的方法是：假定圖中某個頂點假定圖中某個頂點v v1 1為出發(fā)點。搜索方法是：首先訪問出發(fā)點，然后任為出發(fā)點。搜索方法是：首先訪問出發(fā)點，然后任選未訪問過的鄰接點，再以該鄰接點為新的出發(fā)點繼續(xù)進行深度優(yōu)先選未訪問過的鄰接點，再以該鄰接點為新的出發(fā)點繼續(xù)進行深度優(yōu)先搜索，直至所有頂點都被訪問過。連通圖廣度優(yōu)先搜索的方法是：搜索，直至所有頂點都被訪問過。連通圖廣度優(yōu)先搜索的方法是：從圖中某個頂點從圖中某個頂點v vii出發(fā)，在訪問了出發(fā)，在訪

22、問了v vi i 之后依次訪問之后依次訪問v vii的所有鄰接點，然后的所有鄰接點，然后分別從這些鄰接點出發(fā)按廣度優(yōu)先搜索遍歷圖的其他頂點。重復這一分別從這些鄰接點出發(fā)按廣度優(yōu)先搜索遍歷圖的其他頂點。重復這一過程，直至所有頂點都被訪問到。過程，直至所有頂點都被訪問到。由此得到如圖由此得到如圖7.97.9和圖和圖7.107.10所示的相應的深度優(yōu)先生成樹和廣度優(yōu)先生成所示的相應的深度優(yōu)先生成樹和廣度優(yōu)先生成樹。樹。v1v2v4v5v8v6v3v7v1v2v6v5v3v4v7 (a) (a)頂點頂點v v1 1遍歷的深度優(yōu)先生成樹遍歷的深度優(yōu)先生成樹 (b)(b)頂點頂點v v1 1遍歷的深度優(yōu)先

23、生成遍歷的深度優(yōu)先生成樹樹 圖圖7.97.9v1v2v4v5v3v8v7v6v7v4v3v5v2v1v6 (a)(a)頂點頂點v1v1遍歷的廣度優(yōu)先生成樹遍歷的廣度優(yōu)先生成樹 (b)(b)頂點頂點v1v1遍歷的廣度優(yōu)先生成樹遍歷的廣度優(yōu)先生成樹 圖圖7.107.10例題例題12對如圖對如圖7.14所示的有向圖所示的有向圖,試給出：試給出：鄰接矩陣鄰接矩陣 鄰接表鄰接表 逆鄰接表逆鄰接表 強連通分量強連通分量 從從出發(fā)的深度優(yōu)出發(fā)的深度優(yōu)先遍歷序列先遍歷序列 從從出發(fā)的廣度優(yōu)先遍歷序列。出發(fā)的廣度優(yōu)先遍歷序列。653241圖圖7.14 7.14 有向圖有向圖【解【解】 鄰接矩陣如下：鄰接矩陣如下

24、：12345644652532141鄰接表如圖鄰接表如圖7.157.15所示。所示。圖圖7.15 鄰接表鄰接表首先改變圖首先改變圖7.147.14中有向邊的方向得到如圖中有向邊的方向得到如圖7.167.16所示的有向圖，然后根所示的有向圖，然后根據(jù)圖據(jù)圖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的強連通分量的強連通分量從從出發(fā)的深度優(yōu)先遍歷序列為出發(fā)的深度優(yōu)先遍歷序列為: :。從從出發(fā)的廣度優(yōu)先遍歷序列為出發(fā)的廣度優(yōu)先遍歷序列為: :。145623例題例題13有一帶權無向圖的頂點集合為有一帶權無向圖的頂點集合為v1，v2，v3，v4，v5，v6，v7，v8，已知，已知其鄰

26、接矩陣的三元組表如圖其鄰接矩陣的三元組表如圖7.19所示。所示。畫出該無向圖的鄰接表。畫出該無向圖的鄰接表。畫出所有可能的最小生成樹。畫出所有可能的最小生成樹。根據(jù)你給的鄰接表分別寫出從根據(jù)你給的鄰接表分別寫出從v1出發(fā)進行深度優(yōu)先遍歷和廣度優(yōu)先遍出發(fā)進行深度優(yōu)先遍歷和廣度優(yōu)先遍歷的頂點序列。歷的頂點序列。寫出從寫出從v1到到v2的最短路徑。的最短路徑?！窘狻窘狻渴紫雀鶕?jù)鄰接矩陣的三元組表畫出帶權無向圖，如圖首先根據(jù)鄰接矩陣的三元組表畫出帶權無向圖，如圖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根據(jù)圖根據(jù)圖7.21鄰接表得到的深度優(yōu)先遍歷序列為鄰接表得到的深度優(yōu)先遍歷序列為:v1,v5,v4,v7,v6,v3,v2,v8;廣度優(yōu)先遍歷序列為廣度優(yōu)先遍歷序列為:v1,v5,v2,v4,v3,v8,v6,v7。從從v1到到v2的最短路徑為的最短路徑為v1,v5,v3,v6,v2。例題例題20試列出圖試列出圖7.23中全部可能的拓撲排序序列。中全部可能的拓撲排序序列。圖圖7.23 有向圖有向圖【解【解】拓撲排序算法的步驟為拓撲排序算法的步驟為:在有向圖中選擇一個沒有前驅(qū)的頂點在有向圖中選擇