數據結構查找習題及復習資料

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

2、gn) D. O(n 2) 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. -1 1 B. -2 2 C. 1 2 D. 0 1 7. 根據一組關鍵字( 56， 42， 50， 64，48)依次插入結點生成一

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

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

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

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

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

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

9、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,建立一棵二叉搜索樹， 然后 刪除結點 72，分別畫出該二叉樹及刪除結點 72 后的二叉樹。 10. 根據元素插入的先后次序不同， 可構成多種形態(tài)的二叉搜索樹。 請畫出 4 棵含 1 ,2,3, 4 四個元素且以

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

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

12、鍵詞輸入序列 CAP, AQU, PIS, ARI, TAU, GEM, CAN, LIB, VIR, LEO, SCO ，假 定關鍵詞比較按英文字典序，試畫出從一棵空樹開始，依上述順序 (從左到右)輸入關 鍵詞，用 AVL 樹的插入算法生成一棵 AVL 樹的過程，并說明生成過程中采用了何種轉 動方式進行平衡調整，標出樹中各結點的平衡因子。 參考答案 1-5. BCABC 6-10. ABCCC 1-5. WW6-10. xxx11Z13. Wx5 / 10 1. 中序 2. 二叉搜索樹 3. 小于，大于 4. 查找成功，左子樹，右子樹 5. 左子樹，右子樹 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. 平均查找長度=1+2 X 2+3 X 2+4 X 2=19/74. 6. 7. 二叉搜索樹如圖所示，平均查找長度等于 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)構造的二叉搜索樹為:Q S) (4 )刪除結點 66 后 二叉搜索樹 54 SO 刪除 72 后的二叉搜索樹 40 SO ?! 8 / 10 后讀左子樹的遍歷這顆二叉樹就可以了。 如果是要從小到大的序列， 則只需中序遍歷這 顆二叉樹即可。 該二叉樹的平均查找長度為： ASL= ( 1*1+2*2+3*4+4*3 )/10=2.9 14. 略 15