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

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

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

3、有 n個(gè)結(jié)點(diǎn)的二叉排序樹(shù)中查找一個(gè)元素時(shí)， 在最壞情況下的時(shí)間復(fù)雜度為 () 。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 計(jì)算哈希地址，A. 4B. 8C. 12D. 1310. 若根據(jù)查找表建立長(zhǎng)度為 m的哈希表，采用線性探測(cè)法處理沖突，假定對(duì)一個(gè)元素第 次計(jì)算的哈希地址為 d，則下一次的哈希地址為 ( ) 。A. d B. d+1 C. (d+1)/m D. (d+1)%m二、填空題1. 以順序查找方法從長(zhǎng)度為 n

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

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