數(shù)據(jù)結(jié)構(gòu)查找習(xí)題及復(fù)習(xí)資料

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

2、gn) D. O(n 2) 5. 分別以下列序列構(gòu)造二叉搜索樹(shù)，與用其它三個(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 樹(shù)中，每個(gè)結(jié)點(diǎn)的平衡因子的取值范圍是() 。 A. -1 1 B. -2 2 C. 1 2 D. 0 1 7. 根據(jù)一組關(guān)鍵字( 56， 42， 50， 64，48)依次插入結(jié)點(diǎn)生成一

3、棵 AVL 樹(shù)，當(dāng)插入到值 為()的結(jié)點(diǎn)時(shí)需要進(jìn)行旋轉(zhuǎn)調(diào)整。 A. 42 B. 50 C. 64 D. 48 8. 深度為 4 的 AVL 樹(shù)至少有()個(gè)結(jié)點(diǎn)。 A9 B. 8 C. 7 D. 6 9. 一棵深度為 k 的 AVL 樹(shù)，其每個(gè)分支結(jié)點(diǎn)的平衡因子均為 0，則該平衡二叉樹(shù)共有 () 個(gè)結(jié)點(diǎn)。 A.2k-1-1 B.2k-1+1 C.2k-1 D.2k 10. 在 AVL 樹(shù)中插入一個(gè)結(jié)點(diǎn)后造成了不平衡，設(shè)最低的不平衡結(jié)點(diǎn)為 A ，并已知 A 的左 孩子的平衡因子為 0，右孩子的平衡因子為 1，則應(yīng)作( ) 型調(diào)整以使其平衡。 A. LL B. LR C. RL D. RR 二、判斷

4、題 2 / 10 1. 二叉搜索樹(shù)的任意一棵子樹(shù)中， 關(guān)鍵字最小的結(jié)點(diǎn)必?zé)o左孩子， 關(guān)鍵字最大的結(jié)點(diǎn)必?zé)o 右孩子。 2. 二叉搜索樹(shù)中每個(gè)結(jié)點(diǎn)的關(guān)鍵字值大于其左非空子樹(shù) （若存在的話）所有結(jié)點(diǎn)的關(guān)鍵字 值，且小于其右非空子樹(shù)（若存在的話）所有結(jié)點(diǎn)的關(guān)鍵字值。 3. 二叉搜索樹(shù)按照中序遍歷將各結(jié)點(diǎn)打印出將各結(jié)點(diǎn)打印出來(lái)， 將得到按照由小到大的排 列。 4. 若二叉搜索樹(shù)的根結(jié)點(diǎn)沒(méi)有左兒子，則根結(jié)點(diǎn)一定是值最小的結(jié)點(diǎn)。 5. 二叉搜索樹(shù)一定是滿二叉樹(shù)。 6. 從二叉搜索樹(shù)的根結(jié)點(diǎn)一直沿右兒子向下找不一定能找到樹(shù)中值最大的結(jié)點(diǎn)。 7. 二叉搜索樹(shù)的充要條件是任一結(jié)點(diǎn)的值均大于其左孩子的值，小于其右孩

5、子的值。 8. 若二叉搜索樹(shù)中關(guān)鍵碼互不相同，則其中最小元素和最大元素一定是葉子結(jié)點(diǎn)。 9. 在任意一棵非空二叉搜索樹(shù)中，刪除某結(jié)點(diǎn)后又將其插入，則所得二叉搜索樹(shù)與原二叉 搜索樹(shù)相同。 10. 當(dāng)向二叉搜索樹(shù)中插入一個(gè)結(jié)點(diǎn)，則該結(jié)點(diǎn)一定成為葉子結(jié)點(diǎn)。 11. AVL 樹(shù)是指左右子樹(shù)的高度差的絕對(duì)值不大于 1 的二叉樹(shù)。 12. AVL 是一棵二叉樹(shù)，其樹(shù)上任一結(jié)點(diǎn)的平衡因子的絕對(duì)值不大于 1。 13. 在 AVL 樹(shù)中，向某個(gè)平衡因子不為零的結(jié)點(diǎn)的樹(shù)中插入一新結(jié)點(diǎn)，必引起平衡旋轉(zhuǎn)。 三、填空題 1. 在一棵二叉搜索樹(shù)上實(shí)施 _ 遍歷后，其關(guān)鍵字序列是一個(gè)有序表。 2. 一個(gè)無(wú)序序列可以通過(guò)構(gòu)造

6、一棵 _ 而變成一個(gè)有序序列，構(gòu)造樹(shù)的過(guò)程即為對(duì)無(wú) 序序列進(jìn)行排序的過(guò)程。 3. 在一棵二叉搜索樹(shù)中，每個(gè)分支結(jié)點(diǎn)的左子樹(shù)上所有結(jié)點(diǎn)的值一定 _ 該結(jié)點(diǎn)的值, 右子樹(shù)上所有結(jié)點(diǎn)的值一定 _ 該結(jié)點(diǎn)。 4. 從一棵二叉搜索樹(shù)中查找一個(gè)元素時(shí)，若元素的值等于根結(jié)點(diǎn)的值，則表明 _， 若元素的值小于根結(jié)點(diǎn)的值，則繼續(xù)向 _ 查找，若元素的值大于根結(jié)點(diǎn)的值，則 繼續(xù)向 _ 查找。 5. 向一棵二叉搜索樹(shù)中插入一個(gè)元素時(shí)， 若元素的值小于根結(jié)點(diǎn)的值， 則接著向根結(jié)點(diǎn)的 _ 插入，若元素的值大于根結(jié)點(diǎn)的值，則接著向根結(jié)點(diǎn)的 _ 插入。 6. 根據(jù) n個(gè)元素建立一棵二叉搜索樹(shù)的時(shí)間復(fù)雜度大致為 _ 。 7.

7、 二叉樹(shù)中某一結(jié)點(diǎn)左子樹(shù)的深度減去右子樹(shù)的深度稱為該結(jié)點(diǎn)的 3 / 10 8. 深度為 4 的平衡二叉樹(shù)中至少有 _ 個(gè)結(jié)點(diǎn)，至多有 _ 個(gè)結(jié)點(diǎn)。 9. 在一棵 AVL 樹(shù)中，每個(gè)結(jié)點(diǎn)的左子樹(shù)高度與右子樹(shù)高度之差的絕對(duì)值不超過(guò) 四、應(yīng)用題 1. 一棵二叉搜索樹(shù)的結(jié)構(gòu)如下圖所示，結(jié)點(diǎn)的值為 18,請(qǐng)標(biāo)出各結(jié)點(diǎn)的值。 2. 若依次輸入序列62,68,30,61,25,14,53,47,90,84中的元素，生成一棵二叉搜索樹(shù)。畫出 生成后的二叉搜索樹(shù)(畫出生成過(guò)程) 。 3. 依次讀入給定的整數(shù)序列 7,16,4,8,20,9,6,18,5,構(gòu)造一棵二叉搜索樹(shù)，并計(jì)算在等概率 情況下該二叉搜索樹(shù)的平

8、均查找長(zhǎng)度 ASL。(要求給出構(gòu)造過(guò)程) 4. 從空二叉樹(shù)開(kāi)始，嚴(yán)格按照二叉搜索樹(shù)的插入算法(不進(jìn)行平衡旋轉(zhuǎn)) ，逐個(gè)插入關(guān)鍵 碼18, 73, 10, 5, 68, 99, 27, 41,51,32, 25構(gòu)造出一棵二叉搜索樹(shù)，畫出這棵二叉搜索樹(shù) 并寫出其前序、后序遍歷序列。 5. 若一棵二叉搜索樹(shù)的關(guān)鍵字輸入序列為 80 , 6, 10, 7, 8, 25, 100, 90，請(qǐng)畫出該二 叉搜索樹(shù)。 6. 設(shè)有一組初始記錄關(guān)鍵字為 (45 , 80, 48, 40, 22, 78)，要求構(gòu)造一棵二叉搜索樹(shù)并給 出構(gòu)造過(guò)程。 7. 假定一個(gè)關(guān)鍵字序列為(38, 52, 25, 74, 68,

9、16, 30, 54, 90, 72)，畫出按序列中元素的次序 生成的一棵二叉搜索樹(shù)，求出其平均查找長(zhǎng)度。 8. 將數(shù)列(24, 15 , 38, 27, 121, 76, 130)的各元素依次插入一棵初始為空的二叉搜索 樹(shù)中，請(qǐng)畫出最后的結(jié)果并求等概率情況下查找成功的平均查找長(zhǎng)度。 9. 輸入一個(gè)正整數(shù)序列40, 28, 6, 72, 100, 3, 54, 1,80, 91,38,建立一棵二叉搜索樹(shù)， 然后 刪除結(jié)點(diǎn) 72，分別畫出該二叉樹(shù)及刪除結(jié)點(diǎn) 72 后的二叉樹(shù)。 10. 根據(jù)元素插入的先后次序不同， 可構(gòu)成多種形態(tài)的二叉搜索樹(shù)。 請(qǐng)畫出 4 棵含 1 ,2,3, 4 四個(gè)元素且以

10、1 為根、深度為 3 的二叉搜索樹(shù)。 11. 請(qǐng)畫出從下面的二叉搜索樹(shù)中刪除關(guān)鍵碼 40 后的結(jié)4 / 10 果。 20 3 8 45 60 28 12. 對(duì)關(guān)鍵字序列(25, 16, 34, 39, 28, 56)， 1) 畫出按此序列生成的二叉搜索樹(shù)。 2) 計(jì)算等概率下查找成功時(shí)的平均查找長(zhǎng)度。 13. 輸入一個(gè)正整數(shù)序列(53, 17, 12, 66, 58, 70, 87, 25, 56, 60)，試完成下列各題。 (1)按次序構(gòu)造一棵二叉搜索樹(shù) BS。 依此二叉搜索樹(shù)，如何得到一個(gè)從大到小的有序序列？ (3) 假定每個(gè)元素的查找概率相等，試計(jì)算該二叉搜索樹(shù)的平均查找長(zhǎng)度 (4) 畫

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

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

13、 8. 7, 15 9. 1 四、 1. 3. 0 Q 0 0 0 0 o 回 o O 0 ASL= (1+2*2+3*3+4*3)/9 = 26/9 = 2.892. 6 / 10 前序： 18 10 5 73 68 27 25 41 32 51 99 后序： 5 10 25 32 51 41 27 68 99 73 18 5. 8. 平均查找長(zhǎng)度=1+2 X 2+3 X 2+4 X 2=19/74. 6. 7. 二叉搜索樹(shù)如圖所示，平均查找長(zhǎng)度等于 32/10。 38 25 52 74 16 30 90 6S 54 72 7 / 10 9. 10. 0 0 11. 12. (1) (2) (1+2*2+3*2+4*1)/6 = 2.5 13. (1)構(gòu)造的二叉搜索樹(shù)為:Q S) (4 )刪除結(jié)點(diǎn) 66 后 二叉搜索樹(shù) 54 SO 刪除 72 后的二叉搜索樹(shù) 40 SO ?! 8 / 10 后讀左子樹(shù)的遍歷這顆二叉樹(shù)就可以了。 如果是要從小到大的序列， 則只需中序遍歷這 顆二叉樹(shù)即可。 該二叉樹(shù)的平均查找長(zhǎng)度為： ASL= ( 1*1+2*2+3*4+4*3 )/10=2.9 14. 略 15