數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題-第9章答案2014-6-16

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

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

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

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

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

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

7、點(diǎn)的值均大于根結(jié)點(diǎn)的值；（3）它的左、右子樹也都分別是二叉排序樹。二叉排序樹又稱二叉查找樹。2. 什么是平衡二叉樹（AVL樹）？答：平衡二叉樹又稱 AVL樹，它或是一棵空樹，或是具有下列性質(zhì)的樹：它的左子樹和右 子樹均是平衡二叉樹，且左子樹和右子樹的深度之差絕對(duì)值不超過1。3. 為什么有序的單鏈表不能進(jìn)行折半查找？答：因?yàn)殒湵頍o法進(jìn)行隨機(jī)訪問， 如果要訪問鏈表的中間結(jié)點(diǎn)， 就必須先從頭結(jié)點(diǎn)開始進(jìn)行 依次訪問，這就要浪費(fèi)很多時(shí)間，還不如進(jìn)行順序查找，而且，用鏈存儲(chǔ)結(jié)構(gòu)將無法判定二分的過程是否結(jié)束，因此無法用鏈表實(shí)現(xiàn)二分查找。五、應(yīng)用題無答案六、算法題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ū)間進(jìn)行查找 else low = mid + 1;/ 繼續(xù)在后半?yún)^(qū)間進(jìn)行查找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 中，查找關(guān)鍵字與 key 相同的元素；若成功，返回其位置信息，否則返回 0 ST.elem0.key =key; / 設(shè)立哨兵 for( i=ST.length; ST.elem i .key!=key; - - i ) ;return i; / 查找不成功，返回 0 值 (i=0) 。 成功時(shí)則返回找到的那個(gè)元素的位置 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