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

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

2、.7 。 解：顯然，平均查找長(zhǎng)度二 0（ log 2n） 5 次（25）。但具體是多少次，則不應(yīng)當(dāng)按照公式 ASL =n 1 log2（n 1）來(lái)計(jì)算（即（21 X log 221） /20 = 4.6 次并不正確?。?。因?yàn)檫@是在假設(shè) n = 21 n 的情況下推導(dǎo)出來(lái)的公式。應(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、種查找方法中，平均查找長(zhǎng)度與結(jié)點(diǎn)個(gè)數(shù) n 無(wú)關(guān)的查找方法是散列查找 。 6. 散列法存儲(chǔ)的基本思想是由 關(guān)鍵字的值 決定數(shù)據(jù)的存儲(chǔ)地址。 7. 有一個(gè)表長(zhǎng)為 m 的散列表，初始狀態(tài)為空，現(xiàn)將 n （nm 個(gè)不同的關(guān)鍵碼插入到散列表 中，解決沖突的方法是用線性探測(cè)法。如果這 n 個(gè)關(guān)鍵碼的散列地址都相同，貝U探測(cè)的總 次數(shù)是 n（n-1）/2= （ 1 土 2+ , 土 n-1 ）。（而任一元素查找次數(shù) n-1） &設(shè)一哈希表表長(zhǎng) M 為 100，用除留余數(shù)法構(gòu)造哈希函數(shù)，即 H（ K） =K MOIP （ P=M ,為 使函數(shù)具有較好性能，P 應(yīng)選（97 ） 9、 在各種查找方法中，平

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

5、， 則 左子樹 _ 上所有結(jié)點(diǎn)的值均小于它的 根結(jié)點(diǎn)值， 右子樹 _ 所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值。 2 16. 中序遍歷二叉排序樹得到的序列是 有序 序列（填有序或無(wú)序）。 17、從有序表(10, 16, 25, 40, 61, 28, 80, 93)中依次二分查找 40 和 61 元素時(shí)，其查找 長(zhǎng)度分別為 1和 3 二、單項(xiàng)選擇題 (B )1 在表長(zhǎng)為n的鏈表中進(jìn)行順序查找，它的平均查找長(zhǎng)度為 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. 對(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í)都是 0 (lo

7、g 2n) 6. 散列表的地址區(qū)間為 0-17,散列函數(shù)為 H(K)=K mod 17。采用線性探測(cè)法處理沖突，并將 關(guān)鍵字序列 26, 25, 72, 38, 8, 18, 59 依次存儲(chǔ)到散列表中。元素 59 存放在散列表中的地 址是(D ) o A. 8 B. 9 C. 10 D. 11 7. 當(dāng)采用分快查找時(shí)，數(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ù)個(gè)數(shù)需相同 8. 散列函數(shù)有一個(gè)共同的性質(zhì)，即函數(shù)值應(yīng)當(dāng)以 (D )取其值域的每個(gè)值。 A.最大概率 B. 最小概率 C. 平均概率 D. 同等概率 9. 假定有 k 個(gè)關(guān)鍵字互為同義詞，若用線性探測(cè)法把這 k 個(gè)關(guān)鍵字存入散列表中，至少要進(jìn) 行多少次探測(cè)？(D ) A. k-1 次 B. k 次 C. k+1 次 D. k (k+1) /2 次 3 10. 哈希查找中 k 個(gè)關(guān)鍵字具有同一哈希值，若用線性探測(cè)法將這 k 個(gè)關(guān)鍵字對(duì)應(yīng)的記錄存 入哈希表中，至少要進(jìn)行() 次探測(cè)。【西安電子科技大學(xué) 1998 一、8 (2 分)】 A k B. k+1 C. k(k+1)/2 D.1+k

9、(k+1)/2 11、 在平衡二叉樹中插入一個(gè)結(jié)點(diǎn)后造成了不平衡，設(shè)最低的不平衡結(jié)點(diǎn)為 A,并已知A的左 孩子的平衡因子為 0 右孩子的平衡因子為 1,則應(yīng)作( C ) 型調(diào)整以使其平衡。 A. LL B. LR C. RL D. RR 12、 二叉查找樹的查找效率與二叉樹的 ( C) 有關(guān), 在 (B )時(shí)其查找效率最低 (1) : A. 高度 B. 結(jié)點(diǎn)的多少 C. 樹型 D. 結(jié)點(diǎn)的位置 (2) : A. 結(jié)點(diǎn)太多 B. 完全二叉樹 C. 呈單枝樹 D. 結(jié)點(diǎn)太復(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、 對(duì)包含 n 個(gè)元素的哈希表進(jìn)行查找，平均查找長(zhǎng)度為( D) A) O(log 2n) B) O(n) C) O(nlog 2n) D) 不直接依賴于 n 15、 若查找每個(gè)記錄的概率均等，則在具有 n 個(gè)記錄的連續(xù)順序文件中采用順序查找法查找 一個(gè)記錄，其平均查找長(zhǎng)度 ASL 為(C )。 A (n-1)/2 B. n/2 C. (n+1)/2 D. n 16、 下面關(guān)于二分查找的敘述正確的是 ( D ) A. 表必須有序，表可以順序方式存儲(chǔ)，也可以鏈表方式存儲(chǔ) C. 表必須有序，而且只能從 小

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

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

13、4. 二叉排序樹的查找效率與二叉樹的(C)有關(guān) A. 高度 B. 結(jié)點(diǎn)的多少 C. 樹型 D. 結(jié)點(diǎn)的位置 25. 在等概率情況下,一棵平衡樹的 ASL 為(B ) A. 0(1) B. 0( log2n ) C. O(log2 n)2) D.O( nl og2 n) 26. 分別以下列序列構(gòu)造二叉排序樹，與用其它三個(gè)序列所構(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. 在平衡二叉樹中插入一個(gè)結(jié)點(diǎn)后造成了不平衡，設(shè)最低的不平衡結(jié)點(diǎn)為 孩子的平衡因子為 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-樹的說(shuō)法錯(cuò)誤的是(D A.根結(jié)點(diǎn)至多有 m 棵子樹 B .所有葉子都在同一層次上 C.

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

16、點(diǎn)之間通過(guò)指針鏈接 33、設(shè)散列表中有 m 個(gè)存儲(chǔ)單元，散列函數(shù) H(key)= key % p ，則 p 最好選擇( B)。 (A) 小于等于 m 的最大奇數(shù) (B) 小于等于 m 的最大素?cái)?shù) (C) 小于等于 m 的最大偶數(shù) (D) 小于等于 m 的最大合數(shù) 34、適于對(duì)動(dòng)態(tài)查找表進(jìn)行高效率查找的組織結(jié)構(gòu)是( C ) A 有序表 B 分塊有序表 C.二叉排序樹 D 線性鏈表 35、當(dāng)采用分快查找時(shí)，數(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ù)個(gè)數(shù)需相同 三、判斷題 1 查找相同結(jié)點(diǎn)的效率折半查找總比順序查找高。 (X) 2. 索引順序表的特點(diǎn)是塊內(nèi)可無(wú)序，塊間要有序。 (V ) 3. 在采用線性探測(cè)法處理沖突的散列表中，所有同義詞在表中一定相鄰。 ( ) 4. 在平衡二叉樹中，任意結(jié)點(diǎn)左右子樹的高度差(絕對(duì)值)不超過(guò) 1。 (V ) 5. 若查找表的長(zhǎng)度為 n,則順序查找法的平均查找長(zhǎng)度為(n+1) /2 0 (V ) 6. 折半搜索適用于有序表，包括有序的順序表和有序的鏈表。 (X ) 7. 采用線性探測(cè)法處理散列時(shí)的沖突，當(dāng)從哈希表

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

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

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

21、7，24, 30，42, 54, 63, 72, 87，95)進(jìn)行折半查找，試回答 下列問(wèn)題： (1) 畫出描述折半查找過(guò)程的判定樹； (2) 若查找元素 54,需依次與哪些元素比較？ (3) 若查找元素 90,需依次與哪些元素比較？ (4) 假定每個(gè)元素的查找概率相等，求查找成功時(shí)的平均查找長(zhǎng)度。 解： (1) 先畫出判定樹如下(注： mid=j(1+12)/2 =6)： 查找元素 54,需依次與 30, 63, 42, 54 等元素比較； 查找元素 90,需依次與 30, 63,87, 95, 72 等元素比較； 8 (4)求 ASL 之前，需要統(tǒng)計(jì)每個(gè)元素的查找次數(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)鍵字，用線性探測(cè)法再散列法處理沖突，輸入關(guān)鍵字序列： (10, 24, 32, 17, 31, 30, 46, 47, 40, 63, 49) 造出 Hash 表，試回答下列問(wèn)題： (1) 畫出哈希表的示意圖； (2) 若查找關(guān)鍵字 63,需要依次與哪些關(guān)鍵字進(jìn)行比較？ (3) 若查找關(guān)鍵字 60,需要依次與哪些關(guān)鍵字

23、比較？ (4) 假定每個(gè)關(guān)鍵字的查找概率相等，求查找成功時(shí)的平均查找長(zhǎng)度。 解：(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 號(hào)單元內(nèi)容比較，即 63 vs 31 ,no; 然后順移，與 46,47,32,17,63 相比，一共比較了 6 次！ (3) 查找 60,首先要與 H(60)=60%16=12 號(hào)單元內(nèi)容比較， 但因?yàn)?12 號(hào)單元為空(應(yīng)當(dāng)有空 標(biāo)記),所以應(yīng)當(dāng)只比較這一次即可。 (4) 對(duì)于黑色數(shù)

24、據(jù)元素，各比較 1 次；共 6 次； 對(duì)紅色元素則各不相同，要統(tǒng)計(jì)移位的位數(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è)哈希表長(zhǎng)度為 11,哈希函數(shù) H( K) = ( K 的第一字母在字母表中的序號(hào)) MOD1,1 若輸 入順序?yàn)?D, BA TN M Cl, I , K X, TA),處理沖突方法為線性探測(cè)再散列或鏈地址法， 要求構(gòu)造哈希表，并求出等概率情況下查找成功平均查找長(zhǎng)度。 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、輸入一個(gè)正整數(shù)序列100, 50, 302, 450, 66, 200, 30, 260，建立一棵二叉排序樹, 要求： 畫出該二叉排序樹； 畫出刪除結(jié)點(diǎn) 302 后的二叉排序樹。 解: 6、設(shè)有一組關(guān)鍵字： 19 , 01, 23, 14, 55, 20, 84, 27, 68，采用哈希函數(shù): H( key)=key mod 7 ,采用開放地址法的線性探測(cè)再散列方法解決沖突。 要求：在 0s

26、 11 的散列地址空間中對(duì)該關(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、已知如下所示長(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ì)此有序表進(jìn)行折半查找時(shí)查 找

27、成BA Cl 200 450 解: TN TA M 100 100 30 66 200 450 10 功的平均查找長(zhǎng)度。11 （3）按表中元素順序構(gòu)造一棵平衡二叉排序樹，并求其在等概率的情況下查找成功的平均查找 high) return 0; / 查找不到時(shí)返回 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. 試寫一個(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ù)首部: bool BisortTree（BiTr

29、ee T, BiTree&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 點(diǎn)都比前驅(qū)大就行。 是全局變量，用來(lái)記錄前驅(qū)結(jié)點(diǎn)值，只要每個(gè)結(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. 已知一個(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ù)。 劉注：要求 ASLC 3,則 m 必然要盡量長(zhǎng)，以減少?zèng)_突； 4. 已知某哈希表的裝載因子小于 1，哈希函數(shù) H(key) 為關(guān)鍵字(標(biāo)識(shí)符)的第一個(gè)字母在字 母表中的序號(hào)， 處理沖突的方法為線性探測(cè)開放定

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

32、何得到次小值。（并畫出相應(yīng)結(jié)果圖） 答：略 &有一隨機(jī)數(shù)組（25,84,21,46,13,27,68,35,20）, 現(xiàn)采用某種方法對(duì)它們進(jì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、 對(duì)給定文件（28, 07，39，10，65，14, 61，17, 50，21）選擇第一個(gè)元素 28 進(jìn)行劃分, 寫出其快

33、速排序第一遍的排序過(guò)程。 答：初始序列：28,07,39,10,65,14,61,17,50,21 21 移動(dòng)： 21,07,39,10,65,14,61,17,50, 39 移動(dòng)：21,07,10,65,14,61,17,50,39 17 移動(dòng)： 21,07,17,10,65,14,61,50,39 65 移動(dòng)：21,07,17,10,14,61,65,50,39 14 移動(dòng)： 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è)計(jì)題 1、下面是冒泡排序算法，請(qǐng)閱讀并完成該程序，并回答以下問(wèn)題： 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) 請(qǐng)?jiān)谏厦鏅M線上填上適當(dāng)?shù)恼Z(yǔ)句，完成該算法程序。 (2) 設(shè)計(jì)標(biāo)志 flag 的作用是什么？ (3) 該算法結(jié)點(diǎn)的最大比較次數(shù)和最大移動(dòng)次數(shù)是多少？ (4) 該分類算法穩(wěn)定嗎？ 答： 略 2、有 n 個(gè)記錄存儲(chǔ)在帶頭結(jié)點(diǎn)的雙向鏈表中，現(xiàn)用雙向起泡排序法對(duì)其按上升序進(jìn)行排序， 請(qǐng)寫出這種排序的算法。(注：雙向起泡排序即相鄰兩趟排序向相反方向起泡) 答： typedef struct node ElemType data; struct node *prior,*next; node ， *DLinkedList; void TwoWayBubbleSort(DLinkedList la) / 對(duì)存儲(chǔ)在帶頭結(jié)點(diǎn)的雙向鏈表 la 中的元素進(jìn)行雙向起泡排序。 int exchang