第9章自測(cè)卷答案

1、-作者xxxx-日期xxxx第9章自測(cè)卷答案【精品文檔】第8章 查找 自測(cè)卷答案 一、填空題（每空1分，共10分）1. 在數(shù)據(jù)的存放無規(guī)律而言的線性表中進(jìn)行檢索的最佳方法是 順序查找（線性查找） 。2. 線性有序表（a1，a2，a3，a256)是從小到大排列的，對(duì)一個(gè)給定的值k，用二分法檢索表中與k相等的元素，在查找不成功的情況下，最多需要檢索 8 次。設(shè)有100個(gè)結(jié)點(diǎn)，用二分法查找時(shí)，最大比較次數(shù)是 7 。3. 假設(shè)在有序線性表a20上進(jìn)行折半查找，則比較一次查找成功的結(jié)點(diǎn)數(shù)為1；比較兩次查找成功的結(jié)點(diǎn)數(shù)為 2 ；比較四次查找成功的結(jié)點(diǎn)數(shù)為 8 ；平均查找長(zhǎng)度為 。解：顯然，平均查找長(zhǎng)度O（

2、log2n）<5次（25）。但具體是多少次，則不應(yīng)當(dāng)按照公式來計(jì)算（即（21×log221）/204.6次并不正確?。?。因?yàn)檫@是在假設(shè)n2m-1的情況下推導(dǎo)出來的公式。應(yīng)當(dāng)用窮舉法羅列：全部元素的查找次數(shù)為（12×24×38×45×5）74； ASL74/20=3.7 ！4折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它將依次與表中元素 28，6，12，20 比較大小。5. 在各種查找方法中，平均查找長(zhǎng)度與結(jié)點(diǎn)個(gè)數(shù)n無關(guān)的查找方法是 散列查找 。6. 散列法存儲(chǔ)的基本思想是由 關(guān)鍵字的值

3、決定數(shù)據(jù)的存儲(chǔ)地址。7. 有一個(gè)表長(zhǎng)為m的散列表，初始狀態(tài)為空，現(xiàn)將n（n<m）個(gè)不同的關(guān)鍵碼插入到散列表中，解決沖突的方法是用線性探測(cè)法。如果這n個(gè)關(guān)鍵碼的散列地址都相同，則探測(cè)的總次數(shù)是 n(n-1)/2=（ 12n-1） 。(而任一元素查找次數(shù) n-1)二、單項(xiàng)選擇題（每小題1分，共27分）（ B ）1在表長(zhǎng)為的鏈表中進(jìn)行線性查找，它的平均查找長(zhǎng)度為. ; . （）; . ; . （）（ A ）2折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，則它將依次與表中 比較大小，查找結(jié)果是失敗。A20，70，30，50 B30，88，70，5

4、0 C20，50 D30，88，50（ C ）3對(duì)22個(gè)記錄的有序表作折半查找，當(dāng)查找失敗時(shí)，至少需要比較 次關(guān)鍵字。A3 B4 C5 D 6（ A ）4. 鏈表適用于 查找A順序 B二分法 C順序，也能二分法 D隨機(jī)（ C ）5. 折半搜索與二叉搜索樹的時(shí)間性能 A. 相同 B. 完全不同 C. 有時(shí)不相同 D. 數(shù)量級(jí)都是O（log2n）6從供選擇的答案中，選出應(yīng)填入下面敘述 ？ 內(nèi)的最確切的解答，把相應(yīng)編號(hào)寫在答卷的對(duì)應(yīng)欄內(nèi)。要進(jìn)行線性查找，則線性表 A ；要進(jìn)行二分查找，則線性表 B ；要進(jìn)行散列查找，則線性表 C 。某順序存儲(chǔ)的表格，其中有90000個(gè)元素，已按關(guān)鍵項(xiàng)的值的上升順序排

5、列?，F(xiàn)假定對(duì)各個(gè)元素進(jìn)行查找的概率是相同的，并且各個(gè)元素的關(guān)鍵項(xiàng)的值皆不相同。當(dāng)用順序查找法查找時(shí)，平均比較次數(shù)約為 D ，最大比較次數(shù)為 E 。供選擇的答案：AC： 必須以順序方式存儲(chǔ) 必須以鏈表方式存儲(chǔ) 必須以散列方式存儲(chǔ) 既可以以順序方式，也可以以鏈表方式存儲(chǔ) 必須以順序方式存儲(chǔ)且數(shù)據(jù)元素已按值遞增或遞減的次序排好 必須以鏈表方式存儲(chǔ)且數(shù)據(jù)元素已按值遞增或遞減的次序排好D，E： 25000 30000 45000 90000答案： A= B= C= D E 7.從供選擇的答案中，選出應(yīng)填入下面敘述 ？ 內(nèi)的最確切的解答，把相應(yīng)編號(hào)寫在答卷的對(duì)應(yīng)欄內(nèi)。數(shù)據(jù)結(jié)構(gòu)反映了數(shù)據(jù)元素之間的結(jié)構(gòu)關(guān)系。

6、鏈表是一種 A ，它對(duì)于數(shù)據(jù)元素的插入和刪除 B 。通常查找線性表數(shù)據(jù)元素的方法有 C 和 D 兩種方法，其中 C 是一種只適合于順序存儲(chǔ)結(jié)構(gòu)但 E 的方法；而 D 是一種對(duì)順序和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)均適用的方法。 供選擇的答案：A：順序存儲(chǔ)線性表 非順序存儲(chǔ)非線性表順序存儲(chǔ)非線性表 非順序存儲(chǔ)線性表B： 不需要移動(dòng)結(jié)點(diǎn)，不需改變結(jié)點(diǎn)指針 不需要移動(dòng)結(jié)點(diǎn)，只需改變結(jié)點(diǎn)指針 只需移動(dòng)結(jié)點(diǎn)，不需改變結(jié)點(diǎn)指針 既需移動(dòng)結(jié)點(diǎn)，又需改變結(jié)點(diǎn)指針C： 順序查找 循環(huán)查找 條件查找二分法查找D： 順序查找 隨機(jī)查找 二分法查找分塊查找E： 效率較低的線性查找 效率較低的非線性查找 效率較高的非線性查找效率較高的線性

7、查找答案：A B C D E 8. 從供選擇的答案中，選出應(yīng)填入下面敘述 ？ 內(nèi)的最確切的解答，把相應(yīng)編號(hào)寫在答卷的對(duì)應(yīng)欄內(nèi)。在二叉排序樹中，每個(gè)結(jié)點(diǎn)的關(guān)鍵碼值 A ， B 一棵二叉排序，即可得到排序序列。同一個(gè)結(jié)點(diǎn)集合，可用不同的二叉排序樹表示，人們把平均檢索長(zhǎng)度最短的二叉排序樹稱作最佳二叉排序，最佳二叉排序樹在結(jié)構(gòu)上的特點(diǎn)是 C 。供選擇的答案A： 比左子樹所有結(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: 前序遍歷 中序

8、（對(duì)稱）遍歷 后序遍歷 層次遍歷C： 除最下二層可以不滿外，其余都是充滿的 除最下一層可以不滿外，其余都是充滿的 每個(gè)結(jié)點(diǎn)的左右子樹的高度之差的絕對(duì)值不大于1 最下層的葉子必須在最左邊答案：A B C 9. 從供選擇的答案中，選出應(yīng)填入下面敘述 ？ 內(nèi)的最確切的解答，把相應(yīng)編號(hào)寫在答卷的對(duì)應(yīng)欄內(nèi)。散列法存儲(chǔ)的基本思想是根據(jù) A 來決定 B ，碰撞（沖突）指的是 C ，處理碰撞的兩類主要方法是 D 。供選擇的答案A，B： 存儲(chǔ)地址 元素的符號(hào) 元素個(gè)數(shù) 關(guān)鍵碼值 非碼屬性 平均檢索長(zhǎng)度 負(fù)載因子 散列表空間 C: 兩個(gè)元素具有相同序號(hào) 兩個(gè)元素的關(guān)鍵碼值不同，而非碼屬性相同 不同關(guān)鍵碼值對(duì)應(yīng)到相

9、同的存儲(chǔ)地址 負(fù)載因子過大 數(shù)據(jù)元素過多D： 線性探查法和雙散列函數(shù)法 建溢出區(qū)法和不建溢出區(qū)法 除余法和折疊法 拉鏈法和開地址法答案：A B C D 10.考慮具有如下性質(zhì)的二叉樹：除葉子結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)的值都大于其左子樹上的一切結(jié)點(diǎn)的值。并小于等于其右子樹上的一切結(jié)點(diǎn)的值?，F(xiàn)把9個(gè)數(shù)1，2，3，8，9填入右圖所示的二叉樹的9個(gè)結(jié)點(diǎn)中，并使之具有上述性質(zhì)。此時(shí)，n1的值是 A ，n2的值是 B ，n9的值是 C 。現(xiàn)欲把放入此樹并使該樹保持前述性質(zhì)，增加的一個(gè)結(jié)點(diǎn)可以放在 D 或 E 。供選擇的答案AC： 1 2 3 4 5 6 7 8 9DE： n7下面 n8下面 n9下面 n6下面 n1

10、與n2之間 n2與n4之間 n6與n9之間 n3與n6之間 答案：A B C D E 三、簡(jiǎn)答題（每小題4分，共16分）1.對(duì)分（折半）查找適不適合鏈表結(jié)構(gòu)的序列，為什么？用二分查找的查找速度必然比線性查找的速度快，這種說法對(duì)嗎？答：不適合！雖然有序的單鏈表的結(jié)點(diǎn)是按從小到大（或從大到小）順序排列，但因其存儲(chǔ)結(jié)構(gòu)為單鏈表，查找結(jié)點(diǎn)時(shí)只能從頭指針開始逐步搜索，故不能進(jìn)行折半查找。二分查找的速度在一般情況下是快些，但在特殊情況下未必快。例如所查數(shù)據(jù)位于首位時(shí)，則線性查找快；而二分查找則慢得多。2.假定對(duì)有序表：（3，4，5，7，24，30，42，54，63，72，87，95）進(jìn)行折半查找，試回答下

11、列問題：（1） 畫出描述折半查找過程的判定樹；（2） 若查找元素54，需依次與哪些元素比較？（3） 若查找元素90，需依次與哪些元素比較？（4） 假定每個(gè)元素的查找概率相等，求查找成功時(shí)的平均查找長(zhǎng)度。解：（1） 先畫出判定樹如下（注：mid=ë(1+12)/2û=6）：305 633 7 42 87 4 24 54 72 95(2) 查找元素54，需依次與30, 63, 42, 54 等元素比較；(3) 查找元素90，需依次與30, 63,87, 95, 72等元素比較；（4） 求ASL之前，需要統(tǒng)計(jì)每個(gè)元素的查找次數(shù)。判定樹的前3層共查找12×24×

12、3=17次；但最后一層未滿，不能用8×4，只能用5×4=20次，所以ASL1/12（1720）37/123.用比較兩個(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ù)都是O（1）。4.設(shè)哈希（Hash）表的地址范圍為017，哈希函數(shù)為：H（K）K MOD 16。K為關(guān)鍵字，用線性探測(cè)法再散列法處理沖突，輸入關(guān)鍵字

13、序列： （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í)的平均查找長(zhǎng)度。解： （1）畫表如下：012345678910111213141516173217634924401030314647（2） 查找63,首先要與H(63)=63%16=15號(hào)單元內(nèi)容比較，即63 vs 31 ,no;然后順移，與46,47,32,17,63相比，一共比較了6次！（3）查找6

14、0,首先要與H(60)=60%16=12號(hào)單元內(nèi)容比較，但因?yàn)?2號(hào)單元為空（應(yīng)當(dāng)有空標(biāo)記），所以應(yīng)當(dāng)只比較這一次即可。（4） 對(duì)于黑色數(shù)據(jù)元素，各比較1次；共6次；對(duì)紅色元素則各不相同，要統(tǒng)計(jì)移位的位數(shù)?！?3”需要6次，“49”需要3次，“40”需要2次，“46”需要3次，“47”需要3次，所以ASL=1/11（623×3）17/11=1.5454545454四、分析題（每小題6分，共24分）1. 】畫出對(duì)長(zhǎng)度為10的有序表進(jìn)行折半查找的判定樹，并求其等概率時(shí)查找成功的平均查找長(zhǎng)度。解：判定樹應(yīng)當(dāng)描述每次查找的位置：52 81 3 6 9 4 7 102.在一棵空的二叉查找樹中依

15、次插入關(guān)鍵字序列為12，7，17，11，16，2，13，9，21，4，請(qǐng)畫出所得到的二叉查找樹。答： 127 17 2 11 16 21 4 9 13驗(yàn)算方法： 用中序遍歷應(yīng)得到排序結(jié)果： 2,4,7,9,11,12,13,16,17，213. 】已知如下所示長(zhǎng)度為12的表：（Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec）(1) 試按表中元素的順序依次插入一棵初始為空的二叉排序樹，畫出插入完成之后的二叉排序樹，并求其在等概率的情況下查找成功的平均查找長(zhǎng)度。(2) 若對(duì)表中元素先進(jìn)行排序構(gòu)成有序表，求在等概率的情況下對(duì)此

16、有序表進(jìn)行折半查找時(shí)查找成功的平均查找長(zhǎng)度。(3) 按表中元素順序構(gòu)造一棵平衡二叉排序樹，并求其在等概率的情況下查找成功的平均查找長(zhǎng)度。解：4. 選取散列函數(shù)H（key）=（3*key）%11，用線性探測(cè)法處理沖突，對(duì)下列關(guān)鍵碼序列構(gòu)造一個(gè)散列地址空間為010，表長(zhǎng)為11的散列表，22，41，53，08，46，30，01，31，66。解：由題意知，m=11(剛好為素?cái)?shù))地址值鏈接指針022116624133084,7430553646701831910則(22*3)%11=60 (41*3)%11=112 (53*3)%11=145(08*3)%11=22(46*3)%11=126(30*3)

17、%11=82(01*3)%11=03(31*3)%11=85(66*3)%11=902266418305346131012345678910134，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)寫出折半查找的算法程序，查找關(guān)鍵字為key的數(shù)據(jù)元素 (建議上機(jī)調(diào)試)。解：折半查找的C程序有很多參考資料，注意此題要求是整型量。折半查找的一個(gè)遞歸算法如下，形式非常簡(jiǎn)潔！int Search_Bin_Recursive(SSTable ST, int key, int low,

18、 int high) /折半查找的遞歸算法 if(low>high) return 0; /查找不到時(shí)返回0 mid=(low+high)/2; if(ST.elemmid.key= =key) return mid; else if(ST.elemmid.key>key) return Search_Bin_Recursive(ST, key, low, mid-1); else return Search_Bin_Recursive(ST, key, mid+1, high); /Search_Bin_Recursive 】試寫一個(gè)判別給定二叉樹是否為二叉排序樹的算法，設(shè)此二叉

19、樹以二叉鏈表作存儲(chǔ)結(jié)構(gòu)。且樹中結(jié)點(diǎn)的關(guān)鍵字均不同。解：注意仔細(xì)研究二叉排序樹的定義。易犯的典型錯(cuò)誤是按下述思路進(jìn)行判別：“若一棵非空的二叉樹其左、右子樹均為二叉排序樹，且左子樹的根的值小于根結(jié)點(diǎn)的值，又根結(jié)點(diǎn)的值不大于右子樹的根的值，則是二叉排序樹”（即不能只判斷左右孩子的情況，還要判斷左右孩子與雙親甚至根結(jié)點(diǎn)的比值也要遵循（左小右大）原則）。若要采用遞歸算法，建議您采用如下的函數(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=0, flag=1; / last是全局變量，用來記錄前驅(qū)結(jié)點(diǎn)值，只要每個(gè)結(jié)點(diǎn)都比前驅(qū)大就行。int Is_BSTree(Bitree T) /判斷二叉樹T是否二叉排序樹，是則返回1，否則返回0 if(T->lchild&&flag) Is_BSTree(T->lchild); if(T->data<last) flag=0; /與其中序前驅(qū)相比