課程課件作業(yè)chapter9答案

1復(fù)習(xí)題在二叉排序樹中，凡是新插入的點(diǎn)，都是沒有_____的。P229

A.孩子 B.關(guān)鍵字

C.平衡因子 D.賦值有一個(gè)長度為12的有序表，按折半查找法對(duì)該表進(jìn)行查找，在表內(nèi)各元素等概率情況下，查找成功所需的平均比較次數(shù)為_____。p220

A.35/12 B.37/12C.39/12 D.43/12AB2復(fù)習(xí)題如下圖所示的一棵二叉排序樹，其不成功的平均查找長度是_____。葉子結(jié)點(diǎn)點(diǎn)是查找失敗的結(jié)點(diǎn)

A.21/7 B.28/7 C.15/6 D.21/6A4815307462563復(fù)習(xí)題采用分塊查找時(shí)，若線性表中共有625個(gè)元素，查找每個(gè)元素的概率相同，假設(shè)采用順序查找來確定結(jié)點(diǎn)所在的塊，則每塊分為_____個(gè)結(jié)點(diǎn)最佳。

A.9 B.25 C.6 D.625 (提示：教材p.226，若用順序查找確定所在的塊，容易證明，當(dāng)s取n1/2時(shí)，ASLbs取最小值n1/2+1）

B4復(fù)習(xí)題具有5層結(jié)點(diǎn)的AVL樹，至少有_____個(gè)結(jié)點(diǎn)。

A.10 B.12 C.15 D.17下面關(guān)于B-樹和B+樹的敘述中，不正確的結(jié)論是______。

A.B-樹和B+樹都能有效地支持順序查找

B.B-樹和B+樹都能有效地支持隨機(jī)查找

C.B-樹和B+樹都是平衡的多路查找樹

D.B-樹和B+樹都可以用于文件索引結(jié)構(gòu)

BA5復(fù)習(xí)題設(shè)哈希表長m=12，哈希函數(shù)H(key)=keyMOD11。表中已有4個(gè)結(jié)點(diǎn)，addr(15)=4，addr(38)=5，addr(61)=6，addr(84)=7，其余地址為空，如用二次探測再散列法處理沖突，則關(guān)鍵字為49的結(jié)點(diǎn)的地址是_____。

A.8 B.3 C.5 D.9D6復(fù)習(xí)題判斷以下敘述的正確性。

1)一個(gè)10階的B-樹上，除根以外每個(gè)非終端結(jié)點(diǎn)中所含關(guān)鍵字的數(shù)目最多允許為9個(gè)，最少允許為5個(gè)。2)在哈希存儲(chǔ)中，裝填因子α越大，則存取元素時(shí)發(fā)生沖突的可能性越大；α越小，則存取元素時(shí)發(fā)生沖突的可能性越小。3)分塊查找的效率與線性表被分成多少塊有關(guān)。4)在二叉排序樹中，新插入的關(guān)鍵字總是處于最底層。()()()P226()7復(fù)習(xí)題5)有n個(gè)數(shù)存放在一維數(shù)組A[1..n]中，在進(jìn)行順序查找時(shí)，這n個(gè)數(shù)的排列有序或無序，其平均查找長度不同。6)在二叉排序樹上刪除一個(gè)結(jié)點(diǎn)時(shí)，不必移動(dòng)其他結(jié)點(diǎn)，只要將該結(jié)點(diǎn)的雙親結(jié)點(diǎn)的相應(yīng)指針置空即可。7)用順序表和單鏈表存儲(chǔ)的有序表均可使用二分查找方法來提高查找速度。8)對(duì)二叉排序樹的查找都是從根結(jié)點(diǎn)開始，則查找失敗一定