數(shù)據(jù)結(jié)構(gòu)習(xí)題解析第10章

1、209第10章索引與散列一、復(fù)一、復(fù)習(xí)要點(diǎn)要點(diǎn)索引結(jié)構(gòu)和散列結(jié)構(gòu)是用于外部搜索的搜索結(jié)構(gòu)。數(shù)據(jù)在外存的組織即文件結(jié)構(gòu)，主要分順序、直接存?。ㄉ⒘校┖退饕募?。在這些文件組織中使用的主要是索引和散列方法。1、基本知識(shí)點(diǎn)要求掌握靜態(tài)索引結(jié)構(gòu)，包括線性索引、倒排索引、靜態(tài)索引樹的搜索和構(gòu)造方法。掌握動(dòng)態(tài)索引結(jié)構(gòu)，包括B樹的搜索、插入、刪除，通過關(guān)鍵碼個(gè)數(shù)估算B樹的高度的方法；B樹的搜索、插入與刪除。掌握散列法，包括散列函數(shù)的構(gòu)造、處理溢出的閉

2、散列方法；處理溢出的開散列方法；散列表分析。二、二、難點(diǎn)與重點(diǎn)點(diǎn)與重點(diǎn)1、線性索引?密集索引、稀疏索引、索引表計(jì)算?基于屬性查找建立倒排索引、單元式倒排表2、動(dòng)態(tài)搜索樹?平衡的m路搜索樹的定義、搜索算法?B樹的定義、B樹與平衡的m路搜索樹的關(guān)系?B樹的插入(包括結(jié)點(diǎn)分裂)、刪除(包括結(jié)點(diǎn)調(diào)整與合并)方法?B樹中結(jié)點(diǎn)個(gè)數(shù)與高度的關(guān)系?B樹的定義、搜索、插入與刪除的方法3、散列表?散列函數(shù)的比較?裝載因子?與平均搜索長度的關(guān)系，平均搜索長度

3、的關(guān)系?表長m、表中已有數(shù)據(jù)對象個(gè)數(shù)n和裝載因子的關(guān)系?解決沖突的(閉散列)線性探查法的運(yùn)用，平均探查次數(shù)的計(jì)算?線性探查法的刪除問題、散列表類的設(shè)計(jì)中必須為各地址設(shè)置三個(gè)狀態(tài)?線性探查法中的堆積聚集問題?解決沖突的(閉散列)雙散列法的運(yùn)用，平均探查次數(shù)計(jì)算?雙散列法中再散列函數(shù)的設(shè)計(jì)要求與表長m互質(zhì)，為此m設(shè)計(jì)為質(zhì)數(shù)較宜?解決沖突的(閉散列)二次散列法的運(yùn)用，平均探查次數(shù)計(jì)算?注意：二次散列法中裝載因子?與表長m的設(shè)置?解決沖突的(開

4、散列)開散列法的運(yùn)用，平均探查次數(shù)計(jì)算?由平均探查次數(shù)計(jì)算裝載因子?，再計(jì)算表大小的方法三、教材中三、教材中習(xí)題習(xí)題的解析的解析101什么是靜態(tài)索引結(jié)構(gòu)？什么是動(dòng)態(tài)索引結(jié)構(gòu)？它們各有哪些優(yōu)缺點(diǎn)？【解答】211索引表ID堆ste關(guān)鍵碼串長度串起始地址0HelloWld!XYZThisstringisratherlongThis4235682312isShterABCHellonewWld!3971201037154110382615222

5、21659105設(shè)有一個(gè)職工文件：記錄地址職工號(hào)姓名性別職業(yè)年齡籍貫月工資(元)10032034劉激揚(yáng)男教師29山東720.0010068064蔡曉莉女教師32遼寧1200.0010104073朱力男實(shí)驗(yàn)員26廣東480.0010140081洪偉男教師36北京1400.0010176092盧聲凱男教師28湖北720.0010212123林德康男行政秘書33江西480.0010248140熊南燕女教師27上海780.0010284175呂

6、穎女實(shí)驗(yàn)員28江蘇480.0010320209袁秋慧女教師24廣東720.00其中，關(guān)鍵碼為職工號(hào)。試根據(jù)此文件，對下列查詢組織主索引和倒排索引，再寫出搜索結(jié)果關(guān)鍵碼。(1)男性職工；(2)月工資超過800元的職工；(3)月工資超過平均工資的職工；(4)職業(yè)為實(shí)驗(yàn)員和行政秘書的男性職工；(5)男性教師或者年齡超過25歲且職業(yè)為實(shí)驗(yàn)員和教師的女性職工。【解答】主索引月工資倒排索引職務(wù)倒排索引職工號(hào)記錄地址月工資長度指針職務(wù)長度指針0034