第十一章 文件答案

1、第十一章文件一選擇題1.D2.A3.B4.A5.B6.B7.B二.判斷題1.√2.√3.4.√5.6.7.8.9.10.11.√三填空題1操作系統(tǒng)文件數(shù)據(jù)庫(kù)2單關(guān)鍵字文件多關(guān)鍵字文件3（1）數(shù)據(jù)庫(kù)（2）文本（3）順序組織（4）隨機(jī)組織（5）鏈組織（6）隨機(jī)組織（7）m（8）?m2?（9）2（10）k4記錄數(shù)據(jù)項(xiàng)5串聯(lián)文件6第I17隨機(jī)8提高查找速度9樹10檢索記錄快11（1）關(guān)鍵字（2）記錄號(hào)（3）記錄號(hào)（4）順序（5）直接12構(gòu)造散列

2、函數(shù)解決沖突的方法13索引集順序集數(shù)據(jù)集14分配和釋放存儲(chǔ)空間重組對(duì)插入的記錄四應(yīng)用題1文件是由大量性質(zhì)相同的記錄組成的集合，按記錄類型不同可分為操作系統(tǒng)文件和數(shù)據(jù)庫(kù)文件。2文件的基本組織方式有順序組織、索引組織、散列組織和鏈組織。文件的存儲(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è)記錄在

3、存儲(chǔ)位置上相鄰，則為連續(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)

4、，也稱計(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ì)文件作何種操作。3在主文件外，再建立索引表指示關(guān)鍵字及其物理記錄的地址間一一對(duì)應(yīng)關(guān)系。這種由索引表和主文件一起構(gòu)成的文件稱為索引文件。索引表依關(guān)鍵字有序。主文件若按

5、關(guān)鍵字有序稱為索引順序文件，否則稱為索引非順序文件（通常簡(jiǎn)稱索引文件）。索引順序文件因主文件有序，一般用稀疏索引，占用空間較少。常用索引順序文件有ISAM和VSAM。ISAM采用靜態(tài)索引結(jié)構(gòu)，而VSAM采用B樹的動(dòng)態(tài)索引結(jié)構(gòu)。索引文件既能順序存取，也能隨機(jī)存取。4在索引文件中，若（數(shù)據(jù)區(qū)）主文件中關(guān)鍵字有序，則文件稱為索引順序文件，參見上題3。引起磁頭頻繁移動(dòng)。索引順序文件是最常用的文件組織，因主文件有序，既可順序存取也可隨機(jī)存取。索引

6、非順序文件是稠密索引，可以“預(yù)查找”，索引順序文件是稀疏索引，不能“預(yù)查找”，但由于索引占空間較少，管理要求低，提高了索引的查找速度。（3）散列文件也稱直接存取文件，根據(jù)關(guān)鍵字的散列函數(shù)值和處理沖突的方法，將記錄散列到外存上。這種文件組織只適用于像磁盤那樣的直接存取設(shè)備，其優(yōu)點(diǎn)是文件隨機(jī)存放，記錄不必排序，插入、刪除方便，存取速度快，無需索引區(qū)，節(jié)省存儲(chǔ)空間。缺點(diǎn)是散列文件不能順序存取，且只限于簡(jiǎn)單查詢。經(jīng)多次插入、刪除后，文件結(jié)構(gòu)不合

7、理，需重組文件，這很費(fèi)時(shí)。14類似最優(yōu)二叉樹（哈夫曼樹），可先合并含較少記錄的文件，后合并較多記錄的文件，使移動(dòng)次數(shù)減少。見下面的哈夫曼樹。15[問題分析]在職務(wù)項(xiàng)中增加一個(gè)指針項(xiàng)，指向其領(lǐng)導(dǎo)者。因題目中未提出具體的隸屬關(guān)系，如哪個(gè)系的系主任，哪個(gè)系哪個(gè)室的室主任，哪個(gè)室的教員等。這里假設(shè)每個(gè)室主任隸屬于他前邊離他最近的那個(gè)系主任，每個(gè)教員隸屬于他前邊離他最近的那個(gè)室主任，見下面多重表文件。在職稱項(xiàng)中增加一個(gè)指針項(xiàng)，指向同一職稱的下一個(gè)

8、職工，增加一個(gè)次關(guān)鍵字索引表：關(guān)鍵字頭指針長(zhǎng)度講師0012副教授0042教授0026“職稱”索引表記錄號(hào)職工號(hào)職工姓名職務(wù)職稱01020304050607080910001002003004005006007008009010張軍沈靈葉明張蓮葉宏周芳劉光黃兵李民趙松教員系主任校長(zhǎng)室主任系主任教員系主任教員室主任教員0403?02030403040709講師教授教授副教授教授教授教授講師教授副教授08030510060709???F2AF