《數(shù)據(jù)結(jié)構(gòu)》期末考試復習題第11章

1、第十一章文件一、選擇題散列文件使用散列函數(shù)將記錄的關(guān)鍵字值計算轉(zhuǎn)化為記錄的存放地址 , 因為散列函數(shù)是一對一的關(guān)系， 則選擇好的 （ ） 方法是散列文件的關(guān)鍵 . 【哈爾濱工業(yè)大學2001 二、 5 （2分） 】A。 散列函數(shù)B 。 除余法中的質(zhì)數(shù)C. 沖突處理D 。 散列函數(shù)和沖突處順序文件采用順序結(jié)構(gòu)實現(xiàn)文件的存儲，對大型的順序文件的少量修改，要求重新復制整個文件 , 代價很高， 采用 （ ）的方法可降低所需的代價。 【北京郵電大學 2000 二、 8（20/8 分） 】A. 附加文件B 。 按關(guān)鍵字大小排序C 。 按記錄輸入先后排序D. 連續(xù)排序用ISAM組織文件適合于（）?！局锌圃很浖?/p>

2、所1998 】A 磁帶B 磁盤下述文件中適合于磁帶存儲的是（ ）。 【中科院計算所 2000 一、 7（2 分） 】A 。 順序文件 B. 索引文件 C. 散列文件D. 多關(guān)鍵字文件用ISAM和VSAM1織文彳屬于（）。A。 順序文件B.索引文件C. 散列文件【中國科技大學1998 二、 5（2 分） 中科院計算所 1998 二、 5（ 2 分） 】ISAM文件和VASMt件屬于（）。【山東大學2001二、5（1分）】A. 索引非順序文件B 。 索引順序文件C 。 順序文件D. 散列文件B+ 樹應用在（ ） 文件系統(tǒng)中。 【北京郵電大學 2001 一、 1 （ 2 分） 】A. ISAM B.

3、 VSAM二、判斷題文件是記錄的集合， 每個記錄由一個或多個數(shù)據(jù)項組成 , 因而一個文件可看作由多個記錄組成的數(shù)據(jù)結(jié)構(gòu)。 【長沙鐵道學院 1998 一、 5 （1 分） 】倒排文件是對次關(guān)鍵字建立索引 . 【南京航空航天大學 1997 一、 10 （ 1 分 ） 】倒排序文件的優(yōu)點是維護簡單。 【南京航空航天大學1995 五、 10（ 1 分） 】倒排文件與多重表文件的次關(guān)鍵字索引結(jié)構(gòu)是不同的 . 【西安交通大學 1996 二、 6 （3分） 】5。Hash表與Hash文件的唯一區(qū)別是Hash文件引入了 桶的概念.【南京航空航天大學1996 六 10（1 分） 】文件系統(tǒng)采用索引結(jié)構(gòu)是為了節(jié)省

4、存儲空間。 【北京郵電大學 2000 一、 10 （ 1 分） 】對處理大量數(shù)據(jù)的外存介質(zhì)而言 , 索引順序存取方法是一種方便的文件組織方法?！緰|南大學2001 一、 1-10（ 1 分） 】8。對磁帶機而言，ISAM是一種方便的穩(wěn)健組織方法?！局锌圃很浖?997 一、10 （1分）】。 直接訪問文件也能順序訪問， 只是一般效率不高 . 【北京郵電大學2002 一、 10（ 1 分） 】. 存放在磁盤，磁帶上的文件，即可以是順序文件, 也可以是索引結(jié)構(gòu)或其他結(jié)構(gòu)類型的文件?！旧綎|大學2001 一、 7 （1 分） 】.檢索出文件中的關(guān)鍵碼值落在某個連續(xù)的范圍內(nèi)的全部記錄，這種操作稱為范圍檢索

5、。對經(jīng)常需要做范圍檢索的文件進行組織，采用散列法優(yōu)于順序檢索法?！局猩酱髮W1994 一、5 （ 2分）】三、填空題1。文件可按其記錄的類型不同而分成兩類，即 和 文件?！疚靼搽娮涌萍即髮W 1998二、6 （3分）】.數(shù)據(jù)庫文件按記錄中關(guān)鍵字的多少可分成 和 兩種文件。【燕山大學1998 一、10 （2分）】.從用戶的觀點看，文件的邏輯結(jié)構(gòu)通?？梢詤^(qū)分為兩類：一類是如dBASE中數(shù)據(jù)庫文件那樣的文件組織結(jié)構(gòu)，稱為（1）文件；另一種是諸如用各種文字處理軟件編輯成的文本文件，稱為_（2）_文件。從文件在存儲器上的存放方式來看，文件的物理結(jié)構(gòu)往往可區(qū)分為三類，即包，_（4）_和（5）。B+樹適用于組織

6、（6）的索弓佟勾，m階B+樹每個結(jié)點至 多有_（7 ） _個兒子，除根結(jié)點外每個結(jié)點至少有 （8）個兒子，根結(jié)點至少有（9）個兒子, 有k個兒子的結(jié)點必有（10 ）個關(guān)鍵碼?！旧綎|工業(yè)大學1996 、4 （5分）】.文件由 組成；記錄由 組成?！敬筮B海事大學 1996 （2分）】5。物理記錄之間的次序由指針相鏈表示的順序文件稱為 .【燕山大學1998 一、11 （1分）】6.順序文件中，要存取第I個記錄，必須先存取 個記錄?！竟枮I工業(yè)大學 2001 一、4 （ 2分）】7。索引順序文件既可以順序存取，也可以 存取?！疚錆h大學2000 一、108。建立索引文件的目的是 ?！局猩酱髮W1998 、

7、12 （1分）】9。索引順序文件是最常用的文件組織之一，通常用 結(jié)構(gòu)來組織索引?！鹃L沙鐵道學院 1998 二、6（2 分）】10.倒排序文件的主要優(yōu)點在于 ?！旧綎|工業(yè)大學1995、3（1分）】11。檢索是為了在文件中尋找滿足一定條件的記錄而設置的操作。檢索可以按 檢索，也可以按 檢索；按 檢索又可以有 檢索和 檢索.【山東大學1999 一、1 （5 分）】12。散列檢索技術(shù)的關(guān)鍵是 和.【山東工業(yè)大學1995 、2 （2分）】VSAM系統(tǒng)是由、構(gòu)成的.【北京科技大學1997 、9VSAM（虛擬存儲存取方法）文件的優(yōu)點是：動態(tài)地 ,不需要文件進行 ，并能 較快地 進行查找.【山東大學2001三

8、、4 （2分）】四、應用題.文件【山東工業(yè)大學 1998 、11（2分）】.文件存儲結(jié)構(gòu)的基本形式有哪些？ 一個文件采用何種存儲結(jié)構(gòu)應考慮哪些因素？【燕山大學1999二、4 （4分）】.名詞解釋：索引文件【哈爾濱工業(yè)大學 2000 、4 （3分）】4。什么是索引順序文件？【哈爾濱工業(yè)大學2001三、5 （3分）】【山東工業(yè)大學1998 、1-2（2分）】.索引順序存取方法（ISAM）中，主文件已按關(guān)鍵字排序，為何還需要主關(guān)鍵字索引？【東南大學1995四（6分）】. 分析 ISAM文件（INDEXEDSEQUENTIAACCESMETHOR歷）VSAMt件（VIRTUAL STORAGEACCE

9、SS METHO RD應用場合、優(yōu)缺點等?！救A南理工大學2001 、4 （4分）】. 一個ISAM文件除了主索引外，還包括哪兩級索引？【北京科技大學1999 一、8（2分）】.倒排文件 【山東工業(yè)大學1998 一、13（2分）】。 為什么在倒排文件（inverted files） 組織中，實際記錄中的關(guān)鍵字域 （key fields ）可 刪除以節(jié)約空間？而在多表（multilists ）結(jié)構(gòu)中這樣做為什么要犧牲性能？【東南大學1997 一、4 （8 分）.簡單比較文件的多重表和倒排表組織方式各自特點?！緰|南大學2000一、2（6分）】11。組織待檢索文件的倒排表的優(yōu)點是什么？【北京科技大學2

10、001 一、10 （2分）】.為什么文件的倒排表比多重表組織方式節(jié)省空間？【東南大學2001一、2（1分）】.試比較順序文件，索引非順序文件，索引順序文件，散列文件的存儲代價，檢索，插入，刪除記錄時的優(yōu)點和缺點.【西北工業(yè)大學1999四（8分）】14。已知兩個各包含 N和M個記錄的排好序的文件能在 O（N+M時間內(nèi)合并為一個包含 N+M 個記錄的排好序的文件。當有多于兩個排好序的文件要被合并在一起時，只需重復成對地合并便可完成。合并的步驟不同，所需花費的記錄移動次數(shù)也不同?，F(xiàn)有文件F1,F2,F3 ,F4,F5 ,各有記錄數(shù)為20, 30, 10, 5和30,試找出記錄移動次數(shù)最少的合并步驟。

11、【重慶大學2000二、3】15.已知職工文件中包括職工號、職工姓名、職務和職稱4個數(shù)據(jù)項（見下表）。職務有校長、系主任、室主任和教員；校長領(lǐng)導所有系主任，系主任領(lǐng)導他所在系的所有室主任，室主任領(lǐng)導 他所在室的全體教員；職稱有教授、副教授和講師3種。請在職工文件的數(shù)據(jù)結(jié)構(gòu)中設置若干指針和索引，以滿足下列兩種查找的需要：能夠檢索出全體職工間領(lǐng)導與被領(lǐng)導的情況；能夠分別檢索出全體教授、全體副教授、全體講師。要求指針數(shù)量盡可能少，給出各指針項索引的名稱及含義即可。表職工文件職工號職工姓名職務職稱001張軍教員講師002沈靈系主任教授003葉明校長教授004張蓮室主任副教授005系主任教授006喃教員教

12、授007劉光系主任教授008黃兵教員講師009李民室主任教授010 趙松教員副教授【北京航空航天大學 1996】第十一章文件選擇題1。D 2。A 3.B4。A 5。B 6。B 7.B二。判斷題2 3。XXxXxx 10. x11。V.填空題1 .8.操作系統(tǒng)文件(1)數(shù)據(jù)庫(6)隨機組織記錄 數(shù)據(jù)項提高查找速度數(shù)據(jù)庫 (2)文本m2(3)(8)單關(guān)鍵字文件多關(guān)鍵字文件. (1)關(guān)鍵字.構(gòu)造散列函數(shù)59(2)記錄號順序組織m/2.串聯(lián)文件.樹(3)記錄號解決沖突的方法10(413(4)隨機組織2.第 I 1.檢索記錄快(5)鏈組織k7.隨機順序 (5)直接.索引集 順序集 數(shù)據(jù)集14.分配和釋放

13、存儲空間重組 對插入的記錄四.應用題.文件是由大量性質(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)，相應文件為順序文件，其記錄按存入文件的先后次序順序存放。順序文件本質(zhì)上就是順序表。若邏輯上相鄰的兩個記錄在存儲位置上相鄰，則為連續(xù)文件；若記錄之間以指針相鏈接，則稱為串聯(lián)文件。順序文件只能順序存取，要更新某個記錄，必須復制整個文件。順序文件連續(xù)存取的速度快，主要適用于順序存取，批量修改的情況。(2)帶索引的結(jié)構(gòu)

14、，相應文件為索引文件。索引文件包括索引表和數(shù)據(jù)表，索引表中 的索引項包括數(shù)據(jù)表中數(shù)據(jù)的關(guān)鍵字和相應地址，索引表有序，其物理順序體現(xiàn)了文件的邏輯次序，實現(xiàn)了文件的線性結(jié)構(gòu)。索引文件只能是磁盤文件，既能順序存取，又能隋機存取。(3)散列結(jié)構(gòu)，也稱計算尋址結(jié)構(gòu)，相應文件稱為散列文件，其記錄是根據(jù)關(guān)鍵字值經(jīng)散列函數(shù)計算確定其地址，存取速度快，不需索引，節(jié)省存儲空間。不能順序存取，只能隨機存取。其它文件均由以上文件派生而得。文件采用何種存儲結(jié)構(gòu)應綜合考慮各種因素，如：存儲介質(zhì)類型、記錄的類型、大小和關(guān)鍵字的數(shù)目以及對文件作何種操作.在主文件外，再建立索引表指示關(guān)鍵字及其物理記錄的地址間一一對應關(guān)系。這種

15、 由索引表和主文件一起構(gòu)成的文件稱為索引文件.索引表依關(guān)鍵字有序。主文件若按關(guān)鍵字有序稱為索引順序文件，否則稱為索引非順序文件 (通常簡稱索引文件)。索引順序文件因主 文件有序，一般用稀疏索引，占用空間較少.常用索引順序文件有ISAM和VSAM ISAM采用靜 態(tài)索引結(jié)構(gòu)，而 VSA怵用B+樹的動態(tài)索引結(jié)構(gòu)。索引文件既能順序存取，也能隨機存取。.在索引文件中，若(數(shù)據(jù)區(qū))主文件中關(guān)鍵字有序，則文件稱為索引順序文件，參見上題3 。 ISAM 是專為磁盤存取設計的文件組織方式. 即使主文件關(guān)鍵字有序，但因磁盤是以盤組、柱面和磁道（ 盤面 ） 三級地址存取的設備， 因此通常對磁盤上的數(shù)據(jù)文件建立盤組

16、、 柱面和磁道（盤面）三級索引.在ISAM文件上檢索記錄時，先從主索引（柱面索引的索引）找到相應柱面索引。再從柱面索引找到記錄所在柱面的磁道索引 , 最后從磁道索引找到記錄所在 磁道的第一個記錄的位置, 由此出發(fā)在該磁道上進行順序查找直到查到為止；反之，若找遍該磁道而未找到所查記錄, 則文件中無此記錄. ISAM是一種專為磁盤存取設計的文件組織形式，采用靜態(tài)索引結(jié)構(gòu)，對磁盤上的數(shù)據(jù)文件建立盤組、柱面、磁道三級索引 .ISAM 文件中記錄按關(guān)鍵字順序存放，插入記錄時需移動記錄并將同一磁道上最后的一個記錄移至溢出區(qū)， 同時修改磁道索引項， 刪除記錄只需在存儲位置作標記，不需移動記錄和修改指針 .

17、經(jīng)過多次插入和刪除記錄后，文件結(jié)構(gòu)變得 不合理，需周期整理ISAM文件。VSAMt件采用B+樹動態(tài)索引結(jié)構(gòu)，文件只有控制區(qū)間和控制區(qū)域等邏輯存儲單位，與 外存儲器中柱面、磁道等具體存儲單位沒有必然聯(lián)系。VSAM文件結(jié)構(gòu)包括索引集、順序集和數(shù)據(jù)集三部分，記錄存于數(shù)據(jù)集中，順序集和索引集構(gòu)成B+樹，作為文件的索引部分可實現(xiàn)順鏈查找和從根結(jié)點開始的隨機查找。與ISAM文件相比，VSAMC件有如下優(yōu)點：動態(tài)分配和釋放存儲空間，不需對文件進行 重組；能保持較高的查找效率，且查找先后插入記錄所需時間相同。因此，基于B+樹的VSAM文件通常作為大型索引順序文件的標準組織。. ISAM文件有三級索引：磁盤組、

18、柱面和磁盤，柱面索引存放在某個柱面上，若柱面 索引較大， 占多個磁道時， 可建立柱面索引的索引 - 主索引 . 故本題中所指的兩級索引是盤組 和磁道。8倒排文件是一種多關(guān)鍵字的文件，主數(shù)據(jù)文件按關(guān)鍵字順序構(gòu)成串聯(lián)文件，并建立主關(guān)鍵字索引。對次關(guān)鍵字也建立索引 , 該索引稱為倒排表。倒排表包括兩項，一項是次關(guān)鍵字， 另一項是具有同一次關(guān)鍵字值的記錄的物理記錄號 （若數(shù)據(jù)文件非串聯(lián)文件， 而是索 引順序文件-如ISAM,則倒排表中存放記錄的主關(guān)鍵字而不是物理記錄號）。倒排表作索引的優(yōu)點是索引記錄快，缺點是維護困難。在同一索引表中，不同的關(guān)鍵字其記錄數(shù)不同 , 各 倒排表的長度不同，同一倒排表中各項

19、長度也不相等.9因倒排文件組織中，倒排表有關(guān)鍵字值及同一關(guān)鍵字值的記錄的所有物理記錄號，可方便地查詢具有同一關(guān)鍵字值的所有記錄；而多重表文件中次關(guān)鍵字索引結(jié)構(gòu)不同 , 刪除 關(guān)鍵字域后查詢性能受到影響。多重表文件是把索引與鏈接結(jié)合而形成的組織方式。 記錄按主關(guān)鍵字順序構(gòu)成一個串聯(lián)文件，建立主關(guān)鍵字的索引（主索引） 。對每一次關(guān)鍵字建立次關(guān)鍵字索引，具有同一關(guān)鍵字的記錄構(gòu)成一個鏈表。主索引為非稠密索引，次索引為稠密索引 , 每個索引項包括次 關(guān)鍵字，頭指針和鏈表長度。多重表文件易于編程，也易于插入，但刪除繁鎖。需在各次關(guān) 鍵字鏈表中刪除。倒排文件的特點見上面題8。倒排表作索引的優(yōu)點是索引記錄快，

20、 因為從次關(guān)鍵字值直接找到各相關(guān)記錄的物理 記錄號， 倒排因此而得名 （因通常的查詢是從關(guān)鍵字查到記錄） . 在插入和刪除記錄時, 倒排表隨之修改，倒排表中具有相同次關(guān)鍵字的記錄號是有序的。12排表有兩項，一是次關(guān)鍵字值， 二是具有相同次關(guān)鍵字值的物理記錄號，這些記錄 號有序且順序存儲，不使用多重表中的指針鏈接，因而節(jié)省了空間 .13 （ 1）順序文件只能順序查找, 優(yōu)點是批量檢索速度快， 不適于單個記錄的檢索。 順序文件不能象順序表那樣插入、 刪除和修改， 因文件中的記錄不能象向量空間中的元素那樣 “移 動” ，只能通過復制整個文件實現(xiàn)上述操作。(2)索引非順序文件適合隨機存取，不適合順序存取，因主關(guān)鍵字未排序，若順序存取會引起磁頭頻繁移動.索引順序文件是最常用的文件組織 ，因主文件有序，既可順序