數據結構(查找)習題與答案

1、正確答案：A一、單選題1、對于查找表（13,27,38,49,50,65,76,97）采用順序查找，在等概率情況下查找成功的平均查找長度是（）。A.4.5B.9C.4D.8正確答案：A2、在關鍵字序列（10,20,30,40,50）中采用折半查找20，依次與（）關鍵字進行了比較。A.30,10,20B.20C.30,20D.40,20正確答案：A3、在關鍵字序列（8,12,20,25,33）中，采用二分查找25，關鍵字之間比較需要（）次。A.2B.1C.3D.4正確答案：A4、對于長度為11的有序表，按折半查找，在等概率情況下查找成功時，其平均查找長度是（）。A.3B.4C.1D.2D.15正

2、確答案：D5、對于長度為11的有序表，按折半查找，在查找失敗時，待查找值域表中關鍵字比較的次數是()。A.3次或4次B.2次或3次C.4次或5次D.1次或2次正確答案：A6、對于長度為n的有序表，按折半查找，在等概率情況下查找成功平均時間復雜度是()。A.O(logn)B.O(n)C.O(1)D.O(ngn)正確答案：A7、索引順序查找也叫分塊查找，其查找過程分為是()個步驟。A.1B.3C.4D.2正確答案：D8、對于長度為n的關鍵字序列創(chuàng)建一顆二叉排序樹，該樹可能的最大高度是()。A.n+1B.n-1C.gnD.n9、對于關鍵字序列（30,25,40,35,45），按序列次序創(chuàng)建一顆二叉排

3、序樹，在等概率情況下查找成功時，其平均查找長度是（）。A.8/3B.11/5C.8D.11正確答案：B10、影響散列查找時間效率的主要因素（）。A.僅與散列表中實際元素個數相關B.僅與散列表長相關C.與散列表長和散列表中實際元素個數均相關D.與散列表長和散列表中實際元素個數均不相關正確答案：C11、一組關鍵字序列為（27，17，9，19，16，43，53，8，63），用哈希函數H（key）=keyMOD8和鏈地址法處理沖突，查找關鍵字43，與散列表中關鍵字進行了（）次比較。A.3B.6C.4D.5正確答案：A12、設哈希表下標為015，哈希函數為H（key）=keyMOD13，其中key為關鍵

4、字，MOD為取余數運算，處理沖突方法為線性探查法，對于關鍵字序列為（22，18，38，39，48，35，9，64，29），建立哈希表后，關鍵字9的在哈希表的位置是（）。A.13B.9C.11A.13正確答案：A正確答案：A13、對于關鍵字序列(14,26,38,54,91)，按序列次序創(chuàng)建一顆平衡二叉排序樹，在等概率情況下查找成功時，其平均查找長度是()。A.9/5B.7/5C.11/5D.13/5正確答案：C14、對于關鍵字序列(63,72,88,68,66,38,43)，在按序列次序創(chuàng)建一顆平衡二叉排序樹上，查找71時依次與()關鍵字進行了比較。A.66,43,38B.63,72,68C.

5、66,72,68D.63,38,43正確答案：C15、對包含n個元素的散列表進行檢索，平均查找長度為()。A.O(logn)B.O(nlogn)C.不直接依賴于nD.O(n)正確答案：C16、折半查找有序表(5,15,25,35,40,65,70,75,80,85,88,90)，若查找元素75，與表中元素進行了()次比較。A.4B.2C.1D.317、折半查找一個長度為56的有序表,若查找不成功,最少需要比較（）次關鍵字。A.5B.7C.4D.6正確答案：A18、假設哈希函數h（k尸kmod29,那么（）為7的同義詞。A.46B.36C.16D.26正確答案：B19、在下列查找算法中，（）屬于

6、動態(tài)表上的查找法。A.順序查找B.折半查找C.哈希查找D.斐波那契查找正確答案：C20、在二叉排序樹查找中，創(chuàng)建平衡二叉排序的目的是提高（）。A.查找時間效率和存儲效率B.存儲效率插入和刪除數據效率D.查找時間效率正確答案：D21、高度為3的平衡二叉排序樹的形態(tài)共有（）種。B.15C.14D.16正確答案：B22、在下列查找算法中，（）算法要求關鍵字序列是有序的。A.折半查找B.分塊查找C.順序查找D.二叉樹查找正確答案：A23、假設查找表長為n，對于分塊查找，如過采用）11順序查找確定待查值可能所在的塊，那么每塊的關鍵字個數為（）時，分塊查找的平均查找長度可以達到最佳。a.VnB.Vn-1C

7、.ln（n）D.Vn+1正確答案：A24、對于表長為n的查找表，如果采用順序查找，查找失敗時的平均查找長度是（）。A.nB.n-1C.（n+1）/2D.n/2正確答案：A25、若根據查找表建立長度為m的哈希表，采用線性探測法處理沖突，假定對一個元素第一次計算的哈希地址為d，則下一次的哈希地址為（）。A.（d+1）%mB.dC.d+1D.(d+1)/m正確答案：A二、判斷題1、對長度為n的”頁序表做查找運算，在等概率條件下，查找成功的ASL為n/20(x)2、如果含有n個記錄的HASH表中沒有同義詞，則查找成功的ASL為1O(V)3、高度為4的平衡二叉樹至少有4個結點。(x)4、分塊查找要求關鍵

8、字序列一定是有序的。(x)5、對于二叉排序樹，中序遍歷的關鍵字序列一定是有序。(V)6、對于任何應用情況，如果采用哈希查找法，那么就無法避免沖突情況的發(fā)生。(x)7、分塊查找需要額外的輔助存儲空間。(V)8、含有n個關鍵字的二叉排序樹，其高度可以達到no(V)9、如果一顆二叉樹的左右子樹高度差的絕對值不大于2，則該二叉樹是一顆平衡二叉樹。)10、如果關鍵字序列是有序的，則可以提高“順序查找的效率。(x)11、在有序的單鏈表上不適合折半查找。(V)12、對于相同的關鍵字集，如果不同的初始序列，那么創(chuàng)建的二叉排序樹也不相同。(x)13、假定有k個關鍵字互為同義詞，若線性再散列處理沖突，查找這些同義

9、詞其中的任意一個關鍵字，那么比較次數不會超過k次。(x)14、二分查找過程所對應的判定樹是一棵平衡的二叉排序樹。(-)15、對于相同的關鍵字集，如果不同的初始序列，那么創(chuàng)建的平衡二叉排序樹是相同的o(x)16、在二叉排序樹中插入一個新結點，總是作為葉子結點插入。()17、當采用分快查找時，數據的組織方式為數據分成若干塊，每塊(除最后一塊外)中數據個數需相同0(x)18、二叉排序樹查找法能適應查找表中數據的動態(tài)變化的要求。（V）19、用線性探測法解決突出時，同義詞在散列表中是相鄰的。（X）20、一顆完全二叉樹也是一顆平衡二叉樹。（V）21、對于散列表進行檢索，其平均查找長度取決于表中填入的記錄數與哈希表長之比。（V）22、含有12個結點的平衡二叉樹，