查找練習(xí)習(xí)題(答案)

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

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

3、. O(n) B. O(1) C. O(log2n) D. O(n2)9. 若根據(jù)查找表(23,44,36,48,52,73,64,58)建立哈希表，采用h(K)=K%13計算哈希地址，則元素64的哈希地址為()。A. 4 B. 8 C. 12 D. 1310. 若根據(jù)查找表建立長度為m的哈希表，采用線性探測法處理沖突，假定對一個元素第一次計算的哈希地址為d，則下一次的哈希地址為()。A. d B. d+1 C. (d+1)/m D. (d+1)%m二、填空題1. 以順序查找方法從長度為n的順序表或單鏈表中查找一個元素時，平均查找長度為_（n+1）/2_。2. 以折半查找方法從長度為n的有序表

4、中查找一個元素時，平均查找長度約等于_log2n_的向上取整減1，時間復(fù)雜度為_O(log2n) _。3. 以折半查找方法在一個查找表上進行查找時，該查找表必須組織成_順序_存儲的_有序_表。4. 從有序表(12,18,30,43,56,78,82,95)中分別折半查找43和56元素時，其比較次數(shù)分別為_1_和_3_。5. 在索引查找中，假定查找表（即主表）的長度為96，被等分為8個子表，則進行索引查找的平均查找長度為_11_。6. 在一棵二叉排序樹中，每個分支結(jié)點的左子樹上所有結(jié)點的值一定_小于等于_該結(jié)點的值，右子樹上所有結(jié)點的值一定_大于等于_該結(jié)點的值。7. 對一棵二叉排序樹進行中序遍

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