數(shù)據(jù)結構第九章--查找-習題及答案

1、第九章查找選擇題1 .假設查找每個記錄的概率均等,那么在具有n個記錄的連續(xù)順序文件中采用順序查找法查找一個記錄,其平均查找長度人$1為.A.n-1/2B.n/2C.n+1/2D.n2 .下面關于二分查找的表達正確的選項是A.表必須有序,表可以順序方式存儲,也可以鏈表方式存儲C.表必須有序,而且只能從小到大排列B.表必須有序且表中數(shù)據(jù)必須是整型,實型或字符型D.表必須有序,且表只能以順序方式存儲3 .用二分對半查找表的元素的速度比用順序法A.必然快B.必然慢C.相等D.不能確定4 .具有12個關鍵字的有序表,折半查找的平均查找長度A.3.1B.4C.2.5D.55 .當采用分塊查找時,數(shù)據(jù)的組織

2、方式為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ù)需相同在2時其查找效率最低樹型D.結點的位置呈單枝樹D.結點太復雜.,在等概率查找的情況下,對于查找失,他們的平均查找長度是2供選擇6 .二叉查找樹的查找效率與二叉樹的1有關,1：A.高度B.結點的多少C.2:A.結點太多B.完全二叉樹C.7 .對大小均為n的有序表和無序表分別進行順序查找敗,它們的平均查找長度是1,對于查找成功的答案：A.相同的B

3、.不同的9 .分別以以下序列構造二叉排序樹,與用其它三個序列所構造的結果不同的是A.100,80,90,60,120,110,130B.100,120,110,130,80,60,90C.100,60,80,90,120,110,130D.100,80,60,90,120,130,11010 .在平衡二叉樹中插入一個結點后造成了不平衡,設最低的不平衡結點為A,并A的左孩子的平衡因子為0右孩子的平衡因子為1,那么應作型調(diào)整以使其平衡.A.LLB.LRC.RLD.RR11.下面關于m階B-樹說法正確的選項是每個結點至少有兩棵非空子樹；所有葉子在同一層上；長tWj層.A.B.C.樹中每個結點至多有m

4、1個關鍵字；當插入一個數(shù)據(jù)項引起B(yǎng)樹結點分裂后,樹D.12. m階B-樹是一棵C.m-1叉平衡排序樹D.m+1叉平衡排序樹A.m叉排序樹B.m叉平衡排序樹15 .設有一組記錄的關鍵字為19,14,23,1,68,20,84,27,55,11,10,79,用鏈地址法構造散列表,散列函數(shù)為Hkey=keyMOD3,散列地址為1的鏈中有個記錄.A.1B.2C.3D.416 .關于哈希查找說法不正確的有幾個1采用鏈地址法解決沖突時,查找一個元素的時間是相同的2采用鏈地址法解決沖突時,假設插入規(guī)定總是在鏈首,那么插入任一個元素的時間是相同的3用鏈地址法解決沖突易引起聚集現(xiàn)象4再哈希法不易產(chǎn)生聚集A.1B

5、.2C.3D.417 .設哈希表長為14,哈希函數(shù)是Hkey=key%11,表中已有數(shù)據(jù)的關鍵字為15,38,61,84共四個,現(xiàn)要將關鍵字為49的結點加到表中,用二次探測再散列法解決沖突,那么放入的位置是A.8B.3C.5D.918 .假定哈希查找中k個關鍵字具有同一哈希值,假設用線性探測法把這k個關鍵字存入散列表中,至少要進行多少次探測？A.k-1次B.k次C.k+1次D.kk+1/2次19 .好的哈希函數(shù)有一個共同的性質(zhì),即函數(shù)值應當以取其值域的每個值.A.最大概率B.最小概率C.平均概率D.同等概率20 .將10個元素散列到100000個單元的哈希表中,那么產(chǎn)生沖突.A.一定會B.一定

6、不會C.仍可能會二、判斷題1 .采用線性探測法處理散列時的沖突,當從哈希表刪除一個記錄時,不應將這個記錄的所在位置置空,由于這會影響以后的查找.2 .在散列檢索中,“比擬操作一般也是不可防止的.3 .Hash表的平均查找長度與處理沖突的方法無關.4 .散列法的平均檢索長度不隨表中結點數(shù)目的增加而增加,而是隨負載因子的增大而增大.5 .在索引順序表中,實現(xiàn)分塊查找,在等概率查找情況下,其平均查找長度不僅與表中元素個數(shù)有關,而且與每塊中元素個數(shù)有關.6 .就平均查找長度而言,分塊查找最小,折半查找次之,順序查找最大.7 .最正確二叉樹是AVL樹平衡二叉樹.8 .在查找樹二叉樹排序樹中插入一個新結點

7、,總是插入到葉結點下面.9 .二叉樹中除葉結點外,任一結點X,其左子樹根結點的值小于該結點X的值；其右子樹根結點的值?該結點X的值,那么此二叉樹一定是二叉排序樹.10 .有n個數(shù)存放在一維數(shù)組A1.n中,在進行順序查找時,這n個數(shù)的排列有序或無序其平均查找長度不同.11 .N個結點的二叉排序樹有多種,其中樹高最小的二叉排序樹是最正確的.12 .在任意一棵非空二叉排序樹中,刪除某結點后又將其插入,那么所得二排序叉樹與原二排序叉樹相同.13 .B-樹中所有結點的平衡因子都為零.14 .在平衡二叉樹中,向某個平衡因子不為零的結點的樹中插入一新結點,必引起平衡旋轉(zhuǎn).三、填空題1 .順序查找n個元素的順

8、序表,假設查找成功,那么比擬關鍵字的次數(shù)最多為次；當使用監(jiān)視哨時,假設查找失敗,那么比擬關鍵字的次數(shù)為.2 .在有序表A1.12中,采用二分查找算法查等于A12的元素,所比擬的元素下標依次為.3 .在有序表A1.20中,按二分查找方法進行查找,查找長度為5的元素個數(shù)是4 .高度為4含葉子結點層的3階b-樹中,最多有個關鍵字.5 .在一棵m階B-樹中,假設在某結點中插入一個新關鍵字而引起該結點分裂,那么此結點中原有的關鍵字的個數(shù)是；假設在某結點中刪除一個關鍵字而導致結點合并,那么該結點中原有的關鍵字的個數(shù)是.6 .在哈希函數(shù)Hkey=key%p中,p值最女?取.8 .如果按關鍵碼值遞增的順序依次

9、將關鍵碼值插入到二叉排序樹中,那么對這樣的二叉排序樹檢索時,平均比擬次數(shù)為.9 .如果關鍵碼按值排序,而后用二分法依次檢索這些關鍵碼,并把檢索中遇到的在二叉樹中沒有出現(xiàn)的關鍵碼依次插入到二叉排序樹中,那么對這樣的二叉排序樹檢索時,平均比較次數(shù)為.(提示：此時二叉排序樹與折半查找的二叉判定樹一樣了)10 .平衡因子的定義是=11 .查找是非數(shù)值程序設計的一個重要技術問題,根本上分成_(1)_查找,應匚查找和_(3)_查找.處理哈希沖突的方法有_(4)_、_(5)_、_(6)_和.12 .具有N個關鍵字的B樹的查找路徑長度不會入廠.！1二棵有N"高點的非平衡二叉樹中進行查找,平均時間復雜

10、度的上限(即最壞情況平均時間復雜度)為13 .高度為5(除葉子層之外)的三階B-樹至少有個結點.14 .可以唯一的標識一個記錄的關鍵字稱為.15 .動態(tài)查找表和靜態(tài)查找表的重要區(qū)別在于前者包含有和運算,而后者不包含這兩種運算.16 .N元整型數(shù)組a存放N個學生的成績,已按由大到小排序,以下算法是用對分(折半)查找方法統(tǒng)計成績大于或等于X分的學生人數(shù),請?zhí)羁帐怪晟?(提示：這時需要找的是最后一個大于等于X的下標,假設查找成功其下標假設為m,那么有m個學生成績大于或等于X,假設查找不成功,假設這時low所指向的值小于X,那么有l(wèi)ow-1個學生成績大于或等于X,注意這時表中可能不止一個數(shù)值為X的值

11、,這時我們要查找的是下標最大的)#defineN/*學生人數(shù)*/intuprx(intaN,intx)/*函數(shù)返回大于等于X分的學生人數(shù)*/intlow=1,mid,high=N;domid=(low+high)/2;if(x<=amid)_(1)else_(2)_;while(_(3)"if(alow<x)returnlow-1;returnlow;四、應用題1.名詞解釋：哈希表表達B-樹定義,主要用途是什么？平衡二叉樹(AVL樹)平衡因子平均查找長度(ASL)3 .設有一組關鍵字9,01,23,14,55,20,84,27,采用哈希函數(shù)：H(key)=keymod7,

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

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

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

15、1.B12.B15.D16.B17.D18.D19.D20.C.判斷題1.V2.V3.x4.V5.V6.X7.V8.x9.x10.X11.V12.X13.V14.X三.填空題1.nn+12.6,9,11,123.54. 26(第4層是葉子結點,每個結點兩個關鍵字).2,4,320的質(zhì)因子的合數(shù)5. m-1,m/2-196. .小于等于表長的最大素數(shù)或不包含小于8.(n+1)/29.(n+1)/n*log2(n+1)-110,結點的左子樹的高度減去結點的右子樹的高度11. (1)靜態(tài)查找表(2)動態(tài)查找樹表(3)哈希表(4)開放定址方法(5)鏈地址方法(6)再哈希建立公共溢出區(qū)n112. log

16、m/2(2)+1,(n+1)/2(最壞情況是每個結點只要一個孩子結點的情況,這時的平均時間復雜度為(n+1)/2,而10g(J5(n1)2是通常情況下的ASL)13. 3114. 主關鍵字15. 插入刪除16(1)1ow=mid+1(2)high=mid-1(3)high>=1ow四.應用題1.概念是根本知識的主要局部,要牢固掌握.這里只列出一局部,目的是引起重視,解答略.3.散列地址0123456789關鍵字140192384275520比擬次數(shù)11123412查找成功平均查找長度：AS&cc=(1+1+1+2+3+4+1+2)/8=15/8以關鍵字27為例：H(27)=27%

17、7=6(沖突)H1=(6+1)%10=7(沖突)Hb=(6+22)%10=0(沖突)H3=(6+33)%10=5所以比擬了4次.注意：計算查找失敗時的平均查找長度,必須計算不在表中的關鍵字,當其哈希地址為i(0WiWm-1)時的查找次數(shù).如下例中m=1Q對于關鍵字集30,15,21,40,25,26,36,37假設查找表的裝填因子為0.8,哈希函數(shù)為H(key)=key%7采用線性探測再散列方法解決沖突,那么哈希表如下：散列地址0123456789關鍵字2115303625402637比擬次數(shù)11131126故查找失敗時的平均查找長度為：ASLnsucc=(4+8+7+6+5+4+3+2+1+1)/10=4.64.0123456789012-11XASL查找成功=18/137.如以下圖：9. (1)當插入26后的樹形為:插入85后樹形為:(2)刪除53后為:刪除37后:(4)刪除結點66后;10.(1)構