【正文】 元素，已按關(guān)鍵項(xiàng)的值的上升順序排列?，F(xiàn)假定對各個(gè)元素進(jìn)行查找的概率是相同的，并且各個(gè)元素的關(guān)鍵項(xiàng)的值皆不相同。當(dāng)用順序查找法查找時(shí)，平均比較次數(shù)約為 D ，最大比較次數(shù)為 E 。供選擇的答案：A~C：① 必須以順序方式存儲 ② 必須以鏈表方式存儲 ③ 必須以散列方式存儲 ④ 既可以以順序方式，也可以以鏈表方式存儲⑤ 必須以順序方式存儲且數(shù)據(jù)元素已按值遞增或遞減的次序排好⑥ 必須以鏈表方式存儲且數(shù)據(jù)元素已按值遞增或遞減的次序排好D，E： ① 25000 ② 30000 ③ 45000 ④ 90000答案： A= ④ B= ⑤ C= ③ D ＝ ③ E ＝ ④ 7. 數(shù)據(jù)結(jié)構(gòu)反映了數(shù)據(jù)元素之間的結(jié)構(gòu)關(guān)系。鏈表是一種 A ，它對于數(shù)據(jù)元素的插入和刪除 B 。通常查找線性表數(shù)據(jù)元素的方法有 C 和 D 兩種方法，其中 C 是一種只適合于順序存儲結(jié)構(gòu)但 E 的方法；而 D 是一種對順序和鏈?zhǔn)酱鎯Y(jié)構(gòu)均適用的方法。 供選擇的答案：A：①順序存儲線性表 ②非順序存儲非線性表 ③順序存儲非線性表 ④非順序存儲線性表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：① 效率較低的線性查找 ②效率較低的非線性查找 ③效率較高的非線性查找 ④效率較高的線性查找答案： A ＝ ④ B ＝ ② C ＝ ④ D ＝ ① E ＝ ③8. 在二叉排序樹中，每個(gè)結(jié)點(diǎn)的關(guān)鍵碼值 A ， 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: ①前序遍歷 ② 中序（對稱）遍歷 ③ 后序遍歷 ④ 層次遍歷C： ① 除最下二層可以不滿外，其余都是充滿的 ②除最下一層可以不滿外，其余都是充滿的 ③ 每個(gè)結(jié)點(diǎn)的左右子樹的高度之差的絕對值不大于1 ④ 最下層的葉子必須在最左邊答案： A ＝ ① B ＝ ② C ＝ ②9. 散列法存儲的基本思想是根據(jù) A 來決定 B ，碰撞（沖突）指的是 C ，處理碰撞的兩類主要方法是 D 供選擇的答案A，B： ①存儲地址 ② 元素的符號 ③ 元素個(gè)數(shù) ④ 關(guān)鍵碼值 ⑤ 非碼屬性 ⑥ 平均檢索長度 ⑦ 負(fù)載因子 ⑧ 散列表空間 C: ①兩個(gè)元素具有相同序號 ② 兩個(gè)元素的關(guān)鍵碼值不同，而非碼屬性相同③ 不同關(guān)鍵碼值對應(yīng)到相同的存儲地址 ④ 負(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 。供選擇的答案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 ＝ ⑥ 三、簡答題（每小題4分，共16分）1. 對分（折半）查找適不適合鏈表結(jié)構(gòu)的序列，為什么？用二分查找的查找速度必然比線性查找的速度快，這種說法對嗎？答： 不適合！雖然有序的單鏈表的結(jié)點(diǎn)是按從小到大（或從大到?。╉樞蚺帕校蚱浯鎯Y(jié)構(gòu)為單鏈表，查找結(jié)點(diǎn)時(shí)只能從頭指針開始逐步搜索，故不能進(jìn)行折半查 找。二分查找的速度在一般情況下是快些，但在特殊情況下未必快。例如所查數(shù)據(jù)位于首位時(shí)，則線性查找快；而二分查找則慢得多。 2. 假定對有序表：（3，4，5，7，24，30，42，54，63，72，87，95）進(jìn)行折半查找，試回答下列問題：（1） 畫出描述折半查找過程的判定樹；（2） 若查找元素54，需依次與哪些元素比較？（3） 若查找元素90，需依次與哪些元素比較？（4） 假定每個(gè)元素的查找概率相等，求查找成功時(shí)的平均查找長度。? 先畫出判定樹如下（注： mid= ? (1+12)/2 ? =6）： 30 5 63 3 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 層共查找 1 ＋ 2 2 ＋ 4 3=17 次； 但最后一層未滿，不能用 8 4 ，只能用 5 4=20 次， 所以 ASL ＝ 1/12 （ 17 ＋ 20 ）＝ 37/12 ≈ 3. 用比較兩個(gè)元素大小的方法在一個(gè)給定的序列中查找某個(gè)元素的時(shí)間復(fù)雜度下限是什么? 如果要求時(shí)間復(fù)雜度更小,你采用什么方法？此方法的時(shí)間復(fù)雜度是多少? 答： 查找某個(gè)元素的時(shí)間復(fù)雜度下限，如果理解為最短查找時(shí)間，則當(dāng)關(guān)鍵字值與表頭元素相同時(shí)，比較 1次即可。要想降低時(shí)間復(fù)雜度，可以改用Hash查找法。此方法對表內(nèi)每個(gè)元素的比較次數(shù)都是O（1）。4. 設(shè)哈希（Hash）表的地址范圍為0～17，哈希函數(shù)為：H（K）＝K MOD 16。K為關(guān)鍵字，用線性探測法再散列法處理沖突，輸入關(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 ）畫表如下： 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 32 17 63 49 24 40 10 30 31 46 47 （ 2） 查找63,首先要與H(63)=63%16=15號單元內(nèi)容比較，即63 vs 31 ,no。 然后順移，與 46,47,32,17,63相比，一共比較了6次！ （ 3 ）查找 60, 首先要與 H(60)=60%16=12 號單元內(nèi)容比較，但因?yàn)?12 號單元為空（應(yīng)當(dāng)有空標(biāo)記），所以 應(yīng)當(dāng)只比較這一次即可。 （ 4 ） 對于黑色數(shù)據(jù)元素，各比較 1 次；共 6 次； 對紅色元素則各不相同，要統(tǒng)計(jì)移位的位數(shù)。 “ 63 ” 需要 6 次，“ 49 ”需要 3 次，“ 40 ”需要 2 次，“ 46 ”需要 3 次，“ 47 ”需要 3 次， 所以 ASL=1/11 （ 6 ＋ 2 ＋ 3 3 ）＝ 17/11= ≈ 四、分析題（每小題6分，共24分）1. 【②】畫出對長度為10的有序表進(jìn)行折半查找的判定樹，并求其等概率時(shí)查找成功的平均查找長度。解：判定樹應(yīng)當(dāng)描述每次查找的位置： 5 ? 8 1 3 6 9 4 7 102. 在一棵空的二叉查找樹中依次插入關(guān)鍵字序列為12，7，17，11，16，2，13，9，21，4，請畫出所得到的二叉查找樹。答： 12 ? 17 2 11 16 21 4 9 13 驗(yàn)算方法： 用中序遍歷應(yīng)得到排序結(jié)果： 2,4,7,9,11,12,13,16,17 ， 21 【③】已知如下所示長度為12的表：（Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec）(1) 試按表中元素的順序依次插入一棵初始為空的二叉排序樹，畫出插入完成之后的二叉排序樹，并求其在等概率的情況下查找成功的平均查找長度。(2) 若對表中元素先進(jìn)行排序構(gòu)成有序表，求在等概率的情況下對此有序表進(jìn)行折半查找時(shí)查找成功的平均查找長度。(3) 按表中元素順序構(gòu)造一棵平衡二叉排序樹，并求其在等概率的情況下查找成功的平均查找長度。4. 選取散列函數(shù)H（key）=（3*key）%11，用線性探測法處理沖突，對下列關(guān)鍵碼序列構(gòu)造一個(gè)散列地址空間為0～10，表長為11的散列表，{22，41，53，08，46，30，01，31，66}。解：由題意知， m=11( 剛好為素?cái)?shù) ) 則 (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 …… 0 22 66 41 8 30 53 46 1 31 0 1 2 3 4 5 6 7 8 9 10 1 3 4 ， 7 第9章 排序 自測卷 答案 姓名 班級 一、填空題（每空1分，共24分）1. 大多數(shù)排序算法都有兩個(gè)基本的操作： 比較（兩個(gè)關(guān)鍵字的大小） 和 移動(dòng)（記錄或改變指向記錄的指針） 2. 在對一組記錄（54，38，96，23，15，72，60，45，83）進(jìn)行直接插入排序時(shí)，當(dāng)把第7個(gè)記錄60插入到有序表時(shí)，為尋找插入位置至少需比較 3 次。(可約定為，從后向前比較)3. 在插入和選擇排序中，若初始數(shù)據(jù)基本正序，則選用 插入排序（到尾部） ；若初始數(shù)據(jù)基本反序，則選用 選擇排序 。4. 在堆排序和快速排序中，若初始記錄接近正序或反序，則選用 堆排序 ；若初始記錄基本無序，則最好選用 快速排序 。5. 對于n個(gè)記錄的集合進(jìn)行冒泡排序，在最壞的情況下所需要的時(shí)間是 O(n2) 若對其進(jìn)行快速排序，在最壞的情況下所需要的時(shí)間是 O(n2) 6. 對于n個(gè)記錄的集合進(jìn)行歸并排序，所需要的平均時(shí)間是 O(nlog2n) ，所需要的附加空間是 O(n) 7．【計(jì)研題2000】對于n個(gè)記錄的表進(jìn)行2路歸并排序，整個(gè)歸并排序需進(jìn)行 log2n 趟（遍），共計(jì)移動(dòng) n log2n 次記錄。(即移動(dòng)到新表中的總次數(shù)！共log2n趟，每趟都要移動(dòng)n個(gè)元素)（Q, H, C, Y, P, A, M, S, R, D, F, X）中的關(guān)鍵碼按字母序的升序重新排列，則：冒泡排序一趟掃描的結(jié)果是 H, C, Q, P, A, M, S, R, D, F, X ,Y ；初始步長為4的希爾（shell）排序一趟的結(jié)果是 P, A, C, S, Q, D, F, X , R, H,M, Y ；二路歸并排序一趟掃描的結(jié)果是 H, Q, C, Y，A, P, M, S, D, R, F, X ；快速排序一趟掃描的結(jié)果是 F, H, C, D, P, A, M, Q, R, S, Y，X