查找練習題(答案)

1、查找練習題一、單項選擇題1. 若查找每個元素的概率相等， 則在長度為 n 的順序表上查找任一元素的平均查找長度為 ( ) 。A. n B. n+1 C. (n-1)/2 D. (n+1)/22. 對于長度為 9 的順序存儲的有序表，若采用折半查找，在等概率情況下的平均查找長度 為() 。A. 20/9B. 18/9C. 25/9 D. 22/93. 對于長度為 18 的順序存儲的有序表，若采用折半查找，則查找第15 個元素 (從 1 開始數(shù)) 的比較次數(shù)為 ()。A. 3B. 4C. 5D. 64. 對于順序存儲的有序表(5,12,20,26,37,42,46,50,64)，若采用折半查找，則

2、查找元素26 的比較次數(shù)為 ( ) 。A. 2B. 3C. 4D. 55. 對具有 n 個元素的有序表采用折半查找，則算法的時間復雜度為 ( ) 。2A. O(n)B. O(n 2)C. O(1) D. O(log 2n)6. 在索引查找中， 若用于保存數(shù)據(jù)元素的主表的長度為 144，它被均分為 12子表， 每個子 表的長度均為 12，則索引查找的平均查找長度為 ( ) 。A. 13 B. 24 C. 12 D. 797. 從具有 n 個結點的二叉排序樹中查找一個元素時，在平均情況下的時間復雜度大致為() 。2A. O(n) B. O(1) C. O(log 2n)D. O(n 2)8. 從具

3、有 n個結點的二叉排序樹中查找一個元素時， 在最壞情況下的時間復雜度為 () 。A. O(n)B. O(1)C. O(log 2n)2D. O(n 2)9. 若根據(jù)查找表 (23,44,36,48,52,73,64,58) 則元素 64 的哈希地址為 ( ) 。建立哈希表，采用 h(K)=K%13 計算哈希地址，A. 4B. 8C. 12D. 1310. 若根據(jù)查找表建立長度為 m的哈希表，采用線性探測法處理沖突，假定對一個元素第 次計算的哈希地址為 d，則下一次的哈希地址為 ( ) 。A. d B. d+1 C. (d+1)/m D. (d+1)%m二、填空題1. 以順序查找方法從長度為 n

4、 的順序表或單鏈表中查找一個元素時， 平均查找長度為 _ (n+1) /2。2. 以折半查找方法從長度為 n 的有序表中查找一個元素時，平均查找長度約等于_log2n的向上取整減 1，時間復雜度為 _O(log 2n) 。3. 以折半查找方法在一個查找表上進行查找時， 該查找表必須組織成 _順序 存儲的_有序 _表。4. 從有序表 (12,18,30,43,56,78,82,95)中分別折半查找 43 和 56 元素時，其比較次數(shù)分別為 _1和_3。5. 在索引查找中，假定查找表(即主表)的長度為96，被等分為 8 個子表，則進行索引查找的平均查找長度為 _11。6. 在一棵二叉排序樹中， 每

5、個分支結點的左子樹上所有結點的值一定_小于等于 該結點的值，右子樹上所有結點的值一定_大于等于 該結點的值。7. 對一棵二叉排序樹進行中序遍歷時，得到的結點序列是一個_升序 _(升序或降序) 。8. 對線性表 (18,25,63,50,42,32,90)進行哈希存儲時，若選用 H(K)=K % 9 作為哈希函數(shù)，則 哈希地址為 0的元素有 _2個，哈希地址為 5 的元素有 _2個。三、判斷題1. 在索引順序結構的搜索中， 對索引表既可以采取順序搜索， 也可以采用折半搜索。 (1 )2. 對二叉排序樹的中序遍歷結果是結點的升序排列。 ( 1 )3. 執(zhí)行折半查找法要求查找表必須為順序結構。 ( 1 )4. 100 個元素的有序表中，折半查找成功的最大查找長度為 8。( 1 )四、應用題1. 已知一個順序存儲的有序表為 (15,26,34,39,45,56,58,63,74,76) ，試畫出對應的折半查找判定樹，求出其平均查找長度。平均查找長度 =29/102. 假定一個線性表為 (38,52,25,74,68,16,30,54,90,72) ，畫出按線性表中元素的次序生成的一 棵二叉排序樹，求出其平均查找長度。3. 假定一個待哈希存儲的線性表為(32,75,29,63,48,94,25,46,18,70) ，哈希地址空間為 HT13 ，若采用除留余數(shù)法構造哈希函數(shù) H