可編輯的第9章I.單選問題1.通過（）查找并遍歷二叉搜索樹以獲取節點值從小到大的排列順序. A.預定B.中間C.預定D.級別2.當從具有n個節點的二叉搜索樹中查找元素時，平均時間復雜度大約為（）. A. O（n）B. O（1）C. O（logn）D. O（n2）3.當從具有n個節點的二叉搜索樹中查找元素時，最壞情況的時間是（） . A. O（n）B. O（1）C. O（logn）D. O（n2）4.在二叉搜索樹中插入節點的時間復雜度為（）. A. O（1）B. O（n）C. O（logn）D. O（n2）5.用以下序列構造一個二叉搜索樹，該樹不同于用其他三個序列構造的結果（） . 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、80、60、90、120、130、110）6.在AVL樹中，每個節點的平衡因子的值范圍為（）. A.-1？1 B.-2？2 C.1？2 D.0？17. 根據一組關鍵字（56、42、50、64、48），當插入具有值（）的節點時需要旋轉調整時，依次插入節點以生成AVL樹.

A. 42 B. 50 C. 64 D. 488.深度為4的AVL樹至少具有（）個節點. A. 9 B. 8 C. 7 D. 69.深度為k的AVL樹的每個分支節點的平衡因子為0，那么平衡的二叉樹總共有（）個節點. A.2k-1-1 B.2k-1 + 1 C.2k-1 D.2k10. 在AVL樹中插入一個節點會導致不平衡，將最低不平衡節點設置為A，并且已知A的左孩子的平衡因子為0，而右孩子的平衡因子為1，則應進行（）類型調整以使其平衡. A. LL 2.判斷詞的完美格式B. LRC. RLD. RR可編輯版本1.在二分搜索樹的任何子樹中，關鍵字最小的節點必須沒有左子節點，關鍵字最大的節點必須沒有右子節點. 2.二叉搜索樹中每個節點的鍵值大于其左非空子樹（如果存在）中所有節點的鍵值，小于其右非空子樹中所有節點的鍵值子樹（如果存在）關鍵字值. 3.以中間順序遍歷二叉搜索樹以打印出節點并打印出節點，并且排列從小到大. 4. 5. 6. 7. 8. 9.如果二進制搜索樹的根節點沒有左子節點，則該根節點必須是值最小的節點. 二進制搜索樹必須充滿二進制樹.

從二叉搜索樹的根節點一直到右子為止，可能找不到樹中值最大的節點. 二叉搜索樹的充分必要條件是任何節點的值都大于其左子節點的值，并且小于其右子節點的值. 如果二進制搜索樹中的關鍵字代碼彼此不同，則最小元素和最大元素必須是葉節點. 在任何非空二進制搜索樹中，刪除節點并將其插入后，生成的二進制搜索樹與原始二進制搜索樹相同. 10.將節點插入二叉搜索樹時，該節點必須成為葉節點. 11. AVL樹是指左子樹和右子樹之間的高度差不大于1的二叉樹. 12. AVL是二叉樹，并且樹上任何節點的平衡因子的絕對值都不大于大于1. 13.在AVL樹中，將新節點插入平衡因子不為零的節點的樹中將不可避免地導致平衡旋轉. 3.填寫空白的問題1. 2.遍歷二叉搜索樹后，關鍵字序列是一個有序列表. 通過構造_______，可以將無序序列轉換為有序序列. 構造樹的過程是對無序序列進行排序的過程. 3.在二叉搜索樹中，每個分支節點左子樹上所有節點的值必須是________節點的值，而右子樹上所有節點的值必須是________ Node. 4.當從二叉搜索樹中查找元素時，如果該元素的值等于根節點的值二叉排序樹 構造，則表示_______，如果該元素的值小于根節點的值，則繼續搜索________，如果元素的值大于根節點的值，則繼續搜索________.

5. 將元素插入二叉搜索樹時，如果元素的值小于根節點的值，則將其插入到根節點________，如果元素的值大于根節點的Value，則插入到根節點________. 6.基于n個元素構建二進制搜索樹的時間復雜度大約為________. Word完美格式可編輯版本7. 8. 9.二叉樹中節點左子樹的深度減去右子樹的深度稱為該節點的_______. 深度為4的平衡二叉樹至少具有節點，最多具有節點. 在AVL樹中，每個節點的左子樹的高度和右子樹的高度之差的絕對值不超過________. 4.應用問題1.二進制搜索樹的結構如下圖所示. 節點的值是1到8. 請標記每個節點的值. 2.如果按順序{62,68,30,61,25,14,53,47,90,84}順序輸入元素，則會生成二叉搜索樹. 繪制生成的二進制搜索樹（繪制生成過程）. 3.依次讀取給定的整數序列{7,16,4,8,20,9,6,18,5}，構建二叉搜索樹，并以等概率計算二叉搜索樹ASL的平均搜索長度. （需要構建過程）4.從一棵空的二叉樹開始，嚴格遵循二叉搜索樹的插入算法（無平衡旋轉），將關鍵碼一一插入{18，73，10，5，68， 99、27、41、51、32、25}構造一個二叉搜索樹，繪制該二叉搜索樹并編寫其前后遍歷序列.

5. 如果二叉搜索樹的關鍵字輸入順序為{80，6，10，7，8，25，100，90}，請繪制二叉搜索樹. 6.將一組初始記錄關鍵字設置為（45、80、48、40、22、78），要求構造一個二分搜索樹并給出構造過程. 7.假設關鍵字序列為（38、52、25、74、68、16、30、54、90、72），繪制按序列中元素順序生成的二叉搜索樹，并找到其平均值搜索長度. 8.將序列中的每個元素（24、15、38、27、121、76、130）依次插入到最初為空的二進制搜索樹中，請繪制最終結果并以相等的概率找到成功. . 9.輸入一個正整數序列{40，28，6，72，100，3，54二叉排序樹 構造，1，1，80，91，38}來構建一個二叉搜索樹，然后刪除節點72并分別繪制二叉樹并刪除在節點72之后是二叉樹. 10.根據元素插入的順序，它可以形成各種形式的二叉搜索樹. 繪制4個具有1、2、3和4元素以及根1和深度3的二進制搜索樹. WordPerfect Format 11的可編輯版本. 從下面的二進制搜索樹中刪除鍵碼40后，請繪制結果. 20 11 6 24 35 3 8 28 45 60 405012. 對于關鍵字序列（25，16，34，39，28，56），1）繪制根據該序列生成的二叉搜索樹.

2）計算以相等概率成功搜索時的平均搜索長度. 13.輸入一個正整數序列（53、17、12、66、58、70、87、25、56、60），然后嘗試完成以下問題. （1）按順序構造二分搜索樹BS. （2）根據該二叉搜索樹，如何從大到小獲得有序序列？ （3）假設每個元素的搜索概率相等，請嘗試計算二叉搜索樹的平均搜索長度. （4）在二進制搜索樹中刪除“ 66”后，繪制樹結構. 14.嘗試導出深度為5的平衡二叉樹中的最小節點數，并繪制這樣的樹. 15.在最初為空的AVL樹中依次插入3、1、4、6、9、8、5、7后，繪制AVL樹的形狀. 如果進行旋轉，則指示旋轉類型. 16.給定關鍵字序列4、5、7、2、1、3、6，生成AVL樹并繪制構造過程. 17.給定關鍵字序列4、5、7、2、1、3、6，分別生成二叉搜索樹和AVL樹，并使用兩種方法: 二叉搜索樹和AVL樹進行搜索，并給出搜索6成功搜索的次數和平均搜索長度. 18.給定關鍵字輸入序列{CAP，AQU，PIS，ARI，TAU，GEM，CAN，LIB，VIR，LEO，SCO}，假設關鍵字以英語字典順序進行比較，請嘗試從一棵空樹中提取出來，按從上到下的順序輸入關鍵字，使用AVL樹的插入算法生成AVL樹，并說明在生成過程中使用了哪種旋轉方法來調整余額，并標記樹中的每個節點平衡因子.

請參閱答案1. 1-5. BCABC 2. 1-5. √√√√×6-10. ××××√11-13. √√×Word完美格式6-10. ABCCC可編輯版本三，1. 2. 3. 4. 5. 6. 7. 8. 9.四，1.中階二進制搜索樹小于，大于搜索成功，左子樹，右子樹，左子樹，右子樹O（n2）平衡因子7、15 12.3. ASL =（1 + 2 * 2 + 3 * 3 + 4 * 3）/ 9 = 26/9 = 2.89Word完美格式可編輯版本4.序言: 18 10 5 73 68 27 25 41 32 51 99后置訂單: 5 10 25 32 51 41 27 68 99 73 18 5.6.7. 如圖所示，平均搜索長度等于32/10. 8.平均搜索長度= 1 + 2×2 + 3×2 + 4×2 = 19/7. Word完美格式可編輯版本9.二進制搜索樹刪除二進制搜索樹10.72. 或12. （1）（2）（1 + 2 * 2 + 3 * 2 + 4 * 1）/ 6 = 2.5 13.（1）二進制搜索樹的結構為: （4）Word的可編輯版本刪除節點66后的理想格式（2）對于二叉搜索樹，如果要獲取從大到小的序列，請先讀取正確的子節點. 樹再次讀取根節點，最后讀取該二叉樹的遍歷從左側的子樹開始.

如果要從小到大的順序，則只需要以中間順序遍歷二叉樹即可. （3）二叉樹的平均搜索長度為: ASL =（1 * 1 + 2 * 2 + 3 * 4 + 4 * 3）/10=2.9 14.省略15.16. Word完美格式可編輯版本17.二進制搜索樹AVL樹需要4次從二進制搜索樹中搜索6，并且平均搜索長度ASL =（1 + 2 + 2 + 3 + 3 + 3 + 4）/ 7 = 18 /7≈2.57. 從平衡二叉樹中找到6需要2次，平均搜索長度ASL =（1 + 2 + 2 + 3 + 3 + 3 + 3）= 17 /7≈2.43. 18. Word完美格式的單向左手先右手再左手多年的金融工作實踐的可編輯版本為我提供了一個巨大的階段，可以提高我觀察問題，分析問題，處理問題的能力，以便我的業務水平和工作能力取得了長足的進步，但我也清楚地意識到我的工作仍然存在許多不足. 今后，我將更加注重學習，努力克服工作中遇到的困難. 我將進一步提高我的職業道德和商業知識. 以及組織管理水平，為縣域交通發展做出新貢獻. Word完美格式

本文來自本站，轉載請注明本文網址：
http://www.pc-fly.com/a/jisuanjixue/article-246508-1.html