算法與數(shù)據(jù)結(jié)構(gòu) C語言版 第二版 (陳守孔 孟佳娜 武秀川 著) 機(jī)械工業(yè)出版社 課后答案 第11章 文件

課后答案網(wǎng) 11 章 文件 一、基礎(chǔ)知識題 詞解釋：索引文件 , 索引順序文件， 件， 件，散列文件，倒排文件。 【解答】先介紹文件的概念： 文件是由大量性質(zhì)相同的記錄組成的集合 ,按記錄類型不同可分為操作系統(tǒng)文件和數(shù)據(jù)庫文件。 文件的基本組織方式有順序組織、索引組織、散列組織和鏈組織。文件的存儲結(jié)構(gòu)可以采用將基本組織結(jié)合的方法 ,常用的結(jié)構(gòu)有順序結(jié)構(gòu)、索引結(jié)構(gòu)、散列結(jié)構(gòu)。 （ 1） 順序結(jié)構(gòu) ,相應(yīng)文件為順序文件 ,其記錄按存入文件的先后次序順序存放。順序文件本質(zhì)上就是順序表。若邏輯上相鄰的兩個(gè)記錄在存 儲位置上相鄰 ,則為連續(xù)文件；若記錄之間以指針相鏈接 ,則稱為串聯(lián)文件。順序文件只能順序存取 ,要更新某個(gè)記錄 ,必須復(fù)制整個(gè)文件。順序文件連續(xù)存取的速度快 ,主要適用于順序存取 ,批量修改的情況。 （ 2） 帶索引的結(jié)構(gòu) ,相應(yīng)文件為索引文件。索引文件包括索引表和數(shù)據(jù)表 ,索引表中的索引項(xiàng)包括數(shù)據(jù)表中數(shù)據(jù)的關(guān)鍵字和相應(yīng)地址 ,索引表有序 ,其物理順序體現(xiàn)了文件的邏輯次序 ,實(shí)現(xiàn)了文件的線性結(jié)構(gòu)。索引文件只能是磁盤文件 ,既能順序存取 ,又能隨機(jī)存取。 （ 3） 散列結(jié)構(gòu) ,也稱計(jì)算尋址結(jié)構(gòu) ,相應(yīng)文件稱為散列文件 ,其記錄是根據(jù)關(guān)鍵字值經(jīng)散 列函數(shù)計(jì)算確定其地址 ,存取速度快 ,不需索引 ,節(jié)省存儲空間。不能順序存取 ,只能隨機(jī)存取。 其它文件均由以上文件派生而得。 文件采用何種存儲結(jié)構(gòu)應(yīng)綜合考慮各種因素 ,如：存儲介質(zhì)類型、記錄的類型、大小和關(guān)鍵字的數(shù)目以及對文件作何種操作。 索引文件 ： 在主文件外 ,再建立索引表指示關(guān)鍵字及其物理記錄的地址間一一對應(yīng)關(guān)系。這種由索引表和主文件一起構(gòu)成的文件稱為索引文件。索引表依關(guān)鍵字有序。主文件若按關(guān)鍵字有序稱為 索引順序文件 ,否則稱為 索引非順序文件（通常簡稱索引文件）。索引順序文件因主文件有序 ,一般用稀疏索引 ,占用空間較 少。 專為磁盤存取設(shè)計(jì)的文件組織方式。即使主文件關(guān)鍵字有序 ,但因磁盤是以盤組、柱面和磁道（盤面）三級地址存取的設(shè)備 ,因此通常對磁盤上的數(shù)據(jù)文件建立盤組、柱面和磁道（盤面）三級索引。在 件上檢索記錄時(shí) ,先從主索引（柱面索引的索引）找到相應(yīng)柱面索引。再從柱面索引找到記錄所在柱面的磁道索引 ,最后從磁道索引找到記錄所在磁道的第一個(gè)記錄的位置 ,由此出發(fā)在該磁道上進(jìn)行順序查找直到查到為止；反之 ,若找遍該磁道而未找到所查記錄 ,則文件中無此記錄。 課后答案網(wǎng) 件 ： 件采用 B+樹動態(tài)索引 結(jié)構(gòu) ,文件只有控制區(qū)間和控制區(qū)域等邏輯存儲單位 ,與外存儲器中柱面、磁道等具體存儲單位沒有必然聯(lián)系。 序集和數(shù)據(jù)集三部分 ,記錄存于數(shù)據(jù)集中 ,順序集和索引集構(gòu)成 B+樹 ,作為文件的索引部分可實(shí)現(xiàn)順鏈查找和從根結(jié)點(diǎn)開始的隨機(jī)查找。 散列文件 ： 散列文件也稱直接存取文件 ,根據(jù)關(guān)鍵字的散列函數(shù)值和處理沖突的方法 ,將記錄散列到外存上。這種文件組織只適用于像磁盤那樣的直接存取設(shè)備 ,其優(yōu)點(diǎn)是文件隨機(jī)存放 ,記錄不必排序 ,插入、刪除方便 ,存取速度快 ,無需索引區(qū) ,節(jié)省存儲空間。缺點(diǎn)是散列文件不能順序存取 ,且只限于簡單查詢。經(jīng)多次插入、刪除后 ,文件結(jié)構(gòu)不合理 ,需重組文件 ,這很費(fèi)時(shí)。 倒排文件： 倒排文件是一種多關(guān)鍵字的文件 ,主數(shù)據(jù)文件按關(guān)鍵字順序構(gòu)成串聯(lián)文件 ,并建立主關(guān)鍵字索引。對次關(guān)鍵字也建立索引 ,該索引稱為倒排表。倒排表包括兩項(xiàng) ,一項(xiàng)是次關(guān)鍵字 ,另一項(xiàng)是具有同一次關(guān)鍵字值的記錄的物理記錄號（若數(shù)據(jù)文件非串聯(lián)文件 ,而是索引順序文件 如 倒排表中存放記錄的主關(guān)鍵字而不是物理記錄號）。倒排表作索引的優(yōu)點(diǎn)是索引記錄快 ,缺點(diǎn)是維護(hù)困難。在同一索引表中 ,不同的關(guān)鍵字其記錄數(shù)不同 ,各倒排表的長度不同 ,同一倒排表 中各項(xiàng)長度也不相等。 它們有什么區(qū)別與聯(lián)系 ? 【解答】文件的邏輯結(jié)構(gòu)是用戶或程序員能夠看見的數(shù)據(jù)組織形式，是用戶對數(shù)據(jù)的表示和存取方式。文件的各記錄間也存在邏輯關(guān)系，可以把文件看作一種線性結(jié)構(gòu)。即記錄間滿足唯一直接前驅(qū)和唯一直接后繼的關(guān)系。 文件的物理結(jié)構(gòu)是數(shù)據(jù)的物理表示和組織。文件的邏輯結(jié)構(gòu)著眼于用戶使用方便，而物理結(jié)構(gòu)需考慮節(jié)約存儲空間和減少存取時(shí)間。存儲記錄的方式依據(jù)實(shí)際需要及設(shè)備的特性的差異而不同：一個(gè)物理記錄可以存放一條或多條邏輯記錄；多個(gè)物理記錄也可 以表示一個(gè)邏輯記錄。 引順序存取方法（ ，主文件已按關(guān)鍵字排序，為何還需要主關(guān)鍵字索引？ 【解答】 專為磁盤存取設(shè)計(jì)的文件組織方式。即使主文件關(guān)鍵字有序 ,但因磁盤是以盤組、柱面和磁道（盤面）三級地址存取的設(shè)備 ,因此通常對磁盤上的數(shù)據(jù)文件建立盤組、柱面和磁道（盤面）三級索引。在 件上檢索記錄時(shí) ,先從主索引（柱面索引的索引）找到相應(yīng)柱面索引。再從柱面索引找到記錄所在柱面的磁道索引 ,最后從磁道索引找到記錄所在磁道的第一個(gè)記錄的位置 ,由此出發(fā)在該磁道上進(jìn)行順序查找直到查到為 止；反之 ,若找遍該磁道而未找到所查記錄 ,則文件中無此記錄。 課后答案網(wǎng) 析 件和 件的應(yīng)用場合、優(yōu)缺點(diǎn)等。 【解答】 采用靜態(tài)索引結(jié)構(gòu) ,對磁盤上的數(shù)據(jù)文件建立盤組、柱面、磁道三級索引。 件中記錄按關(guān)鍵字順序存放 ,插入記錄時(shí)需移動記錄并將同一磁道上最后的一個(gè)記錄移至溢出區(qū) ,同時(shí)修改磁道索引項(xiàng) ,刪除記錄只需在存儲位置作標(biāo)記 ,不需移動記錄和修改指針。經(jīng)過多次插入和刪除記錄后 ,文件結(jié)構(gòu)變得不合理 ,需周期整理 件。 件采用 B+樹動態(tài)索引結(jié)構(gòu) ,文件只有控制區(qū)間和控制區(qū)域等邏輯存儲單位 ,與外存儲器中柱面、磁道等具體存儲單位沒有必然聯(lián)系。 件結(jié)構(gòu)包括索引集、順序集和數(shù)據(jù)集三部分 ,記錄存于數(shù)據(jù)集中 ,順序集和索引集構(gòu)成B+樹 ,作為文件的索引部分可實(shí)現(xiàn)順鏈查找和從根結(jié)點(diǎn)開始的隨機(jī)查找。 與 件相比 ,件有如下優(yōu)點(diǎn)：動態(tài)分配和釋放存儲空間 ,不需對文件進(jìn)行重組；能保持較高的查找效率 ,且查找先后插入記錄所需時(shí)間相同。因此 ,基于 B+樹的 件通常作為大型索引順序文件的標(biāo)準(zhǔn)組織。 個(gè) 件除了主索引外 ，還包括哪兩級索引？ 【解答】 件有三級索引：磁盤組、柱面和磁盤 ,柱面索引存放在某個(gè)柱面上 ,若柱面索引較大 ,占多個(gè)磁道時(shí) ,可建立柱面索引的索引 主索引。故本題中所指的兩級索引是盤組和磁道。 什么在倒排文件組織中，實(shí)際記錄中的關(guān)鍵字域可刪除以節(jié)約空間？而在多重表結(jié)構(gòu)中這樣做為什么要犧牲性能？ 【解答】因倒排文件組織中 ,倒排表有關(guān)鍵字值及同一關(guān)鍵字值的記錄的所有物理記錄號 ,可方便地查詢具有同一關(guān)鍵字值的所有記錄；而多重表文件中次關(guān)鍵字索引結(jié)構(gòu)不同 ,刪除關(guān)鍵字域后查詢性能受到影響。 單比較文件的多重表和倒排表組織方式各自特點(diǎn)。 【解答】多重表文件是把索引與鏈接結(jié)合而形成的組織方式。記錄按主關(guān)鍵字順序構(gòu)成一個(gè)串聯(lián)文件 ,建立主關(guān)鍵字的索引（主索引）。對每一次關(guān)鍵字建立次關(guān)鍵字索引 ,具有同一關(guān)鍵字的記錄構(gòu)成一個(gè)鏈表。主索引為非稠密索引 ,次索引為稠密索引 ,每個(gè)索引項(xiàng)包括次關(guān)鍵字 ,頭指針和鏈表長度。多重表文件易于編程 ,也易于插入 ,但刪除繁鎖。需在各次關(guān)鍵字鏈表中刪除。 倒排文件是一種多關(guān)鍵字的文件 ,主數(shù)據(jù)文件按關(guān)鍵字順序構(gòu)成串聯(lián)文件 ,并建立主關(guān)鍵字索引。對次關(guān)鍵字也建立索引 ,該索引稱 為倒排表。倒排表包括兩項(xiàng) ,一項(xiàng)是次關(guān)鍵字 ,另一項(xiàng)是具有同一次關(guān)鍵字值的記錄的物理記錄號（若數(shù)據(jù)文件非串聯(lián)文件 ,而是索引順序文件 如 倒排表中存放記錄的主關(guān)鍵字而不是物理記錄號）。倒排表作索引的優(yōu)點(diǎn)是索引記錄快 ,缺點(diǎn)是維護(hù)困難。在同一索引表中 ,不同的關(guān)鍵字其記錄數(shù)不同 ,各倒排表的長度不同 ,同一倒排表中各項(xiàng)長度也不相等。 課后答案網(wǎng) 織待檢索文件的倒排表的優(yōu)點(diǎn)是什么？ 【解答】 倒排表作索引的優(yōu)點(diǎn)是索引記錄快 ,因?yàn)閺拇侮P(guān)鍵字值直接找到各相關(guān)記錄的物理記錄號 ,倒排因此而得名（因通常的查詢是從關(guān)鍵字查 到記錄）。在插入和刪除記錄時(shí) ,倒排表隨之修改 ,倒排表中具有相同次關(guān)鍵字的記錄號是有序的。 什么文件的倒排表比多重表組織方式節(jié)省空間？ 【解答】 排表有兩項(xiàng) ,一是次關(guān)鍵字值 ,二是具有相同次關(guān)鍵字值的物理記錄號 ,這些記錄號有序且順序存儲 ,不使用多重表中的指針鏈接 ,因而節(jié)省了空間。 比較順序文件，索引非順序文件，索引順序文件，散列文件的存儲代價(jià)，檢索，插入，刪除記錄時(shí)的優(yōu)點(diǎn)和缺點(diǎn)。 【解答】 （ 1）順序文件只能順序查找 ,優(yōu)點(diǎn)是批量檢索速度快 ,不適于單個(gè)記錄的檢索。順序文件不能象順序表 那樣插入、刪除和修改 ,因文件中的記錄不能象向量空間中的元素那樣“移動” ,只能通過復(fù)制整個(gè)文件實(shí)現(xiàn)上述操作。 （ 2）索引非順序文件適合隨機(jī)存取 ,不適合順序存取 ,因主關(guān)鍵字未排序 ,若順序存取會引起磁頭頻繁移動。索引順序文件是最常用的文件組織 ,因主文件有序 ,既可順序存取也可隨機(jī)存取。索引非順序文件是稠密索引 ,可以“預(yù)查找” ,索引順序文件是稀疏索引 ,不能“預(yù)查找” ,但由于索引占空間較少 ,管理要求低 ,提高了索引的查找速度。 （ 3）散列文件也稱直接存取文件 ,根據(jù)關(guān)鍵字的散列函數(shù)值和處理沖突的方法 ,將記錄散列到外存上。這 種文件組織只適用于像磁盤那樣的直接存取設(shè)備 ,其優(yōu)點(diǎn)是文件隨機(jī)存放 ,記錄不必排序 ,插入、刪除方便 ,存取速度快 ,無需索引區(qū) ,節(jié)省存儲空間。缺點(diǎn)是散列文件不能順序存取 ,且只限于簡單查詢。經(jīng)多次插入、刪除后 ,文件結(jié)構(gòu)不合理 ,需重組文件 ,這很費(fèi)時(shí)。 5個(gè)記錄，關(guān)鍵字分別為 285， 070