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

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

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

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

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

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

6、（6）的索弓佟勾，m階B+樹每個(gè)結(jié)點(diǎn)至 多有_（7 ） _個(gè)兒子，除根結(jié)點(diǎn)外每個(gè)結(jié)點(diǎn)至少有 （8）個(gè)兒子，根結(jié)點(diǎn)至少有（9）個(gè)兒子, 有k個(gè)兒子的結(jié)點(diǎn)必有（10 ）個(gè)關(guān)鍵碼。【山東工業(yè)大學(xué)1996 、4 （5分）】.文件由 組成；記錄由 組成。【大連海事大學(xué) 1996 （2分）】5。物理記錄之間的次序由指針相鏈表示的順序文件稱為 .【燕山大學(xué)1998 一、11 （1分）】6.順序文件中，要存取第I個(gè)記錄，必須先存取 個(gè)記錄。【哈爾濱工業(yè)大學(xué) 2001 一、4 （ 2分）】7。索引順序文件既可以順序存取，也可以 存取。【武漢大學(xué)2000 一、108。建立索引文件的目的是 。【中山大學(xué)1998 、

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

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

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

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

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

12、授007劉光系主任教授008黃兵教員講師009李民室主任教授010 趙松教員副教授【北京航空航天大學(xué) 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)隨機(jī)組織記錄 數(shù)據(jù)項(xiàng)提高查找速度數(shù)據(jù)庫 (2)文本m2(3)(8)單關(guān)鍵字文件多關(guān)鍵字文件. (1)關(guān)鍵字.構(gòu)造散列函數(shù)59(2)記錄號(hào)順序組織m/2.串聯(lián)文件.樹(3)記錄號(hào)解決沖突的方法10(413(4)隨機(jī)組織2.第 I 1.檢索記錄快(5)鏈組織k7.隨機(jī)順序 (5)直接.索引集 順序集 數(shù)據(jù)集14.分配和釋放

13、存儲(chǔ)空間重組 對(duì)插入的記錄四.應(yīng)用題.文件是由大量性質(zhì)相同的記錄組成的集合，按記錄類型不同可分為操作系統(tǒng)文件和數(shù)據(jù)庫文件。.文件的基本組織方式有順序組織、索引組織、散列組織和鏈組織。文件的存儲(chǔ)結(jié)構(gòu) 可以采用將基本組織結(jié)合的方法 ，常用的結(jié)構(gòu)有順序結(jié)構(gòu)、索引結(jié)構(gòu)、散列結(jié)構(gòu)。(1)順序結(jié)構(gòu)，相應(yīng)文件為順序文件，其記錄按存入文件的先后次序順序存放。順序文件本質(zhì)上就是順序表。若邏輯上相鄰的兩個(gè)記錄在存儲(chǔ)位置上相鄰，則為連續(xù)文件；若記錄之間以指針相鏈接，則稱為串聯(lián)文件。順序文件只能順序存取，要更新某個(gè)記錄，必須復(fù)制整個(gè)文件。順序文件連續(xù)存取的速度快，主要適用于順序存取，批量修改的情況。(2)帶索引的結(jié)構(gòu)

14、，相應(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é)省存儲(chǔ)空間。不能順序存取，只能隨機(jī)存取。其它文件均由以上文件派生而得。文件采用何種存儲(chǔ)結(jié)構(gòu)應(yīng)綜合考慮各種因素，如：存儲(chǔ)介質(zhì)類型、記錄的類型、大小和關(guān)鍵字的數(shù)目以及對(duì)文件作何種操作.在主文件外，再建立索引表指示關(guān)鍵字及其物理記錄的地址間一一對(duì)應(yīng)關(guān)系。這種

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

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

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

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

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

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