1、數據結構與算法上機作業第五章 查找一、選擇題1、若構造一棵具有n個結點的二叉排序樹，在最壞情況下，其高度不超過 B 。A. n/2B. nC. (n+1)/2D. n+12、分別以下列序列構造二叉排序數（二叉查找樹），與用其他3個序列所構造的結果不同的是 C ：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)3、不可能生成下圖所示的二叉排序樹的關鍵字的序列是 A 。

2、A. 4 5 3 1 2 B. 4 2 5 3 1 C. 4 5 2 1 3 D. 4 2 3 1 54、在二叉平衡樹中插入一個結點造成了不平衡，設最低的不平衡點為A，并已知A的左孩子的平衡因子為0，右孩子的平衡因子為1，則應作 C 型調整使其平衡。A. LLB. LRC. RLD. RR5、一棵高度為k的二叉平衡樹，其每個非葉結點的平衡因子均為0，則該樹共有 C 個結點。A. 2k-1-1B. 2k-1+1C. 2k-1D. 2k+16、具有5層結點的平衡二叉樹至少有 A 個結點。A. 12B. 11C. 10D. 97、下面關于B-和B+樹的敘述中，不正確的是 C 。A. B-樹和B+樹都

3、是平衡的多叉樹B. B-樹和B+樹都可用于文件的索引結構C. B-樹和B+樹都能有效地支持順序檢索D. B-樹和B+樹都能有效地支持隨機檢索8、下列關于m階B-樹的說法錯誤的是 D 。A. 根結點至多有m棵子樹B. 所有葉子結點都在同一層次C. 非葉結點至少有m/2（m為偶數）或m/2+1(m為奇數)棵子樹D. 根結點中的數據是有序的9、下面關于哈希查找的說法正確的是 C 。A. 哈希函數構造得越復雜越好，因為這樣隨機性好，沖突小B. 除留余數法是所有哈希函數中最好的C. 不存在特別好與壞的哈希函數，要視情況而定D. 若需在哈希表中刪去一個元素，不管用何種方法解決沖突都只要簡單地將該元素刪去即

4、可10、與其他查找方法相比，散列查找法的特點是 C 。A. 通過關鍵字的比較進行查找B. 通過關鍵字計算元素的存儲地址進行查找C. 通過關鍵字計算元素的存儲地址并進行一定的比較進行查找D. 以上都不是11、有一組關鍵字8, 24, 16, 3, 12, 32, 51，采用除留余數法構造散列函數：H(key)=key mod 12，則將發生 次沖突。A. 3B. 4C. 5D. 612、有一個結點的關鍵字為3276012483，采用移位疊加法生成4位散列地址，則生成的地址為 B 。A. 3482B. 3583C. 9018D. 9019二、填空題1、在查找過程中有插入或刪除元素操作的，稱為 動態

5、 查找。2、一個無序序列可以通過構造一棵 二叉排序 樹而變為一個有序序列，構造樹的過程即為對無序序列進行排序的過程。3、對于一棵二叉排序樹，按 中根 方法遍歷得出的結點序列是從小到大排列的。4、對二叉排序樹進行查找的方法是用待查找的值與根結點的鍵值進行比較，若比根結點的值小，則繼續在 左 子樹中查找。5、AVL樹為在構造二叉排序樹時，為確保搜索的性能而保持樹的平衡，保持平衡的方法為在構建AVL樹時根據特定條件而進行LL, RR, LR, RL四種旋轉操作，如對于下圖的樹，應該進行 RL RR 旋轉。 6、在m階一棵B-樹中，若在某個結點中插入一個新關鍵字而引起該結點分裂，則此結點中原有的關鍵字

6、的個數是 m-1 ；若在某結點中刪除一個關鍵字而導致結點合并，則該結點中原有的關鍵字的個數是 ém/2ù -1 。7、127階B-樹中每個結點最多有 126 個關鍵字；除根結點外所有非終端結點至少有 棵子樹；65階B+樹中，除根結點外所有非葉結點至少有 33 個關鍵字，最多有 65 棵子樹8、假設有k個關鍵字互為同義詞（哈希值相同），若用線性探測再散列法把這k個關鍵字存入散列表中，至少要進行 k(k-1)/2 次探測。9、在散列排序法中，折疊法的哈希函數可分為 移位法和分界法 兩種類型。10、散列法的填充因子= 表中填入的記錄數 / 哈希表的長度 。11、設散列函數H和關鍵

7、字k1, k2，若k1不等于k2，而H(k1)=H(k2)，則稱這種現象為 沖突 。12、在哈希函數H(key)=key % p中，p一般應取 不大于表長的質數或是不含20以下的質因數的合數 。三、依次輸入表(30, 15, 28, 20, 24, 10, 12, 68, 35, 50, 46, 55)中的元素，生成一棵二叉排序數，要求： 1、試畫出生成之后的二叉排序樹。 2、對該二叉排序數作中根遍歷，寫出遍歷序列。 3、編程構建一個二叉排序數，并中根遍歷驗證上述結果。四、二叉排序樹如下圖所示，分別畫出： 1、刪除關鍵字15以后的二叉樹，并要求平均查找長度盡可能小。 2、在原二叉排序樹(即沒有

8、刪除15)上，插入關鍵字20五、編寫一個判別給定二叉樹是否為二叉排序樹的算法，假設二叉樹是用左右鏈方式存儲。六、試畫出從空樹開始，有字符序列(t, d, e, s, u, g, b, j, a, k, r, i)構成的二叉平衡樹，并為每一次平衡處理指明旋轉類型。七、假設一棵平衡二叉樹的每個結點都標明了平衡因子b，試設計一個算法，利用平衡因子求平衡二叉樹的高度。八、設有三階B-樹（如下圖所示）， 1、畫出依次插入18、33、97后的B-樹 2、分別畫出刪除66、16、43后的B-樹九、給定一組記錄，其關鍵字為字符。各關鍵字插入順序為C, S, M, T, A, E, P, U, X, K, G,

9、 B 1、給出從空樹開始，順序插入這些關鍵字后的3階B+樹，假設葉節點所能容納最大關鍵碼的數量為4。 2、分別給出在(1)建立的B+樹上刪除E、P、T后的3階B+樹十、畫出如下數據集合的Trie樹：Amiot, Avenger, Avro, Heinkel, HellDivder, Macchi, Marauder, Mustang, SpitFire, Sykhoi。 1、對關鍵字實行從左到右一次一個字符采樣 2、利用單字符采樣，在上述數據上構造最少層數的Trie樹。十一、假定一個待散列存儲的線性表為32, 75, 29, 63, 48, 94, 25, 46, 18, 70，散列地址空間為HT13，若采用除留余數法構造散列函數(假設p取1