《數(shù)據(jù)結(jié)構(gòu)》習(xí)題匯編08-第八章-查找-試題(共13頁(yè))

1、精選優(yōu)質(zhì)文檔-傾情為你奉上數(shù)據(jù)結(jié)構(gòu)課程（本科）第七章試題一、單項(xiàng)選擇題1. 若搜索每一個(gè)元素的概率相等，則在長(zhǎng)度為n的順序表上搜索到表中任一元素的平均搜索長(zhǎng)度為（ ）。 A. n B. n+1 C. (n-1)/2 D. (n+1)/22. 對(duì)長(zhǎng)度為10的順序表進(jìn)行搜索，若搜索前面5個(gè)元素的概率相同，均為1/8，搜索后面5個(gè)元素的概率相同，均為3/40，則搜索到表中任一元素的平均搜索長(zhǎng)度為（ ）。 A. 5.5 B. 5 C. 39/8 D. 19/43. 對(duì)長(zhǎng)度為3的順序表進(jìn)行搜索，若搜索第一個(gè)元素的概率為1/2，搜索第二個(gè)元素的概率為1/3，搜索第三個(gè)元素的概率為1/6，則搜索到表中任一元

2、素的平均搜索長(zhǎng)度為（ ）。 A. 5/3 B. 2 C. 7/3 D. 4/34. 對(duì)長(zhǎng)度為n的有序單鏈表，若搜索每個(gè)元素的概率相等，則順序搜索到表中任一元素的平均搜索長(zhǎng)度為（ ）。 A. n/2 B. (n+1)/2 C. (n-1)/2 D. n/45. 對(duì)于長(zhǎng)度為n的有序順序表，若采用折半搜索，則對(duì)所有元素的搜索長(zhǎng)度中最大的為（ ）的值的向上取整。 A. log2(n+1) B. log2n C. n/2 D. (n+1)/26. 對(duì)于長(zhǎng)度為n的有序順序表，若采用折半搜索，則對(duì)所有元素的搜索長(zhǎng)度中最大的為（ ）的值的向下取整加一。 A. log2(n+1) B. log2n C. n/2

3、 D. (n+1)/27. 對(duì)于長(zhǎng)度為9的有序順序表，若采用折半搜索，在等概率情況下搜索成功的平均搜索長(zhǎng)度為（ ）的值除以9。 A. 20 B. 18 C. 25 D. 228. 對(duì)于長(zhǎng)度為18的有序順序表，若采用折半搜索，則搜索第15個(gè)元素的搜索長(zhǎng)度為（ ）。 A. 3 B. 4 C. 5 D. 69. 對(duì)具有n個(gè)元素的有序順序表進(jìn)行折半搜索，則搜索任一元素的時(shí)間復(fù)雜度為（ ）。 A. O(n) B. O(n2) C. O(1) D. O(log2n)10. 在一棵高度為h的具有n個(gè)元素的二叉搜索樹(shù)中，搜索所有元素的搜索長(zhǎng)度中最大的為（ ）。 A. n B. log2n C. (h+1)/2

4、 D. h+111. 從具有n個(gè)結(jié)點(diǎn)的二叉搜索樹(shù)中搜索一個(gè)元素時(shí)，在等概率情況下進(jìn)行成功搜索的時(shí)間復(fù)雜度大致為（ ）。A. O(n) B. O(1) C. O(log2n) D. O(n2)12. 從具有n個(gè)結(jié)點(diǎn)的二叉搜索樹(shù)中搜索一個(gè)元素時(shí)，在最壞情況下進(jìn)行成功搜索的時(shí)間復(fù)雜度為（ ）。 A. O(n) B. O(1) C. O(log2n) D. O(n2)13. 向具有n個(gè)結(jié)點(diǎn)的二叉搜索樹(shù)中插入一個(gè)元素時(shí)，其時(shí)間復(fù)雜度大致為（ ）。 A. O(1) B. O(log2n ) C. O(n) D. O(nlog2n)14. 在一棵AVL樹(shù)（高度平衡的二叉搜索樹(shù)）中，每個(gè)結(jié)點(diǎn)的平衡因子的取值范

5、圍是（ ）。 A. -11 B. -22 C. 12 D. 0115. 向一棵AVL樹(shù)（高度平衡的二叉搜索樹(shù)）插入元素時(shí)，可能引起對(duì)最小不平衡子樹(shù)的調(diào)整過(guò)程，此調(diào)整分為（ ）種旋轉(zhuǎn)類(lèi)型。 A. 2 B. 3 C. 4 D. 516. 向一棵AVL樹(shù)（高度平衡的二叉搜索樹(shù)）插入元素時(shí)，可能引起對(duì)最小不平衡子樹(shù)的左單或右單旋轉(zhuǎn)的調(diào)整過(guò)程，此時(shí)需要修改相關(guān)（ ）個(gè)結(jié)點(diǎn)指針域的值。 A. 2 B. 3 C. 4 D. 517. 向一棵AVL樹(shù)（高度平衡的二叉搜索樹(shù)）插入元素時(shí)，可能引起對(duì)最小不平衡子樹(shù)的雙向旋轉(zhuǎn)的調(diào)整過(guò)程，此時(shí)需要修改相關(guān)（ ）個(gè)結(jié)點(diǎn)指針域的值。 A. 2 B. 3 C. 4 D. 5

6、參考答案：1. D2. C3. A4. B5. A6. B7. C 8. A9. D10. D11. C12. A13. B14. A15. C16. A17. C二、填空題1. 以順序搜索方法從長(zhǎng)度為n的順序表或單鏈表中搜索一個(gè)元素時(shí)，其時(shí)間復(fù)雜度為_(kāi)。2. 對(duì)長(zhǎng)度為n的搜索表進(jìn)行搜索時(shí)，假定搜索第i個(gè)元素的概率為pi，搜索長(zhǎng)度（即在搜索過(guò)程中依次同有關(guān)元素比較的總次數(shù)）為ci，則在搜索成功情況下的平均搜索長(zhǎng)度的計(jì)算公式為_(kāi)。3. 假定一個(gè)順序表的長(zhǎng)度為40，并假定搜索每個(gè)元素的概率都相同，則在搜索成功情況下的平均搜索長(zhǎng)度為_(kāi)。4. 以折半搜索方法從長(zhǎng)度為n的有序表中搜索一個(gè)元素時(shí)，時(shí)間復(fù)雜

7、度為_(kāi)。5. 從有序表 (12, 18, 30, 43, 56, 78, 82, 95) 中折半搜索元素56時(shí)，其搜索長(zhǎng)度為_(kāi)。6. 假定對(duì)長(zhǎng)度n = 50的有序表進(jìn)行折半搜索，則對(duì)應(yīng)的判定樹(shù)中最后一層的結(jié)點(diǎn)數(shù)為_(kāi)個(gè)。7. 從一棵二叉搜索樹(shù)中搜索一個(gè)元素時(shí)，若給定值小于根結(jié)點(diǎn)的值，則需要向_繼續(xù)搜索。8. 從一棵二叉搜索樹(shù)中搜索一個(gè)元素時(shí)，若給定值大于根結(jié)點(diǎn)的值，則需要向_繼續(xù)搜索。9. 向一棵二叉搜索樹(shù)中插入一個(gè)新元素時(shí)，若該新元素的值小于根結(jié)點(diǎn)的值，則應(yīng)把它插入到根結(jié)點(diǎn)的_上。10. 向一棵二叉搜索樹(shù)中插入一個(gè)新元素時(shí)，若該新元素的值大于根結(jié)點(diǎn)的值，則應(yīng)把它插入到根結(jié)點(diǎn)的_上。11. 向一

8、棵二叉搜索樹(shù)_一個(gè)元素時(shí)，若查找到的根結(jié)點(diǎn)為空值，則應(yīng)把該元素結(jié)點(diǎn)鏈接到這個(gè)空指針位置上。12. 根據(jù)n個(gè)元素建立一棵二叉搜索樹(shù)的時(shí)間復(fù)雜度性大致為_(kāi)。13. 在一棵AVL樹(shù)（高度平衡的二叉搜索樹(shù)）中，每個(gè)結(jié)點(diǎn)的左子樹(shù)高度與右子樹(shù)高度之差的絕對(duì)值不超過(guò)_。14. 根據(jù)一組記錄 ( 56, 42, 50, 64, 48 ) 依次插入結(jié)點(diǎn)生成一棵AVL樹(shù)（高度平衡的二叉搜索樹(shù)）時(shí)，當(dāng)插入到值為_(kāi)的結(jié)點(diǎn)時(shí)需要進(jìn)行旋轉(zhuǎn)調(diào)整。 15. 根據(jù)一組記錄 ( 56, 74, 63, 64, 48 ) 依次插入結(jié)點(diǎn)生成一棵AVL樹(shù)（高度平衡的二叉搜索樹(shù)）時(shí)，當(dāng)插入到值為63的結(jié)點(diǎn)時(shí)需要進(jìn)行_調(diào)整。16. 根據(jù)一

9、組記錄 ( 56, 42, 38, 64, 48 ) 依次插入結(jié)點(diǎn)生成一棵AVL樹(shù)（高度平衡的二叉搜索樹(shù)）時(shí)，當(dāng)插入到值為38的結(jié)點(diǎn)時(shí)需要進(jìn)行_調(diào)整。17. 根據(jù)一組記錄 ( 56, 42, 73, 50, 64, 48, 22 ) 依次插入結(jié)點(diǎn)生成一棵AVL樹(shù)（高度平衡的二叉搜索樹(shù)）時(shí)，當(dāng)插入到值為_(kāi)的結(jié)點(diǎn)時(shí)才出現(xiàn)不平衡，需要進(jìn)行旋轉(zhuǎn)調(diào)整。 18. 在一棵AVL樹(shù)（高度平衡的二叉搜索樹(shù)）上進(jìn)行插入或刪除元素時(shí)，所需的時(shí)間復(fù)雜度為_(kāi)。參考答案：1. O(n)2. 3. 20.54. O(log2n)5. 36. 197. 左子樹(shù)8. 右子樹(shù)9. 左子樹(shù)10. 右子樹(shù)11. 插入12. O(nl

10、og2n)13. 114. 5015. 先右后左雙旋轉(zhuǎn)16. 右單旋轉(zhuǎn)17. 4818. O(lon2n) 三、判斷題1. 在順序表中進(jìn)行順序搜索時(shí)，若各元素的搜索概率不等，則各元素應(yīng)按照搜索概率的降序排列存放，則可得到最小的平均搜索長(zhǎng)度。2. 進(jìn)行折半搜索的表必須是順序存儲(chǔ)的有序表。3. 能夠在鏈接存儲(chǔ)的有序表上進(jìn)行折半搜索，其時(shí)間復(fù)雜度與在順序存儲(chǔ)的有序表上相同。4. 假定用兩個(gè)有序單鏈表表示兩個(gè)集合，則這兩個(gè)集合交運(yùn)算得到的集合單鏈表，其長(zhǎng)度小于參加運(yùn)算的任一個(gè)集合單鏈表的長(zhǎng)度。5. 假定用兩個(gè)有序單鏈表表示兩個(gè)集合，則這兩個(gè)集合的差運(yùn)算得到的集合單鏈表，其長(zhǎng)度小于參加運(yùn)算的任一個(gè)集合單

11、鏈表的長(zhǎng)度。6. 折半搜索所對(duì)應(yīng)的判定樹(shù)，既是一棵二叉搜索樹(shù)，又是一棵理想平衡二叉樹(shù)（它的特點(diǎn)是除最底層結(jié)點(diǎn)外其他各層結(jié)點(diǎn)數(shù)都是滿(mǎn)的，最底層的若干結(jié)點(diǎn)可能散布在該層各處）。7. 對(duì)二叉搜索樹(shù)進(jìn)行前序遍歷得到的結(jié)點(diǎn)序列是一個(gè)有序序列。8. 在由n個(gè)元素組成的有序表上進(jìn)行折半搜索時(shí)，對(duì)任一個(gè)元素進(jìn)行搜索的長(zhǎng)度（即比較次數(shù)）都不會(huì)大于log2n+1。9. 根據(jù)n個(gè)元素建立一棵二叉搜索樹(shù)的時(shí)間復(fù)雜度大致為O(log2n)。10. 根據(jù)n個(gè)元素建立一棵二叉搜索樹(shù)的時(shí)間復(fù)雜度大致為O(nlog2n)。11. 對(duì)于同一組記錄，若生成二叉搜索樹(shù)時(shí)插入記錄的次序不同則得到不同結(jié)構(gòu)的二叉搜索樹(shù)。12. 對(duì)于同一組

12、記錄，生成二叉搜索樹(shù)的結(jié)構(gòu)與插入記錄的次序無(wú)關(guān)。13. 對(duì)于兩棵具有相同記錄集合而具有不同結(jié)構(gòu)的二叉搜索樹(shù)，按中序遍歷得到的結(jié)點(diǎn)序列是相同的。14. 在二叉搜索樹(shù)中，若各結(jié)點(diǎn)的搜索概率不等，使得搜索概率越大的結(jié)點(diǎn)離樹(shù)根越近，則得到的是最優(yōu)二叉搜索樹(shù)。15. 在二叉搜索樹(shù)中，若各結(jié)點(diǎn)的搜索概率不等，使得搜索概率越小的結(jié)點(diǎn)離樹(shù)根越近，則得到的是最優(yōu)二叉搜索樹(shù)。參考答案：1. 是2. 是3. 否4. 是5. 否6. 是7. 否8. 是9. 否10. 是11. 是12. 否13. 是14. 是15. 否四、運(yùn)算題1. 一個(gè)一維數(shù)組a10中存儲(chǔ)著一個(gè)有序表，該有序表為：(15, 26, 34, 39,

13、45, 56, 58, 63, 74, 76 )，根據(jù)折半搜索所對(duì)應(yīng)的判定樹(shù)，寫(xiě)出該判定樹(shù)的廣義表表示，并求出在等概率情況下搜索成功的平均搜索長(zhǎng)度。判定樹(shù)的廣義表表示：_平均搜索長(zhǎng)度：_2. 已知一個(gè)有序表 ( 15, 26, 34, 39, 45, 56, 58, 63, 74, 76, 83, 94 ) 順序存儲(chǔ)于一維數(shù)組a12中，根據(jù)折半搜索過(guò)程填寫(xiě)成功搜索下表中所給元素34, 56, 58, 63, 94時(shí)的比較次數(shù)。34 56 58 63 94 元素值 比較次數(shù)3. 假定一個(gè)線(xiàn)性序列為 ( 38, 52, 25, 74, 68, 16, 30, 54, 90, 72 )，根據(jù)此線(xiàn)性序

14、列中元素的排列次序生成一棵二叉搜索樹(shù)，求出對(duì)該二叉搜索樹(shù)查找38, 74, 68, 30, 72等元素時(shí)的比較次數(shù)。38 74 68 30 72 待查元素： 比較次數(shù)：4. 假定一個(gè)線(xiàn)性序列為 ( 56, 27, 34, 95, 73, 16, 50, 62, 65 )，根據(jù)此線(xiàn)性序列中元素的排列次序生成一棵二叉搜索樹(shù)，求出該二叉搜索樹(shù)的高度（假定樹(shù)根結(jié)點(diǎn)的高度為0）、度為2的結(jié)點(diǎn)個(gè)數(shù)和葉子結(jié)點(diǎn)個(gè)數(shù)。高度：_度為2的結(jié)點(diǎn)個(gè)數(shù)：_葉子結(jié)點(diǎn)個(gè)數(shù)：_5. 假定一個(gè)線(xiàn)性序列為 ( 38, 42, 55, 15, 23, 44, 30, 74, 48, 26 )，根據(jù)此線(xiàn)性序列中元素的排列次序生成一棵二

15、叉搜索樹(shù)，求出該二叉搜索樹(shù)中左子樹(shù)為空的所有單支結(jié)點(diǎn)和右子樹(shù)為空的所有單支結(jié)點(diǎn)，請(qǐng)按從小到大的次序排列寫(xiě)出。左子樹(shù)為空的所有結(jié)點(diǎn)：_右子樹(shù)為空的所有結(jié)點(diǎn)：_6. 已知一棵二叉搜索樹(shù)的廣義表表示為：28 (12 ( , 16), 49 (34 (30), 72 (63) ) )，按主教材介紹的刪除算法，求出從中依次刪除72, 12, 49, 28結(jié)點(diǎn)后得到的二叉搜索樹(shù)的廣義表表示。廣義表表示：_7. 假定一組數(shù)據(jù)對(duì)象為 ( 40, 28, 16, 56, 50, 32, 30, 63 )，按次序插入每個(gè)對(duì)象生成一棵AVL樹(shù)（高度平衡的二叉搜索樹(shù)），根據(jù)插入過(guò)程填寫(xiě)下表，在相應(yīng)位置填寫(xiě)所需要的調(diào)整

16、類(lèi)型：“左單旋轉(zhuǎn)”、“右單旋轉(zhuǎn)”、“先左后右雙旋轉(zhuǎn)”、“先右后左雙旋轉(zhuǎn)”，若不需要旋轉(zhuǎn)則填寫(xiě)“無(wú)”。40 28 16 56 50 32 30 63 數(shù)據(jù)： 調(diào)整：8. 假定一組數(shù)據(jù)對(duì)象為 ( 40, 28, 16, 56, 50, 32, 30, 63, 44, 38 )，按次序插入每個(gè)對(duì)象生成一棵AVL樹(shù)（高度平衡的二叉搜索樹(shù)），請(qǐng)回答插入后需調(diào)整的結(jié)點(diǎn)個(gè)數(shù)和插入后不調(diào)整的結(jié)點(diǎn)個(gè)數(shù)。插入時(shí)伴隨旋轉(zhuǎn)調(diào)整的結(jié)點(diǎn)個(gè)數(shù)：_插入不調(diào)整的結(jié)點(diǎn)個(gè)數(shù)：_ 9. 假定一組記錄為 ( 36, 75, 83, 54, 12, 67, 60, 40 )，按次序插入每個(gè)結(jié)點(diǎn)生成一棵AVL樹(shù)（高度平衡的二叉搜索樹(shù)），請(qǐng)

17、回答在插入時(shí)需進(jìn)行“左單旋轉(zhuǎn)”、“右單旋轉(zhuǎn)”、“先左后右雙旋轉(zhuǎn)”、“先右后左雙旋轉(zhuǎn)”，“不調(diào)整”的結(jié)點(diǎn)數(shù)各是多少？左單旋轉(zhuǎn)結(jié)點(diǎn)個(gè)數(shù)：_右單旋轉(zhuǎn)結(jié)點(diǎn)個(gè)數(shù)：_先左后右雙旋轉(zhuǎn)結(jié)點(diǎn)個(gè)數(shù)：_先右后左雙旋轉(zhuǎn)結(jié)點(diǎn)個(gè)數(shù)：_不調(diào)整結(jié)點(diǎn)個(gè)數(shù)：_10. 假定一組記錄為 ( 38, 42, 55, 15, 23, 44, 30, 74, 48, 26 )，按次序插入每個(gè)結(jié)點(diǎn)生成一棵AVL樹(shù)（高度平衡的二叉搜索樹(shù)），給出最后得到的AVL樹(shù)中度為2、度為1和度為0的結(jié)點(diǎn)個(gè)數(shù)。度為2的結(jié)點(diǎn)個(gè)數(shù)：_度為1的結(jié)點(diǎn)個(gè)數(shù)：_度為0的結(jié)點(diǎn)個(gè)數(shù)：_參考答案：1. 判定樹(shù)的廣義表表示：45 (26 (15, 34 ( , 39 ) ),

18、 63 ( 56 ( , 58 ), 74 ( , 76 ) ) ) /4分平均查找長(zhǎng)度：29/10/2分34 56 58 63 9402 1 3 4 42. 判斷結(jié)果元素值 比較次數(shù) /對(duì)1個(gè)給1分，全對(duì)給6分38 74 68 30 7201 3 4 3 53. 判斷結(jié)果待查元素：比較次數(shù)：/對(duì)1個(gè)給1分，全對(duì)給6分4. 高度：4 /2分度為2的結(jié)點(diǎn)個(gè)數(shù)：2 /2分葉子結(jié)點(diǎn)個(gè)數(shù)：3 /2分5. 左子樹(shù)為空的結(jié)點(diǎn)：15, 23, 42, 44 /全對(duì)4分，否則不得分右子樹(shù)為空的結(jié)點(diǎn)：30 /2分6. 廣義表表示：30 (16 , 63 (34) )7. 插入結(jié)果和調(diào)整類(lèi)型為40 28 16 5

19、6 50 32 30 63無(wú) 無(wú) 右單旋 無(wú) 先右后左 先右后左 無(wú) 左單旋 雙旋轉(zhuǎn) 雙旋轉(zhuǎn)插入數(shù)據(jù)： 調(diào)整類(lèi)型： 8. 插入時(shí)伴隨旋轉(zhuǎn)調(diào)整的結(jié)點(diǎn)個(gè)數(shù)：4 /3分，若誤差1給1分，其余情況不得分插入不調(diào)整的結(jié)點(diǎn)個(gè)數(shù)：6 /3分，若誤差1給1分，其余情況不得分9. 左單旋轉(zhuǎn)結(jié)點(diǎn)個(gè)數(shù)：1 /1分右單旋轉(zhuǎn)結(jié)點(diǎn)個(gè)數(shù)：0 /1分先左后右雙旋轉(zhuǎn)結(jié)點(diǎn)個(gè)數(shù)：1 /1分先右后左雙旋轉(zhuǎn)結(jié)點(diǎn)個(gè)數(shù)：0 /1分不調(diào)整結(jié)點(diǎn)個(gè)數(shù)：6 /2分10. 度為2的結(jié)點(diǎn)個(gè)數(shù)：4 /2分度為1的結(jié)點(diǎn)個(gè)數(shù)：1 /2分度為0的結(jié)點(diǎn)個(gè)數(shù)：5 /2分五、算法分析題1. 已知二叉搜索樹(shù)中的結(jié)點(diǎn)類(lèi)型用BinTreeNode表示，被定義為: str

20、uct BinTreeNode ElemType data;BinTreeNode *leftChild, *rightChild; ;其中data為結(jié)點(diǎn)值域，leftChild和rightChild分別為指向左、右子女結(jié)點(diǎn)的指針域。假定具有BinTreeNode*類(lèi)型的指針參數(shù)BST指向一棵二叉搜索樹(shù)的根結(jié)點(diǎn)，試根據(jù)下面的函數(shù)定義指出此算法所能實(shí)現(xiàn)的功能。ElemType unknown ( BinTreeNode* BST ) if ( BST = NULL ) cerr << "此樹(shù)為空樹(shù)" << endl; exit (1); BinTree

21、Node* t = BST;while ( t->rightChild != NULL ) t = t->rightChild;return t->data; 算法功能：_2. 假定p1和p2是兩個(gè)有序單鏈表的表頭指針，用來(lái)表示兩個(gè)集合，單鏈表中的結(jié)點(diǎn)包括值域data和指向后繼結(jié)點(diǎn)的指針域link，試根據(jù)下面算法指出算法功能。LinkNode* unknown ( LinkNode* p1, LinkNode* p2 ) LinkNode* p3 = new LinkNode, * p = p3;while ( p1 != NULL && p2 != NULL

22、 ) LinkNode* newptr = new LinkNode; if ( p1->data < p2->data ) newptr->data = p1->data; p1 = p1->link; else if ( p1->data > p2->data ) newptr->data = p2->data; p2 = p2->link; else newptr->data = p1->data; p1 = p1->link; p2 = p2->link; p3->link = new

23、ptr; p3 = newptr;if ( p2 != NULL ) p1 = p2;while (p1 != NULL ) p3 = p3->link = new LinkNode; p3->data = p1->data; p1 = p1->link; p3->link = NULL; return p->link;算法功能：_3. 假定p1和p2是兩個(gè)單鏈表的表頭指針，用來(lái)表示兩個(gè)集合，單鏈表中的結(jié)點(diǎn)包括值域data和指向后繼結(jié)點(diǎn)的指針域link，試根據(jù)下面算法指出算法功能。int unknown ( LinkNode* p1, LinkNode* p

24、2 ) while ( p2 != NULL ) LinkNode* r = p1;while ( r != NULL ) if ( p2->data = r->data ) break; r = r->link;if ( r = NULL ) return 0;p2 = p2->link;return 1; 算法功能：_4. 假定HL為保存一個(gè)集合的有序單鏈表的表頭指針，item為一個(gè)新元素，HL單鏈表中的結(jié)點(diǎn)包括值域data和指向后繼結(jié)點(diǎn)的指針域link，試根據(jù)下面算法指出算法功能。void unknown ( LinkNode *& HL, const E

25、lemType& item ) LinkNode* newptr; Newptr = new LinkNode; Newptr->data = item; if ( HL = NULL | item < HL->data ) newptr->link = HL; HL = newptr; return; LinkNode *cp, *ap; ap = HL; cp = HL->link;while (cp != NULL ) if ( item < cp->data ) break; ap = cp; cp = cp->link; new

26、ptr->link = cp; ap->link = newptr;算法功能：_5. 已知二叉搜索樹(shù)中的結(jié)點(diǎn)類(lèi)型用BinTreeNode表示，被定義為: struct BinTreeNode ElemType data;BinTreeNode *leftChild, *rightChild; ;其中data為結(jié)點(diǎn)值域，leftChild和rightChild分別為指向左、右子女結(jié)點(diǎn)的指針域。假定pt所指向的二叉搜索樹(shù)的廣義表表示為: 25 (10 (5, 16 (12) ), 40 (32 ( , 38) ) )，按照下面算法，則： (1) 執(zhí)行unknown ( pt, 40 )

27、 調(diào)用后返回的值為_(kāi)。 (2) 執(zhí)行unknown ( pt, 38 ) 調(diào)用后返回的值為_(kāi)。 (1) 執(zhí)行unknown ( pt, 5 ) 調(diào)用后返回的值為_(kāi)。 (1) 執(zhí)行unknown ( pt, 60 ) 調(diào)用后返回的值為_(kāi)。 int unknown ( BinTreeNode* t, ElemType x ) if ( t = NULL ) return 0; else if ( t->data = x ) return 1;else if ( t->data > x ) return 1+unknown ( t->leftChild, x );elsere

28、turn 1+unknown ( t->rightChild, x );6. 已知二叉樹(shù)中的結(jié)點(diǎn)類(lèi)型用BinTreeNode表示，被定義為: struct BinTreeNode ElemType data;BinTreeNode *leftChild, *rightChild; ;其中data為結(jié)點(diǎn)值域，leftChild和rightChild分別為指向左、右子女結(jié)點(diǎn)的指針域。假定具有BinTreeNode * 類(lèi)型的指針參數(shù)bt指向一棵二叉樹(shù)的根結(jié)點(diǎn)，引用參數(shù)x初始具有最小值（即小于樹(shù)中所有結(jié)點(diǎn)的值），試根據(jù)下面的函數(shù)定義指出此算法所能實(shí)現(xiàn)的功能。 int unknown ( Bin

29、TreeNode* bt, ElemType& x ) if ( bt = NULL ) return 1;else if (unknown ( bt->leftChild, x ) = 0 ) return 0; if ( bt->data < x ) return 0; x = bt->data;if (unknown ( bt->rightChild, x ) = 0 ) return 0; else return 1; 算法功能：_參考答案： 1. 算法功能：從二叉搜索樹(shù)BST中查找出具有最大值的結(jié)點(diǎn)并返回這個(gè)值。2. 算法功能：實(shí)現(xiàn)集合的并運(yùn)算，

30、即把有序單鏈表表示的兩個(gè)集合合并為一個(gè)新的集合，并由函數(shù)返回新集合的表頭指針。3. 算法功能：判斷p2單鏈表所代表的集合是否為p1單鏈表所代表的集合的子集合，若是則返回1否則返回0。4. 算法功能：向表示集合的有序單鏈表HL中插入一個(gè)新元素，使得插入后仍然保持集合單鏈表有序。5. (1) 2 /2分(2) 4 /2分(3) 3 /2分(4) 0 /2分6. 算法功能：判斷二叉樹(shù)bt是否為一棵二叉搜索樹(shù)，若是則返回1否則返回0。六、算法設(shè)計(jì)題1. 假定元素類(lèi)型為ElemType的一維數(shù)組Rn 中保存著按關(guān)鍵碼升序排列的n個(gè)對(duì)象，對(duì)象的關(guān)鍵碼域key的類(lèi)型為KeyType，試按照下面的函數(shù)聲明編寫(xiě)

31、一個(gè)非遞歸算法，從一維數(shù)組Rn中用折半搜索法找出關(guān)鍵碼等于k的對(duì)象，若搜索成功則返回對(duì)象位置（即元素下標(biāo)），否則返回-1。 int BinSearch ( ElemType R , int n, KeyType k );2. 已知二叉搜索樹(shù)中的結(jié)點(diǎn)類(lèi)型用BinTreeNode表示，被定義為: struct BinTreeNode ElemType data;BinTreeNode *leftChild, *rightChild; ;其中data為結(jié)點(diǎn)值域，leftChild和rightChild分別為指向左、右子女結(jié)點(diǎn)的指針域。假定具有BinTreeNode * 類(lèi)型的指針參數(shù)BST指向一棵二

32、叉搜索樹(shù)的根結(jié)點(diǎn)，試根據(jù)下面的函數(shù)聲明編寫(xiě)一個(gè)非遞歸算法，從BST樹(shù)中查找出具有x參數(shù)值的結(jié)點(diǎn)，若查找成功則返回該結(jié)點(diǎn)的地址，否則返回NULL。 BinTreeNode* Find ( BinTreeNode* BST, ElemType& x );3. 已知二叉搜索樹(shù)中的結(jié)點(diǎn)類(lèi)型用BinTreeNode表示，被定義為: struct BinTreeNode ElemType data;BinTreeNode *leftChild, *rightChild; ;其中data為結(jié)點(diǎn)值域，leftChild和rightChild分別為指向左、右子女結(jié)點(diǎn)的指針域。假定具有BinTreeNod

33、e * 類(lèi)型的指針參數(shù)BST指向一棵二叉搜索樹(shù)的根結(jié)點(diǎn)，試根據(jù)下面的函數(shù)聲明編寫(xiě)一個(gè)遞歸算法，向BST樹(shù)中插入值為x的結(jié)點(diǎn)，若樹(shù)中不存在x結(jié)點(diǎn)則進(jìn)行插入并返回1表示插入成功，若樹(shù)中已存在x結(jié)點(diǎn)則不插入并返回0表示插入失敗。 int Insert ( BinTreeNode *& BST, const ElemType& x );4. 已知二叉搜索樹(shù)中的結(jié)點(diǎn)類(lèi)型用BinTreeNode表示，被定義為: struct BinTreeNode ElemType data;BinTreeNode *leftChild, *rightChild; ;其中data為結(jié)點(diǎn)值域，leftChi

34、ld和rightChild分別為指向左、右子女結(jié)點(diǎn)的指針域。假定具有BinTreeNode * 類(lèi)型的指針參數(shù)BST指向一棵二叉搜索樹(shù)的根結(jié)點(diǎn)，試根據(jù)下面的函數(shù)聲明編寫(xiě)一個(gè)非遞歸算法，向BST樹(shù)中插入值為x的結(jié)點(diǎn)，若樹(shù)中不存在x結(jié)點(diǎn)則進(jìn)行插入并返回1表示插入成功，若樹(shù)中已存在x結(jié)點(diǎn)則不插入并返回0表示插入失敗。 int insert ( BinTreeNode*& BST, const ElemType& x );參考答案：1. 算法如下：int BinSearch ( ElemType R , int n, KeyType k ) int low = 0, high = n-1; /賦初值2分while ( low <= high ) /循環(huán)條件1分int mid = (low + high) / 2;/中點(diǎn)位置1分 if ( k = Rmid.key ) return mid;/成功返回1分 else if ( k < Rmid.key) high = mid-1;/向左半?yún)^(qū)查找1分else low = mid+1;/向右半?yún)^(qū)查找1分 return -1; /失敗返回1分2. 算法如下：BinT