[精品]第9章自測(cè)卷答案

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

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

3、本思想是由關(guān)鍵字的值7. 有一個(gè)表長為 m的散列表，初始狀態(tài)為空，現(xiàn)將比較大小。n無關(guān)的查找方法是散列查找。決定數(shù)據(jù)的存儲(chǔ)地址。n(n<m)個(gè)不同的關(guān)鍵碼插入到散列表中，解決沖突的方法是用線性探測(cè)法。如果這 n個(gè)關(guān)鍵碼的散列地址都相同，則探測(cè)的總次數(shù)是n(n-1)/2=( 1+2+ +n-l)。(而任元素查找次數(shù)<n-I)二、單項(xiàng)選擇題(每小題1分，共27分)(B ) 1 .在表長為n的鏈表中進(jì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.【計(jì)研題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 .【計(jì)研題2001】對(duì)22個(gè)記錄的有序表作折半查找，當(dāng)查找失敗時(shí)，至少需要比較次關(guān)鍵字。A. 3B. 4C. 5D. 6(A ) 4.鏈表適用于查找A.順序B.二分法C.順序，也能二分法D,隨機(jī)(c )5.折半搜索與二叉搜索樹的時(shí)間性能A.相同B.完全不同C.有時(shí)不相同D.數(shù)量級(jí)都是

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

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

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

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

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

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

11、未必快。 例如所查數(shù)據(jù)位于首位時(shí)，則線性查找快；而二分查找則慢得多。2. 【計(jì)研題1999 假定對(duì)有序表：(3, 4, 5, 1, 24, 30, 42, 54, 63, 72, 87, 95)進(jìn)行折半查找，試 回答下列問題:(1) 畫岀描述折半查找過程的判定樹；(2) 若查找元素54,需依次與哪些元素比較？(3) 若查找元素90,需依次與哪些元素比較？(4) 假定每個(gè)元素的查找概率相等，求查找成功時(shí)的平均查找長度。解：(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)計(jì)每個(gè)元素的查找次數(shù)。判定樹的前但最后一層未滿，不能用 8X4,只能用5X4=20 次,所以 ASL=1/12 (17+20) =37/12A3.083. 【全國專升本題】用比較兩個(gè)元素大小的方法在一個(gè)給定的序列中查找某個(gè)元素的時(shí)間復(fù)雜度下限是什么?如果要求時(shí)間復(fù)雜度更小，你采用什么方法？此方法的時(shí)間復(fù)雜度是多少？答：查找某個(gè)元素的時(shí)間復(fù)雜度下限，如果理解為最短查找時(shí)間，則當(dāng)關(guān)鍵字值與表頭元素相同時(shí)，比較1次即可。要想降低時(shí)間復(fù)雜度，可以改用Hash查找法。此方法對(duì)表內(nèi)每個(gè)元素的比較次數(shù)都是0 (1)。4. 【計(jì)研

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

14、與 46, 47, 32, 17, 63相比，一共比較了 6次! 查找60,首先要與H(60)=60%16=12號(hào)單元內(nèi)容比較，但因?yàn)?12號(hào)單元為空(應(yīng)當(dāng)有空標(biāo)記)，所以 應(yīng)當(dāng) 只比較這一次即可。 對(duì)于黑色數(shù)據(jù)元素，各比較 1次；共6次；對(duì)紅色元素則各不相同，要統(tǒng)計(jì)移位的位數(shù)?！?3需要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?畫岀對(duì)長度為10的有序表進(jìn)行折半查找的判定樹，并求其等概率時(shí)查找成功的平均查找長 度。

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,請(qǐng)畫岀所2. 【全國專升本考題】在一棵空的二叉查找樹中依次插入關(guān)鍵字序列為得到的二叉查找樹。答：/ 12、八八JI/16 214913驗(yàn)算方法：用中序遍歷應(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) 若對(duì)表中元素先進(jìn)行排序構(gòu)成有序表，求在等概率的情況下對(duì)此有序表進(jìn)行折半查找時(shí)查找成功的平均查找長度。(3) 按表中元素順序構(gòu)造一棵平衡二叉排序樹，并求其在等概率的情況下查找成功的平均查找長度。 解：(1)求得的二叉排序樹如下圖所示，在等概率情況下查找成功的平均查找長度為ASL, e = %(1 X1 + 2X2 + 3X3 + 4X3 + 5X2 + 6X1)=普(2)經(jīng)排序后的表及在畔理時(shí)找到表中元素所經(jīng)比較的次數(shù)對(duì)照如下：Apr Aug De

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

18、,7430553r646701331910解：由題意知，m=ll(剛好為素?cái)?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è)計(jì)題(4中選3,第1題7分必選，其余每題8分，共23分)1. 已知11個(gè)元素的有序表為(05 13 19 21 37 56 64 75 80 88 92),請(qǐng)寫岀折半查找的算法程序，

19、查找關(guān)鍵字為key的數(shù)據(jù)元素(建議上機(jī)調(diào)試)。解：折半查找的 C程序有很多參考資料，注意此題要求是整型量。折半查找的一個(gè)遞歸算法如下，形式非常簡潔！int Search_Bin_Recursive(SSTable ST, i nt key, i nt low, i nt high)折半查找的遞歸算法(if(low>high) return 0;查找不到時(shí)返回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】試寫一個(gè)判別給定二叉樹是否為二叉排序樹的算法，設(shè)此二叉樹以二叉鏈表作存儲(chǔ)結(jié)構(gòu)。且樹中結(jié)點(diǎn)的關(guān)鍵字均不同。解：注意仔細(xì)研究二叉排序樹的定義。易犯的典型錯(cuò)誤是按下述思路進(jìn)行判別：“若一棵非空的二叉樹其左、右子樹均為二叉排序樹，且左子樹的根的值小于根結(jié)點(diǎn)的值，又根結(jié)點(diǎn)的值不大于右子樹的根的值，則是二叉排序樹”(劉注：即不能只判斷左右孩子的情況，還要判斷左右孩子與雙親甚至根結(jié)點(diǎn)的比值也要

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