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

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

2、方式為A.數(shù)據(jù)分成假設(shè)干塊,每塊內(nèi)數(shù)據(jù)有序B.數(shù)據(jù)分成假設(shè)干塊,每塊內(nèi)數(shù)據(jù)不必有序,但塊間必須有序,每塊內(nèi)最大或最小的數(shù)據(jù)組成索引塊C.數(shù)據(jù)分成假設(shè)干塊,每塊內(nèi)數(shù)據(jù)有序,每塊內(nèi)最大或最小的數(shù)據(jù)組成索引塊D.數(shù)據(jù)分成假設(shè)干塊,每塊除最后一塊外中數(shù)據(jù)個(gè)數(shù)需相同在2時(shí)其查找效率最低樹型D.結(jié)點(diǎn)的位置呈單枝樹D.結(jié)點(diǎn)太復(fù)雜.,在等概率查找的情況下,對(duì)于查找失,他們的平均查找長(zhǎng)度是2供選擇6 .二叉查找樹的查找效率與二叉樹的1有關(guān),1：A.高度B.結(jié)點(diǎn)的多少C.2:A.結(jié)點(diǎn)太多B.完全二叉樹C.7 .對(duì)大小均為n的有序表和無序表分別進(jìn)行順序查找敗,它們的平均查找長(zhǎng)度是1,對(duì)于查找成功的答案：A.相同的B

3、.不同的9 .分別以以下序列構(gòu)造二叉排序樹,與用其它三個(gè)序列所構(gòu)造的結(jié)果不同的是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 .在平衡二叉樹中插入一個(gè)結(jié)點(diǎn)后造成了不平衡,設(shè)最低的不平衡結(jié)點(diǎn)為A,并A的左孩子的平衡因子為0右孩子的平衡因子為1,那么應(yīng)作型調(diào)整以使其平衡.A.LLB.LRC.RLD.RR11.下面關(guān)于m階B-樹說法正確的選項(xiàng)是每個(gè)結(jié)點(diǎn)至少有兩棵非空子樹；所有葉子在同一層上；長(zhǎng)tWj層.A.B.C.樹中每個(gè)結(jié)點(diǎn)至多有m

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

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

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

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

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

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

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

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

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

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

14、典序,試畫出從一棵空樹開始,依上述順序(從左到右)輸入關(guān)鍵詞,用平衡樹的查找和插入算法生成一棵平衡樹的過程,并說明生成過程中采用了何種轉(zhuǎn)動(dòng)方式進(jìn)行平衡調(diào)整,標(biāo)出樹中各結(jié)點(diǎn)的平衡系數(shù).12 .假定對(duì)有序表：(3,4,5,7,24,30,42,54,63,72,87,95)進(jìn)行折半查找,試答復(fù)以下問題:(1) .畫出描述折半查找過程的判定樹；(2) .假設(shè)查找元素54,需依次與那些元素比擬？(3) .假設(shè)查找元素90,需依次與那些元素比擬？(4) .假定每個(gè)元素的查找概率相等,求查找成功時(shí)的平均查找長(zhǎng)度.第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層是葉子結(jié)點(diǎn),每個(gè)結(jié)點(diǎn)兩個(gè)關(guān)鍵字).2,4,320的質(zhì)因子的合數(shù)5. m-1,m/2-196. .小于等于表長(zhǎng)的最大素?cái)?shù)或不包含小于8.(n+1)/29.(n+1)/n*log2(n+1)-110,結(jié)點(diǎn)的左子樹的高度減去結(jié)點(diǎn)的右子樹的高度11. (1)靜態(tài)查找表(2)動(dòng)態(tài)查找樹表(3)哈希表(4)開放定址方法(5)鏈地址方法(6)再哈希建立公共溢出區(qū)n112. log

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

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