數(shù)據(jù)結(jié)構(gòu)第九、十章作業(yè)答案

1、1 第九章查找 一、填空題 1. 在數(shù)據(jù)的存放無規(guī)律而言的線性表中進行檢索的最佳方法是 順序查找（線性查找） 。 2. 線性有序表（ai，a2，a3，,， a256）是從小到大排列的，對一個給定的值 k，用二分法檢索 表中與 k 相等的元素，在查找不成功的情況下，最多需要檢索 _8 次。設(shè)有 100 個結(jié)點， 用二分法查找時，最大比較次數(shù)是_7_ _ 。 3假設(shè)在有序線性表 a1.2O上進行折半查找，則比較一次查找成功的結(jié)點數(shù)為 1；比較兩 次查找成功的結(jié)點數(shù)為_2 _ ;比較四次查找成功的結(jié)點數(shù)為 8 ,其下標(biāo)從小到大依次 是 1,3,6,8,11,13,16,19 _ ，平均查找長度為 3

2、.7 。 解：顯然，平均查找長度二 0（ log 2n） 5 次（25）。但具體是多少次，則不應(yīng)當(dāng)按照公式 ASL =n 1 log2（n 1）來計算（即（21 X log 221） /20 = 4.6 次并不正確！）。因為這是在假設(shè) n = 21 n 的情況下推導(dǎo)出來的公式。應(yīng)當(dāng)用窮舉法羅列： 全部元素的查找次數(shù)為=（1 + 2X 2+ 4X 3+ 8X 4+ 5X 5）= 74; ASL= 74/20=3.7 ! 4折半查找有序表（4, 6，12，20, 28, 38，50，70, 88，100），若查找表中元素 20，它 將依次與表中元素 28 ，6，12, 20 比較大小。 5. 在各

3、種查找方法中，平均查找長度與結(jié)點個數(shù) n 無關(guān)的查找方法是散列查找 。 6. 散列法存儲的基本思想是由 關(guān)鍵字的值 決定數(shù)據(jù)的存儲地址。 7. 有一個表長為 m 的散列表，初始狀態(tài)為空，現(xiàn)將 n （nm 個不同的關(guān)鍵碼插入到散列表 中，解決沖突的方法是用線性探測法。如果這 n 個關(guān)鍵碼的散列地址都相同，貝U探測的總 次數(shù)是 n（n-1）/2= （ 1 土 2+ , 土 n-1 ）。（而任一元素查找次數(shù) n-1） &設(shè)一哈希表表長 M 為 100，用除留余數(shù)法構(gòu)造哈希函數(shù)，即 H（ K） =K MOIP （ P=M ,為 使函數(shù)具有較好性能，P 應(yīng)選（97 ） 9、 在各種查找方法中，平

4、均查找長度與結(jié)點個數(shù)無關(guān)的是哈 _ 10、 對線性表進行二分查找時，要求線性表必須以 順序 方式存儲，且結(jié)點按關(guān)鍵字 有序排列。 11 在分塊查找方法中，首先查找索引，然后再查找相應(yīng)的 _。 12. 順序查找 n 個元素的順序表，若查找成功，則比較關(guān)鍵字的次數(shù)最多為 _n_次；當(dāng)使 用監(jiān)視哨時，若查找失敗，則比較關(guān)鍵字的次數(shù)為 n+1 。 13. 在有序表 A1.12中，采用二分查找算法查等于 A12的元素，所比較的元素下標(biāo)依次 為 6,9,11,12 . 。 14. 在有序表 A1.20中，按二分查找方法進行查找，查找長度為 5 的元素個數(shù)是 5 . 15. 已知二叉排序樹的左右子樹均不為空

5、， 則 左子樹 _ 上所有結(jié)點的值均小于它的 根結(jié)點值， 右子樹 _ 所有結(jié)點的值均大于它的根結(jié)點的值。 2 16. 中序遍歷二叉排序樹得到的序列是 有序 序列（填有序或無序）。 17、從有序表(10, 16, 25, 40, 61, 28, 80, 93)中依次二分查找 40 和 61 元素時，其查找 長度分別為 1和 3 二、單項選擇題 (B )1 在表長為n的鏈表中進行順序查找，它的平均查找長度為 A. ASL=n ; B . ASL=(n+l)/2 ; C . ASL= n + 1 ; D . ASLlog 2 (n+l)l (A ) 2折半查找有序表(4, 6, 10, 12, 20

6、, 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. 對 22 個記錄的有序表作折半查找， 鍵字。 當(dāng)查找失敗時， 至少需要比較 次關(guān) A. 3 B . 4 C . 5 D .6 (A )4. 鏈表適用于 查找 A 順序 B .二分法 C .順序， 也能二分法 D .隨機 (C )5. 折半搜索與二叉搜索樹的時間性能 A. 相同 B. 完全不同 C. 有時不相同 D. 數(shù)量級都是 0 (lo

7、g 2n) 6. 散列表的地址區(qū)間為 0-17,散列函數(shù)為 H(K)=K mod 17。采用線性探測法處理沖突，并將 關(guān)鍵字序列 26, 25, 72, 38, 8, 18, 59 依次存儲到散列表中。元素 59 存放在散列表中的地 址是(D ) o A. 8 B. 9 C. 10 D. 11 7. 當(dāng)采用分快查找時，數(shù)據(jù)的組織方式為 (B ) A. 數(shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)有序 B. 數(shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)不必有序，但塊間必須有序，每塊內(nèi)最大(或最小)的數(shù)據(jù) 組成索引塊 C. 數(shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)有序，每塊內(nèi)最大(或最小)的數(shù)據(jù)組成索引塊 D. 數(shù)據(jù)分成若干塊，每塊(除最后一塊外

8、)中數(shù)據(jù)個數(shù)需相同 8. 散列函數(shù)有一個共同的性質(zhì)，即函數(shù)值應(yīng)當(dāng)以 (D )取其值域的每個值。 A.最大概率 B. 最小概率 C. 平均概率 D. 同等概率 9. 假定有 k 個關(guān)鍵字互為同義詞，若用線性探測法把這 k 個關(guān)鍵字存入散列表中，至少要進 行多少次探測？(D ) A. k-1 次 B. k 次 C. k+1 次 D. k (k+1) /2 次 3 10. 哈希查找中 k 個關(guān)鍵字具有同一哈希值，若用線性探測法將這 k 個關(guān)鍵字對應(yīng)的記錄存 入哈希表中，至少要進行() 次探測?！疚靼搽娮涌萍即髮W(xué) 1998 一、8 (2 分)】 A k B. k+1 C. k(k+1)/2 D.1+k

9、(k+1)/2 11、 在平衡二叉樹中插入一個結(jié)點后造成了不平衡，設(shè)最低的不平衡結(jié)點為 A,并已知A的左 孩子的平衡因子為 0 右孩子的平衡因子為 1,則應(yīng)作( C ) 型調(diào)整以使其平衡。 A. LL B. LR C. RL D. RR 12、 二叉查找樹的查找效率與二叉樹的 ( C) 有關(guān), 在 (B )時其查找效率最低 (1) : A. 高度 B. 結(jié)點的多少 C. 樹型 D. 結(jié)點的位置 (2) : A. 結(jié)點太多 B. 完全二叉樹 C. 呈單枝樹 D. 結(jié)點太復(fù)雜。 13、 在順序表 ( 3, 6, 8, 10, 12, 15, 16, 18, 21, 25, 30 ) 中，用折半法查

10、找關(guān)鍵碼值 11，所需的關(guān)鍵碼比較次數(shù)為( C ) A) 2 B) 3 C) 4 D) 5 14、 對包含 n 個元素的哈希表進行查找，平均查找長度為( D) A) O(log 2n) B) O(n) C) O(nlog 2n) D) 不直接依賴于 n 15、 若查找每個記錄的概率均等，則在具有 n 個記錄的連續(xù)順序文件中采用順序查找法查找 一個記錄，其平均查找長度 ASL 為(C )。 A (n-1)/2 B. n/2 C. (n+1)/2 D. n 16、 下面關(guān)于二分查找的敘述正確的是 ( D ) A. 表必須有序，表可以順序方式存儲，也可以鏈表方式存儲 C. 表必須有序，而且只能從 小

11、到大排列 B. 表必須有序且表中數(shù)據(jù)必須是整型，實型或字符型 D. 表必須有序，且表只能以 順序方式存儲 17、 對線性表進行二分查找時，要求線性表必須( B ) A.以順序方式存儲 B.以順序方式存儲，且數(shù)據(jù)元素有序 C.以鏈接方式存儲 D.以鏈接方式存 儲, 且數(shù)據(jù)元素有序 18適用于折半查找的表的存儲方式及元素排列要求為 ( D ) A 鏈接方式存儲，元素?zé)o序 B 鏈接方式存儲，元素有序 C. 順序方式存儲，元素?zé)o序 D 順序方式存儲，元素有序 19. 用二分(對半)查找表的元素的速度比用順序法 ( D ) A 必然快 B. 必然慢 C. 相等 D. 不能確定 20當(dāng)在一個有序的順序存儲

12、表上查找一個數(shù)據(jù)時，即可用折半查找，也可用順序查找，但 前者比后者的查找速度 ( C ) A.必定快 B.不一定 C. 在大部分情況下要快 D. 取決于表遞增還是遞減 4 21. 具有 12 個關(guān)鍵字的有序表，折半查找的平均查找長度( A ) A. 3.1 B. 4 C. 2.5 D. 5 22. 折半查找的時間復(fù)雜性為( D )5 A. O (n2) B. O (n) C. O (nlogn ) D. O (logn ) 23. 設(shè)順序線性表的長度為 30,分成 5 塊，每塊 6 個元素，如果采用分塊查找，則其平均查找長度為(D )。 (A) 6 (B) 11 (C) 5 (D) 6.5 2

13、4. 二叉排序樹的查找效率與二叉樹的(C)有關(guān) A. 高度 B. 結(jié)點的多少 C. 樹型 D. 結(jié)點的位置 25. 在等概率情況下,一棵平衡樹的 ASL 為(B ) A. 0(1) B. 0( log2n ) C. O(log2 n)2) D.O( nl og2 n) 26. 分別以下列序列構(gòu)造二叉排序樹，與用其它三個序列所構(gòu)造的結(jié)果不同的是 (C ) A (100, 80, 90 , 60 , 120 , 110, 130) B (100, 120, 110, 130 ,80, 60 , 90 ) C (100, 60, 80 , 90 , 120 , 110, 130) D (100， 8

14、0, 60 , 90 , 120 , 130, 110) 27. 在平衡二叉樹中插入一個結(jié)點后造成了不平衡，設(shè)最低的不平衡結(jié)點為 孩子的平衡因子為 0 右孩子的平衡因子為 1,則應(yīng)作(C ) A. LL B. LR C. RL D. RR 28、 下列二叉排序樹中，滿足平衡二叉樹定義的是( 31. 下面關(guān)于 B 和 B+樹的敘述中，不正確的是(C ) A. B 樹和 B+樹都是平衡的多叉樹。 B. B 樹和 B+樹都可用于文件的索引結(jié)構(gòu) A,并已知 A 的左 型調(diào)整以使其平衡。 29. 下列關(guān)于 m 階 B-樹的說法錯誤的是(D A.根結(jié)點至多有 m 棵子樹 B .所有葉子都在同一層次上 C.

15、非葉結(jié)點至少有 m/2 (m 為偶數(shù))或 m/2+1 (m 為奇數(shù))棵子樹 的 30. 下面關(guān)于 m 階 B 樹說法正確的是(B ) 每個結(jié)點至少有兩棵非空子樹； 樹中每個結(jié)點至多有 所有葉子在同一層上； A. B. D.根結(jié)點中的數(shù)據(jù)是有序 m1 個關(guān)鍵字； 當(dāng)插入一個數(shù)據(jù)項引起 B 樹結(jié)點分裂后，樹長高一層。 C. D. A、 6 C. B 樹和 B+樹都能有效地支持順序檢索。 D. B 樹和 B+樹都能有效地支持隨機檢索 32、 下列敘述中，不符合 m 階 B 樹定義要求的是(D) A .根節(jié)點最多有 m 棵子樹 B.所有葉結(jié)點都在同一層上 C .各結(jié)點內(nèi)關(guān)鍵字均升序或降序排列 D.葉結(jié)

16、點之間通過指針鏈接 33、設(shè)散列表中有 m 個存儲單元，散列函數(shù) H(key)= key % p ，則 p 最好選擇( B)。 (A) 小于等于 m 的最大奇數(shù) (B) 小于等于 m 的最大素數(shù) (C) 小于等于 m 的最大偶數(shù) (D) 小于等于 m 的最大合數(shù) 34、適于對動態(tài)查找表進行高效率查找的組織結(jié)構(gòu)是( C ) A 有序表 B 分塊有序表 C.二叉排序樹 D 線性鏈表 35、當(dāng)采用分快查找時，數(shù)據(jù)的組織方式為 ( B ) A. 數(shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)有序 B. 數(shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)不必有序，但塊間必須有序，每塊內(nèi)最大(或最小)的數(shù)據(jù) 組成索引塊 C. 數(shù)據(jù)分成若干塊，每塊內(nèi)

17、數(shù)據(jù)有序，每塊內(nèi)最大(或最小)的數(shù)據(jù)組成索引塊 D. 數(shù)據(jù)分成若干塊，每塊(除最后一塊外)中數(shù)據(jù)個數(shù)需相同 三、判斷題 1 查找相同結(jié)點的效率折半查找總比順序查找高。 (X) 2. 索引順序表的特點是塊內(nèi)可無序，塊間要有序。 (V ) 3. 在采用線性探測法處理沖突的散列表中，所有同義詞在表中一定相鄰。 ( ) 4. 在平衡二叉樹中，任意結(jié)點左右子樹的高度差(絕對值)不超過 1。 (V ) 5. 若查找表的長度為 n,則順序查找法的平均查找長度為(n+1) /2 0 (V ) 6. 折半搜索適用于有序表，包括有序的順序表和有序的鏈表。 (X ) 7. 采用線性探測法處理散列時的沖突，當(dāng)從哈希表

18、刪除一個記錄時，不應(yīng)將這個記錄的所在 位置置空，因為這會影響以后的查找。(V ) 8. 在散列檢索中，“比較”操作一般也是不可避免的。(V ) 9. 在 m 階 B-樹中每個結(jié)點上至少有 個關(guān)鍵字，最多有 m 個關(guān)鍵字。(X ) 10. 負(fù)載因子(裝填因子)是散列表的一個重要參數(shù)，它反映散列表的裝滿程度。(V ) 11. 散列法的平均檢索長度不隨表中結(jié)點數(shù)目的增加而增加， 而是隨負(fù)載因子的增大而增大。 (V ) 12. 哈希表的結(jié)點中只包含數(shù)據(jù)元素自身的信息，不包含任何指針。 ( X ) 13若散列表的負(fù)載因子a 1，則可避免沖突的產(chǎn)生。(X ) 14. 用向量和單鏈表表示的有序表均可使用折半

19、查找方法來提高查找速度。 (X ) 7 15. 在平衡二叉樹中， 向某個平衡因子不為零的結(jié)點的樹中插入一新結(jié)點， 必引起平衡旋轉(zhuǎn) (X ) 16. 二叉樹為二叉排序樹的充分必要條件是其任一結(jié)點的值均大于其左孩子的值、小于其右孩子的值。 ( X ) 17. 就平均查找長度而言，分塊查找最小，折半查找次之，順序查找最大。 (X ) 18. 對大小均為 n 的有序表和無序表分別進行順序查找，在等概率查找的情況下，對于查找 成功，它們的平均查找長度是相同的，而對于查找失敗，它們的平均查找長度是不同的。 (V ) 19. 任一查找樹(二叉分類樹)的平均查找時間都小于用順序查找法查找同樣結(jié)點的線性表的 平

20、均查找時間.(x ) 20、 在二叉樹排序樹中插入一個新結(jié)點，總是插入到葉結(jié)點下面。 (x ) 21、 順序查找法適用于存儲結(jié)構(gòu)為順序或鏈接存儲的線性表。(V ) 四、簡答題 1. 對分(折半)查找適不適合鏈表結(jié)構(gòu)的序列，為什么？用二分查找的查找速度必然比線性 查找的速度快，這種說法對嗎？ 答：不適合！雖然有序的單鏈表的結(jié)點是按從小到大(或從大到小)順序排列，但因其存儲 結(jié)構(gòu)為單鏈表，查找結(jié)點時只能從頭指針開始逐步搜索，故不能進行折半查找。 二分查找的速度在一般情況下是快些，但在特殊情況下未必快。例如所查數(shù)據(jù)位于首位時， 則線性查找快；而二分查找則慢得多。 2. 假定對有序表：(3，4, 5，

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

22、查找 1 + 2X 2+ 4X 3=17 次； 但最后一層未滿，不能用 8X4,只能用 5X4=20 次， 所以 ASL= 1/12 (17 + 20)= 37/12 3.08 3. 設(shè)哈希(Hash)表的地址范圍為 017,哈希函數(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)鍵字進行比較？ (3) 若查找關(guān)鍵字 60,需要依次與哪些關(guān)鍵字

23、比較？ (4) 假定每個關(guān)鍵字的查找概率相等，求查找成功時的平均查找長度。 解：(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)容比較， 但因為 12 號單元為空(應(yīng)當(dāng)有空 標(biāo)記),所以應(yīng)當(dāng)只比較這一次即可。 (4) 對于黑色數(shù)

24、據(jù)元素，各比較 1 次；共 6 次； 對紅色元素則各不相同，要統(tǒng)計移位的位數(shù)。 “63”需要 6 次，“49”需要 3 次，“40”需要 2 次，“ 46”需要 3 次，“ 47”需要 3 次， 所以 ASL=1/11 (6 + 2 + 3X 3)= 17/11=1.5454545454 1.55 4、設(shè)哈希表長度為 11,哈希函數(shù) H( K) = ( K 的第一字母在字母表中的序號) MOD1,1 若輸 入順序為(D, BA TN M Cl, I , K X, TA),處理沖突方法為線性探測再散列或鏈地址法， 要求構(gòu)造哈希表，并求出等概率情況下查找成功平均查找長度。 0 1 2 3 4 5

25、6 7 8 9 10 K TA BA M D CI X TN I ASL=20/9 0 1 2 3 4 5 6 7 8 9 10 9 0 1 2 3 4 5 6 7 8 1 9 10 ASL=15/9 5、輸入一個正整數(shù)序列100, 50, 302, 450, 66, 200, 30, 260，建立一棵二叉排序樹, 要求： 畫出該二叉排序樹； 畫出刪除結(jié)點 302 后的二叉排序樹。 解: 6、設(shè)有一組關(guān)鍵字： 19 , 01, 23, 14, 55, 20, 84, 27, 68，采用哈希函數(shù): H( key)=key mod 7 ,采用開放地址法的線性探測再散列方法解決沖突。 要求：在 0s

26、 11 的散列地址空間中對該關(guān)鍵字序列構(gòu)造哈希表。 0 1 2 3 4 5 6 7 8 9 10 11 2 3 4 5 6 7 8 9 10 11 14 01 23 84 19 55 20 27 68 7、已知如下所示長度為 12 的表: (Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec ) (1) 試按表中元素的順序依次插入一棵初始為空的二叉排序樹， 畫出插入完成之后的二叉排序 樹，并求其在等概率的情況下查找成功的平均查找長度。 (2) 若對表中元素先進行排序構(gòu)成有序表，求在等概率的情況下對此有序表進行折半查找時查 找

27、成BA Cl 200 450 解: TN TA M 100 100 30 66 200 450 10 功的平均查找長度。11 （3）按表中元素順序構(gòu)造一棵平衡二叉排序樹，并求其在等概率的情況下查找成功的平均查找 high) return 0; / 查找不到時返回 0 mid=(low+high)/2; if(ST.elemmid.key= =key) return mid; else if(ST.elemmid.keykey) return Search_Bin_Recursive(ST, key, low, mid-1); else return Search_Bin_Recursive(S

28、T, key, mid+1, high); /Search_Bin_Recursive 2. 試寫一個判別給定二叉樹是否為二叉排序樹的算法，設(shè)此二叉樹以二叉鏈表作存儲結(jié)構(gòu) 且樹中結(jié)點的關(guān)鍵字均不同。 解：注意仔細研究二叉排序樹的定義。易犯的典型錯誤是按下述思路進行判別： “若一棵非空 的二叉樹其左、右子樹均為二叉排序樹，且左子樹的根的值小于根結(jié)點的值，又根結(jié)點的值 不大于右子樹的根的值，則是二叉排序樹” （劉注：即不能只判斷左右孩子的情況，還要判斷左右孩子與雙親甚至根結(jié)點的比值也要遵 循（左小右大）原則）。 若要采用遞歸算法，建議您采用如下的函數(shù)首部: bool BisortTree（BiTr

29、ee T, BiTree&PRE） ，其中 PRE 為指向當(dāng)前訪問結(jié)點的前驅(qū)的指針 （或者直接存儲前驅(qū)的數(shù)值，隨時與當(dāng)前根結(jié)點比較） 一個漂亮的算法設(shè)計如下： int last=0, flag=1; / last 點都比前驅(qū)大就行。 是全局變量，用來記錄前驅(qū)結(jié)點值，只要每個結(jié) 判斷二叉樹 T 是否二叉排序樹，是則返回 1,否則返回 0 16 int Is_BSTree（Bitree T） / if(T-lchild&flag) Is_BSTree(T-lchild); if(T-datadata; if(T-rchild&flag) Is_BSTree(T-rchild

30、); return flag; /Is_BSTree 3. 已知一個含有 1000 個記錄的表，關(guān)鍵字為中國人姓氏的拼音，請給出此表的一個哈希表 設(shè)計方案，要求它在等概率情況下查找成功的平均查找長度不超過 3。 解：設(shè)計哈希表的步驟為： a) 根據(jù)所選擇的處理沖突的方法求出裝載因子 a 的上界； b) 由 a 值設(shè)計哈希表的長度 m； c) 根據(jù)關(guān)鍵字的特性和表長 m 選定合適的哈希函數(shù)。 劉注：要求 ASLC 3,則 m 必然要盡量長，以減少沖突； 4. 已知某哈希表的裝載因子小于 1，哈希函數(shù) H(key) 為關(guān)鍵字(標(biāo)識符)的第一個字母在字 母表中的序號， 處理沖突的方法為線性探測開放定

31、址法。 試編寫一個按第一個字母的順序 輸出哈希表中所有關(guān)鍵字的算法。 解：注意此題給出的條件：裝載因子 a1, 則哈希表未填滿。由此可寫出下列形式簡明的算 法： void PrintWord(Hash Table ht) / 按第一個字母的順序輸出哈希表 ht 中的標(biāo)識符。哈希函數(shù)為表示符的第一個字母在字母 表中的序號，處理沖突的方法是線性探測開放定址法。 for(i=1; i03, 87, 512, 61, 908, 170, 897, 275, 653, 462),試完成下 列各題。 （1） 根據(jù)以上序列建立一個堆（畫出第一步和最后堆的結(jié)果圖），希望先輸出最小值。 （2） 輸出最小值后，如

32、何得到次小值。（并畫出相應(yīng)結(jié)果圖） 答：略 &有一隨機數(shù)組（25,84,21,46,13,27,68,35,20）, 現(xiàn)采用某種方法對它們進行排序,其每趟排 序結(jié)果如下，則該排序方法是什么？ 初 始:25,84,21,46,13,27,68,35,20 第一趟:20,13,21,25,46,27,68,35,84 第二趟:13,20,21,25,35,27,46,68,84 第三趟:13,20,21,25,27,35,46,68,84 答：該排序方法為快速排序 9、 對給定文件（28, 07，39，10，65，14, 61，17, 50，21）選擇第一個元素 28 進行劃分, 寫出其快

33、速排序第一遍的排序過程。 答：初始序列：28,07,39,10,65,14,61,17,50,21 21 移動： 21,07,39,10,65,14,61,17,50, 39 移動：21,07,10,65,14,61,17,50,39 17 移動： 21,07,17,10,65,14,61,50,39 65 移動：21,07,17,10,14,61,65,50,39 14 移動： 21,07,17,10,14,28,61,65,50,39 10、 已知一關(guān)鍵碼序列為：3, 87, 12, 61, 70, 97, 26, 45。試根據(jù)堆排序原理，填寫完整 下示各步驟結(jié)果。 建立堆結(jié)構(gòu)： _ 交換

34、與調(diào)整： （1）87 70 26 61 45 12 3 97; （2） _ ; （3）61 45 26 3 12 70 87 97; _ （ 4） ; （5）26 12 3 45 61 70 87 97; （ 6） _ ; （7）3 12 26 45 61 70 87 97; 答：建立堆結(jié)構(gòu) :97,87,26,61,70,12,3,45 (2)70,61,26,3,45,12,87,97 24 (4) 45,12,26,3,61,70,87,97 (6)12,3,26,45,61,70,87,97 四、算法設(shè)計題 1、下面是冒泡排序算法，請閱讀并完成該程序，并回答以下問題： PROCEDUR

35、E bubblesort (r,n) BEGIN i:=1; m:=n-1; flag:=1; WHILE (irj+1.key THEN BEGIN flag:= (4)_; t:=rj; rj:=rj+1; rj+1:=t END; i:=i+1;m:=m-1 END; END. (1) 請在上面橫線上填上適當(dāng)?shù)恼Z句，完成該算法程序。 (2) 設(shè)計標(biāo)志 flag 的作用是什么？ (3) 該算法結(jié)點的最大比較次數(shù)和最大移動次數(shù)是多少？ (4) 該分類算法穩(wěn)定嗎？ 答： 略 2、有 n 個記錄存儲在帶頭結(jié)點的雙向鏈表中，現(xiàn)用雙向起泡排序法對其按上升序進行排序， 請寫出這種排序的算法。(注：雙向起泡排序即相鄰兩趟排序向相反方向起泡) 答： typedef struct node ElemType data; struct node *prior,*next; node ， *DLinkedList; void TwoWayBubbleSort(DLinkedList la) / 對存儲在帶頭結(jié)點的雙向鏈表 la 中的元素進行雙向起泡排序。 int exchang