數(shù)據(jù)結構復習題-第9章答案2014-6-16

1、若查找每個元素的概率相同，則平均查找長度為C. ND. （ 1+N ） *N /2n的順序表時，搜索成功的平均搜索長度為（D.（ n+1）/2A )°3. 當在一個有序的順序存儲表上查找一個數(shù)據(jù)時，既可用折半查找，也可用順序查找，但前 者比后者的查找速度（C ）。A.必定快C.在大部分情況下要快B.不一定D.取決于表遞增還是遞減（D4. 適用于折半查找的表的存儲方式及元素排列要求為A.鏈接方式存儲，元素無序C.順序方式存儲，元素無序5. 采用折半搜索算法搜索長度為A. O （n2）B. O （nlog 2n）6. 折半查找有序表（4，6，10， 它將依次與表中（AA. 20，70，3

2、0，507. 對二叉排序樹進行（A.前序B.中序B.鏈接方式存儲，元素有序D.順序方式存儲，元素有序n的有序表時，元素的平均搜索長度為（C. O （ log 2n） D. O （n）12，20，30，50，70，88，100）。若查找表中元素C )°58,則8. 下列二叉排序樹中，滿足平衡二叉樹定義的是（）比較大小，查找結果是失敗。B. 30，88，70，50C. 20，50 D. 30，88，50B ）遍歷，可以得到關鍵字的有序序列。C.后序D.層次B)°第9章查找一、選擇題（每小題 1分，共10分）1. 對長度為N的表做順序查找時，A. （ N+1）12B. N/22.

3、 采用順序搜索方法查找長度為A.n B. n/2C.（ n-1）/29. 鏈表適用于（ A ）查找A.順序B.二分法C.順序，也能二分法D.隨機10. 以下說法錯誤的是（ B ） °A. 散列法存儲的基本思想是由關鍵碼值決定數(shù)據(jù)的存儲地址B. 散列表的結點中只包含數(shù)據(jù)元素自身的信息，不包含任何指針C. 負載因子是散列表的一個重要參數(shù)，它反映了散列表的飽滿程度D. 散列表的查找效率主要取決于散列表造表時選取的散列函數(shù)和處理沖突的方法11 有一個有序表為 1，3，9，12，32，41，45, 62，75，77，82，95，100，當折半查 找值為82的結點時，（C ）次比較后查找成功。A

4、.11B 5C 4 D 812. 查找效率最高的二叉排序樹是（C ）°A.所有結點的左子樹都為空的二叉排序樹。B.所有結點的右子樹都為空的二叉排序樹。C.平衡二叉樹。 D.沒有左子樹的二叉排序樹。13. 有一個長度為12的有序表，按折半查找法對該表進行查找，在表內(nèi)各元素等概率的情況下查找成功所需的平均比較次數(shù)為（B ）°A. 35/12B 37/12C 39/12 D43/12二、判斷題（每小題 1分，共10分）1順序查找方法只能在順序存儲結構上進行。（錯）2二叉排序樹刪除一個葉子結點后，仍是二叉排序樹。（對）3在查找樹（二叉樹排序樹）中插入一個新結點，總是插入到葉結點下面

5、。（對）4在二叉排序樹中，新結點總是作為葉子結點來插入。（對）5.Hash表的平均查找長度與處理沖突的方法無關。（錯）6哈希表的查找效率主要取決于哈希表造表時選取的哈希函數(shù)和處理沖突的方法。（對 ）7對線性表進行折半查找時，要求線性表必須以鏈式方式存儲，且結點按關鍵字有序排列。（X ）8散列法存儲的思想是由關鍵字值決定數(shù)據(jù)的存儲地址。（V ）9二叉樹為二叉排序樹的充分必要條件是其任一結點的值均大于其左孩子的值、小于其右 孩子的值。（X ）10直接選擇排序算法在最好情況下的時間復雜度為0（n）。（X ）11. 二叉樹為二叉排序樹的充分必要條件是其任一結點的值均大于其左孩子的值、小于其右 孩子的值

6、。（X ）三、填空題（每空1分，共10分）1折半查找的時間復雜性為 。log 2n2. 設h是一哈希函數(shù)，key1和key2為關鍵碼值，且 key1豐key2，但h （key1） =h （key2）,這種現(xiàn)象稱為。沖突3. 順序查找不要求關鍵字 ，其ASL（平均查找長度）為;折半查找要求關鍵字，其ASL為。有序O（n）有序 問4. 平衡二叉排序樹上任一結點的平衡因子只可能是 、或。-1, 0, 1四、簡答題1. 敘述什么是二叉排序樹？答：二叉排序樹或者是一棵空樹；或者是具有如下特性的二叉樹：（1）若它的左子樹不空，則左子樹上所有結點的值均小于根結點的值；（2）若它的右子樹不空，則右子樹上所有結

7、點的值均大于根結點的值；（3）它的左、右子樹也都分別是二叉排序樹。二叉排序樹又稱二叉查找樹。2. 什么是平衡二叉樹（AVL樹）？答：平衡二叉樹又稱 AVL樹，它或是一棵空樹，或是具有下列性質的樹：它的左子樹和右 子樹均是平衡二叉樹，且左子樹和右子樹的深度之差絕對值不超過1。3. 為什么有序的單鏈表不能進行折半查找？答：因為鏈表無法進行隨機訪問， 如果要訪問鏈表的中間結點， 就必須先從頭結點開始進行 依次訪問，這就要浪費很多時間，還不如進行順序查找，而且，用鏈存儲結構將無法判定二分的過程是否結束，因此無法用鏈表實現(xiàn)二分查找。五、應用題無答案六、算法題1. （ 6分）編寫折半查找算法。答案一：in

8、t Search_Bin ( SSTable ST, KeyType key ) low = 1; high = ST.length; / 置區(qū)間初值while (low <= high) mid = (low + high) / 2;if ( EQ (key , ST.elemmid.key) ) return mid; / 找到待查元素else if ( LT (key , ST.elemmid.key) )high = mid - 1; / 繼續(xù)在前半?yún)^(qū)間進行查找 else low = mid + 1;/ 繼續(xù)在后半?yún)^(qū)間進行查找return 0; / 順序表中不存在待查元素 / S

9、earch_Bin答案二：int Locate_Bin(SSTable ST,int key)int *r; r=ST.elem; if(key<r .key) return 0;else if(key>=rST.length.key) return ST.length; low=1;high=ST.length; 1 分 while(low<high) mid=(low+high)/2; if(key>=rmid.key&&key<rmid+1.key) return mid; 3 分 else if(key<rmid.key) high=

10、mid-1;else low=mid+1; 6 分 2. (6 分)編寫順序查找算法。答案一：int Search_Seq( SSTable ST , KeyType key )/ 在順序表 ST 中，查找關鍵字與 key 相同的元素；若成功，返回其位置信息，否則返回 0 ST.elem0.key =key; / 設立哨兵 for( i=ST.length; ST.elem i .key!=key; - - i ) ;return i; / 查找不成功，返回 0 值 (i=0) 。 成功時則返回找到的那個元素的位置 i 。 / Search_Seq 答案二： int Search_Seq(SSTable ST, KeyType key)int i;for(i=1; i<=ST.length ; i+ );if(k=ST.elemi.key)return i