數(shù)據(jù)結(jié)構(gòu)第五章查找答案

1、數(shù)據(jù)結(jié)構(gòu)與算法上機(jī)作業(yè)第五章查找、選擇題1若構(gòu)造一棵具有n個(gè)結(jié)點(diǎn)的二叉排序樹，在最壞情況下，其高度不超過BA.n/2B.nC.(n+l)/2D.n+12、分別以下列序列構(gòu)造二叉排序數(shù)(二叉查找樹)，與用其他3個(gè)序列所構(gòu)造的結(jié)果不同的是C:A.(100,80,90,60,120,110,130)B.(100,120,110,C.(100,60,80,90,120,110,130)D.(100,80,60,93、不可能生成下圖所示的二叉排序樹的關(guān)鍵字的序列是AA.453B.42531C.45213124、在二叉平衡樹中插入一個(gè)結(jié)點(diǎn)造成了不平衡，設(shè)最低的不平衡點(diǎn)為子的平衡因子為0,右孩子的平衡因子為

2、1,則應(yīng)作_cA.LLB.LRC.RLD.RR5、一棵高度為k的二叉平衡樹，其每個(gè)非葉結(jié)點(diǎn)的平衡因子均為結(jié)點(diǎn)。k-lk-1kk.A.2-1B.2+1C.2-1D.2+16、具有5層結(jié)點(diǎn)的平衡二叉樹至少有A個(gè)結(jié)點(diǎn)。A.12B.11C.10D.97、下面關(guān)于B-和B+樹的敘述中，不正確的是_CA.B-樹和B+樹都是平衡的多叉樹130,80,60,90)>0,120,130,110)OD.42315A,并已知A的左孩型調(diào)整使其平衡。0,則該樹共有_C個(gè)B.B-樹和B+樹都可用于文件的索引結(jié)構(gòu)C. B-樹和B+樹都能有效地支持順序檢索D. B-樹和B+樹都能有效地支持隨機(jī)檢索8、下列關(guān)于ni階B

3、-樹的說法錯(cuò)誤的是_D。A.根結(jié)點(diǎn)至多有m棵子樹B.所有葉子結(jié)點(diǎn)都在同一層次C.非葉結(jié)點(diǎn)至少有m/2（m為偶數(shù)）或m/2+1（m為奇數(shù)）棵子樹D.根結(jié)點(diǎn)中的數(shù)據(jù)是有序的9、下面關(guān)于哈希查找的說法正確的是C。A.哈希函數(shù)構(gòu)造得越復(fù)雜越好，因?yàn)檫@樣隨機(jī)性好，沖突小B.除留余數(shù)法是所有哈希函數(shù)中最好的C.不存在特別好與壞的哈希函數(shù)，要視情況而定D.若需在哈希表中刪去一個(gè)元素，不管用何種方法解決沖突都只要簡單地將該元素刪去即可10、與其他查找方法相比，散列查找法的特點(diǎn)是_C。A.通過關(guān)鍵字的比較進(jìn)行查找B.通過關(guān)鍵字計(jì)算元素的存儲(chǔ)地址進(jìn)行查找C.通過關(guān)鍵字計(jì)算元素的存儲(chǔ)地址并進(jìn)行一定的比較進(jìn)行查找D.

4、以上都不是11、有一組關(guān)鍵字8,24,16,3,12,32,51）,采用除留余數(shù)法構(gòu)造散列函數(shù)：H（key）=keymod12,則將發(fā)生次沖突。A.3B.4C.5D.612、有一個(gè)結(jié)點(diǎn)的關(guān)鍵字為83,采用移位疊加法生成4位散列地址，則生成的地址為BoA.3482B.3583C.9018D.9019、填空題1、在查找過程中有插入或刪除元素操作的，稱為動(dòng)態(tài)查找。2、一個(gè)無序序列可以通過構(gòu)造一棵二叉排序樹而變?yōu)橐粋€(gè)有序序列，構(gòu)造樹的過程即為對(duì)無序序列進(jìn)行排序的過程。3、對(duì)于一棵二叉排序樹，按生根方法遍歷得出的結(jié)點(diǎn)序列是從小到大排列的。4、對(duì)二叉排序樹進(jìn)行查找的方法是用待查找的值與根結(jié)點(diǎn)的鍵值進(jìn)行比較

5、，若比根結(jié)點(diǎn)的值小，則繼續(xù)在左子樹中查找。5、AVL樹為在構(gòu)造二叉排序樹時(shí)，為確保搜索的性能而保持樹的平衡，保持平衡的方法為在構(gòu)建AVL樹時(shí)根據(jù)特定條件而進(jìn)行LL,RR,LR,RL四種旋轉(zhuǎn)操作，如對(duì)于下圖的樹，應(yīng)該進(jìn)行RLRR旋轉(zhuǎn)。段；19322740274026新插入結(jié)點(diǎn)新插入結(jié)點(diǎn)K456、在m階一棵B-樹中，若在某個(gè)結(jié)點(diǎn)中插入一個(gè)新關(guān)鍵字而引起該結(jié)點(diǎn)分裂，則此結(jié)點(diǎn)中原有的關(guān)鍵字的個(gè)數(shù)是mzl；若在某結(jié)點(diǎn)中刪除一個(gè)關(guān)鍵字而導(dǎo)致結(jié)點(diǎn)合并，則該結(jié)點(diǎn)中原有的關(guān)鍵字的個(gè)數(shù)是m2原o7、127階B-樹中每個(gè)結(jié)點(diǎn)最多有弊個(gè)關(guān)鍵字；除根結(jié)點(diǎn)外所有非終端結(jié)點(diǎn)至少有棵子樹；65階B+樹中，除根結(jié)點(diǎn)外所有非葉結(jié)

6、點(diǎn)至少有33個(gè)關(guān)鍵字，最多有區(qū)棵子樹8、假設(shè)有k個(gè)關(guān)鍵字互為同義詞(哈希值相同)，若用線性探測再散列法把這k個(gè)關(guān)鍵字存入散列表中，至少要進(jìn)行入k-1)/2次探測。9、在散列排序法中，折疊法的哈希函數(shù)可分為移位法和分界法兩種類型。10、散列法的填充因子二o11、設(shè)散列函數(shù)H和關(guān)鍵字kl,k2,若kl不等于k2,而H(kl)=H(k2),則稱這種現(xiàn)象為沖突o12、在哈希函數(shù)H(key)=key%p中，p一般應(yīng)取不大于表長的質(zhì)數(shù)或是不含20以下的質(zhì)因數(shù)的合數(shù)三、依次輸入表(30,15,28,20,24,10,12,68,35,50,46,55)中的元素，生成一棵二叉排序數(shù)，要求：1 、試畫出生成之后

7、的二叉排序樹。2 、對(duì)該二叉排序數(shù)作中根遍歷，寫出遍歷序列。3 、編程構(gòu)建一個(gè)二叉排序數(shù)，并中根遍歷驗(yàn)證上述結(jié)果。四、二叉排序樹如下圖所示，分別畫出：1 、刪除關(guān)鍵字15以后的二叉樹，并要求平均查找長度盡可能小。2 、在原二叉排序樹(即沒有刪除15)上，插入關(guān)鍵字20五、編寫一個(gè)判別給定二叉樹是否為二叉排序樹的算法，假設(shè)二叉樹是用左右鏈方式存儲(chǔ)。六、試畫出從空樹開始，有字符序列(t,d,e,s,u,g,b,j,a,k,r,i)構(gòu)成的二叉平衡樹，并為每一次平衡處理指明旋轉(zhuǎn)類型。七、假設(shè)一棵平衡二叉樹的每個(gè)結(jié)點(diǎn)都標(biāo)明了平衡因子b,試設(shè)計(jì)一個(gè)算法，利用平衡因子求平衡二叉樹的高度。八、設(shè)有三階B-樹(

8、如下圖所示)、畫出依次插入18、33、97后的B-樹、分別回出刪除66、16>43后的B-樹九、給定一組記錄，其關(guān)鍵字為字符。各關(guān)鍵字插入順序?yàn)镃,S,M,T,A,E,P,U,X,K,G,B1、給出從空樹開始，順序插入這些關(guān)鍵字后的3階B+樹假設(shè)葉節(jié)點(diǎn)所能容納最大關(guān)鍵碼的數(shù)量為4。2、分別給出在建立的B+樹上刪除E、P、T后的3階B+樹十、畫出如下數(shù)據(jù)集合的Trie樹：Amiot,Avenger,Avro,Heinkel,HellDivder,Macchi,Marauder,Mustang,SpitFire,Sykhoi。1 、對(duì)關(guān)鍵字實(shí)行從左到右一次一個(gè)字符采樣2 、利用單字符采樣，在上述數(shù)據(jù)上構(gòu)造最少層數(shù)的Trie樹。十八一、假定一個(gè)待散列存儲(chǔ)的線性表為32,75,29,63,48,94,25,46,18,70），散列地址空間為HT13,若采用除留余數(shù)法構(gòu)造散列函數(shù)（假設(shè)p取11）和線性探測法（假設(shè)