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

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

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

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

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

5、C. 1 2D. 0115. 向一棵AVL樹(高度平衡的二叉搜索樹)插入元素時，可能引起對最小不平衡子樹的調(diào)整過程，此調(diào) 整分為()種旋轉(zhuǎn)類型。A. 2B. 3C. 4D. 516. 向一棵AVL樹(高度平衡的二叉搜索樹)插入元素時，可能引起對最小不平衡子樹的左單或右單旋轉(zhuǎn)的調(diào)整過程，此時需要修改相關(guān)()個結(jié)點指針域的值。A. 2B. 3C. 4D. 517. 向一棵AVL樹(高度平衡的二叉搜索樹)插入元素時，可能引起對最小不平衡子樹的雙向旋轉(zhuǎn)的調(diào)整過程，此時需要修改相關(guān)()個結(jié)點指針域的值。A. 2B. 3C. 4D. 5參考答案：1. D2. C3. A4. B5. A6. B7. C8.

6、 A9. D10. D11. C12. A13. B14. A15. C16. A17. C、填空題1 .以順序搜索方法從長度為n的順序表或單鏈表中搜索一個元素時，其時間復(fù)雜度為 。2 .對長度為n的搜索表進(jìn)行搜索時，假定搜索第i個元素的I率為 pi,搜索長度(即在搜索過程中依次同有關(guān)元素比較的總次數(shù))為Ci,則在搜索成功情況下的平均搜索長度的計算公式為 。3 .假定一個順序表的長度為40,并假定搜索每個元素的概率都相同，則在搜索成功情況下的平均搜索長度為。4 .以折半搜索方法從長度為n的有序表中搜索一個元素時，時間復(fù)雜度為 。5 .從有序表(12,18, 30, 43, 56, 78, 82

7、, 95)中折半搜索元素 56時，其搜索長度為 。6 .假定對長度n = 50的有序表進(jìn)行折半搜索，則對應(yīng)的判定樹中最后一層的結(jié)點數(shù)為 個。7 .從一棵二叉搜索樹中搜索一個元素時，若給定值小于根結(jié)點的值，則需要向 繼續(xù)搜索。8 .從一棵二叉搜索樹中搜索一個元素時，若給定值大于根結(jié)點的值，則需要向 繼續(xù)搜索。9 .向一棵二叉搜索樹中插入一個新元素時，若該新元素的值小于根結(jié)點的值，則應(yīng)把它插入到根結(jié)點的上。10 .向一棵二叉搜索樹中插入一個新元素時，若該新元素的值大于根結(jié)點的值，則應(yīng)把它插入到根結(jié)點的 上。11 .向一棵二叉搜索樹 一個元素時，若查找到的根結(jié)點為空值，則應(yīng)把該元素結(jié)點鏈接到這個空

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

9、平衡的二叉搜索樹）時，當(dāng) 插入到值為38的結(jié)點時需要進(jìn)行 調(diào)整。17 .根據(jù)一組記錄（56, 42, 73, 50, 64, 48, 22 ）依次插入結(jié)點生成一棵 AVL樹（高度平衡的二叉搜索樹） 時，當(dāng)插入到值為 的結(jié)點時才出現(xiàn)不平衡，需要進(jìn)行旋轉(zhuǎn)調(diào)整。18 .在一棵AVL樹（高度平衡的二叉搜索樹）上進(jìn)行插入或刪除元素時，所需的時間復(fù)雜度為n 13. 20.57.左子樹11.插入15.先右后左雙旋轉(zhuǎn)4. O(log 2n)8.右子樹12. O(nlog 2n)16.右單旋轉(zhuǎn)參考答案： 1. O(n)2.picii 05. 36. 199.左子樹10.右子樹13. 114. 5017. 481

10、8. O(lon2n)三、判斷題1 .在順序表中進(jìn)行順序搜索時，若各元素的搜索概率不等，則各元素應(yīng)按照搜索概率的降序排列存放, 則可得到最小的平均搜索長度。2 .進(jìn)行折半搜索的表必須是順序存儲的有序表。3 .能夠在鏈接存儲的有序表上進(jìn)行折半搜索，其時間復(fù)雜度與在順序存儲的有序表上相同。4 .假定用兩個有序單鏈表表示兩個集合，則這兩個集合交運算得到的集合單鏈表，其長度小于參加運算 的任一個集合單鏈表的長度。5 .假定用兩個有序單鏈表表示兩個集合，則這兩個集合的差運算得到的集合單鏈表，其長度小于參加運 算的任一個集合單鏈表的長度。6 .折半搜索所對應(yīng)的判定樹，既是一棵二叉搜索樹，又是一棵理想平衡二

11、叉樹(它的特點是除最底層結(jié) 點外其他各層結(jié)點數(shù)都是滿的，最底層的若干結(jié)點可能散布在該層各處)。7 .對二叉搜索樹進(jìn)行前序遍歷得到的結(jié)點序列是一個有序序列。8 .在由n個元素組成的有序表上進(jìn)行折半搜索時，對任一個元素進(jìn)行搜索的長度(即比較次數(shù))都不會 大于 log 2n+1。9 .根據(jù)n個元素建立一棵二叉搜索樹的時間復(fù)雜度大致為O(log2n)。10 .根據(jù)n個元素建立一棵二叉搜索樹的時間復(fù)雜度大致為O(nlog2n)。11 .對于同一組記錄，若生成二叉搜索樹時插入記錄的次序不同則得到不同結(jié)構(gòu)的二叉搜索樹。12 .對于同一組記錄，生成二叉搜索樹的結(jié)構(gòu)與插入記錄的次序無關(guān)。13 .對于兩棵具有相同

12、記錄集合而具有不同結(jié)構(gòu)的二叉搜索樹，按中序遍歷得到的結(jié)點序列是相同的。14 .在二叉搜索樹中，若各結(jié)點的搜索概率不等，使得搜索概率越大的結(jié)點離樹根越近，則得到的是最優(yōu) 二叉搜索樹。15 .在二叉搜索樹中，若各結(jié)點的搜索概率不等，使得搜索概率越小的結(jié)點離樹根越近，則得到的是最優(yōu) 二叉搜索樹。參考答案：1.是2.是3.否4.是5.否6.是7.否8.是9.否10.是11.是12.否13.是14.是15.否四、運算題1. 一個一維數(shù)組a10中存儲著一個有序表，該有序表為：(15, 26, 34, 39, 45, 56, 58, 63, 74, 76 ),根據(jù)折半搜索所對應(yīng)的判定樹，寫出該判定樹的廣義表

13、表示，并求出在等概率情況下搜索成功的平均搜索長度。判定樹的廣義表表示：平均搜索長度：2.已知一個有序表 ( 15,26,34,39,45,56,58,63,74,76,83,94)順序存儲于一維數(shù)組 a12中，根據(jù)折半 搜索過程填寫成功搜索下表中所給元素34, 56, 58, 63, 94時的比較次數(shù)。3456586394元素值比較次數(shù)3.假定一個線T曲序列為(38, 52, 25, 74, 68, 16, 30, 54, 90, 72 ),根據(jù)此線性序列中元素的排列次序生成一棵二叉搜索樹，求出對該二叉搜索樹查找38, 74, 68, 30, 72等元素時的比較次數(shù)。3874683072待查元

14、素: 比較次數(shù):4.假定一個線T曲序列為(56, 27, 34, 95, 73, 16, 50, 62, 65 ),根據(jù)此線性序列中元素的排列次序生成一棵0)、度為2的結(jié)點個數(shù)和葉子結(jié)點個二叉搜索樹，求出該二叉搜索樹的高度(假定樹根結(jié)點的高度為高度：度為2的結(jié)點個數(shù)：葉子結(jié)點個數(shù)：5.假定一個線T曲序列為(38, 42, 55, 15, 23, 44, 30, 74, 48, 26),根據(jù)此線性序列中元素的排列次序生成一棵二叉搜索樹，求出該二叉搜索樹中左子樹為空的所有單支結(jié)點和右子樹為空的所有單支結(jié)點，請按 從小到大的次序排列寫出。左子樹為空的所有結(jié)點： 右子樹為空的所有結(jié)點：6.已知一棵二叉

15、搜索樹的廣義表表示為：28 (12 (,16),49 (34 (30), 72 (63),按主教材介紹的刪除算法,求出從中依次刪除72, 12, 49, 28結(jié)點后得到的二叉搜索樹的廣義表表示。廣義表表示：7.假定一組數(shù)據(jù)對象為 (40, 28, 16, 56, 50, 32, 30, 63 ),按次序插入每個對象生成一棵AVL樹(高度平衡的二叉搜索樹)，根據(jù)插入過程填寫下表，在相應(yīng)位置填寫所需要的調(diào)整類型：“左單旋轉(zhuǎn)”、“右單旋轉(zhuǎn)”、“先左后右雙旋轉(zhuǎn)”、“先右后左雙旋轉(zhuǎn)”，若不需要旋轉(zhuǎn)則填寫“無”。4028165650323063數(shù)據(jù): 調(diào)整:8.假定一組數(shù)據(jù)對象為(40, 28, 16,

16、56, 50, 32, 30, 63, 44, 38 ),按次序插入每個對象生成一棵AVL樹(高度平衡的二叉搜索樹)，請回答插入后需調(diào)整的結(jié)點個數(shù)和插入后不調(diào)整的結(jié)點個數(shù)。插入時伴隨旋轉(zhuǎn)調(diào)整的結(jié)點個數(shù)： 插入不調(diào)整的結(jié)點個數(shù)：9 .假定一組記錄為(36, 75, 83, 54, 12, 67, 60, 40 ),按次序插入每個結(jié)點生成一棵AVL樹(高度平衡的二叉搜索樹)，請回答在插入時需進(jìn)行“左單旋轉(zhuǎn)”、“右單旋轉(zhuǎn)”、“先左后右雙旋轉(zhuǎn)”、“先右后左雙旋 轉(zhuǎn)”，“不調(diào)整”的結(jié)點數(shù)各是多少？左單旋轉(zhuǎn)結(jié)點個數(shù)：右單旋轉(zhuǎn)結(jié)點個數(shù)：先左后右雙旋轉(zhuǎn)結(jié)點個數(shù)： 先右后左雙旋轉(zhuǎn)結(jié)點個數(shù)： 不調(diào)整結(jié)點個數(shù)：10

17、 .假定一組記錄為 (38, 42, 55, 15, 23, 44, 30, 74, 48, 26 ),按次序插入每個結(jié)點生成一棵AVL樹(高度平衡的二叉搜索樹)，給出最后得到的 AVL樹中度為2、度為1和度為0的結(jié)點個數(shù)。度為2的結(jié)點個數(shù)：度為1的結(jié)點個數(shù)：度為0的結(jié)點個數(shù)：參考答案：/4分/2分1.判定樹的廣義表表示：45 (26 (15, 34 ( , 39 ) ), 63 ( 56 ( , 58 ), 74 ( , 76 )平均查找長度：29/102.3.判斷結(jié)果 元素值比較次數(shù)判斷結(jié)果 待查元素：比較次數(shù)：3456586394021344/對1個名1分，全對給6分3874683072

18、013435/對1個名1分，全對給6分歡迎下載14/2分/2分/2分/全又4分，否則不得分/2分4 .高度：4度為2的結(jié)點個數(shù)：2葉子結(jié)點個數(shù)：35 . 左子樹為空的結(jié)點：15, 23, 42, 44右子樹為空的結(jié)點：306 . 廣義表表示：30 (16,63 (34)7 .插入結(jié)果和調(diào)整類型為插入數(shù)據(jù)： 調(diào)整類型：4028165650323063無無右單旋無先右后左 雙旋轉(zhuǎn)先右后左 雙旋轉(zhuǎn)無左單旋8 .插入時伴隨旋轉(zhuǎn)調(diào)整的結(jié)點個數(shù)：4插入不調(diào)整的結(jié)點個數(shù)：69 .左單旋轉(zhuǎn)結(jié)點個數(shù)：1右單旋轉(zhuǎn)結(jié)點個數(shù)：0先左后右雙旋轉(zhuǎn)結(jié)點個數(shù)：1先右后左雙旋轉(zhuǎn)結(jié)點個數(shù)：0不調(diào)整結(jié)點個數(shù)：610 .度為2的結(jié)點

19、個數(shù)：4度為1的結(jié)點個數(shù)：1度為0的結(jié)點個數(shù)：5/3分，若誤差1給1分，其余情況不得分/3分，若誤差1給1分，其余情況不得分/1分/1分/1分/1分/2分/2分/2分/2分五、算法分析題1 .已知二叉搜索樹中的結(jié)點類型用BinTreeNode表示，被定義為：struct BinTreeNode ElemType data; BinTreeNode *leftChild , *rightChild ; ;其中data為結(jié)點值域，leftChild和rightChild分別為指向左、右子女結(jié)點的指針域。假定具有 BinTreeNode*類型的指針參數(shù) BST指向一棵二叉搜索樹的根結(jié)點，試根據(jù)下面的

20、函數(shù)定義指出此算法所能實現(xiàn)的功能。ElemType unknown ( BinTreeNode* BST ) if ( BST = NULL ) cerr << ”此樹為空樹"<< endl; exit (1); BinTreeNode* t = BST ;while (t-> rightChild != NULL ) t = t -> rightChild ; return t-> data;算法功能：2 .假定p1和p2是兩個有序單鏈表的表頭指針，用來表示兩個集合，單鏈表中的結(jié)點包括值域data和指向后繼結(jié)點的指針域link，試根據(jù)下面算

21、法指出算法功能。LinkNode* unknown ( LinkNode* p1 , LinkNode* p2 ) LinkNode* p3 = new LinkNode , * p = p3 ;while ( p1 != NULL && p2 != NULL ) LinkNode* newptr = new LinkNode ;if ( p1 -> data < p2-> data ) newptr-> data = p1-> data; p1 = p1 -> link; else if ( p1-> data > p2->

22、; data ) newptr-> data = p2-> data; p2 = p2-> link; else newptr-> data = p1-> data; pl = pl -> link ; p2 = p2-> link; p3-> link = newptr ; p3 = newptr; if ( p2 != NULL ) pl = p2 ;while (p1 != NULL ) p3 = p3-> link = new LinkNode ;p3->data = p1->data; p1 = p1 -> li

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

24、) return 0;p2 = p2-> link ; return 1;算法功能：4 .假定HL為保存一個集合的有序單鏈表的表頭指針，item為一個新元素，HL單鏈表中的結(jié)點包括值域data和指向后繼結(jié)點的指針域link,試根據(jù)下面算法指出算法功能。void unknown ( LinkNode * & HL, const ElemType& item ) LinkNode* newptr ;Newptr = new LinkNode ;Newptr -> data = item;if ( HL = NULL | item < HL -> data )

25、 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;newptr-> link = cp ;ap-> link = newptr ;算法功能：5 .已知二叉搜索樹中的結(jié)點類型用BinTreeNode表示，被定義為：struct BinTreeNode ElemType data; BinTreeN

26、ode *leftChild, *rightChild ; ;其中data為結(jié)點值域，leftChild和rightChild分別為指向左、右子女結(jié)點的指針域。假定pt所指向的二叉搜索樹的廣義表表示為：25 (10 (5,16 (12) ), 40 (32 ( , 38),按照下面算法，則：(1)執(zhí)行unknown ( pt, 40 )調(diào)用后返回的值為 。(2)執(zhí)行unknown ( pt, 38 )調(diào)用后返回的值為 。(1)執(zhí)行unknown ( pt, 5 )調(diào)用后返回的值為 。(1)執(zhí)行unknown ( pt, 60 )調(diào)用后返回的值為 。int unknown ( BinTreeNo

27、de* 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 );elsereturn 1+unknown ( t -> rightChild , x );6 .已知二叉樹中的結(jié)點類型用BinTreeNode表示，被定義為：struct BinTreeNode ElemType data; BinTreeNode *leftChild , *ri

28、ghtChild ; ;其中data為結(jié)點值域，leftChild和rightChild分別為指向左、右子女結(jié)點的指針域。假定具有 BinTreeNode *類型的指針參數(shù) bt指向一棵二叉樹的根結(jié)點，引用參數(shù)x初始具有最小值(即小于樹中所有結(jié)點的值)，試根據(jù)下面的函數(shù)定義指出此算法所能實現(xiàn)的功能。int unknown ( BinTreeNode* bt , ElemType & x ) if ( bt = NULL ) return 1;else if (unknown ( bt -> leftChild, x ) = 0 ) return 0;if ( bt-> da

29、ta < x ) return 0;x = bt-> data;if (unknown ( bt -> rightChild, x ) = 0 ) return 0;else return 1;算法功能：參考答案：1 .算法功能：從二叉搜索樹BST中查找出具有最大值的結(jié)點并返回這個值。2 .算法功能：實現(xiàn)集合的并運算，即把有序單鏈表表示的兩個集合合并為一個新的集合，并由函數(shù)返回 新集合的表頭指針。3 .算法功能：判斷p2單鏈表所代表的集合是否為pl單鏈表所代表的集合的子集合，若是則返回1否則返回0。4 .算法功能：向表示集合的有序單鏈表HL中插入一個新元素，使得插入后仍然保持

30、集合單鏈表有序。5 . (1) 22分(2) 4/2分3/2分(4) 0/2分6.算法功能：判斷二叉樹 bt是否為一棵二叉搜索樹，若是則返回1否則返回0。六、算法設(shè)計題1 .假定元素類型為 ElemType的一維數(shù)組Rn中保存著按關(guān)鍵碼升序排列的n個對象，對象的關(guān)鍵碼域key的類型為KeyType,試按照下面的函數(shù)聲明編寫一個非遞歸算法，從一維數(shù)組 Rn中用折半搜索 法找出關(guān)鍵碼等于 k的對象，若搜索成功則返回對象位置(即元素下標(biāo))，否則返回-1。int BinSearch ( ElemType R , int n, KeyType k );2 .已知二叉搜索樹中的結(jié)點類型用BinTreeNo

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

32、 .已知二叉搜索樹中的結(jié)點類型用BinTreeNode表示，被定義為：struct BinTreeNode ElemType data; BinTreeNode *leftChild , *rightChild ; ;其中data為結(jié)點值域，leftChild和rightChild分別為指向左、右子女結(jié)點的指針域。假定具有 BinTreeNode *類型的指針參數(shù)BST指向一棵二叉搜索樹的根結(jié)點，試根據(jù)下面的函數(shù)聲明編寫一個 遞歸算法，向BST樹中插入值為x的結(jié)點，若樹中不存在 x結(jié)點則進(jìn)行插入并返回1表示插入成功,若樹中已存在x結(jié)點則不插入并返回0表示插入失敗。int Insert ( Bi

33、nTreeNode * & BST, const ElemType& x );4 .已知二叉搜索樹中的結(jié)點類型用BinTreeNode表示，被定義為：struct BinTreeNode ElemType data; BinTreeNode *leftChild , *rightChild ; ;其中data為結(jié)點值域，leftChild和rightChild分別為指向左、右子女結(jié)點的指針域。假定具有 BinTreeNode *類型的指針參數(shù)BST指向一棵二叉搜索樹的根結(jié)點，試根據(jù)下面的函數(shù)聲明編寫一個 非遞歸算法，向BST樹中插入值為x的結(jié)點，若樹中不存在x結(jié)點則進(jìn)行插入并返

34、回1表示插入成功,若樹中已存在x結(jié)點則不插入并返回0表示插入失敗。int insert ( BinTreeNode* & BST, const ElemType& x );參考答案:1.算法如下：int BinSearch ( ElemType R , int n, KeyType k ) int low = 0 , high = n -1;while (low <= high ) int mid = (low + high) / 2 ;if ( k = Rmid.key ) return mid ;else if ( k < Rmid.key) high = mid -1;else low = mid+1 ;return -1;賦初值2分循環(huán)條件1分中點位置1分成功返回1分向左半?yún)^(qū)查找1分向右半?yún)^(qū)查找1分失敗返回1分循環(huán)條件1分成功返回2分向左孩子查找2分向右孩