數(shù)據(jù)結(jié)構(gòu)第十一章《文件》應(yīng)用題及參考答案_跨考網(wǎng)

? 1．名詞解釋：文件?！旧綎|工業(yè)大學(xué) 1998 一、1-1（2分）】

　　【參考答案】

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

　　【參考答案】

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

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

　?。?）帶索引的結(jié)構(gòu)，相應(yīng)文件為索引文件。索引文件包括索引表和數(shù)據(jù)表，索引表中的索引項包括數(shù)據(jù)表中數(shù)據(jù)的關(guān)鍵字和相應(yīng)地址，索引表有序，其物理順序體現(xiàn)了文件的邏輯次序，實(shí)現(xiàn)了文件的線性結(jié)構(gòu)。索引文件只能是磁盤文件，既能順序存取，又能隋機(jī)存取。

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

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

　　文件采用何種存儲結(jié)構(gòu)應(yīng)綜合考慮各種因素，如：存儲介質(zhì)類型、記錄的類型、大小和關(guān)鍵字的數(shù)目以及對文件作何種操作。
　　
　　3．名詞解釋：索引文件?！?a target="_blank">哈爾濱工業(yè)大學(xué) 2000 一、4 （3分）】

　　【參考答案】

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

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

　　【參考答案】

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

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

　　【參考答案】

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

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

　　【參考答案】

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