[精品]第9章自測卷答案

1、題號三四五總分題分1027162423100得分一、填空題(每空I分，共10分)1. 在數(shù)據(jù)的存放無規(guī)律而言的線性表中進行檢索的最佳方法是順序查找(線性查找)。2. 線性有序表(a】，a?, a3 ,，a?56)是從小到大排列的，對一個給定的值k,用二分法檢索表中與k相 等的元素，在查找不成功的情況下，最多需要檢索次。設(shè)有100個結(jié)點，用二分法查找時，最大比 較次數(shù)是_03. 假設(shè)在有序線性表a : 20上進行折半查找，則比較一次查找成功的結(jié)點數(shù)為1;比較兩次查找成功的結(jié)點數(shù)為2；比較四次查找成功的結(jié)點數(shù)為* ；平均查找長度為37。解：顯然，平均查找長度 =0 (logm) <5次(2、

2、)。但具體是多少次，則不應(yīng)當(dāng)按照公式A5L = Iog2(,i + I)來計算(即(21 x log 221 ) /20 = 4. 6次并不正確！)。因為這是在假設(shè)n = 2m-l的情況下 n推導(dǎo)岀來的公式。應(yīng)當(dāng)用窮舉法羅列：全部元素的查找次數(shù)為 =(1 + 2X2 + 4X3 + 8X4 + 5X5) =74; ASL = 74/20=3. 7 !4. 【計研題2000折半查找有序表(4, 6, 12, 20, 28, 38, 50, 70, 88, 100),若查找表中元素 20,它將依次與表中元素28, 6, 12, 205. 在各種查找方法中，平均查找長度與結(jié)點個數(shù)6. 散列法存儲的基

3、本思想是由關(guān)鍵字的值7. 有一個表長為 m的散列表，初始狀態(tài)為空，現(xiàn)將比較大小。n無關(guān)的查找方法是散列查找。決定數(shù)據(jù)的存儲地址。n(n<m)個不同的關(guān)鍵碼插入到散列表中，解決沖突的方法是用線性探測法。如果這 n個關(guān)鍵碼的散列地址都相同，則探測的總次數(shù)是n(n-1)/2=( 1+2+ +n-l)。(而任元素查找次數(shù)<n-I)二、單項選擇題(每小題1分，共27分)(B ) 1 .在表長為n的鏈表中進行線性查找，它的平均查找長度為A. A S L = n;B. AS L= (n+ 1 ) / 2;C. A S L = Vn + 1 ; D. ASLAI og 2 (n + 1) -1(A

4、 ) 2.【計研題2001】折半查找有序表(4, 6, 10, 12, 20, 30, 50, 70, 88, 100)=若查找表中元素58,則它將依次與表中 比較大小，查找結(jié)果是失敗。A. 20, 70, 30, 50 B. 30, 88, 70, 50 C. 20, 50 D. 30, 88, 50(C )3 .【計研題2001】對22個記錄的有序表作折半查找，當(dāng)查找失敗時，至少需要比較次關(guān)鍵字。A. 3B. 4C. 5D. 6(A ) 4.鏈表適用于查找A.順序B.二分法C.順序，也能二分法D,隨機(c )5.折半搜索與二叉搜索樹的時間性能A.相同B.完全不同C.有時不相同D.數(shù)量級都是

5、0 (Iog2n )6.【91程P3】從供選擇的答案中，選岀應(yīng)填入下面敘述丄內(nèi)的最確切的解答，把相應(yīng)編號寫在答卷的對應(yīng)欄內(nèi)。要進行線性查找，則線性表A ;要進行二分查找，則線性表；要進行散列查找，則線性表C。某順序存儲的表格，其中有 90000個元素，已按關(guān)鍵項的值的上升順序排列。現(xiàn)假定對各個元素進行查找的概率是相同的，并且各個元素的關(guān)鍵項的值皆不相同。當(dāng)用順序查找法查找時，平均比較次數(shù)約為D,最大比較次數(shù)為E。供選擇的答案：A-C :必須以順序方式存儲必須以鏈表方式存儲必須以散列方式存儲 既可以以順序方式，也可以以鏈表方式存儲 必須以順序方式存儲且數(shù)據(jù)元素已按值遞增或遞減的次序排好 必須以鏈

6、表方式存儲且數(shù)據(jù)元素已按值遞增或遞減的次序排好D, E : 25000 30000 45000 90000答案：A=B=C=D=E=7. ( 96初程P73 )從供選擇的答案中， 在答卷的對應(yīng)欄內(nèi)。數(shù)據(jù)結(jié)構(gòu)反映了數(shù)據(jù)元素之間的結(jié)構(gòu)關(guān)系 性表數(shù)據(jù)元素的方法有和 D兩種方法順序和鏈?zhǔn)酱鎯Y(jié)構(gòu)均適用的方法。供選擇的答案：選岀應(yīng)填入下面敘述內(nèi)的最確切的解答，把相應(yīng)編號寫鏈表是一種A,它對于數(shù)據(jù)元素的插入和刪除B。通常查找線,其中C是一種只適合于順序存儲結(jié)構(gòu)但 E的方法：而D是一種對A :順序存儲線性表非順序存儲非 線性表B :不需要移動結(jié)點，不需改變結(jié)點 指針只需移動結(jié)點，不需改變結(jié)點 指針順序存儲非

7、線性表非順序存儲線性表不需要移動結(jié)點，只需改變結(jié)點指針既需移動結(jié)點，又需改變結(jié)點指針條件查找二分法查找二分法查找分塊查找效率較低的非線性查找效率較高的線性查找C= D=?C :順序查找循環(huán)查找D:順序查找隨機查找E:效率較低的線性查找效率較高的非線性查找 答案：A=B=8. 【97程P18】 從供選擇的答案中，選岀應(yīng)填入下面敘述 ?內(nèi)的最確切的解答，把相應(yīng)編號寫在答卷的對應(yīng)欄內(nèi)。在二叉排序樹中，每個結(jié)點的關(guān)鍵碼值里，R 一棵二叉排序，即可得到排序序列。同一個結(jié)點集合，可用不同的二叉排序樹表示，人們把平均檢索長度最短的二叉排序樹稱作最佳二叉排序，最佳二叉排序樹在結(jié)構(gòu)上的特點是C。供選擇的答案A

8、:比左子樹所有結(jié)點的關(guān)鍵碼值大，比右子樹所有結(jié)點的關(guān)鍵碼值小比左子樹所有結(jié)點的關(guān)鍵碼值小，比右子樹所有結(jié)點的關(guān)鍵碼值大比左右子樹的所有結(jié)點的關(guān)鍵碼值都大 與左子樹所有結(jié)點的關(guān)鍵碼值和右子樹所有結(jié)點的關(guān)鍵碼值無必然的大小關(guān)系B：前序遍歷 中序（對稱）遍歷后序遍歷層次遍歷C :除最下二層可以不滿外，其余都是充滿的除最下一層可以不滿外，其余都是充滿的最下層的葉子必須在最左邊每個結(jié)點的左右子樹的高度之差的絕對值不大于答案：A=B=C=9. 92程P6從供選擇的答案中，選岀應(yīng)填入下面敘述 ？ 內(nèi)的最確切的解答，把相應(yīng)編號寫在答卷的對應(yīng)欄內(nèi)。散列法存儲的基本思想是根據(jù)卷 _來決定 旦，碰撞（沖突）指的是C

9、,處理碰撞的兩類主要方法是 D。供選擇的答案A, B :存儲地址兀素的符號元素個數(shù)關(guān)鍵碼值非碼屬性平均檢索長度負載因子散列表空間C：兩個兀素具有相冋序號兩個元素的關(guān)鍵碼值不同，而非碼屬性相同不同關(guān)鍵碼值對應(yīng)到相同的存儲地址負載因子過大數(shù)據(jù)元素過多D :線性探查法和雙散列函數(shù)法建溢出區(qū)法和不建溢出區(qū)法D=除余法和折疊法拉鏈法和開地址法答案：A= B=C=10. 91程P4】考慮具有如下性質(zhì)的二叉樹： 除葉子結(jié)點外，每個結(jié)點 的值都大于其左子樹上的一切結(jié)點的值。并小于等于其右子樹上的一切結(jié)點的值?，F(xiàn)把9個數(shù)1,2, 3,8, 9填入右圖所示的二叉樹的9個 結(jié)點中，并使之具有上述性質(zhì)。此時,nl的值

10、是 A , n2的值 是 旦，n9的值是_o現(xiàn)欲把應(yīng)放入此樹并使該樹保持前述性質(zhì)，增加的一個結(jié)點可以放在D或ED? E :n7下面n8下面n9下面nl與n2之間n2與n4之間n6與n9之間n3與n6之間n6下面答案：A=B=C=D=E=三、簡答題（每小題4分，共16分）1. 【全國專升本題】對分（折半）查找適不適合鏈表結(jié)構(gòu)的序列，為什么？用二分查找的查找速度必然比 線性查找的速度快，這種說法對嗎？答：不適合！雖然有序的單鏈表的結(jié)點是按從小到大(或從大到小)順序排列，但因其存儲結(jié)構(gòu)為單鏈表 ，查找結(jié)點時只能從頭指針開始逐步搜索，故不能進行折半查找。二分查找的速度在一般情況下是快些，但在特殊情況下

11、未必快。 例如所查數(shù)據(jù)位于首位時，則線性查找快；而二分查找則慢得多。2. 【計研題1999 假定對有序表：(3, 4, 5, 1, 24, 30, 42, 54, 63, 72, 87, 95)進行折半查找，試 回答下列問題:(1) 畫岀描述折半查找過程的判定樹；(2) 若查找元素54,需依次與哪些元素比較？(3) 若查找元素90,需依次與哪些元素比較？(4) 假定每個元素的查找概率相等，求查找成功時的平均查找長度。解：(1) 先畫岀判定樹如下(注：mid=L(l+12)/2j=6):查找元素54,需依次與30,63,42,54等元素比較； 查找元素90,需依次與30, 63,87,95, 7

12、2等元素比較；3層共查找1+2X2+4X3=17 次;(4)求ASL之前，需要統(tǒng)計每個元素的查找次數(shù)。判定樹的前但最后一層未滿，不能用 8X4,只能用5X4=20 次,所以 ASL=1/12 (17+20) =37/12A3.083. 【全國專升本題】用比較兩個元素大小的方法在一個給定的序列中查找某個元素的時間復(fù)雜度下限是什么?如果要求時間復(fù)雜度更小，你采用什么方法？此方法的時間復(fù)雜度是多少？答：查找某個元素的時間復(fù)雜度下限，如果理解為最短查找時間，則當(dāng)關(guān)鍵字值與表頭元素相同時，比較1次即可。要想降低時間復(fù)雜度，可以改用Hash查找法。此方法對表內(nèi)每個元素的比較次數(shù)都是0 (1)。4. 【計研

13、題1999設(shè)哈希(Hash)表的地址范圍為 0? 17,哈希函數(shù)為：H (K) =K MOD 16K為關(guān)鍵字，用線性探測法再散列法處理沖突，輸入關(guān)鍵字序列：(10, 24, 32, 17, 31,30, 46, 47, 40, 63, 49)造岀Hash表，試回答下列問題：(1) 畫岀哈希表的示意圖；(2) 若查找關(guān)鍵字63，需要依次與哪些關(guān)鍵字進行比較？(3) 若查找關(guān)鍵字60,需要依次與哪些關(guān)鍵字比較？(4) 假定每個關(guān)鍵字的查找概率相等，求查找成功時的平均查找長度。解：(1)畫表如下012345678910111213141516173217634924401030314647然后順移，

14、與 46, 47, 32, 17, 63相比，一共比較了 6次! 查找60,首先要與H(60)=60%16=12號單元內(nèi)容比較，但因為 12號單元為空(應(yīng)當(dāng)有空標(biāo)記)，所以 應(yīng)當(dāng) 只比較這一次即可。 對于黑色數(shù)據(jù)元素，各比較 1次；共6次；對紅色元素則各不相同，要統(tǒng)計移位的位數(shù)。“63需要6次，“49需要3次，“40需要2次，“46需 要3次，“ 47需要3次，所以 ASL=1/11 (6+2+3X3) =17/11=1.5454545454人 1.55四、分析題(每小題6分，共24分)1. 【嚴(yán)題集9.3?畫岀對長度為10的有序表進行折半查找的判定樹，并求其等概率時查找成功的平均查找長 度。

15、解：判定樹應(yīng)當(dāng)描述每次查找的位置ASL=l/10 (1 + 2X2 + 3X4+4X3)=1/10 (1+4+12+12) =29/10=2.912, 7, 17, 11, 16, 2, 13, 9, 21,4,請畫岀所2. 【全國專升本考題】在一棵空的二叉查找樹中依次插入關(guān)鍵字序列為得到的二叉查找樹。答：/ 12、八八JI/16 214913驗算方法：用中序遍歷應(yīng)得到排序結(jié)果：2,4,7,9,11,12,13,16,17, 213. 【嚴(yán)題集9.9已知如下所示長度為12的表：(Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, D

16、ec)(1) 試按表中元素的順序依次插入一棵初始為空的二叉排序樹，畫岀插入完成之后的二叉排序樹，并求其在等概率的情況下查找成功的平均查找長度。(2) 若對表中元素先進行排序構(gòu)成有序表，求在等概率的情況下對此有序表進行折半查找時查找成功的平均查找長度。(3) 按表中元素順序構(gòu)造一棵平衡二叉排序樹，并求其在等概率的情況下查找成功的平均查找長度。 解：(1)求得的二叉排序樹如下圖所示，在等概率情況下查找成功的平均查找長度為ASL, e = %(1 X1 + 2X2 + 3X3 + 4X3 + 5X2 + 6X1)=普(2)經(jīng)排序后的表及在畔理時找到表中元素所經(jīng)比較的次數(shù)對照如下：Apr Aug De

17、c Feb Jan July Ju ne Mar May Nov Oct Sept342341342434等概率情況下查找成功時的平均查找長度為AS J = 土 (1 X1 + 2X2 + 3X4 + 4X5)=答它在等概率情況下的平均查找長度為38ASL = 土 ( 1 X1+2X2 + 3X4 + 4X4 + 5X1)= 行4. 選取散列函數(shù) H (key) = (3*key) % 11,用線性探測法處理沖突，對下列關(guān)鍵碼序列構(gòu)造一個散列地址空間為? 10,表長為 11 的散列表，22, 41,53, 08, 46, 30, 01, 31, 66地址值鏈接指針022116624133084

18、,7430553r646701331910解：由題意知，m=ll(剛好為素數(shù))則(22*3) % 11=60(41*3) % 11=112(53*3) % 11=145(08*3) % 1仁22(46*3) % 11=126(30*3) % 1仁82(01*3) % 11=0 3(31*3)%11=8 5(66*3) % 11=9 02266418305346 | 131012345678910134?7五、算法設(shè)計題(4中選3,第1題7分必選，其余每題8分，共23分)1. 已知11個元素的有序表為(05 13 19 21 37 56 64 75 80 88 92),請寫岀折半查找的算法程序，

19、查找關(guān)鍵字為key的數(shù)據(jù)元素(建議上機調(diào)試)。解：折半查找的 C程序有很多參考資料，注意此題要求是整型量。折半查找的一個遞歸算法如下，形式非常簡潔！int Search_Bin_Recursive(SSTable ST, i nt key, i nt low, i nt high)折半查找的遞歸算法(if(low>high) return 0;查找不到時返回0mid=(low+high)/2;if(ST.elemmid .key= =key) return mid;else if(ST.elemmid .key>key)return Search_Bin_Recursive(ST,

20、 key, low, mid-1);else return Search_Bin_Recursive(ST, key, mid+1, high);) /Search_B in_Recursive2. 【嚴(yán)題集9.31】試寫一個判別給定二叉樹是否為二叉排序樹的算法，設(shè)此二叉樹以二叉鏈表作存儲結(jié)構(gòu)。且樹中結(jié)點的關(guān)鍵字均不同。解：注意仔細研究二叉排序樹的定義。易犯的典型錯誤是按下述思路進行判別：“若一棵非空的二叉樹其左、右子樹均為二叉排序樹，且左子樹的根的值小于根結(jié)點的值，又根結(jié)點的值不大于右子樹的根的值，則是二叉排序樹”(劉注：即不能只判斷左右孩子的情況，還要判斷左右孩子與雙親甚至根結(jié)點的比值也要

21、遵循(左小右大)原則)。若要采用遞歸算法，建議您采用如下的函數(shù)首部：bool BisortTree(BiTree T, BiTree&PRE),其中PRE為指向當(dāng)前訪問結(jié)點的前驅(qū)的指針。(或者直接存儲前驅(qū)的數(shù)值，隨時與當(dāng)前根結(jié)點比較)一個漂亮的算法設(shè)計如下：int last=O, flag=l;/ last是全局變量，用來記錄前驅(qū)結(jié)點值，只要每個結(jié)點都比前驅(qū)大就行。int Is_BSTree(Bitree T) 判斷二叉樹 T是否二叉排序樹，是則返回1,否則返回0if(T->lchild&&flag) ls_BSTree(T->lchild);if(T->data<last) f