數(shù)據(jù)結(jié)構(gòu)第四教學(xué)單元測(cè)驗(yàn)練習(xí)題(答案)(自動(dòng)保存的)

1、數(shù)據(jù)結(jié)構(gòu)第4教學(xué)單元測(cè)試練習(xí)題第 9 頁(yè) 共 9 頁(yè)一、 選擇題1. 對(duì)N個(gè)元素的表做順序查找時(shí)，若查找每個(gè)元素的概率相同，則平均查找長(zhǎng)度為( ) A（N+1）/2 B. N/2 C. N D. （1+N）*N /2AB2適用于折半查找的表的存儲(chǔ)方式及元素排列要求為( ) A鏈接方式存儲(chǔ)，元素?zé)o序 B鏈接方式存儲(chǔ)，元素有序C順序方式存儲(chǔ)，元素?zé)o序 D順序方式存儲(chǔ)，元素有序3當(dāng)在一個(gè)有序的順序存儲(chǔ)表上查找一個(gè)數(shù)據(jù)時(shí)，即可用折半查找，也可用順序查找，但前者比后者的查找速度( ) A必定快 B.不一定 C. 在大部分情況下要快 D. 取決于表遞增還是遞減4. 具有12個(gè)關(guān)鍵字的有序表，折半查找的平均

2、查找長(zhǎng)度（ ）A. 3.1 B. 4 C. 2.5 D. 55. 折半查找的時(shí)間復(fù)雜性為（ ）A. O（n2） B. O（n） C. O（nlogn）D. O（logn）6.對(duì)有18個(gè)元素的有序表作折半查找，則查找A3的比較序列的下標(biāo)為（ ）A.1，2，3B.9，5，2，3 C.9，5，3 D.9，4，2，37.設(shè)有序表的關(guān)鍵字序列為1，4，6，10，18，35，42，53，67，71，78，84，92，99，當(dāng)用二分查找法查找健值為84的結(jié)點(diǎn)時(shí)，經(jīng)（ ）次比較后查找成功。A.2 B. 3 C. 4 D.128、用n個(gè)鍵值構(gòu)造一棵二叉排序樹(shù)，最低高度為（ ）A.n/2 B.、n C.logn

3、D.logn+1 9分別以下列序列構(gòu)造二叉排序樹(shù)，與用其它三個(gè)序列所構(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.設(shè)有一組記錄的關(guān)鍵字為19，14，23，1，68，20，84，27，55，11，10，79，用鏈地址法構(gòu)造散列表，散列函數(shù)為H（key）=key% 13,散列地址為1的鏈中有（ ）個(gè)記錄。A1 B. 2 C. 3 D. 411已知一采用開(kāi)放地址法解決Has

4、h表沖突，要從此Hash表中刪除出一個(gè)記錄，正確的做法是(）A.將該元素所在的存儲(chǔ)單元清空。B.將該元素用一個(gè)特殊的元素代替C.將與該元素有相同Hash地址的后繼元素順次前移一個(gè)位置。D.用與該元素有相同Hash地址的最后插入表中的元素替代。11. 假定有k個(gè)關(guān)鍵字互為同義詞，若用線性探測(cè)法把這k個(gè)關(guān)鍵字存入散列表中，至少要進(jìn)行多少次探測(cè)？( ) Ak-1次 B. k次C. k+1次D. k（k+1）/2次12. 散列表的地址區(qū)間為0-17,散列函數(shù)為H(K)=K mod 17。采用線性探測(cè)法處理沖突，并將關(guān)鍵字序列26，25，72，38，8，18，59依次存儲(chǔ)到散列表中。（1）元素59存放在

5、散列表中的地址是（ ）。A 8 B. 9 C. 10 D. 11 （2）存放元素59需要搜索的次數(shù)是（ ）。A 2 B. 3 C. 4 D. 513. 將10個(gè)元素散列到100000個(gè)單元的哈希表中，則（ ）產(chǎn)生沖突。A. 一定會(huì) B. 一定不會(huì) C. 仍可能會(huì)二、 判斷題1查找相同結(jié)點(diǎn)的效率折半查找總比順序查找高。 2對(duì)無(wú)序表用二分法查找比順序查找快。3對(duì)大小均為n的有序表和無(wú)序表分別進(jìn)行順序查找，在等概率查找的情況下，對(duì)于查找成功，它們的平均查找長(zhǎng)度是相同的，而對(duì)于查找失敗，它們的平均查找長(zhǎng)度是不同的。4在查找樹(shù)（二叉樹(shù)排序樹(shù)）中插入一個(gè)新結(jié)點(diǎn)，總是插入到葉結(jié)點(diǎn)下面。 5對(duì)一棵二叉排序樹(shù)按

6、前序方法遍歷得出的結(jié)點(diǎn)序列是從小到大的序列。 6二叉樹(shù)中除葉結(jié)點(diǎn)外, 任一結(jié)點(diǎn)X，其左子樹(shù)根結(jié)點(diǎn)的值小于該結(jié)點(diǎn)（X）的值；其右子樹(shù)根結(jié)點(diǎn)的值該結(jié)點(diǎn)（X）的值,則此二叉樹(shù)一定是二叉排序樹(shù)。7. 在任意一棵非空二叉排序樹(shù)中，刪除某結(jié)點(diǎn)后又將其插入，則所得二排序叉樹(shù)與原二排序叉樹(shù)相同。8采用線性探測(cè)法處理散列時(shí)的沖突，當(dāng)從哈希表刪除一個(gè)記錄時(shí)，不應(yīng)將這個(gè)記錄的所在位置置空，因?yàn)檫@會(huì)影響以后的查找。9在散列檢索中，“比較”操作一般也是不可避免的。10散列函數(shù)越復(fù)雜越好，因?yàn)檫@樣隨機(jī)性好，沖突概率小. 11Hash表的平均查找長(zhǎng)度與處理沖突的方法無(wú)關(guān)。 12負(fù)載因子 (裝填因子)是散列表的一個(gè)重要參數(shù)，

7、它反映散列表的裝滿程度。13. 若散列表的負(fù)載因子1，則可避免碰撞的產(chǎn)生。 三、填空題1.順序查找n個(gè)元素的順序表，若查找成功，則比較關(guān)鍵字的次數(shù)最多為_(kāi)（1）n _次。 2.在有序表A1.20中，按二分查找方法進(jìn)行查找，查找長(zhǎng)度為5的元素個(gè)數(shù)是_ （2）5 _。3.在有序表A120中，按二分查找方法進(jìn)行查找，查找長(zhǎng)度為4的元素的下標(biāo)從小到大依次是_（3）1,3,6,8,11,13,16,19_。4.有序表(12,18,24,35,47,50,62,83,90,115，134)使用二分法查找90時(shí)，需_（4）2_次查找成功，查100時(shí)，需_（5）4_次才能確定不成功。5.在n個(gè)記錄的有序順序表

8、中進(jìn)行折半查找，最大比較次數(shù)是_（6）log2n+1_。（取下界）6.平衡因子的定義是_（7）結(jié)點(diǎn)的左子樹(shù)的高度減去結(jié)點(diǎn)的右子樹(shù)的高度_7.高度為8的平衡二叉樹(shù)的結(jié)點(diǎn)數(shù)至少有_（8）54_個(gè)。（參照教材P238：N0=0,N1=1,N2=2,公式Nh=Nh-1+Nh-2+1）8. 動(dòng)態(tài)查找表和靜態(tài)查找表的重要區(qū)別在于前者包含有_（9）插入 _和_（10）_刪除_運(yùn)算，而后者不包含這兩種運(yùn)算。四、應(yīng)用題1.假定對(duì)有序表：(3,4,5,7,24,30,42,54,63,72,87,95)進(jìn)行折半查找，試回答下列問(wèn)題：(1).畫出描述折半查找過(guò)程的判定樹(shù)；(2).若查找元素54，需依次與那些元素比較?(3).若查找元素90，需依次與那些元素比較?(4).假定每個(gè)元素的查找概率相等，求查找成功時(shí)的平均查找長(zhǎng)度。2.一棵二叉排序樹(shù)結(jié)構(gòu)如下,各結(jié)點(diǎn)的值從小到大依次為1-9，請(qǐng)標(biāo)出各結(jié)點(diǎn)的值。3.依次輸入表(30,15,28,20,24,10,12,68,35,50,46,55)中的元素，生成一棵二叉排序樹(shù)【華中理工大學(xué) 2000 五 （10分）】(1) 試畫出生成之后的二叉排序樹(shù); (2) 對(duì)該二叉排序樹(shù)作中序遍歷，試寫出遍歷序列; (3) 假定每個(gè)元素的查找概率相等，試