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

1、第 9 章 查找歡迎下載13、單選題1. 對(duì)一棵二叉搜索樹按()遍歷，可得到結(jié)點(diǎn)值從小到大的排列序列。A. 先序B. 中序C. 后序D. 層次2. 從具有 n 個(gè)結(jié)點(diǎn)的二叉搜索樹中查找一個(gè)元素時(shí)，在平均情況下的時(shí)間復(fù)雜度大致為()。A. O(n)B. O(1)C. O(logn) D. O(n2)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ù)雜度為()。A. O(1)B. O(n)C. O(logn)D. O(n2)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 1B. -2 27. 根據(jù)一組關(guān)鍵字(56， 42， 50， 64，為()的結(jié)點(diǎn)時(shí)需要進(jìn)行旋轉(zhuǎn)調(diào)整。A. 42B. 50C. 648. 深度為 4 的 AVL 樹至少有()個(gè)結(jié)點(diǎn)。C. 1 2D. 0 148)依次插入結(jié)點(diǎn)生成一

3、棵AVL 樹，當(dāng)插入到值D. 48A 9B. 8C. 7D. 69 . 一棵深度為k 的 AVL 樹，其每個(gè)分支結(jié)點(diǎn)的平衡因子均為0，則該平衡二叉樹共有()個(gè)結(jié)點(diǎn)。A.2k-1-1B.2k-1+1C.2k-1D.2k10 .在AVL樹中插入一個(gè)結(jié)點(diǎn)后造成了不平衡，設(shè)最低的不平衡結(jié)點(diǎn)為A,并已知A的左孩子的平衡因子為0，右孩子的平衡因子為1，則應(yīng)作() 型調(diào)整以使其平衡。A. LLB. LRC. RLD. 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)鍵字值，且

4、小于其右非空子樹（若存在的話）所有結(jié)點(diǎn)的關(guān)鍵字值。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)，則該

5、結(jié)點(diǎn)一定成為葉子結(jié)點(diǎn)。11 . AVL樹是指左右子樹的高度差的絕對(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)的值，則

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

7、,68,30,61,25,14,53,47,90,84中的元素，生成一棵二叉搜索樹。畫出 生成后的二叉搜索樹(畫出生成過程) 。3 .依次讀入給定白整數(shù)序列7,16,4,8,20,9,6,18,5,構(gòu)造一棵二叉搜索樹，并計(jì)算在等概率情況下該二叉搜索樹的平均查找長度ASL。(要求給出構(gòu)造過程)4 .從空二叉樹開始，嚴(yán)格按照二叉搜索樹的插入算法(不進(jìn)行平衡旋轉(zhuǎn))，逐個(gè)插入關(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,

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

9、建立一棵二叉搜索樹，然后刪除結(jié)點(diǎn)72,分別畫出該二叉樹及刪除結(jié)點(diǎn)72后的二叉樹。10 .根據(jù)元素插入的先后次序不同，可構(gòu)成多種形態(tài)的二叉搜索樹。請(qǐng)畫出4棵含1, 2, 3,4四個(gè)元素且以1為根、深度為3的二叉搜索樹。11 .請(qǐng)畫出從下面的二叉搜索樹中刪除關(guān)鍵碼40后的結(jié)果。2011 4062450入 、八353845602812 .對(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

10、)按次序構(gòu)造一棵二叉搜索樹BS。(2)依此二叉搜索樹，如何得到一個(gè)從大到小的有序序列？(3)假定每個(gè)元素的查找概率相等，試計(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 ,分別生成

11、二叉搜索樹和 AVL樹，并用二叉搜索樹和 AVL樹兩種方法查找，給出查找 6的查找次數(shù)及查找成功的平均查找長度。18 .給定關(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. WWX6-10. xxx x41-13.1 .中序2 .二叉搜索樹3 . 小于，

12、大于4 .查找成功，左子樹，右子樹5 .左子樹，右子樹6 . O(n2)7 .平衡因子8 . 7,159 . 1四、1.2.3.0 0 Q &0 © ® 0 ® © ®© ® ®。 。®。 O ©ASL= (1+2*2+3*3+4*3)/ 9 = 2&9 = 2.894.國10$引Jr J 中、蜂4。0 ®、 © ®。00 © © 00n(V4前序:后序:5.6.18 10 5 73 68 27 25 41 32 51 995 1

13、0 25 32 51 41 27 68 99 73 1880.二叉搜索樹如圖所示，平均查找長度等于32/10。7.8. 平均查找長度=1+2 X2+3 X2+4 >2=19/7。F/V©9.二叉搜索樹00010.QO(% 0o 。o。11.一1個(gè)0 © 0 y © aQ ® 靛&須?；?2. (1)Q30)刪除72后的二叉搜索樹(3 ac5®D O。000 O3 ©。(2) (1+2*2+3*2+4*1)/6 = 2.513. (1)構(gòu)造的二叉搜索樹為:(4)刪除結(jié)點(diǎn)66后(2)對(duì)于一個(gè)二叉搜索樹，想得到一個(gè)從大到小的序列只要先讀右子樹再讀根結(jié)點(diǎn)，最后讀左子樹的遍歷這顆二叉樹就可以了。如果是要從小到大的序列，則只需中序遍歷這顆二叉樹即可。該二叉樹的平均查找長度為：ASL= (1*1+2*2+3*4+4*3 ) /10=2.9 14.略 15.© O 00©-,© O ® O 0 © ©®© n。®©00©