2021年第9章自測卷答案

第8章查找自測卷答案歐陽光明（2021.03.07）一、填空題（每空1分，共10分）在數(shù)據(jù)的存放無規(guī)律而言的線性表中進(jìn)行檢索的最佳方法是順序查找（線性查找）線性有序表（a”a2，a3，?…a256）是從小到大排列的，對(duì)一個(gè)給定的值k用二分法檢索表中與k相等的元素，在查找不成功的情況下，最多需要檢索§_次。設(shè)有100個(gè)結(jié)點(diǎn)，用二分法查找時(shí)，最大比較次數(shù)是7假設(shè)在有序線性表a[20]上進(jìn)行折半查找，則比較一次查找成功的結(jié)點(diǎn)數(shù)為1；比較兩次查找成功的結(jié)點(diǎn)數(shù)為2_;比較四次查找成功的結(jié)點(diǎn)數(shù)為丄；平均查找長度為3.7解：顯然，平均查找長度=O（log，"）＜5次（25）。但具體是多少次，則不應(yīng)當(dāng)按照公式ASL=n±1iog2（n+1）來計(jì)算（即（21xlog221）/20=4.6次并不正n2確！）。因?yàn)檫@是在假設(shè)n=2m-1的情況下推導(dǎo)出來的公式。應(yīng)當(dāng)用窮舉法羅列：全部元素的查找次數(shù)為=（1+2x2+4x3+8x4+5x5）=74;ASL=74/20=3.7!!!4．折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20,它將依次與表中元素 28,6,1220比較大小。在各種查找方法中，平均查找長度與結(jié)點(diǎn)個(gè)數(shù)n無關(guān)的查找方法是散列查找散列法存儲(chǔ)的基本思想是由關(guān)鍵字的值_決定數(shù)據(jù)的存儲(chǔ)地址。有一個(gè)表長為m的散列表，初始狀態(tài)為空，現(xiàn)將n(nvm)個(gè)不同的關(guān)鍵碼插入到散列表中，解決沖突的方法是用線性探測法。如果這n個(gè)關(guān)鍵碼的散列地址都相同，則探測的總次數(shù)是n(n-1)/2=(1+2+???+n-1)。(而任一元素查找次數(shù)Vn-1)二、單項(xiàng)選擇題(每小題1分，共27分)(B)1?在表長為n的鏈表中進(jìn)行線性查找，它的平均查找長度為A?ASL=n;B?ASL=(n+l)/2;C?ASL=\訂+1; D?ASL俎log?(n+1)-1(A)2．折半查找有序表(4，6，10，12，20，30，50，70，88，100)。若查找表中元素58，則它將依次與表中比較大小，查找結(jié)果是失敗。A．20， 70， 30， 50 B．30， 88， 70， 50 C．20， 50D．30，88，50(C)3．對(duì)22個(gè)記錄的有序表作折半查找，當(dāng)查找失敗時(shí)，至少需要比較_次關(guān)鍵字。A．3 B．4 C．5 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)的值的上升順序排列?，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ù)元素已按值遞增或遞減的次序排好必須以鏈表方式存儲(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)系。鏈表是一種A,它對(duì)于數(shù)據(jù)元素的插入和刪除丄。通常查找線性表數(shù)據(jù)元素的方法有C和D兩種方法，其中C是一種只適合于順序存儲(chǔ)結(jié)構(gòu)但的方法；而是一種對(duì)順序和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)均適用的方法。供選擇的答案：A：①順序存儲(chǔ)線性表②非順序存儲(chǔ)非線性表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é)③只需移動(dòng)結(jié)點(diǎn)，不需改變結(jié)點(diǎn)指針④既需移動(dòng)結(jié)點(diǎn)，又需改變結(jié)點(diǎn)指針C:點(diǎn)，又需改變結(jié)點(diǎn)指針C:①順序查找②循環(huán)查找查找D:①順序查找②隨機(jī)查找E:①效率較低的線性查找③條件查找 ④二分法③二分法查找④分塊查找②效率較低的非線性查找效率較高的非線性查找效率較高的線性查找效率較高的非線性查找效率較高的線性查找答案：A答案：A=④④D=Q_E=③從供選擇的答案中，選出應(yīng)填入下面敘述內(nèi)的最確切的解答，把相應(yīng)編號(hào)寫在答卷的對(duì)應(yīng)欄內(nèi)。在二叉排序樹中，每個(gè)結(jié)點(diǎn)的關(guān)鍵碼值A(chǔ),B—棵二叉排序，即可得到排序序列。同一個(gè)結(jié)點(diǎn)集合，可用不同的二叉排序樹表示，人們把平均檢索長度最短的二叉排序樹稱作最佳二叉排序，最佳二叉排序樹在結(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:①前序遍歷②中序（對(duì)稱）遍歷③后序遍歷 ④層次遍歷C:①除最下二層可以不滿外，其余都是充滿的 ②除最下一層可以不滿外，其余都是充滿的③每個(gè)結(jié)點(diǎn)的左右子樹的高度之差的絕對(duì)值不大于1④最下層的葉子必須在最左邊答案：A=dB=②C=②從供選擇的答案中，選出應(yīng)填入下面敘述內(nèi)的最確切的解答，把相應(yīng)編號(hào)寫在答卷的對(duì)應(yīng)欄內(nèi)。散列法存儲(chǔ)的基本思想是根據(jù)A來決定B，碰撞（沖突）

指的是￡，處理碰撞的兩類主要方法是旦。供選擇的答案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ū)法③除余法和折疊法法③除余法和折疊法④拉鏈法和開地址法答案：A=④__B= ①C=聖考慮具有如下性質(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的值是旦，n9的值是丄?，F(xiàn)欲把、10放入此樹并使該樹保持前述性質(zhì)，增加的一個(gè)結(jié)點(diǎn)可以放在丄或旦。供選擇的答案

A—C:①1 ②2 ③3⑨9D—E:①n7下面 ②n8下面③n9下面④n6下面n1與n2之間⑥n2與n4之間⑦n6與n9之間⑧n3與n6之間答案：A答案：A=⑦_(dá)B=④C=⑥D(zhuǎn)=②三、簡答題（每小題4分，共16分）1?對(duì)分（折半）查找適不適合鏈表結(jié)構(gòu)的序列，為什么？用二分查找的查找速度必然比線性查找的速度快，這種說法對(duì)嗎？答：不適合！雖然有序的單鏈表的結(jié)點(diǎn)是按從小到大（或從大到小）順序排列，但因其存儲(chǔ)結(jié)構(gòu)為單鏈表，查找結(jié)點(diǎn)肘只能從頭指針開始逐步捜索，故不能進(jìn)行折半查找。二分查找的速度在一般情況下是快些，但在特殊情況下未必快。例如所查數(shù)據(jù)位于首位時(shí)，則線性查找快；而二分查找則慢得多。2假定對(duì)有序表：（3,4,5,7,24,30，42,54,63,72,87,95）進(jìn)行折半查找，試回答下列問題：（1） 畫出描述折半查找過程的判定樹；（2） 若查找元素54,需依次與哪些元素比較？（3） 若查找元素90,需依次與哪些元素比較？（4） 假定每個(gè)元素的查找概率相等，求查找成功時(shí)的平均查找長度。解：/UT?先畫出判定樹如下（注：mid=（1+12）/2=6）：

424547295查找元素54，需依次與30,63,42,54等元素比較；查找元素90，需依次與30,63,87,95,72等元素比較；求ASL之前，需要統(tǒng)計(jì)每個(gè)元素的查找次數(shù)。判定樹的前3層共查找1+2x2+4x3=17次；但最后一層未滿，不能用8x4,只能用5x4=20次，所以ASL=1/12(17+20)=37/12^3.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ù)都是O(1)。4?設(shè)哈希(Hash)表的地址范圍為0一17，哈希函數(shù)為：H(K)=KMOD16。K為關(guān)鍵字，用線性探測法再散列法處理沖突，輸入關(guān)鍵字序列：(10，24，32，17，31，30，46，47，40，63，49)1)造出Hash表，試回答下列問題：畫出哈希表的示意圖；1)若查找關(guān)鍵字63，需要依次與哪些關(guān)鍵字進(jìn)行比較？若查找關(guān)鍵字60，需要依次與哪些關(guān)鍵字比較？假定每個(gè)關(guān)鍵字的查找概率相等，求查找成功時(shí)的平均查找長度。解：(1)畫表如下012345678910111213141516173217634924401030314647(2)查找63,首先要與H(63)=63%16=15號(hào)單元內(nèi)容比較，即63vs31,no;然后順移，與46,47,32,17,63相比，一共比較了6次！查找60,首先要與H(60)=60%16=12號(hào)單元內(nèi)容比較，但因?yàn)?2號(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分)【嚴(yán)題集9?3②】畫出對(duì)長度為10的有序表進(jìn)行折半查找的判定解：判定樹應(yīng)當(dāng)描述每次查找的位樹，并求其等概率時(shí)查找成功的平均查找長度。解：判定樹應(yīng)當(dāng)描述每次查找的位置：L=1/10(1+2X2+3X4+4X3)=1/10(1+4+12+12)=29/10=2.9

4710在一棵空的二叉查找樹中依次插入關(guān)鍵字序列為12，7，17，11，16，2，13，9，21，4，請(qǐng)畫出所得到的二叉查找樹。答：1271771721116214913驗(yàn)算方法：用中序遍歷應(yīng)得到排序結(jié)果：2,4,7,9,11,12,13,16,17，21【嚴(yán)題集9?9③】已知如下所示長度為12的表：(Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,De)c試按表中元素的順序依次插入一棵初始為空的二叉排序樹，畫出插入完成之后的二叉排序樹，并求其在等概率的情況下查找成功的平均查找長度。若對(duì)表中元素先進(jìn)行排序構(gòu)成有序表，求在等概率的情況下對(duì)此有序表進(jìn)行折半查找時(shí)查找成功的平均查找長度。按表中元素順序構(gòu)造一棵平衡二叉排序樹，并求其在等概率的JanJuly*2'1.037*歐陽光明<1JanJuly*2'1.037*歐陽光明<1)求得的二叉排序樹如下圖所示*在等概率情配下查找成功的平均查找隹度為X1-^2X2+3X3+4X3-FSX2+6X1)-^*歐陽光明*創(chuàng)編情況下查找成功的平均查找長度解：HTT?4.選取散列函數(shù)H(key)=(3*key)%11,用線性探測法處理沖突，對(duì)下列關(guān)鍵碼序列構(gòu)造一個(gè)散列地址空間為0—10,表長為11的散列表，{22，41，53，08，46，30，01，31，66}。解：由題意知，m=11(剛好為素?cái)?shù))地址值地址值鏈接指針022116624133084,7430553646701831910則(22*3)%11=6 0(41*3)%11=11???…2(53*3)%11=14 5(08*3)%11=2??2(46*3)%11=12??6(30*3)%11=8??2(01*3)%11=0 3(31*3)%11=8 5(66*3)%11=9??02266418305346131012345678910134,7五、算法設(shè)計(jì)題(4中選3，第1題7分必選，其余每題8分，共23分)已知11個(gè)元素的有序表為(0513192137566475808892),請(qǐng)寫出折半查找的算法程序，查找關(guān)鍵字為key的數(shù)據(jù)元素(建議上機(jī)調(diào)試)。解：折半查找的C程序有很多參考資料，注意此題要求是整型量。折半查找的一個(gè)遞歸算法如下，形式非常簡潔！intSearch_Bin_Recursive(SSTableST,intkey,intlow,inthigh)//折半查找的遞歸算法{if(low>high)return0;//查找不到時(shí)返回0mid=(low+high)/2;if(ST.elem[mid].key==key)returnmid;elseif(ST.elem[mid].key>key)returnSearch_Bin_Recursive(ST,key,low,mid-1);elsereturnSearch_Bin_Recursive(ST,key,mid+1,high);}}//Search_Bin_Recursive【嚴(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)的比值也要遵循(左小右大)原則)。若要采用遞歸算法，建議您采用如下的函數(shù)首部：boolBisortTree(BiTreeT,BiTree&PRE)其中PRE為指向當(dāng)前訪問結(jié)點(diǎn)的前驅(qū)的指針。(或者直接存儲(chǔ)前驅(qū)的數(shù)值，隨時(shí)與當(dāng)前根結(jié)點(diǎn)比較)一個(gè)漂亮的算法設(shè)計(jì)如下：intlast=0,flag=1;//last是全局變量，用來記錄前驅(qū)結(jié)點(diǎn)值，只要每個(gè)結(jié)點(diǎn)都比前驅(qū)大就行。intIs_BSTree(BitreeT)//判斷二叉樹T是否二叉排序樹，是則返回1，否則返回0{if(T->lchild&&flag)Is_BSTree(T-