【正文】 ②比左子樹(shù)所有結(jié)點(diǎn)的關(guān)鍵碼值小，比右子樹(shù)所有結(jié)點(diǎn)的關(guān)鍵碼值大 ③比左右子樹(shù)的所有結(jié)點(diǎn)的關(guān)鍵碼值都大 ④與左子樹(shù)所有結(jié)點(diǎn)的關(guān)鍵碼值和右子樹(shù)所有結(jié)點(diǎn)的關(guān)鍵碼值無(wú)必然的大小關(guān)系B: ①前序遍歷 ② 中序（對(duì)稱）遍歷 ③ 后序遍歷 ④ 層次遍歷C：① 除最下二層可以不滿外，其余都是充滿的 ②除最下一層可以不滿外，其余都是充滿的 ③ 每個(gè)結(jié)點(diǎn)的左右子樹(shù)的高度之差的絕對(duì)值不大于1 ④ 最下層的葉子必須在最左邊答案：A＝ ① B＝ ② C＝ ② 9. 從供選擇的答案中，選出應(yīng)填入下面敘述 ？ 內(nèi)的最確切的解答，把相應(yīng)編號(hào)寫(xiě)在答卷的對(duì)應(yīng)欄內(nèi)。散列法存儲(chǔ)的基本思想是根據(jù) A 來(lái)決定 B ，碰撞（沖突）指的是 C ，處理碰撞的兩類(lèi)主要方法是 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)到相同的存儲(chǔ)地址 ④ 負(fù)載因子過(guò)大 ⑤ 數(shù)據(jù)元素過(guò)多D： ① 線性探查法和雙散列函數(shù)法 ② 建溢出區(qū)法和不建溢出區(qū)法 ③ 除余法和折疊法 ④ 拉鏈法和開(kāi)地址法答案：A＝ ④ B＝ ① C＝ ③ D＝ ④ ：除葉子結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)的值都大于其左子樹(shù)上的一切結(jié)點(diǎn)的值。并小于等于其右子樹(shù)上的一切結(jié)點(diǎn)的值。現(xiàn)把9個(gè)數(shù)1，2，3，…，8，9填入右圖所示的二叉樹(shù)的9個(gè)結(jié)點(diǎn)中，并使之具有上述性質(zhì)。此時(shí)，n1的值是 A ，n2的值是 B ，n9的值是 C ?，F(xiàn)欲把放入此樹(shù)并使該樹(shù)保持前述性質(zhì)，增加的一個(gè)結(jié)點(diǎn)可以放在 D 或 E 。供選擇的答案A～C： ①1 ② 2 ③ 3 ④ 4 ⑤ 5 ⑥ 6 ⑦ 7 ⑧ 8 ⑨ 9D～E： ① n7下面 ② n8下面 ③ n9下面 ④ n6下面 ⑤ n1與n2之間 ⑥ n2與n4之間 ⑦ n6與n9之間 ⑧ n3與n6之間 答案：A＝ ⑦ B＝ ④ C＝ ⑥ D＝ ② E＝ ⑥ 三、簡(jiǎn)答題（每小題4分，共16分）（折半）查找適不適合鏈表結(jié)構(gòu)的序列，為什么？用二分查找的查找速度必然比線性查找的速度快，這種說(shuō)法對(duì)嗎？答：不適合！雖然有序的單鏈表的結(jié)點(diǎn)是按從小到大（或從大到?。╉樞蚺帕?，但因其存儲(chǔ)結(jié)構(gòu)為單鏈表，查找結(jié)點(diǎn)時(shí)只能從頭指針開(kāi)始逐步搜索，故不能進(jìn)行折半查找。二分查找的速度在一般情況下是快些，但在特殊情況下未必快。例如所查數(shù)據(jù)位于首位時(shí)，則線性查找快；而二分查找則慢得多。：（3，4，5，7，24，30，42，54，63，72，87，95）進(jìn)行折半查找，試回答下列問(wèn)題：（1） 畫(huà)出描述折半查找過(guò)程的判定樹(shù)；（2） 若查找元素54，需依次與哪些元素比較？（3） 若查找元素90，需依次與哪些元素比較？（4） 假定每個(gè)元素的查找概率相等，求查找成功時(shí)的平均查找長(zhǎng)度。解：（1） 先畫(huà)出判定樹(shù)如下（注：mid=235。(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ù)。判定樹(shù)的前3層共查找1＋22＋43=17次；但最后一層未滿，不能用84，只能用54=20次，所以ASL＝1/12（17＋20）＝37/12≈? 如果要求時(shí)間復(fù)雜度更小,你采用什么方法？此方法的時(shí)間復(fù)雜度是多少? 答：查找某個(gè)元素的時(shí)間復(fù)雜度下限，如果理解為最短查找時(shí)間，則當(dāng)關(guān)鍵字值與表頭元素相同時(shí)，比較1次即可。要想降低時(shí)間復(fù)雜度，可以改用Hash查找法。此方法對(duì)表內(nèi)每個(gè)元素的比較次數(shù)都是O（1）。（Hash）表的地址范圍為0～17，哈希函數(shù)為：H（K）＝K MOD 16。K為關(guān)鍵字，用線性探測(cè)法再散列法處理沖突，輸入關(guān)鍵字序列： （10，24，32，17，31，30，46，47，40，63，49）造出Hash表，試回答下列問(wèn)題：（1） 畫(huà)出哈希表的示意圖；（2） 若查找關(guān)鍵字63，需要依次與哪些關(guān)鍵字進(jìn)行比較？（3） 若查找關(guān)鍵字60，需要依次與哪些關(guān)鍵字比較？（4） 假定每個(gè)關(guān)鍵字的查找概率相等，求查找成功時(shí)的平均查找長(zhǎng)度。解： （1）畫(huà)表如下：012345678910111213141516173217634924401030314647（2） 查找63,首先要與H(63)=63%16=15號(hào)單元內(nèi)容比較，即63 vs 31 ,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)只比較這一次即可。（4） 對(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＋33）＝17/11=≈四、分析題（每小題6分，共24分）1. 畫(huà)出對(duì)長(zhǎng)度為10的有序表進(jìn)行折半查找的判定樹(shù)，并求其等概率時(shí)查找成功的平均查找長(zhǎng)度。解：判定樹(shù)應(yīng)當(dāng)描述每次查找的位置：52 81 3 6 9 4 7 10，7，17，11，16，2，13，9，21，4，請(qǐng)畫(huà)出所得到的二叉查找樹(shù)。答： 127 17 2 11 16 21 4 9 13驗(yàn)算方法： 用中序遍歷應(yīng)得到排序結(jié)果： 2,4,7,9,11,12,13,16,17，21：（Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec）(1) 試按表中元素的順序依次插入一棵初始為空的二叉排序樹(shù)，畫(huà)出插入完成之后的二叉排序樹(shù)，并求其在等概率的情況下查找成功的平均查找長(zhǎng)度。(2) 若對(duì)表中元素先進(jìn)行排序構(gòu)成有序表，求在等概率的情況下對(duì)此有序表進(jìn)行折半查找時(shí)查找成功的平均查找長(zhǎng)度。(3) 按表中元素順序構(gòu)造一棵平衡二叉排序樹(shù)，并求其在等概率的情況下查找成功的平均查找長(zhǎng)度。解：4. 選取散列函數(shù)H（key）=（3*key）%11，用線性探測(cè)法處理沖突，對(duì)下列關(guān)鍵碼序列構(gòu)造一個(gè)散列地址空間為0～10，表長(zhǎng)為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分）1. 已知11個(gè)元素的有序表為（05 13 19 21 37 56 64 75 80 88 92）, 請(qǐng)寫(xiě)出折半查找的算法程序，查找關(guān)鍵字為key的數(shù)據(jù)元素 (建議上機(jī)調(diào)試)。解：折半查找的C程序有很多參考資料，注意此題要求是整型量。折半查找的一個(gè)遞歸算法如下，形式非常簡(jiǎn)潔！int Search_Bin_Recursive(SSTable ST, int key, int low, int high) //折半查找的遞歸算法 { if(lowhigh) return 0。 //查找不到時(shí)返回0 mid=(low+high)/2。 if([mid].key= =key) return mid。 else if([mid].keykey) return Search_Bin_Recursive(ST, key, low, mid1)。 else return Search_Bin_Recursive(ST, key, mid+1, high)。 } }//Search_Bin_Recursive ，設(shè)此二叉樹(shù)以二叉鏈表作存儲(chǔ)結(jié)構(gòu)。且樹(shù)中結(jié)點(diǎn)的關(guān)鍵字均不同。解：注意仔細(xì)研究二叉排序樹(shù)的定義。易犯的典型錯(cuò)誤是按下述思路進(jìn)行判別：“若一棵非空的二叉樹(shù)其左、右子樹(shù)均為二叉排序樹(shù)，且左子樹(shù)的根的值小于根結(jié)點(diǎn)的值，又根結(jié)點(diǎn)的值不大于右子樹(shù)的根的值，則是二叉排序樹(shù)”（劉注：即不能只判斷左右孩子的情況，還要判斷左右孩子與雙親甚至根結(jié)點(diǎn)的比值也要遵循（左小右大）原則）。若要采用遞歸算法，建議您采用如下的函數(shù)首部：bool BisortTree(BiTree T, BiTreeamp。PRE)，其中PRE為指向當(dāng)前訪問(wèn)結(jié)點(diǎn)的前驅(qū)的指針。（或者直接存儲(chǔ)前驅(qū)的數(shù)值，隨時(shí)與當(dāng)前根結(jié)點(diǎn)比較）一個(gè)漂亮的算法設(shè)計(jì)如下：int last=0, flag=1。 // last是全局變量，用來(lái)記錄前驅(qū)結(jié)點(diǎn)值，只要每個(gè)結(jié)點(diǎn)都比前驅(qū)大就行。int Is_BSTree(Bitree T) //判斷二叉樹(shù)T是否二叉排序樹(shù)，是則返回1，否則返回0 { if(Tlchildamp。amp。flag) Is_BSTree(Tlchild)。 if(Tdatalast) flag=0。 //與其中序前驅(qū)相比較, flag=0表示當(dāng)前結(jié)點(diǎn)比直接前驅(qū)小，則立即返回 last=Tdata。 if(Trchildamp。amp。flag) Is_BSTree(Trchild)。 return flag。 }//Is_BSTree 3. 已知一個(gè)含有1000個(gè)記錄的表，關(guān)鍵字為中國(guó)人姓氏的拼音，請(qǐng)給出此表的一個(gè)哈希表設(shè)計(jì)方案，要求它在等概率情況下查找成功的平均查找長(zhǎng)度不超過(guò)3。解：設(shè)計(jì)哈希表的步驟為：a) 根據(jù)所選擇的處理沖突的方法求出裝載因子a的上界；b) 由a值設(shè)計(jì)哈希表的長(zhǎng)度m；c) 根據(jù)關(guān)鍵字的特性和表長(zhǎng)m選定合適的哈希函數(shù)。劉注：要求ASL≤3，則m必然要盡量長(zhǎng)，以減少?zèng)_突；4. 已知某哈希表的裝載因子小于1，哈希函數(shù)H(key)為關(guān)鍵字（標(biāo)識(shí)符）的第一個(gè)字母在字母表中的序號(hào)，處理沖突的方法為線性探測(cè)開(kāi)放定址法。試編寫(xiě)一個(gè)按第一個(gè)字母的順序輸出哈希表中所有關(guān)鍵字的算法。解：注意此題給出的條件：裝載因子a〈1, 則哈希表未填滿。由此可寫(xiě)出下列形式簡(jiǎn)明的算法：void PrintWord(Hash Table ht){//按第一個(gè)字母的順序輸出哈希表ht中的標(biāo)識(shí)符。哈希函數(shù)為表示符的第一個(gè)字母在字母表中的序號(hào)，處理沖突的方法是線性探測(cè)開(kāi)放定址法。for(i=1。 i=26。 i++){j=i。While([j].key){if(Hash([j].key==i)printf([j].key)。j=(j+1)%m。}}}//PrintWord29 / 29