1.下列叙述中，不符合m階B樹定義要求的是（D）。
-
根結點最多有m棵子樹 -
所有葉結點都在同一層上 -
各結點内關鍵字均升序或降序排列 -
葉結點之間通過指針連結
解析：
選項A、B和C都是B-樹的特點，而選項D則是B+樹的特點。注意差別B-樹和B+樹各自的特點。
2.已知一個長度為16的順序表L，其元素按關鍵字有序排列，若采用折半查找法查找一個 L中 不存在的元素，則 關鍵字的 比較次數最多是（B）
-
4 -
5 -
6 -
7
解析：16個二叉排序樹的深度為5，查找一個不存在的最多查到最後一層，即5
3.為提高散列（Hash）表的查找效率，可以采取的正确措施是（）。
Ⅰ．增大裝填（載）因子
Ⅱ．設計沖突（碰撞）少的散列函數
Ⅲ．處理沖突（碰撞）時避免産生聚集（堆積）現象
-
僅Ⅰ -
僅Ⅱ -
僅Ⅰ、Ⅱ -
僅Ⅱ、Ⅲ
解析：
Hash表的查找效率取決于散列函數、處理沖突的方法和裝填因子。顯然，沖突的産生機率與裝填因子（表中記錄數與表長之比）的大小成正比，即裝填得越滿越容易發生沖突，Ⅰ錯誤。Ⅱ顯然正确。采用合适的處理沖突的方式避免産生聚集現象，也将提高查找效率，例如用拉鍊法解決沖突時就不存在聚集現象，用線性探測法解決沖突時易引起聚集現象，Ⅲ正确。
4.設有一棵3 階 B 樹，如下圖所示。删除關鍵字 78 得到一棵新 B 樹，其最右葉結點所含的關鍵字是（ D）。
-
60 -
60， 62 -
62， 65 -
65
解析：詳解：https://blog.csdn.net/v_JULY_v/article/details/6530142
在B-樹葉結點上删除一個關鍵字的方法是：
首先将要删除的關鍵字 k直接從該葉子結點中删除。然後根據不同情況分别作相應的處理，共有三種可能情況：
（1）如果被删關鍵字所在結點的原關鍵字個數n>=ceil(m/2)（即向上取整），說明删去該關鍵字後該結點仍滿足B-樹的定義。這種情況最為簡單，隻需從該結點中直接删去關鍵字即可。
（2）如果被删關鍵字所在結點的關鍵字個數n等于ceil(m/2)-1，說明删去該關鍵字後該結點将不滿足B-樹的定義，需要調整。
調整過程為：如果其左右兄弟結點中有“多餘”的關鍵字,即與該結點相鄰的右（左）兄弟結點中的關鍵字數目大于ceil(m/2)-1。則可将右（左）兄弟結點中最小（大）關鍵字上移至雙親結點。而将雙親結點中小（大）于該上移關鍵字的關鍵字下移至被删關鍵字所在結點中。
對于本題，n=ceil（3/2）-1 。是以将做節點最大關鍵字62上移，同時将雙親結點中大于62的關鍵字（65）下移至删除結點位置。
5.用哈希（散列）方法處理沖突（碰撞）時可能出現堆積（聚集）現象，下列選項中，會受堆積現象直接影響的是 。
-
存儲效率 -
散列函數 -
裝填（裝載）因子 -
平均查找長度
解析：産生堆積現象，即産生了沖突，它對存儲效率、散列函數和裝填因子均不會有影響，而平均查找長度會因為堆積現象而增大，選D 這題拉鍊法對存儲沒影響
6.在一棵具有15個關鍵字的4階B樹中，含關鍵字的結點個數最多是 。
-
5 -
6 -
10 -
15
解析：
關鍵字數量不變，要求結點數量最多，那麼即每個結點中含關鍵字的數量最少。根據4階B樹的定義，根結點最少含1個關鍵字，非根結點中最少含⌈4/2⌉-1=1個關鍵字，是以每個結點中，關鍵字數量最少都為1個，即每個結點都有2個分支，類似與排序二叉樹，而15個結點正好可以構造一個4層的4階B樹，使得葉結點全在第四層，符合B樹定義，是以選D
7.下列選項中，不能構成折半查找中關鍵字比較序列的是 （）。
-
500,200,450,180 -
500,450,200,180 -
180,500,200,450 -
180,200,500,450
解析：注意是關鍵字比較序列，關鍵字的比較應該滿足邏輯性
500,200,450,180 500
說明第一次比較結果是選擇500之前的區間
200
說明第二次比較結果是選擇200之後的區間
450
此時一定錯了，因為隻能在200-450的區間找數
180
8.已知字元串S為“abaabaabacacaabaabcc”，模式串t為“abaabc”。采用KMP算法進行比對，第一次出現“失配”(s[i]≠t[j]) 時，i=j=5，則下次開始比對時，i和j的值分别是
解析： 通過KMP算法知，i不變，j回退到首字母第一次相同的時候
9.在有n（n＞1000）個元素的升序數組A中查找關鍵字x。查找算法的僞代碼如下所示。
k=0;
while(k<n 且 A[k]<x) k=k+3;
if(k<n 且 A[k]==x) 查找成功;
else if(k-1<n 且 A[k-1]==x) 查找成功;
else if(k-2<n 且 A[k-2]==x) 查找成功;
else 查找失敗;
本算法與折半查找算法相比，有可能具有更少比較次數的情形是 。 B
-
當x不在數組中 -
當x接近數組開頭處 -
當x接近數組結尾處 -
當x位于數組中間位置
解析：送分題。該程式采用跳躍式的順利查找法查找升序數組中的x，顯然是x越靠前，比較次數才會越少。
10.B+樹不同于B樹的特點之一是 。
-
能支援順序查找 -
結點中含有關鍵字 -
根結點至少有兩個分支 -
所有葉結點都在同一層上
解析：
由于B+樹的所有葉結點中包含了全部的關鍵字資訊，且葉結點本身依關鍵字從小到大順序連結，可以進行順序查找，而B樹不支援順序查找（隻支援多路查找）
11.将關鍵字序列（7、8、30、11、18、9、14）散列存儲到散清單中。散清單的存儲空間是一個下标從0開始的一維數組，散列函數為H(key)=(key×3) mod 7，處理沖突采用線性探測再散列法，要求裝填（載）因子為0.7。
1）請畫出所構造的散清單。
2）分别計算等機率情況下查找成功和查找不成功的平均查找長度
解析：
1）由裝載因子為0.7，資料總數為7，得一維數組大小為7/0.7=10，數組下标為0～9。所構造的散列函數值見表B-3。
表B-3
| key | 7 | 8 | 30 | 11 | 18 | 9 | 14 |
| H(key) | 3 | 6 | 5 | 5 | 6 |
采用線性探測再散列法處理沖突，所構造的散清單見表B-4。
表B-4
| 位址 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 關鍵字 | 7 | 14 | 8 | 11 | 30 | 18 | 9 |
表B-5
| key | 7 | 8 | 30 | 11 | 18 | 9 | 14 |
| 次數 | 1 | 1 | 1 | 1 | 3 | 3 | 2 |
故ASL成功=查找次數/元素個數=(1+2+1+1+1+3+3)/7=12/7。
這裡要特别防止慣性思維。查找失敗時，是根據查找失敗位置計算平均次數，根據散列函數mod 7，初始隻可能在0～6的位置。等機率情況下，查找0～6位置查找失敗的查找次數見表B-6。
表B-6
| H(key) | 1 | 2 | 3 | 4 | 5 | 6 | |
| 次數 | 3 | 2 | 1 | 2 | 1 | 5 | 4 |
故ASL不成功=查找次數/散列後的位址個數=(3+2+1+2+1+5+4)/7=18/7。
12. 設包含 4 個資料元素的集合 S={ "do"， "for"， " repeat"， " while"}，各元素的查找機率依次為： p1=0.35， p2 = 0.15， p3=0. 15， p4=0.35。将 S 儲存在一個長度為 4 的順序表中，采用折半查找法，查找成功時的平均查找長度為 2.2。請回答：
（1）若采用順序存儲結構儲存 S，且要求平均查找長度更短， 則元素應如何排列？ 應使用何種查找方法？ 查找成功時的平均查找長度是多少？
（2）若采用鍊式存儲結構儲存 S，且要求平均查找長度更短，則元素應如何排列？應使用何種查找方法？查找成功時的平均查找長度是多少？
解析：
1）采用順序存儲結構，資料元素按其查找機率降序排列。
采用順序查找方法。
查找成功時的平均查找長度= 0.35×1+0.35×2+0.15×3+0.15×4=2.1。
（2）【 答案一】
采用鍊式存儲結構，資料元素按其查找機率降序排列，構成單連結清單。
采用順序查找方法。
查找成功時的平均查找長度=0.35×1+0.35×2+0.15×3+0.15×4=2.1。
【答案二】
采用二叉連結清單存儲結構，構造二叉排序樹，元素存儲方式見下圖。
采用二叉排序樹的查找方法。
查找成功時的平均查找長度=0.15×1+0.35×2+0.35×2+0.15×3=2.0