數(shù)據(jù)結(jié)構(gòu)查找習(xí)題及答案

1、第9章 查找一、單選題1. 對一棵二叉搜索樹按（）遍歷，可得到結(jié)點值從小到大的排列序列。A. 先序B. 中序C. 后序D. 層次2. 從具有n個結(jié)點的二叉搜索樹中查找一個元素時，在平均情況下的時間復(fù)雜度大致為（）。A. O(n) B. O(1) C. O(logn) D. O(n2)3. 從具有n個結(jié)點的二叉搜索樹中查找一個元素時，在最壞情況下的時間復(fù)雜度為（）。A. O(n) B. O(1) C. O(logn) D. O(n2)4. 在二叉搜索樹中插入一個結(jié)點的時間復(fù)雜度為（）。A. O(1)B. O(n)C. O(logn)D. O(n2)5. 分別以下列序列構(gòu)造二叉搜索樹，與用其它三個

2、序列所構(gòu)造的結(jié)果不同的是（）。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樹中，每個結(jié)點的平衡因子的取值范圍是（）。A. -11 B. -22 C. 12 D. 017. 根據(jù)一組關(guān)鍵字（56，42，50，64，48）依次插入結(jié)點生成一棵AVL樹，當插入到值為（）的結(jié)點時需要進行旋轉(zhuǎn)調(diào)整。A. 42B. 50C. 64D. 488. 深度為4的AVL樹至少有（）個結(jié)點。A9B.

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

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

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

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

7、47,90,84中的元素，生成一棵二叉搜索樹。畫出生成后的二叉搜索樹（畫出生成過程）。3. 依次讀入給定的整數(shù)序列7,16,4,8,20,9,6,18,5，構(gòu)造一棵二叉搜索樹,并計算在等概率情況下該二叉搜索樹的平均查找長度ASL。（要求給出構(gòu)造過程）4. 從空二叉樹開始，嚴格按照二叉搜索樹的插入算法（不進行平衡旋轉(zhuǎn)），逐個插入關(guān)鍵碼18, 73, 10, 5, 68, 99, 27, 41, 51, 32, 25構(gòu)造出一棵二叉搜索樹，畫出這棵二叉搜索樹并寫出其前序、后序遍歷序列。5. 若一棵二叉搜索樹的關(guān)鍵字輸入序列為80，6，10，7，8，25，100，90，請畫出該二叉搜索樹。6. 設(shè)有一

8、組初始記錄關(guān)鍵字為(45，80，48，40，22，78)，要求構(gòu)造一棵二叉搜索樹并給出構(gòu)造過程。7. 假定一個關(guān)鍵字序列為(38, 52, 25, 74, 68, 16, 30, 54, 90, 72)，畫出按序列中元素的次序生成的一棵二叉搜索樹，求出其平均查找長度。8. 將數(shù)列（24，15，38，27，121，76，130）的各元素依次插入一棵初始為空的二叉搜索樹中，請畫出最后的結(jié)果并求等概率情況下查找成功的平均查找長度。9. 輸入一個正整數(shù)序列40, 28, 6, 72, 100, 3, 54, 1, 80, 91, 38，建立一棵二叉搜索樹，然后刪除結(jié)點72，分別畫出該二叉樹及刪除結(jié)點7

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

10、計算該二叉搜索樹的平均查找長度(4)畫出在此二叉搜索樹中刪除“66”后的樹結(jié)構(gòu)。14. 試推導(dǎo)深度為5的平衡二叉樹最少包含多少個結(jié)點，并畫出一棵這樣的樹。 15. 畫出在一個初始為空的AVL樹中依次插入3, 1, 4, 6, 9, 8, 5, 7時每一插入后AVL樹的形態(tài)。若做了某種旋轉(zhuǎn)，說明旋轉(zhuǎn)的類型。16. 給定一個關(guān)鍵字序列4, 5, 7, 2, 1, 3, 6，生成一棵AVL樹，畫出構(gòu)造過程。17. 給定關(guān)鍵字序列4, 5, 7, 2, 1, 3, 6，分別生成二叉搜索樹和AVL樹，并用二叉搜索樹和AVL樹兩種方法查找，給出查找6的查找次數(shù)及查找成功的平均查找長度。18. 給定關(guān)鍵詞輸

11、入序列CAP, AQU, PIS, ARI, TAU, GEM, CAN, LIB, VIR, LEO, SCO，假定關(guān)鍵詞比較按英文字典序，試畫出從一棵空樹開始，依上述順序（從左到右）輸入關(guān)鍵詞，用AVL樹的插入算法生成一棵AVL樹的過程，并說明生成過程中采用了何種轉(zhuǎn)動方式進行平衡調(diào)整，標出樹中各結(jié)點的平衡因子。參考答案一、1-5. BCABC6-10. ABCCC二、1-5. ×6-10. ××××11-13. ×三、1. 中序2. 二叉搜索樹3. 小于，大于4. 查找成功，左子樹，右子樹5. 左子樹，右子樹6. O(n2)7.

12、平衡因子8. 7, 159. 1四、1.2.3.ASL= (1+2*2+3*3+4*3)/9 = 26/9 = 2.894.前序：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+2×2+3×2+4×2=19/7。9.二叉搜索樹刪除72后的二叉搜索樹10.11.或12. （1）（2）(1+2*2+3*2+4*1)/6 = 2.513. （1）構(gòu)造的二叉搜索樹為： （4）刪除結(jié)點66后(2) 對于一個二叉搜索樹，想得到一個從大到小的序列只要先讀右子樹再讀根結(jié)點，最后讀左子樹的遍歷這顆二叉樹就可以了。如果是要從