數(shù)據(jù)結(jié)構(gòu)第九章查找 習(xí)題及答案

1、第九章 查找一、 選擇題1.若查找每個記錄的概率均等，則在具有n個記錄的連續(xù)順序文件中采用順序查找法查找一個記錄，其平均查找長度ASL為( )。 A (n-1)/2 B. n/2 C. (n+1)/2 D. n2. 下面關(guān)于二分查找的敘述正確的是 ( ) A. 表必須有序，表可以順序方式存儲，也可以鏈表方式存儲 C. 表必須有序，而且只能從小到大排列B. 表必須有序且表中數(shù)據(jù)必須是整型，實型或字符型 D. 表必須有序，且表只能以順序方式存儲3. 用二分（對半）查找表的元素的速度比用順序法( )A必然快 B. 必然慢 C. 相等 D. 不能確定4. 具有12個關(guān)鍵字的有序表，折半查找的平均查找長

2、度（ ） A. 3.1 B. 4 C. 2.5 D. 55當(dāng)采用分塊查找時，數(shù)據(jù)的組織方式為 ( ) A數(shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)有序B數(shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)不必有序，但塊間必須有序，每塊內(nèi)最大（或最?。┑臄?shù)據(jù)組成索引塊C. 數(shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)有序，每塊內(nèi)最大（或最?。┑臄?shù)據(jù)組成索引塊D. 數(shù)據(jù)分成若干塊，每塊（除最后一塊外）中數(shù)據(jù)個數(shù)需相同6. 二叉查找樹的查找效率與二叉樹的( （1）)有關(guān), 在 (（2）)時其查找效率最低 (1): A. 高度 B. 結(jié)點的多少 C. 樹型 D. 結(jié)點的位置 (2): A. 結(jié)點太多 B. 完全二叉樹 C. 呈單枝樹 D. 結(jié)點太復(fù)雜。7. 對

3、大小均為n的有序表和無序表分別進(jìn)行順序查找,在等概率查找的情況下,對于查找失敗,它們的平均查找長度是(1) ,對于查找成功,他們的平均查找長度是(2)供選擇的答案: A. 相同的 B.不同的9分別以下列序列構(gòu)造二叉排序樹，與用其它三個序列所構(gòu)造的結(jié)果不同的是( ) A（100，80， 90， 60， 120，110，130） B.（100，120，110，130，80， 60， 90）C.（100，60， 80， 90， 120，110，130） D. (100，80， 60， 90， 120，130，110)10. 在平衡二叉樹中插入一個結(jié)點后造成了不平衡，設(shè)最低的不平衡結(jié)點為A,并已知A的

4、左孩子的平衡因子為0右孩子的平衡因子為1,則應(yīng)作( ) 型調(diào)整以使其平衡。A. LL B. LR C. RL D. RR11. 下面關(guān)于m階B-樹說法正確的是( ) 每個結(jié)點至少有兩棵非空子樹； 樹中每個結(jié)點至多有m一1個關(guān)鍵字; 所有葉子在同一層上; 當(dāng)插入一個數(shù)據(jù)項引起B(yǎng)樹結(jié)點分裂后，樹長高一層。A B. C. D. 12. m階B-樹是一棵( ) A. m叉排序樹 B. m叉平衡排序樹 C. m-1叉平衡排序樹 D. m+1叉平衡排序樹15. 設(shè)有一組記錄的關(guān)鍵字為19，14，23，1，68，20，84，27，55，11，10，79，用鏈 地址法構(gòu)造散列表，散列函數(shù)為H（key）=key

5、 MOD 13,散列地址為1的鏈中有（ ） 個記錄。A1 B. 2 C. 3 D. 416. 關(guān)于哈希查找說法不正確的有幾個( ) （1）采用鏈地址法解決沖突時，查找一個元素的時間是相同的 （2）采用鏈地址法解決沖突時，若插入規(guī)定總是在鏈?zhǔn)祝瑒t插入任一個元素的時間是相同的 （3）用鏈地址法解決沖突易引起聚集現(xiàn)象 （4）再哈希法不易產(chǎn)生聚集A. 1 B. 2 C. 3 D. 417. 設(shè)哈希表長為14，哈希函數(shù)是H(key)=key%11,表中已有數(shù)據(jù)的關(guān)鍵字為15，38，61，84共四個，現(xiàn)要將關(guān)鍵字為49的結(jié)點加到表中，用二次探測再散列法解決沖突，則放入的位置是( ) A8 B3 C5 D9

6、 18. 假定哈希查找中k個關(guān)鍵字具有同一哈希值，若用線性探測法把這k個關(guān)鍵字存入散列表中，至少要進(jìn)行多少次探測？( ) Ak-1次 B. k次 C. k+1次 D. k（k+1）/2次19. 好的哈希函數(shù)有一個共同的性質(zhì)，即函數(shù)值應(yīng)當(dāng)以( )取其值域的每個值。A. 最大概率 B. 最小概率 C. 平均概率 D. 同等概率20. 將10個元素散列到100000個單元的哈希表中，則（ ）產(chǎn)生沖突。A. 一定會 B. 一定不會 C. 仍可能會二、 判斷題1采用線性探測法處理散列時的沖突，當(dāng)從哈希表刪除一個記錄時，不應(yīng)將這個記錄的所在位置置空，因為這會影響以后的查找。（ ）2在散列檢索中，“比較”操

7、作一般也是不可避免的。（ ）3Hash表的平均查找長度與處理沖突的方法無關(guān)。 （ ）4. 散列法的平均檢索長度不隨表中結(jié)點數(shù)目的增加而增加，而是隨負(fù)載因子的增大而增大。（ ）5. 在索引順序表中，實現(xiàn)分塊查找，在等概率查找情況下，其平均查找長度不僅與表中元素個數(shù)有關(guān)，而且與每塊中元素個數(shù)有關(guān)。（ ）6. 就平均查找長度而言，分塊查找最小，折半查找次之，順序查找最大。（ ）7 最佳二叉樹是AVL樹（平衡二叉樹）。（ ）8在查找樹（二叉樹排序樹）中插入一個新結(jié)點，總是插入到葉結(jié)點下面。 （ ）9二叉樹中除葉結(jié)點外, 任一結(jié)點X，其左子樹根結(jié)點的值小于該結(jié)點（X）的值；其右子樹根結(jié)點的值該結(jié)點（X）

8、的值,則此二叉樹一定是二叉排序樹。（ ）10有n個數(shù)存放在一維數(shù)組A1.n中，在進(jìn)行順序查找時，這n個數(shù)的排列有序或無序其平均查找長度不同。（ ）11. N個結(jié)點的二叉排序樹有多種，其中樹高最小的二叉排序樹是最佳的。 （ ）12. 在任意一棵非空二叉排序樹中，刪除某結(jié)點后又將其插入，則所得二排序叉樹與原二排序叉樹相同。（ ）13. B-樹中所有結(jié)點的平衡因子都為零。 （ ）14. 在平衡二叉樹中，向某個平衡因子不為零的結(jié)點的樹中插入一新結(jié)點，必引起平衡旋轉(zhuǎn)。（ ）三、填空題1. 順序查找n個元素的順序表，若查找成功，則比較關(guān)鍵字的次數(shù)最多為_ _次；當(dāng)使用監(jiān)視哨時，若查找失敗，則比較關(guān)鍵字的次

9、數(shù)為_ _。2在有序表A1.12中，采用二分查找算法查等于A12的元素，所比較的元素下標(biāo)依次為_。3. 在有序表A1.20中，按二分查找方法進(jìn)行查找，查找長度為5的元素個數(shù)是_4. 高度為4（含葉子結(jié)點層）的3階b-樹中，最多有_個關(guān)鍵字。5. 在一棵m階B-樹中,若在某結(jié)點中插入一個新關(guān)鍵字而引起該結(jié)點分裂,則此結(jié)點中原有的關(guān)鍵字的個數(shù)是_;若在某結(jié)點中刪除一個關(guān)鍵字而導(dǎo)致結(jié)點合并,則該結(jié)點中原有的關(guān)鍵字的個數(shù)是_。6. 在哈希函數(shù)H（key）=key%p中，p值最好取_。8. 如果按關(guān)鍵碼值遞增的順序依次將關(guān)鍵碼值插入到二叉排序樹中，則對這樣的二叉排序 樹檢索時，平均比較次數(shù)為_。 9.

10、如果關(guān)鍵碼按值排序，而后用二分法依次檢索這些關(guān)鍵碼，并把檢索中遇到的在二叉樹中沒有出現(xiàn)的關(guān)鍵碼依次插入到二叉排序樹中，則對這樣的二叉排序樹檢索時，平均比較次數(shù)為_。（提示：此時二叉排序樹與折半查找的二叉判定樹一樣了）10. 平衡因子的定義是_ _11. 查找是非數(shù)值程序設(shè)計的一個重要技術(shù)問題，基本上分成_(1)_查找，_(2)_查找和_(3)_查找。處理哈希沖突的方法有_(4)_、_(5)_、_(6)_和_(7)_。12. 具有N個關(guān)鍵字的B樹的查找路徑長度不會大于_。在一棵有N 個結(jié)點的非平衡二叉樹中進(jìn)行查找，平均時間復(fù)雜度的上限（即最壞情況平均時間復(fù)雜度）為_13. 高度為5（除葉子層之外

11、）的三階B-樹至少有_個結(jié)點。14. 可以唯一的標(biāo)識一個記錄的關(guān)鍵字稱為_。15. 動態(tài)查找表和靜態(tài)查找表的重要區(qū)別在于前者包含有_和_運算，而后者不包含這兩種運算。16. 已知N元整型數(shù)組a存放N個學(xué)生的成績，已按由大到小排序，以下算法是用對分（折半）查找方法統(tǒng)計成績大于或等于X分的學(xué)生人數(shù)，請?zhí)羁帐怪晟啤? 提示：這時需要找的是最后一個大于等于X的下標(biāo)，若查找成功其下標(biāo)若為m，則有m個學(xué)生成績大于或等于X，若查找不成功，若這時low所指向的值小于X，則有l(wèi)ow-1個學(xué)生成績大于或等于X，注意這時表中可能不止一個數(shù)值為X的值，這時我們要查找的是下標(biāo)最大的)#define N /*學(xué)生人數(shù)*

12、/int uprx(int aN,int x ) /*函數(shù)返回大于等于X分的學(xué)生人數(shù)*/ int low=1,mid,high=N; do mid=(low+high)/2;if(x<=amid) _(1)_ else _(2)_;while(_(3)_);if (alow<x) return low-1;return low; 四、應(yīng)用題1. 名詞解釋：哈希表敘述B-樹定義，主要用途是什么？ 平衡二叉樹（AVL樹）平衡因子 平均查找長度（ASL）3. 設(shè)有一組關(guān)鍵字9,01,23,14,55,20,84,27，采用哈希函數(shù)：H（key）=key mod 7 ，表長為10，用開放地

13、址法的二次探測再散列方法解決沖突Hi=(H(key)+di) mod 10(di=12,22,32,)。要求：對該關(guān)鍵字序列構(gòu)造哈希表，并確定其裝填因子，查找成功所需的平均探查次數(shù)。4. 設(shè)一組數(shù)據(jù)為1,14,27,29,55,68,10,11,23，現(xiàn)采用的哈希函數(shù)是H(key)=key MOD 13， 即關(guān)鍵字對13取模，沖突用鏈地址法解決，設(shè)哈希表的大小為13(0.12)，試畫出插入上述數(shù)據(jù)后的哈希表。7. 設(shè)有一棵空的階B-樹，依次插入關(guān)鍵字30,20,10,40,80,58,47,50,29,22,56,98,99，請畫出該樹。9. 已知2棵2-3 B-樹如下（省略外結(jié)點）： （1）

14、 對樹（a）,請分別畫出先后插入26，85兩個新結(jié)點后的樹形；（2） 對樹（b）,請分別畫出先后刪除53，37兩個結(jié)點后的樹形。(a) （b） 10. 輸入一個正整數(shù)序列（53,17,12,66,58,70,87,25,56,60），試完成下列各題。（1） 按次序構(gòu)造一棵二叉排序樹BS。（2） 依此二叉排序樹，如何得到一個從大到小的有序序列？（3） 假定每個元素的查找概率相等，試計算該二叉排序樹的平均查找長度（4） 畫出在此二叉排序樹中刪除“66”后的樹結(jié)構(gòu)。11. 給定關(guān)鍵詞輸入序列CAP,AQU,PIS,ARI,TAU,GEM,CAN,LIB,VIR,LEO,SCO，假定關(guān)鍵詞比較按英文字

15、典序，試畫出從一棵空樹開始，依上述順序（從左到右）輸入關(guān)鍵詞，用平衡樹的查找和插入算法生成一棵平衡樹的過程，并說明生成過程中采用了何種轉(zhuǎn)動方式進(jìn)行平衡調(diào)整，標(biāo)出樹中各結(jié)點的平衡系數(shù)。12. 假定對有序表：(3,4,5,7,24,30,42,54,63,72,87,95)進(jìn)行折半查找，試回答下列問題：(1).畫出描述折半查找過程的判定樹；(2).若查找元素54，需依次與那些元素比較?(3).若查找元素90，需依次與那些元素比較?(4).假定每個元素的查找概率相等，求查找成功時的平均查找長度。第9章 查找一選擇題 1.C2.D3D4.A5.B6.1C6.2C7.1B7.2A9.C10.C11.B1

16、2.B15.D16.B17.D18.D19.D20.C二判斷題1.2.3.×4.5.6.×7.8.×9.×10.×11. 12.×13.14.×三填空題1n n+1 26,9,11,12 35 426（第4層是葉子結(jié)點，每個結(jié)點兩個關(guān)鍵字） 5m-1,m/2ù-1 92,4,36小于等于表長的最大素數(shù)或不包含小于20的質(zhì)因子的合數(shù) 8(n+1)/2 9(n+1)/n*log2(n+1)-1 10結(jié)點的左子樹的高度減去結(jié)點的右子樹的高度11(1)靜態(tài)查找表(2)動態(tài)查找樹表(3)哈希表(4)開放定址方法(5)鏈地址方

17、法(6)再哈希(7)建立公共溢出區(qū)12logém/2ù()+1 ，(n+1)/2（最壞情況是每個結(jié)點只要一個孩子結(jié)點的情況，這時的平均時間復(fù)雜度為（n+1）/2,而是通常情況下的ASL） 1331 14主關(guān)鍵字 15插入 刪除 16(1)low=mid+1 (2)high=mid-1 (3)high>=low四應(yīng)用題1概念是基本知識的主要部分，要牢固掌握。這里只列出一部分，目的是引起重視，解答略。3 散列地址0123456789關(guān)鍵字140192384275520比較次數(shù)1112 3 412查找成功平均查找長度：ASLsucc=（1+1+1+2+3+4+1+2）/8=

18、15/8以關(guān)鍵字27為例：H（27）=27%7=6（沖突） H1=（6+1）%10=7（沖突） H2=（6+22）%10=0（沖突） H3=（6+33）%10=5 所以比較了4次。注意：計算查找失敗時的平均查找長度，必須計算不在表中的關(guān)鍵字，當(dāng)其哈希地址為i（0im-1）時的查找次數(shù)。如下例中m=10。對于關(guān)鍵字集30,15,21,40,25,26,36,37若查找表的裝填因子為0.8，哈希函數(shù)為H（key）=key % 7采用線性探測再散列方法解決沖突，則哈希表如下：散列地址0123456789關(guān)鍵字2115303625402637比較次數(shù)11131126故查找失敗時的平均查找長度為：ASLunsucc=（4+8+7+6+5+4+3+2+1+1）/10=4.64.ASL查找成功=18/137.如下圖：9（1）當(dāng)插入26后的樹形為：插入85后樹形為：（2）刪除53后為：刪除37后：