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

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

2、搜索樹，與用其它三個(gè)序列所構(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 樹中，每個(gè)結(jié)點(diǎn)的平衡因子的取值范圍是() 。A. -1?1 B. -2?2 C. 1?2 D. 0?17. 根據(jù)一組關(guān)鍵字(56, 42, 50, 64, 48)依次插入結(jié)點(diǎn)生成一棵AVL樹，當(dāng)插入到值為()的結(jié)點(diǎn)時(shí)需要進(jìn)行旋轉(zhuǎn)調(diào)整。A. 42B. 50C. 64D. 488. 深度為

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

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

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

6、于根結(jié)點(diǎn)的值，則繼續(xù)向查找。5. 向一棵二叉搜索樹中插入一個(gè)元素時(shí)，若元素的值小于根結(jié)點(diǎn)的值，則接著向根結(jié)點(diǎn)的插入，若元素的值大于根結(jié)點(diǎn)的值，則接著向根結(jié)點(diǎn)的 插入。6.7.8.9.四、1.2.3.4.5.6.7.8.9.10.11.根據(jù)n個(gè)元素建立一棵二叉搜索樹的時(shí)間復(fù)雜度大致為 。二叉樹中某一結(jié)點(diǎn)左子樹的深度減去右子樹的深度稱為該結(jié)點(diǎn)的深度為4的平衡二叉樹中至少有 個(gè)結(jié)點(diǎn)，至多有 個(gè)結(jié)點(diǎn)。在一棵AVL樹中，每個(gè)結(jié)點(diǎn)的左子樹高度與右子樹高度之差的絕對(duì)值不超過應(yīng)用題一棵二叉搜索樹的結(jié)構(gòu)如下圖所示，結(jié)點(diǎn)的值為18,請(qǐng)標(biāo)出各結(jié)點(diǎn)的值。請(qǐng)畫出從下面的二叉搜索樹中刪除關(guān)鍵碼40后的結(jié)果。中的元素，生成

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

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

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

10、概率相等，試計(jì)算該二叉搜索樹的平均查找長度(4) 畫出在此二叉搜索樹中刪除“66”后的樹結(jié)構(gòu)。14. 試推導(dǎo)深度為5的平衡二叉樹最少包含多少個(gè)結(jié)點(diǎn)，并畫出一棵這樣的樹。15. 畫出在一個(gè)初始為空的AVL樹中依次插入 3, 1,4, 6, 9, 8, 5, 7時(shí)每一插入后 AVL樹的形態(tài)。若做了某種旋轉(zhuǎn)，說明旋轉(zhuǎn)的類型。16. 給定一個(gè)關(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

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

12、.2.3.ASL= (1+2*2+3*3+4*3)/9 = 26/9 =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+2X 2+3X 2+4X2 =19/7。9.二叉搜索樹刪除 72 后的二叉搜索樹10.11.或12. (1)2) (1+2*2+3*2+4*1)/6 =13. ( 1)構(gòu)造的二叉搜索樹為：4)刪除結(jié)點(diǎn) 66 后(2) 對(duì)于一個(gè)二叉搜索樹， 想得到一個(gè)從大到小的序列只要先讀右子樹再讀根結(jié)點(diǎn)， 最 后讀左子樹的遍歷這顆二叉樹就可以了。 如果是要從小到