1、-作者xxxx-日期xxxx數據結構查找習題及答案【精品文檔】第9章 查找一、單選題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

2、. 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. -11 B. -22 C. 12 D. 017. 根據一組關鍵字（56，42，50，64，48）依次插入結點生成一棵AVL樹，當插入到值為（）的結點時需要進行旋轉調整。A. 42B. 50C. 6

3、4D. 488. 深度為4的AVL樹至少有（）個結點。A9B. 8C. 7 D. 69. 一棵深度為k的AVL樹，其每個分支結點的平衡因子均為0，則該平衡二叉樹共有（）個結點。 k-1-1 k-1+1 k-1 k 10. 在AVL樹中插入一個結點后造成了不平衡，設最低的不平衡結點為A，并已知A的左孩子的平衡因子為0，右孩子的平衡因子為1，則應作（ ） 型調整以使其平衡。A. LL B. LR C. RL D. RR二、判斷題1. 二叉搜索樹的任意一棵子樹中，關鍵字最小的結點必無左孩子，關鍵字最大的結點必無右孩子。2. 二叉搜索樹中每個結點的關鍵字值大于其左非空子樹（若存在的話）所有結點的關鍵字

4、值，且小于其右非空子樹（若存在的話）所有結點的關鍵字值。3. 二叉搜索樹按照中序遍歷將各結點打印出將各結點打印出來，將得到按照由小到大的排列。4. 若二叉搜索樹的根結點沒有左兒子，則根結點一定是值最小的結點。5. 二叉搜索樹一定是滿二叉樹。6. 從二叉搜索樹的根結點一直沿右兒子向下找不一定能找到樹中值最大的結點。7. 二叉搜索樹的充要條件是任一結點的值均大于其左孩子的值，小于其右孩子的值。8. 若二叉搜索樹中關鍵碼互不相同，則其中最小元素和最大元素一定是葉子結點。9. 在任意一棵非空二叉搜索樹中，刪除某結點后又將其插入，則所得二叉搜索樹與原二叉搜索樹相同。10. 當向二叉搜索樹中插入一個結點，

5、則該結點一定成為葉子結點。11. AVL樹是指左右子樹的高度差的絕對值不大于1的二叉樹。12. AVL是一棵二叉樹，其樹上任一結點的平衡因子的絕對值不大于1。13. 在AVL樹中，向某個平衡因子不為零的結點的樹中插入一新結點，必引起平衡旋轉。三、填空題1. 在一棵二叉搜索樹上實施 遍歷后，其關鍵字序列是一個有序表。2. 一個無序序列可以通過構造一棵_而變成一個有序序列，構造樹的過程即為對無序序列進行排序的過程。3. 在一棵二叉搜索樹中，每個分支結點的左子樹上所有結點的值一定_該結點的值，右子樹上所有結點的值一定_該結點。4. 從一棵二叉搜索樹中查找一個元素時，若元素的值等于根結點的值，則表明_

6、，若元素的值小于根結點的值，則繼續向_查找，若元素的值大于根結點的值，則繼續向_查找。 5. 向一棵二叉搜索樹中插入一個元素時，若元素的值小于根結點的值，則接著向根結點的_插入，若元素的值大于根結點的值，則接著向根結點的_插入。6. 根據n個元素建立一棵二叉搜索樹的時間復雜度大致為_。 7. 二叉樹中某一結點左子樹的深度減去右子樹的深度稱為該結點的_。8. 深度為4的平衡二叉樹中至少有 個結點，至多有 個結點。9. 在一棵AVL樹中，每個結點的左子樹高度與右子樹高度之差的絕對值不超過_。 四、應用題1. 一棵二叉搜索樹的結構如下圖所示，結點的值為18，請標出各結點的值。2. 若依次輸入序列62

7、,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，

8、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, 80, 91, 38，建立一棵二叉搜索樹，然后刪除

9、結點72，分別畫出該二叉樹及刪除結點72后的二叉樹。10. 根據元素插入的先后次序不同，可構成多種形態的二叉搜索樹。請畫出4棵含1，2，3，4四個元素且以1為根、深度為3的二叉搜索樹。11. 請畫出從下面的二叉搜索樹中刪除關鍵碼40后的結果。12. 對關鍵字序列（25, 16, 34, 39, 28, 56），1）畫出按此序列生成的二叉搜索樹。2）計算等概率下查找成功時的平均查找長度。13. 輸入一個正整數序列（53, 17, 12, 66, 58, 70, 87, 25, 56, 60），試完成下列各題。(1)按次序構造一棵二叉搜索樹BS。(2)依此二叉搜索樹，如何得到一個從大到小的有序序列

10、？(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的查找次數及查找成

11、功的平均查找長度。18. 給定關鍵詞輸入序列CAP, AQU, PIS, ARI, TAU, GEM, CAN, LIB, VIR, LEO, SCO，假定關鍵詞比較按英文字典序，試畫出從一棵空樹開始，依上述順序（從左到右）輸入關鍵詞，用AVL樹的插入算法生成一棵AVL樹的過程，并說明生成過程中采用了何種轉動方式進行平衡調整，標出樹中各結點的平衡因子。參考答案一、1-5. BCABC6-10. ABCCC二、1-5. 6-10. 11-13. 三、1. 中序2. 二叉搜索樹3. 小于，大于4. 查找成功，左子樹，右子樹5. 左子樹，右子樹6. O(n2)7. 平衡因子8. 7, 159. 1四、1.2.3.4.前序：18 10 5 73 68 27 25 41 32 51 99后序：5 10 25 32 51 41 27 68 99 73 185.6.7. 二叉搜索樹如圖所示，平均查找長度等于32/10。8. 平均查找長度=1+22+32+42=19/7。9.二叉搜索樹刪除72后的二叉搜索樹10.11.或12. （1）（2）13. （1）構造的二叉搜索樹為： （4）刪除結點66后(2) 對于一個二叉搜索樹