第十章 索引與散列

1、11-1 什么是靜態(tài)索引結(jié)構？什么是動態(tài)索引結(jié)構？它們各有哪些優(yōu)缺點？11-2 設有10000個記錄對象, 通過分塊劃分為若干子表并建立索引, 那么為了提高搜索效率, 每一個子表的大小應設計為多大?11-3如果一個磁盤頁塊大小為1024 (=1K 字節(jié)，存儲的每個記錄對象需要占用16字節(jié)，其中關鍵碼占4字節(jié)，其它數(shù)據(jù)占12字節(jié)。所有記錄均已按關鍵碼有序地存儲在磁盤文件中，每個頁塊的第1個記錄用于存放線性索引。另外在內(nèi)存中開辟了256K 字節(jié)的空間可用于存放線性索引。試問：(1 若將線性索引常駐內(nèi)存，文件中最多可以存放多少個記錄？(每個索引項8字節(jié)，其中關鍵碼4字節(jié)，地址4字節(jié)(2 如果使用二級

2、索引，第二級索引占用1024字節(jié)（有128個索引項），這時文件中最多可以存放多少個記錄？11-4 假設在數(shù)據(jù)庫文件中的每一個記錄是由占2個字節(jié)的整型數(shù)關鍵碼和一個變長的數(shù)據(jù)字段組成。數(shù)據(jù)字段都是字符串。為了存放右面的那些記錄，應如何組織線性索引？11-5 記錄地址 10032 10068 10104 10140 10176 10212 10248 10284 10320 其中，關鍵碼為職工號。試根據(jù)此文件，對下列查詢組織主索引和倒排索引，再寫出搜索結(jié)果關鍵碼。(1 男性職工；(2 月工資超過800元的職工；(3 月工資超過平均工資的職工；(4 職業(yè)為實驗員和行政秘書的男性職工；(5 男性教師或

3、者年齡超過25歲且職業(yè)為實驗員和教師的女性職工。11-6 倒排索引中的記錄地址可以是記錄的實際存放地址，也可以是記錄的關鍵碼。試比較這兩種方式的優(yōu)缺點。11-7 m = 2的平衡m 路搜索樹是A VL 樹，m = 3的平衡m 路搜索樹是2-3樹。它們的葉結(jié)點必須在同一層嗎？m 階B 樹是平衡m 路搜索樹，反過來，平衡m 路搜索樹一定是B 樹嗎？為什么？11-8 下圖是一個3階B 樹。試分別畫出在插入65、15、40、30之后B 樹的變化。 11-9 下圖是一個3階B 樹。試分別畫出在刪除50、40之后B 樹的變化。11-10 對于一棵有1999999個關鍵碼的199階B 樹，試估計其最大層數(shù)(

4、不包括失敗結(jié)點 及最小層數(shù)(不包括失敗結(jié)點 。 11-11 給定一組記錄，其關鍵碼為字符。記錄的插入順序為 C, S, D, T, A, M, P, I, B, W, N, G, U, R, K, E, H, O, L, J ，給出插入這些記錄后的4階B+樹。假定葉結(jié)點最多可存放3個記錄。 11-12 設有一棵B+樹，其內(nèi)部結(jié)點最多可存放100個子女，葉結(jié)點最多可存儲15個記錄。對于1, 2, 3, 4, 5層的B+樹，最多能存儲多少記錄，最少能存儲多少記錄。11-13設散列表為HT13, 散列函數(shù)為 H (key = key %13。用閉散列法解決沖突, 對下列關鍵碼序列 12, 23, 4

5、5, 57, 20, 03, 78, 31, 15, 36 造表。 (1 采用線性探查法尋找下一個空位, 畫出相應的散列表, 并計算等概率下搜索成功的平均搜索長度和搜索不成功的平均搜索長度。 (2 采用雙散列法尋找下一個空位, 再散列函數(shù)為 RH (key = (7*key % 10 + 1, 尋找下一個空位的公式為 H i = (Hi-1 + RH (key % 13, H1 = H (key 。畫出相應的散列表, 并計算等概率下搜索成功的平均搜索長度。11-14 設有150個記錄要存儲到散列表中, 要求利用線性探查法解決沖突, 同時要求找到所需記錄的平均比較次數(shù)不超過2次。試問散列表需要設

6、計多大？ 設是散列表的裝載因子，則有11ASL succ =(1+21-11-15 若設散列表的大小為m ，利用散列函數(shù)計算出的散列地址為h = hash(x。 (1 試證明：如果二次探查的順序為(h + q2, (h + (q-1 2, , (h+1, h, (h-1, , (h-q 2 ，其中， q = (m-1/2。因此在相繼被探查的兩個桶之間地址相減所得的差取模(%m的結(jié)果為 m -2, m-4, m-6, , 5, 3, 1, 1, 3, 5, , m-6, m-4, m-2 (2 編寫一個算法，使用課文中討論的散列函數(shù)h(x和二次探查解決沖突的方法，按給定值x 來搜索一個大小為m

7、的散列表。如果x 不在表中，則將它插入到表中。11-16 編寫一個算法，以字典順序輸出散列表中的所有標識符。設散列函數(shù)為hash(x = x中的第一個字符，采用線性探查法來解決沖突。試估計該算法所需的時間。11-17 設有1000個值在1到10000的整數(shù)，試設計一個利用散列方法的算法，以最少的數(shù)據(jù)比較次數(shù)和移動次數(shù)對它們進行排序。11-18 設有15000個記錄需放在散列文件中，文件中每個桶內(nèi)各頁塊采用鏈接方式連結(jié)，每 個頁塊可存放30個記錄。若采用按桶散列，且要求搜索到一個已有記錄的平均讀盤時間不超過1.5次，則該文件應設置多少個桶？11-19 用可擴充散列法組織文件時，若目錄深度為d ，指向某個頁塊的指針有n 個，則該頁塊的局部深度有多大？11-20 設一組對象的關鍵碼為 69, 115, 110, 255, 185, 143, 208, 96, 63, 175, 160, 99, 171, 137, 149, 229, 167, 121, 204, 52, 127, 57, 1040 。要求用散列函數(shù)將這些對象的關鍵碼轉(zhuǎn)換成二進制地址，存入用可擴充散列法組織的文件里。定義散列函數(shù)為hash(key = k