數(shù)據(jù)結(jié)構(gòu)第8章查找練習(xí)題

《數(shù)據(jù)結(jié)構(gòu)第8章查找練習(xí)題》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、一、單選題1．下列查找方法中，不屬于動態(tài)的查找方法是()。A．二叉排序樹法B．平衡樹法C．散列法D．二分查找法2．適用于靜態(tài)的查找方法為()。A．二分查找、二叉排序樹查找B．二分查找、索引順序表查找C．二叉排序樹查找、索引順序表查找D．二叉排序樹查找、散列法查找3．靜態(tài)查找表與動態(tài)查找表二者的根本差別在于()。A．它們的邏輯結(jié)構(gòu)不一樣B．施加在其上的操作不同C．所包含的數(shù)據(jù)元素的類型不一樣D．存儲實現(xiàn)不一樣4．對長度為10的順序表進(jìn)行查找，若查找前面5個元素的概率相同，均為1/8，查找后面5個元素的概率相同，

2、均為3/40，則查找任一元素的平均查找長度為()。A．5.5B．5C．39/8D．19/45．()存儲方式適用于折半查找。A．鍵值有序的單鏈表B．鍵值有序的順序表C．鍵值有序的雙鏈表D．鍵值無序的順序表6．對線性表進(jìn)行二分查找時，要求線性表必須()。A．以順序方式存儲B．以鏈接方式存儲C．順序存儲，且結(jié)點按關(guān)鍵字有序排序D．鏈?zhǔn)酱鎯?，且結(jié)點按關(guān)鍵字有序排序7．在索引順序表中查找一個元素，可用的且最快的方法是()。A．用順序查找法確定元素所在塊，再用順序查找法在相應(yīng)塊中查找B．用順序查找法確定元素所在塊，再用二

3、分查找法在相應(yīng)塊中查找C．用二分查找法確定元素所在塊，再用順序查找法在相應(yīng)塊中查找D．用二分查找法確定元素所在塊，再用二分查找法在相應(yīng)塊中查找8．在索引查找中，若主表長度為144，它被均分為12子表，每個子表的長度均為12，則索引查找的平均查找長度為()。A．13B．24C．12D．799．由同一關(guān)鍵字集合構(gòu)造的各棵二叉排序樹()。A．形態(tài)和平均查找長度都不一定相同B．形態(tài)不一定相同，但平均查找長度相同C．形態(tài)和平均查找長度都相同D．形態(tài)相同，但平均查找長度不一定相同10．對二叉排序樹進(jìn)行()，可以得到各結(jié)點

4、鍵值的遞增序列。A．先根遍歷B．中根遍歷C．層次遍歷D．后根遍歷11．下述序列中，哪個可能是在二叉排序樹上查找35時所比較過的關(guān)鍵字序列？A．2，25，40，39，53，34，35B．25，39，2，40，53，34，35C．53，40，2，25，34，39，35D．39，25，40，53，34，2，3512．在AVL樹中，每個結(jié)點的平衡因子的取值范圍是()。A．-1~1B．-2~2C．1~2D．0~113．在AVL樹中，任一結(jié)點的()。A．左、右子樹的高度均相同B．左、右子樹高度差的絕對值不超過1C．左、右

5、子樹的結(jié)點數(shù)均相同D．左、右子樹結(jié)點數(shù)差的絕對值不超過114．下面關(guān)于B樹和B+樹的敘述中，不正確的是A．都是平衡的多叉樹B．都是可用于文件的索引結(jié)構(gòu)C．都能有效地支持順序檢索D．都能有效地支持隨機(jī)檢索15．右圖是一棵()。A．4階B-樹B．4階B+樹C．3階B-樹D．3階B+樹16．對包含n個關(guān)鍵字的散列表進(jìn)行檢索，平均檢索長度是()。A．O(log2n)B．O(n)C．不直接依賴于nD．O(nlog2n)17．在散列查找中，平均查找長度主要與()有關(guān)。A．散列表長度B．散列元素的個數(shù)C．裝填因子D．處理沖

6、突方法18．要解決散列引起的沖突問題，常采用的方法有()。A．?dāng)?shù)字分析法、平方取中法B．?dāng)?shù)字分析法、線性探測法C．二次探測法、平方取中法D．二次探測法、鏈地址法19．從理論上講，將數(shù)據(jù)以()結(jié)構(gòu)存放，查找一個數(shù)據(jù)的時間不依賴于數(shù)據(jù)的個數(shù)n。A．二叉查找樹B．鏈表C．散列表D．順序表20．假定有k個關(guān)鍵字互為同義詞，若用線性探測法把這k個關(guān)鍵字存入散列表中，至少要進(jìn)行()次探側(cè)。A．k-1B．kC．k+1D．k(k+1)/2二、判斷題1．順序查找法不僅可用于順序表上的查找，也可用于鏈表上的查找。2．二分查找所對

7、應(yīng)的判定樹，是一棵理想平衡的二叉排序樹。3．二叉排序樹的形態(tài)與關(guān)鍵字的輸入序列有關(guān)，但平衡二叉排序樹是相同的。4．如果根結(jié)點的左子樹和右子樹高度差不超過1，則該二叉樹是平衡二叉樹。5．二叉排序樹上，以根到任一結(jié)點的路徑為界，則：路徑左邊結(jié)點＜路徑結(jié)點＜路徑右邊結(jié)點。1535506570454030256．在二叉排序樹中，即使刪除一個結(jié)點后馬上再插入該結(jié)點，該二叉排序樹的形態(tài)也可能不同。7．用線性探測法解決突出時，同義詞在散列表中是相鄰的。8．不論數(shù)據(jù)如何組織，分別在10000個結(jié)點和10個結(jié)點的查找表中進(jìn)行查

8、找，前者的平均查找長度肯定比后者大。9．在開散列表中不會出現(xiàn)堆積現(xiàn)象。10．開散列表和閉散列表的裝填因子都可大于、等于或小于1。三、填空題1．評價查找效率的主要標(biāo)準(zhǔn)是____。2．查找表的邏輯結(jié)構(gòu)是____。集合3．對長度為100的順序表，在等概率情況下，查找成功時的平均查找長度為____，在查找不成功時的平均查找長度為____。4．在150個結(jié)點的有序表中二分法查找，不論成功與否，鍵值比較次數(shù)最多