1、第9章 查找 一、填空題（每空1分，共10分）1. 在數據的存放無規律而言的線性表中進行檢索的最佳方法是 。2【計研題2000】折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它將依次與表中元素 比較大小。3. 在各種查找方法中，平均查找長度與結點個數n無關的查找方法是 。4. 當關鍵字集合很大時，關鍵字值不同的元素可能會映象到哈希表的同一地址上，即 k1k2 ，但 H（k1）=H（k2），這種現象稱為 .5. 散列（哈希）法存儲的基本思想是由 決定數據的存儲地址。6. 順序查找法中設置監視哨，可以起到 的作用。7. 假設查找每個數據元素的概率相

2、等，即Pi=1/n，則順序查找算法的平均查找長度為： 。8. 在有序表(12,24,36,48,60,72,84)中二分查找關鍵字72時所需進行的關鍵字比較次數為 。9. 在各種查找方法中，平均查找長度與結點個數n無關的查找方法是 10. 設哈希表長m=14, 哈希函數H(key)=key MOD11.表中已有4個結點；addr(15)=4, addr(38)=5, addr(61)=6, addr(84)=7, 其余地址為空。如用二次探測再散列處理沖突，關鍵字為49的結點的地址是 二、單項選擇題（每小題1分，共27分）（ ）1【計研題2001】對22個記錄的有序表作折半查找，當查找失敗時，至

3、少需要比較 次關鍵字。A3 B4 C5 D 6（ ）2. 鏈表適用于 查找A順序 B二分法 C順序，也能二分法 D隨機3【91程P3】從供選擇的答案中，選出應填入下面敘述 ？ 內的最確切的解答，把相應編號寫在答卷的對應欄內。要進行線性查找，則線性表 A ；要進行二分查找，則線性表 B ；要進行散列查找，則線性表 C 。某順序存儲的表格，其中有90000個元素，已按關鍵項的值的上升順序排列。現假定對各個元素進行查找的概率是相同的，并且各個元素的關鍵項的值皆不相同。當用順序查找法查找時，平均比較次數約為 D ，最大比較次數為 E 。供選擇的答案：AC： 必須以順序方式存儲 必須以鏈表方式存儲 必須

4、以散列方式存儲 既可以以順序方式，也可以以鏈表方式存儲 必須以順序方式存儲且數據元素已按值遞增或遞減的次序排好 必須以鏈表方式存儲且數據元素已按值遞增或遞減的次序排好D，E： 25000 30000 45000 90000答案： A= B= C= D E 4. （96初程P73）從供選擇的答案中，選出應填入下面敘述 ？ 內的最確切的解答，把相應編號寫在答卷的對應欄內。數據結構反映了數據元素之間的結構關系。鏈表是一種 A ，它對于數據元素的插入和刪除 B 。通常查找線性表數據元素的方法有 C 和 D 兩種方法，其中 C 是一種只適合于順序存儲結構但 E 的方法；而 D 是一種對順序和鏈式存儲結構

5、均適用的方法。 供選擇的答案：A：順序存儲線性表 非順序存儲非線性表順序存儲非線性表 非順序存儲線性表B： 不需要移動結點，不需改變結點指針 不需要移動結點，只需改變結點指針 只需移動結點，不需改變結點指針 既需移動結點，又需改變結點指針C： 順序查找 循環查找 條件查找二分法查找D： 順序查找 隨機查找 二分法查找分塊查找E： 效率較低的線性查找 效率較低的非線性查找 效率較高的非線性查找效率較高的線性查找答案：A B C D E 三、簡答題（每小題4分，共16分）1.【全國專升本題】對分（折半）查找適不適合鏈表結構的序列，為什么？用二分查找的查找速度必然比線性查找的速度快，這種說法對嗎？

6、2.【計研題1999】假定對有序表：（3，4，5，7，24，30，42，54，63，72，87，95）進行折半查找，試回答下列問題：（1） 畫出描述折半查找過程的判定樹；（2） 若查找元素54，需依次與哪些元素比較？（3） 若查找元素90，需依次與哪些元素比較？4. 關鍵字集合 19, 01, 23, 14, 55, 68, 11, 82, 36 ,設定哈希函數 H(key) = key MOD 11 ( 表長=11 ),（1）若采用線性探測再散列處理沖突,a.則得到的哈希表為：b.若查找關鍵字20，需要依次與哪些關鍵字進行比較？C.若查找關鍵字68，需要依次與哪些關鍵字進行比較？（1） 若采用二次探測再散列處理沖突，a.則得到的哈希表為：b. 若查