【正文】 2 選擇題 ? 3 判斷題 ? 4 解答題 ? 5 算法題 習(xí) 題 __填空題 1. 填空題 (1) 采用二分法進(jìn)行查找的查找表 ， 應(yīng)選擇 ______________________方式的存儲結(jié)構(gòu) 。 (3) 在分塊查找法中 ， 首先查找 ________________， 然后再查找相應(yīng)的_________________。 (5) 查找有序表 R[0? 11]中每個(gè)數(shù)據(jù)元素 ， 假設(shè)查找在等概率情況下進(jìn)行 ，則進(jìn)行順序查找的平均查找長度為 ___________， 進(jìn)行二分查找的平均查找長度為 ___________。 (7) 在散列存儲中 ， 裝填因子的值越大 ， 存取數(shù)據(jù)元素時(shí)發(fā)生沖突的可能性就 ______， 裝填因子的值越小 ， 存取數(shù)據(jù)元素時(shí)發(fā)生沖突的可能性就 ______。 (9) 一棵深度為 h的 B－樹上 ， 任一個(gè)葉子結(jié)點(diǎn)所處的層數(shù)為 _________，當(dāng)向該 B－樹插入一個(gè)新結(jié)點(diǎn)時(shí) ， 為了檢索插入位置需讀取 _______個(gè)結(jié)點(diǎn) 。 習(xí) 題 __選擇題 2. 選擇題 (1) 采用順序查找法檢索長度為 n的線性表 ， 則檢索每個(gè)元素的平均比較次數(shù)為 ______。 (3) 如果要求一個(gè)線性表既能快速查找 ， 又能適應(yīng)動態(tài)變化的要求 ， 則宜采用的檢索方法是 _____。 習(xí) 題 __選擇題 (5) 有一個(gè)有序表 {1， 4， 6， 10， 18， 35， 42， 53， 67， 71， 78， 84，92， 99}， 當(dāng)用二分查找法查找鍵值為 84的結(jié)點(diǎn)時(shí) ， 經(jīng) _____比較后查找成功 。 (n) (log2n) (n2) (nlog2n) (7) 在一棵 3階 B－樹上 ， 每個(gè)結(jié)點(diǎn)包括的子樹相同 ， 最多為 _____， 最少為 _____。 m的最大奇數(shù) m的最大素?cái)?shù) m的最大偶數(shù) m的最大合數(shù) 習(xí) 題 __判斷題 3. 判斷題 (1) 在等概率情況下實(shí)現(xiàn)分塊查找，其平均查找長度不僅與表的個(gè)數(shù)有關(guān)，而且與每一塊中的元素個(gè)數(shù)有關(guān)。 ( ) (3) 只要采用順序存儲結(jié)構(gòu)存放的數(shù)據(jù)元素，都可以利用折半查找法進(jìn)行查找。 ( ) 習(xí) 題 __解答題 4. 解答題 (1) 給定表 ｛ 19， 14， 22， 01， 66， 21， 83， 27， 56， 13， 10｝ ① 試按元素在表中的順序構(gòu)造一棵二叉排序樹； ② 判斷該二叉排序樹是否平衡 ， 若不平衡 ， 調(diào)整其為平衡二叉樹 。 (以字符ASCII大小為序 )畫出相應(yīng)的二叉排序樹 ， 并求出等概率情況下的查找成功的平均查找長度； ② 若根據(jù)該二叉排序樹對表中元素排序構(gòu)成有序表 ， 試求在等概率情況下查找成功的平均查找長度； ③ 按表中元素順序構(gòu)造出一棵平衡二叉樹 ， 并求出等概率情況下查找成功的平均查找長度 。 (4) 現(xiàn)有線性表的關(guān)鍵字集合 {33， 41， 20， 24， 30， 13， 01， 67}共 8個(gè)數(shù)據(jù)元素 ， 已知散列函數(shù)為 H(k)=(3k)％ 11， 用開放定址法解決沖突 ， 且 d1=h(k), di=(di－ 1 +(7k)%10+1)%11(i = 2,3,? )， ① 試在 0～ 10的散列地址空間中構(gòu)造散列表 ， 并計(jì)算出等概率情況下查找成功和查找失敗的平均查找長度 。 習(xí) 題 __解答題 (5) 已知一個(gè)有序表 (13， 18， 24， 35， 47， 50， 62， 83， 90， 115，134)， 寫出利用二分查找法查找 90的過程 。 (7) 含有 9個(gè)葉子結(jié)點(diǎn)的 3階 B－樹中至少有多少個(gè)非葉子結(jié)點(diǎn) ？ 含有 10個(gè)葉子結(jié)點(diǎn)的 3階 B－樹中至少有多少個(gè)非葉子結(jié)點(diǎn) ？ 習(xí) 題 __算法題 5. 算法題 (1) 編寫算法 ， 求出指定結(jié)點(diǎn)在給定的二叉排序樹中的層數(shù) 。 (3) 試設(shè)計(jì)從一個(gè)用開放地址法解決沖突的散列表中刪除一個(gè)指定結(jié)點(diǎn)的算法 。 (5) 寫出二分查找的遞歸算法 。 A? Thanks! 第 9章 文 件 （時(shí)間： 2次課， 4學(xué)時(shí)） 第 9章 文 件 ? 教學(xué)提示： 本章介紹文件存儲在外存儲器上的結(jié)構(gòu) 。本章重點(diǎn)介紹文件的概念 、 運(yùn)算和存儲結(jié)構(gòu) 。 第 9章 文 件 ? 文件的基本概念 ? 順序文件 ? 索引文件 ? 索引順序文件 ? 散列文件 ? 多關(guān)鍵字文件 ? 習(xí)題 文件的基本概念 1. 文件的定義和術(shù)語 ? 文件 (file)是性質(zhì)相同的記錄的集合 。文件可以將數(shù)據(jù)長久 地 保存在計(jì)算機(jī)的外存儲器中 。 數(shù)據(jù)存儲在外存儲器上的結(jié)構(gòu)稱為文件 。 若文件中的記錄只有一個(gè)惟一標(biāo)識記錄的主關(guān)鍵字 ， 則稱其為單關(guān)鍵字文件；若文件中的記錄除了含有一個(gè)主關(guān)鍵字外 ， 還含有若干個(gè)次關(guān)鍵字 ， 則稱其為多關(guān)鍵字文件 。 定長文件是指 ， 文件中記錄含有的信息長度必須相同 。 表 個(gè)定長文件 。 不同結(jié)構(gòu)的文件中的記錄間的邏輯關(guān)系可能不同 。 在這種次序下 ， 文件中每個(gè)記錄最多只有一個(gè)后繼記錄和一個(gè)前驅(qū)記錄 ， 而文件的第一個(gè)記錄只有后繼沒有前驅(qū) ， 文件的最后一個(gè)記錄只有前驅(qū)而沒有后繼。 例如 ， 查找職工編號 =202的記錄 ， 或者查找姓名 =“張淼 ” 的記錄 。 例如 ， 查找工資 3000的所有職工的記錄 。 例如 ， 查詢?nèi)w職工的平均工資是多少 。 (2) 維護(hù)操作 維護(hù)操作是指對文件進(jìn)行記錄的插入 、 刪除及修改等更新操作 。 文件的基本概念 3. 文件的實(shí)時(shí)處理和批量處理 文件的操作有 實(shí)時(shí)處理 和 批量處理 兩種不同的處理方式 。 而批量處理在響應(yīng)時(shí)間要求上比較寬松 ， 接受文件操作 請求后不必立即進(jìn)行 ， 可以隔一段時(shí)間后處理一批操作 。 例如 ， 商店的刷卡系統(tǒng)中 ，顧客交費(fèi)刷卡操作應(yīng)當(dāng)是實(shí)時(shí)處理 。 4. 文件的存儲結(jié)構(gòu) 文件的存儲結(jié)構(gòu)是指文件在外存上的組織方式 。 數(shù)據(jù)的基本組織方式有四種：順序組織 ， 索引組織 ， 散列組織和鏈組織 。 順 序 文 件 提示： 順序文件是指按記錄寫入文件的先后順序存放 、 其邏輯順序和物理順序一致的文件 。 順序文件具有以下特點(diǎn)： ? 在順序文件中，所有邏輯記錄在存儲介質(zhì)中的實(shí)際順序與它們進(jìn)入存儲器的順序一致。 ? 順序文件的缺點(diǎn)是不利于修改。 索 引 文 件 ? 索引文件的特點(diǎn)和術(shù)語 ? 索引文件的存儲 ? 索引文件的檢索與修改 索引文件的特點(diǎn)和術(shù)語 1. 索引文件的特點(diǎn) ? 索引文件由索引表和主文件兩部分構(gòu)成 。 ? 索引文件的檢索方式為直接存取或按關(guān)鍵字存取 。 ? 索引文件只能是磁盤文件 。 ? 索引表都是有序的 ， 查找索引表時(shí)可以用折半查找法。索引指明邏輯記錄和物理記錄之間的一一對應(yīng)關(guān)系。 索引表中的每一項(xiàng)稱作索引項(xiàng)，索引項(xiàng)都是由主關(guān)鍵字和該關(guān)鍵字所在記錄的物理地址組成的。 (2) 索引順序文件和索引非順序文件 主文件本身按主關(guān)鍵字有序的索引文件稱為索引順序文件(Indexed Sequentail File)，主文件無序的索引文件稱為索引非順序文件 (Indexed NonSequentail File)。索引非順序文件的主文件中記錄是無序的，則必須為每個(gè)記錄建立一個(gè)索引項(xiàng)，這樣建立的索引表稱為“稠密索引”。在建立文件過程中，按輸入記錄的先后次序建立數(shù)據(jù)區(qū)和索引表，這樣的索引表其關(guān)鍵字是無序的，待全部記錄輸入完畢后再對索引表進(jìn)行排序，排序后的索引表和主文件一起就形成了索引文件。 2. 在索引文件中插入記錄 在索引文件插入記錄時(shí)，將插入記錄置于數(shù)據(jù)區(qū)的末尾，并在索引表中插入索引項(xiàng)。 索引順序文件 ? ISAM文件 ? VSAM文件 ISAM文件 ISAM(Indexed Sequential Access Methed )是索引順序存取方法 。 1. ISAM文件的特點(diǎn) ? ISAM文件的特點(diǎn)如下： ? ISAM是索引順序存取方法 ， 該方法專為磁盤存取設(shè)計(jì)。 ? ISAM文件由多級主索引 、 柱面索引 、 磁道索引和主文 件組成 。 下面介紹在同一個(gè)盤組上建立的 ISAM文件的方法 。 文件的記錄在同一盤組上存放時(shí) ， 應(yīng)先集中放在一個(gè)柱面上 ， 然后再順序存放在相鄰的柱面上 。 主索引是柱面索引的索引 。 若柱面索引較小時(shí) ， 主索引可省略 。 ISAM文件 3. ISAM文件的檢索 提示： 在 ISAM文件上檢索記錄的步驟如下： (1) 從主索引出發(fā)，找到相應(yīng)的柱面索引； (2) 從柱面索引找到記錄所在柱面的磁道索引； (3) 從磁道索引找到記錄所在磁道的起始地址，由此出發(fā)在該磁道上進(jìn)行順序查找 , 直到找到為止。 若該磁道不滿 ， 則將新記錄插入該磁道的適當(dāng)位置上即可；若該磁道已滿 ， 則新記錄直接插入到該磁道的溢出鏈表上 。 5. 刪除 ISAM文件中的記錄 刪除 ISAM文件中記錄時(shí) ， 先找到待刪除的記錄 ， 在其存儲位置上作刪除標(biāo)記 ， 不需要移動記錄或改變指針 。 ISAM文件需要周期性地進(jìn)行整理 。 VSAM文件 VSAM(Virtual Storage Access Method)是虛擬存儲存取方法 。 1. VSAM文件的特點(diǎn)如下： ? VSAM是虛擬存儲存取方法 ， 該方法為磁盤存取設(shè)計(jì)。 ? VSAM文件采用動態(tài)索引結(jié)構(gòu) 。 對 B+樹進(jìn)行隨機(jī)查找 、 插入和刪除的過程與 B— 樹類似 。 在 B+樹中 ， 不管查找成功與否 ， 每次查找都是走了一條從根到葉子結(jié)點(diǎn)的路徑 。 在 VSAM文件中刪除記錄時(shí) ， 需將同一控制區(qū)間中比刪除記錄關(guān)鍵字大的記錄向前移動 ， 把空間留給以后插入的新記錄 。 散 列 文 件 ? 散列文件的存儲 ? 散列文件的查找 ? 散列文件的刪除操作 散 列 文 件 散列文件是利用散列存儲方式組織的文件，亦稱直接存取文件。 ? 散列文件中的記錄通常是成組存放的，存放一組的存儲單位稱為桶。 散列文件的存儲 散列文件 的存儲類似于散列表 ， 根據(jù)文件中關(guān)鍵字的特點(diǎn) ， 設(shè)計(jì)一個(gè)散列函數(shù)和處理沖突的方法 ， 將記錄散列到外存儲設(shè)備上 。 假如一個(gè)桶能存放 n個(gè)記錄 ， 當(dāng)桶中已有 n個(gè)同義詞的記錄時(shí) ， 存放第 n+1個(gè)同義詞會發(fā)生 “溢出 ” 。 當(dāng)發(fā)生 “ 溢出 ” 時(shí) ， 將第 n+1個(gè)同義詞存放到另一個(gè)桶中 ， 稱此桶為 “ 溢出桶 ” 。 溢出桶和基桶大小相同 。 圖 。同一散列地址的溢出桶和基桶，在磁盤上的物理位置不要相距太遠(yuǎn)。 散列文件的刪除操作 刪除散列文件中的一個(gè)記錄 ， 是對被刪記錄作刪除標(biāo)記 。 散列文件的優(yōu)點(diǎn) 是文件隨機(jī)存放 ， 記錄不需進(jìn)行排序 ， 插入 、 刪除操作方便 ， 存取速度快 ， 不需要索引 ， 節(jié)省存儲空間 。 多關(guān)鍵字文件 ? 多重表文件的概念 ? 倒排文件 多關(guān)鍵字文件 提示：多關(guān)鍵字文件有以下特點(diǎn) : ① 多關(guān)鍵字文件不僅對主關(guān)鍵字索引 ， 還對其余的次關(guān)鍵字進(jìn)行索引 。 ③ 倒排文件也是對數(shù)據(jù)文件中的主關(guān)鍵字和次關(guān)鍵字分別建立索引 ， 但索引是用倒 排表 。 多重表文件的概念 多重表文件 的主文件是一個(gè)順序文件 ， 每個(gè)需要查詢的次關(guān)鍵字建立一 個(gè)索引 ， 并將具有相同次關(guān)鍵字的記錄鏈接成一個(gè)鏈表 ， 將此鏈表的頭指針 、 鏈表長度及次關(guān)鍵字作為索引表的一個(gè)索引項(xiàng) 。 在這個(gè)多重表文件中 ， 主關(guān)鍵字是職工號 ， 職務(wù)和工資級別也是要進(jìn)行查找的次關(guān)鍵字 。 在主文件中 為關(guān)鍵字 “ 工資級別 ” 設(shè)立了鏈接字段 ， 該字段將相同的工資級別記錄鏈在一起 。 有了這些索引 ， 便易于處理各種有關(guān)次關(guān)鍵字的查詢 。 若要查詢工資級別為 11的所有硬件人員 ， 則既可以從職務(wù)索引的 “ 硬件人員 ” 的頭指針出發(fā) ， 也可以從工資級別索引的 “ 11” 的頭指針出發(fā) ， 讀出鏈表上的每個(gè)記錄 ， 判定它是否滿足查詢條件 。相同次關(guān)鍵字的不同記錄之間不進(jìn)行鏈接，而是在倒排表中列出具有該相同次關(guān)鍵字記錄的各存儲地址。例如，對表 ，表 ，表 。 而倒排文件中 ， 是先給定次關(guān)鍵字 ， 然后查找含有該次關(guān)鍵字的各個(gè)記錄 。 倒