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

1、數(shù)據(jù)結(jié)構(gòu)與算法上機(jī)作業(yè)第五章 查找一、選擇題1、若構(gòu)造一棵具有n個(gè)結(jié)點(diǎn)的二叉排序樹，在最壞情況下，其高度不超過(guò) B 。A. n/2B. nC. (n+1)/2D. n+12、分別以下列序列構(gòu)造二叉排序數(shù)（二叉查找樹），與用其他3個(gè)序列所構(gòu)造的結(jié)果不同的是 C ：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)3、不可能生成下圖所示的二叉排序樹的關(guān)鍵字的序列是 A 。

2、A. 4 5 3 1 2 B. 4 2 5 3 1 C. 4 5 2 1 3 D. 4 2 3 1 54、在二叉平衡樹中插入一個(gè)結(jié)點(diǎn)造成了不平衡，設(shè)最低的不平衡點(diǎn)為A，并已知A的左孩子的平衡因子為0，右孩子的平衡因子為1，則應(yīng)作 C 型調(diào)整使其平衡。A. LLB. LRC. RLD. RR5、一棵高度為k的二叉平衡樹，其每個(gè)非葉結(jié)點(diǎn)的平衡因子均為0，則該樹共有 C 個(gè)結(jié)點(diǎn)。A. 2k-1-1B. 2k-1+1C. 2k-1D. 2k+16、具有5層結(jié)點(diǎn)的平衡二叉樹至少有 A 個(gè)結(jié)點(diǎn)。A. 12B. 11C. 10D. 97、下面關(guān)于B-和B+樹的敘述中，不正確的是 C 。A. B-樹和B+樹都

3、是平衡的多叉樹B. B-樹和B+樹都可用于文件的索引結(jié)構(gòu)C. B-樹和B+樹都能有效地支持順序檢索D. B-樹和B+樹都能有效地支持隨機(jī)檢索8、下列關(guān)于m階B-樹的說(shuō)法錯(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)于哈希查找的說(shuō)法正確的是 C 。A. 哈希函數(shù)構(gòu)造得越復(fù)雜越好，因?yàn)檫@樣隨機(jī)性好，沖突小B. 除留余數(shù)法是所有哈希函數(shù)中最好的C. 不存在特別好與壞的哈希函數(shù)，要視情況而定D. 若需在哈希表中刪去一個(gè)元素，不管用何種方法解決沖突都只要簡(jiǎn)單地將該元素刪去即

4、可10、與其他查找方法相比，散列查找法的特點(diǎn)是 C 。A. 通過(guò)關(guān)鍵字的比較進(jìn)行查找B. 通過(guò)關(guān)鍵字計(jì)算元素的存儲(chǔ)地址進(jìn)行查找C. 通過(guò)關(guān)鍵字計(jì)算元素的存儲(chǔ)地址并進(jìn)行一定的比較進(jìn)行查找D. 以上都不是11、有一組關(guān)鍵字8, 24, 16, 3, 12, 32, 51，采用除留余數(shù)法構(gòu)造散列函數(shù)：H(key)=key mod 12，則將發(fā)生 次沖突。A. 3B. 4C. 5D. 612、有一個(gè)結(jié)點(diǎn)的關(guān)鍵字為3276012483，采用移位疊加法生成4位散列地址，則生成的地址為 B 。A. 3482B. 3583C. 9018D. 9019二、填空題1、在查找過(guò)程中有插入或刪除元素操作的，稱為 動(dòng)態(tài)

5、 查找。2、一個(gè)無(wú)序序列可以通過(guò)構(gòu)造一棵 二叉排序 樹而變?yōu)橐粋€(gè)有序序列，構(gòu)造樹的過(guò)程即為對(duì)無(wú)序序列進(jìn)行排序的過(guò)程。3、對(duì)于一棵二叉排序樹，按 中根 方法遍歷得出的結(jié)點(diǎn)序列是從小到大排列的。4、對(duì)二叉排序樹進(jìn)行查找的方法是用待查找的值與根結(jié)點(diǎn)的鍵值進(jìn)行比較，若比根結(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)行 RL RR 旋轉(zhuǎn)。 6、在m階一棵B-樹中，若在某個(gè)結(jié)點(diǎn)中插入一個(gè)新關(guān)鍵字而引起該結(jié)點(diǎn)分裂，則此結(jié)點(diǎn)中原有的關(guān)鍵字

6、的個(gè)數(shù)是 m-1 ；若在某結(jié)點(diǎn)中刪除一個(gè)關(guān)鍵字而導(dǎo)致結(jié)點(diǎn)合并，則該結(jié)點(diǎn)中原有的關(guān)鍵字的個(gè)數(shù)是 ém/2ù -1 。7、127階B-樹中每個(gè)結(jié)點(diǎn)最多有 126 個(gè)關(guān)鍵字；除根結(jié)點(diǎn)外所有非終端結(jié)點(diǎn)至少有 棵子樹；65階B+樹中，除根結(jié)點(diǎn)外所有非葉結(jié)點(diǎn)至少有 33 個(gè)關(guān)鍵字，最多有 65 棵子樹8、假設(shè)有k個(gè)關(guān)鍵字互為同義詞（哈希值相同），若用線性探測(cè)再散列法把這k個(gè)關(guān)鍵字存入散列表中，至少要進(jìn)行 k(k-1)/2 次探測(cè)。9、在散列排序法中，折疊法的哈希函數(shù)可分為 移位法和分界法 兩種類型。10、散列法的填充因子= 表中填入的記錄數(shù) / 哈希表的長(zhǎng)度 。11、設(shè)散列函數(shù)H和關(guān)鍵

7、字k1, k2，若k1不等于k2，而H(k1)=H(k2)，則稱這種現(xiàn)象為 沖突 。12、在哈希函數(shù)H(key)=key % p中，p一般應(yīng)取 不大于表長(zhǎng)的質(zhì)數(shù)或是不含20以下的質(zhì)因數(shù)的合數(shù) 。三、依次輸入表(30, 15, 28, 20, 24, 10, 12, 68, 35, 50, 46, 55)中的元素，生成一棵二叉排序數(shù)，要求： 1、試畫出生成之后的二叉排序樹。 2、對(duì)該二叉排序數(shù)作中根遍歷，寫出遍歷序列。 3、編程構(gòu)建一個(gè)二叉排序數(shù)，并中根遍歷驗(yàn)證上述結(jié)果。四、二叉排序樹如下圖所示，分別畫出： 1、刪除關(guān)鍵字15以后的二叉樹，并要求平均查找長(zhǎng)度盡可能小。 2、在原二叉排序樹(即沒有

8、刪除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-樹（如下圖所示）， 1、畫出依次插入18、33、97后的B-樹 2、分別畫出刪除66、16、43后的B-樹九、給定一組記錄，其關(guān)鍵字為字符。各關(guān)鍵字插入順序?yàn)镃, S, M, T, A, E, P, U, X, K, G,

9、 B 1、給出從空樹開始，順序插入這些關(guān)鍵字后的3階B+樹，假設(shè)葉節(jié)點(diǎn)所能容納最大關(guān)鍵碼的數(shù)量為4。 2、分別給出在(1)建立的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取1