數(shù)據結構Ch9習題答案

1、Ch9查找一、單項選擇題1順序查找法適合于存儲結構為B的線性表。A散列存儲 B順序存儲或鏈接存儲 C壓縮存儲 D索引存儲2對線性表進行二分查找時，要求線性表必須C。A以順序方式存儲 B以鏈接方式存儲C以順序方式存儲，且結點按關鍵字有序排序 D以鏈接方式存儲，且結點按關鍵字有序排序3采用順序查找方法查找長度為n的線性表時，每個元素的平均查找長度為C。An Bn/2 C(n+1)/2 D(n-1)/24 采用二分查找方法查找長度為n的線性表時，每個元素的平均查找長度為D。AO(n2） B O(nlog2n) CO(n) DO(log2n)5二分查找和二叉排序樹的時間性能B。A相同 B不相同就平均時

2、間性能而言，二叉排序樹上的查找和二分查找差不多。就維護表的有序性而言，二叉排序樹無須移動結點，只需修改指針即可完成插入和刪除操作，且其平均的執(zhí)行時間均為O(log2n)，因此更有效。二分查找所涉及的有序表是一個向量，若有插入和刪除結點的操作，則維護表的有序性所花的代價是O(n)。當有序表是靜態(tài)查找表時，宜用向量作為其存儲結構，而采用二分查找實現(xiàn)其查找操作；若有序表里動態(tài)查找表，則應選擇二叉排序樹作為其存儲結構。6有一個有序表為1，3，9，12，32，41，45，62，75，77，82，95，100，當二分查找值82為的結點時，C次比較后查找成功。A1 B2 C4 D87有一個長度為12的有序表

3、，按二分查找法對該表進行查找，在表內各元素等概率情況下查找成功所需的平均比較次數(shù)為B。A35/12 B37/12 C39/12 D43/128根據一組記錄 ( 56, 42, 50, 64, 48 ) 依次插入結點生成一棵AVL樹（高度平衡的二叉搜索樹）時，當插入到值為 50 的結點時需要進行旋轉調整。 9向一棵二叉搜索樹中插入一個新元素時，若該新元素的值大于根結點的值，則應把它插入到根結點 右子樹上。 10根據一組記錄 ( 56, 42, 73, 50, 64, 48, 22 ) 依次插入結點生成一棵AVL樹（高度平衡的二叉搜索樹）時，當插入到值為 48 的結點時才出現(xiàn)不平衡，需要進行旋轉調

4、整。 11以順序搜索方法從長度為n的順序表或單鏈表中搜索一個元素時，其時間復雜度為 O(n) 。 12在一棵AVL樹（高度平衡的二叉搜索樹）中，每個結點的左子樹高度與右子樹高度之差的絕對值不超過 1 。 13在線性表的散列存儲中，裝載因子 a 又稱為裝載系數(shù)，若用m表示散列表的長度，n表示待散列存儲的元素的個數(shù)，則 a 等于 n/m 。 14以折半搜索方法從長度為n的有序表中搜索一個元素時，時間復雜度為 O(log2n)。 15假定一個順序表的長度為40，并假定搜索每個元素的概率都相同，則在搜索成功情況下的平均搜索長度為 20.5 。 16假定要對長度n = 100的線性表進行散列存儲，并采用

5、開散列法處理沖突，則對于長度m = 20的散列表，每個散列地址的同義詞子表（單鏈表）的長度平均為 5 。 17假定對長度n = 50的有序表進行折半搜索，則對應的判定樹中最后一層的結點數(shù)為 19 個。 1 2 4 8 16 1918根據n個元素建立一棵二叉搜索樹(二叉排序樹)的時間復雜度性大致為 O(nlog2n) 。 19從一棵二叉搜索樹中搜索一個元素時，若給定值小于根結點的值，則需要向 左子樹 繼續(xù)搜索。 20假定一個線性表為 (”abcd”, ”baabd”, ”bcef”, ”cfg”, ”ahij”, ”bkwte”, ”ccdt”, ”aayb”)，若按照字符串的第一個字母進行劃分

6、，使得第一個字母相同的字符串被劃分在一個子表中，則得到的以a為第一個字母的子表長度 3 。 21假設在有序線性表A120上進行二分查找，則比較一次查找成功的結點數(shù)為1，則比較二次查找成功的結點數(shù)為2，則比較三次查找成功的結點數(shù)為4，則比較四次查找成功的結點數(shù)為8，則比較五次查找成功的結點數(shù)為5，平均查找長度為37。22對于長度為n的線性表，若進行順序查找，則時間復雜度為O(n)；若采用二分法查找，則時間復雜度為O(log2n) 。 23、 對長度為3的順序表進行搜索，若搜索第一個元素的概率為1/2，搜索第二個元素的概率為1/3，搜索第三個元素的概率為1/6，則搜索到表中任一元素的平均搜索長度為

7、 A 。 A5/3 B2 C7/3 D4/3 1/2*3+1/3*2+1/6*1=9/6+4/6+1/6=7/31/2*1+1/3*2+1/6*3=3/6+4/6+3/6=5/324、 向一棵AVL樹（高度平衡的二叉搜索樹）插入元素時，可能引起對最小不平衡子樹的雙向旋轉的調整過程，此時需要修改相關 C 個結點指針域的值。 A2 B3 C4 D5 25、 向一棵AVL樹（高度平衡的二叉搜索樹）插入元素時，可能引起對最小不平衡子樹的調整過程，此調整分為 C種旋轉類型。 A2 B3 C4 D5 26、 向一棵AVL樹（高度平衡的二叉搜索樹）插入元素時，可能引起對最小不平衡子樹的左單或右單旋轉的調整過

8、程，此時需要修改相關 C個結點指針域的值。 A2 B3 C4 D5 三、判斷題：1(×)對二叉搜索樹進行前序遍歷得到的結點序列是一個有序序列。2()折半搜索所對應的判定樹，既是一棵二叉搜索樹，又是一棵理想平衡二叉樹（它的特點是除最底層結點外其他各層結點數(shù)都是滿的，最底層的若干結點可能散布在該層各處）。3()裝載因子是散列表的一個重要參數(shù)，它反映了散列表的裝滿程度。4()對于兩棵具有相同記錄集合而具有不同結構的二叉搜索樹，按中序遍歷得到的結點序列是相同的。三、綜合練習題:1畫出對長度為10的有序表進行折半查找的判定樹，并求其等概率時查找成功的平均查找長度。等概率時查找成功的平均查找長度

9、=(1*1+2*2+4*3+3*4)/10=292已知一組關鍵字49，38，65，97，76，13，27，44，82，35，50，畫出由此生成的二叉排序樹和平衡二叉樹。二叉排序樹：平衡二叉樹：3設某字典組成如下D=016, 087, 154, 170, 275, 426, 503, 509, 512, 612, 653, 677, 703, 765, 897, 908依次順序表示在內存中，現(xiàn)用二分法的方法查找字典中是否有元素612，問需要進行多少次比較才能得到結論? 每次選擇的比較對象是什么元素?解：比較次數(shù)為3次，第一次和509比較，第二次和677比較，第三次和612比較。4試給出一個關鍵碼

10、序列，使構造AVL樹時四種調整平衡操作( LL, LR, RR, RL )各至少執(zhí)行一次，并畫出其構造過程。:解：設輸入序列為12，6，4，16，24，15，13，1，35設順序表中關鍵字是遞增有序的，試寫一順序查找算法，將哨兵設在表的高下標端。解：Search_Seq(SSTable ST, KeyType key)/順序查找的算法，n號元素為監(jiān)視哨STelemnkey=key; /哨兵for (i=0; !EQ(STelemikey,key);+i); return i;6什么叫靜態(tài)查找？什么叫動態(tài)查找？什么樣的存儲結構適宜于進行靜態(tài)查找？什么樣的存儲結構適宜于進行動態(tài)查找？7什么叫平均查

11、找長度？寫出平均查找長度的定義。8已知一個個數(shù)為12的數(shù)據元素序列為Dec, Feb, Nov, Oct, June, Sept, Aug, Apr, May, July, Jan, Mar，要求：（1）按各數(shù)據元素的順序構造一棵二叉排序樹。（2）設各數(shù)據元素的查找概率相等，給出該二叉排序樹的平均查找長度。（注：字母的大小是指字母的ASCII碼數(shù)值大?。?）按各數(shù)據元素的順序構造一棵平衡二叉樹。解：（1）構造的二叉排序樹：（2）平均查找長度為：（1*1+2*2+2*3+2*4+3*5+2*6）/12=46/12=23/6（3）構造的平衡二叉樹：9使用散列函數(shù)hash (x) = x %11,

12、 把一個整數(shù)值轉換成散列表地址?，F(xiàn)要把數(shù)據1, 13, 12, 34, 38, 33, 27, 22 插入到散列表中。(1) 使用線性探查再散列法來構造散列表。(2) 使用鏈地址法構造散列表。針對這兩種情況, 確定其裝載因子, 搜索成功所需的平均探查次數(shù), 以及搜索不成功所需的平均探查次數(shù)。解：(1)Hash(1)=1；成功hash(13)=2；成功hash(12)=1；沖突；hash(12)=2；沖突；hash(12)=3；成功；hash(34)=1；hash(34)=2；沖突；hash(34)=3；沖突；hash(34)=3；沖突；hash(34)=4；成功hash(38)=5；成功hash(33)=0；成功hash(27)=5；沖突； hash(27)=6；成功hash(22)=0；沖突；hash(22)=1；沖突；hash(22)=2；沖突；hash(22)=3；沖突；hash(22)=4；沖突；hash(22)=5；沖突；hash(22)=6；沖突；hash(22)=7；成功線性探查再散列法來構造的散列表012345678910331131234382722搜索次數(shù)11134128裝載因子