數據結構第十一章《文件》應用題及參考答案_跨考網

? 1．名詞解釋：文件。【山東工業(yè)大學 1998 一、1-1（2分）】

　　【參考答案】

　　文件是由大量性質相同的記錄組成的集合，按記錄類型不同可分為操作系統(tǒng)文件和數據庫文件。
　　
　　2．文件存儲結構的基本形式有哪些？一個文件采用何種存儲結構應考慮哪些因素？【燕山大學 1999 二、4(4分）】

　　【參考答案】

　　文件的基本組織方式有順序組織、索引組織、散列組織和鏈組織。文件的存儲結構可以采用將基本組織結合的方法，常用的結構有順序結構、索引結構、散列結構。

　?。?）順序結構，相應文件為順序文件，其記錄按存入文件的先后次序順序存放。順序文件本質上就是順序表。若邏輯上相鄰的兩個記錄在存儲位置上相鄰，則為連續(xù)文件；若記錄之間以指針相鏈接，則稱為串聯文件。順序文件只能順序存取，要更新某個記錄，必須復制整個文件。順序文件連續(xù)存取的速度快，主要適用于順序存取，批量修改的情況。

　　（2）帶索引的結構，相應文件為索引文件。索引文件包括索引表和數據表，索引表中的索引項包括數據表中數據的關鍵字和相應地址，索引表有序，其物理順序體現了文件的邏輯次序，實現了文件的線性結構。索引文件只能是磁盤文件，既能順序存取，又能隋機存取。

　?。?）散列結構，也稱計算尋址結構，相應文件稱為散列文件，其記錄是根據關鍵字值經散列函數計算確定其地址，存取速度快，不需索引，節(jié)省存儲空間。不能順序存取，只能隨機存取。

　　其它文件均由以上文件派生而得。

　　文件采用何種存儲結構應綜合考慮各種因素，如：存儲介質類型、記錄的類型、大小和關鍵字的數目以及對文件作何種操作。
　　
　　3．名詞解釋：索引文件。【哈爾濱工業(yè)大學 2000 一、4 （3分）】

　　【參考答案】

　　在主文件外，再建立索引表指示關鍵字及其物理記錄的地址間一一對應關系。這種由索引表和主文件一起構成的文件稱為索引文件。索引表依關鍵字有序。主文件若按關鍵字有序稱為索引順序文件，否則稱為索引非順序文件（通常簡稱索引文件）。索引順序文件因主文件有序，一般用稀疏索引，占用空間較少。常用索引順序文件有ISAM和VSAM。ISAM采用靜態(tài)索引結構，而VSAM采用B+樹的動態(tài)索引結構。索引文件既能順序存取，也能隨機存取。

?4．什么是索引順序文件？【哈爾濱工業(yè)大學2001三、5（3分）】【山東工業(yè)大學1998一、1-2（2分）】

　　【參考答案】

　　在索引文件中，若（數據區(qū)）主文件中關鍵字有序，則文件稱為索引順序文件，參見上題3。

??? 5．索引順序存取方法（ISAM）中，主文件已按關鍵字排序，為何還需要主關鍵字索引？【東南大學 1995 四（6分）】
　　【參考答案】
　　ISAM是專為磁盤存取設計的文件組織方式。即使主文件關鍵字有序，但因磁盤是以盤組、柱面和磁道（盤面）三級地址存取的設備，因此通常對磁盤上的數據文件建立盤組、柱面和磁道（盤面）三級索引。在ISAM文件上檢索記錄時，先從主索引（柱面索引的索引）找到相應柱面索引。再從柱面索引找到記錄所在柱面的磁道索引，最后從磁道索引找到記錄所在磁道的第一個記錄的位置，由此出發(fā)在該磁道上進行順序查找直到查到為止；反之，若找遍該磁道而未找到所查記錄，則文件中無此記錄。
　　
　　6．分析ISAM文件（INDEXED SEQUENTIAL ACCESS METHORD）和VSAM文件（VIRTUAL STORAGE ACCESS METHORD）的應用場合、優(yōu)缺點等?！?a target="_blank">華南理工大學 2001 一、4 （4分）】

　　【參考答案】

　　ISAM是一種專為磁盤存取設計的文件組織形式，采用靜態(tài)索引結構，對磁盤上的數據文件建立盤組、柱面、磁道三級索引。ISAM文件中記錄按關鍵字順序存放，插入記錄時需移動記錄并將同一磁道上最后的一個記錄移至溢出區(qū)，同時修改磁道索引項，刪除記錄只需在存儲位置作標記，不需移動記錄和修改指針。經過多次插入和刪除記錄后，文件結構變得不合理，需周期整理ISAM文件。

　　VSAM文件采用B+樹動態(tài)索引結構，文件只有控制區(qū)間和控制區(qū)域等邏輯存儲單位，與外存儲器中柱面、磁道等具體存儲單位沒有必然聯系。VSAM文件結構包括索引集、順序集和數據集三部分，記錄存于數據集中，順序集和索引集構成B+樹，作為文件的索引部分可實現順鏈查找和從根結點開始的隨機查找。
　　與ISAM文件相比，VSAM文件有如下優(yōu)點：動態(tài)分配和釋放存儲空間，不需對文件進行重組；能保持較高的查找效率，且查找先后插入記錄所需時間相同。因此，基于B+樹的VSAM文件通常作為大型索引順序文件的標準組織。
　　
　　7．一個ISAM文件除了主索引外，還包括哪兩級索引？【北京科技大學 1999 一、8（2分）】

　　【參考答案】

　　ISAM文件有三級索引：磁盤組、柱面和磁盤，柱面索引存放在某個柱面上，若柱面索引較大，占多個磁道時，可建立柱面索引的索引—主索引。故本題中所指的兩級索引是盤組和磁道。