第十章文件习题_数据结构

《第十章文件习题_数据结构》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、习题十文件一、单项选择题1．索引无序文件是指（）。A.主文件无序，索引表有序B.主文件有序，索引表无序C.主文件有序，索引表有序D.主文件无序，索引表无序2.散列文件使用散列函数将记录的关键字值计算转化为记录的存放地址，因为散列函数是一对一的关系，则选择好的（）方法是散列文件的关键。A.散列函数B.除余法中的质数C.冲突处理D.散列函数和冲突处理3．下述文件中适合于磁带存储的是（）。A.顺序文件B.索引文件C.散列文件D.多关键字文件4.ISAM文件和VASM文件属于（）。A.索引非顺序文件B.索引顺序文件C.顺序文件D.散列文件5．倒排文件的主要优点是（）。A.便于进行插入

2、和删除运算B.便于进行文件的合并C.能大大提高次关键字的查找速度D.能大大节省存储空间二、填空题1.文件可按其记录的类型不同而分成两类，即___________和____________文件。2.数据库文件按记录中关键字的多少可分成____________和____________两种文件。3.文件由_________组成；记录由_________组成。4.顺序文件中，要存取第I个记录，必须先存取_________个记录。5.索引顺序文件既可以顺序存取，也可以_________存取。6.散列检索技术的关键是_______________和_______________。7.V

3、SAM(虚拟存储存取方法)文件的优点是：动态地_________，不需要文件进行_________，并能较快地_________进行查找。三、应用题1.什么是索引顺序文件？2.试比较顺序文件，索引非顺序文件，索引顺序文件，散列文件的存储代价，检索，插入，删除记录时的优点和缺点。3．已知职工文件中包括职工号、职工姓名、职务和职称4个数据项（见下表）。职务有校长、系主任、室主任和教员；校长领导所有系主任，系主任领导他所在系的所有室主任，室主任领导他所在室的全体教员；职称有教授、副教授和讲师3种。请在职工文件的数据结构中设置若干指针和索引，以满足下列两种查找的需要：4（1）能够检索

4、出全体职工间领导与被领导的情况；（2）能够分别检索出全体教授、全体副教授、全体讲师。要求指针数量尽可能少，给出各指针项索引的名称及含义即可。表职工文件职工号职工姓名职务职称001002003004005006007008009010…张军沈灵叶明张莲叶宏周芳刘光黄兵李民赵松…教员系主任校长室主任系主任教员系主任教员室主任教员…讲师教授教授副教授教授教授教授讲师教授副教授…4参考文献[1]严蔚敏等数据结构北京：清华大学出版社，1997.4[2]殷人昆数据结构北京：清华大学出版社，2001.3[3]李春葆数据结构习题与解析北京：清华大学出版社，2003[4]前沿考试研究室计算机专

5、业研究生入学考试全真题解----数据结构与程序设计分册北京：人民邮电出版社，2003.6[5]何军等数据结构500题北京：人民邮电出版社，2003.4[6]徐孝凯数据结构辅导与提高北京：清华大学出版社，2003.12第十一章文件一、单项选择题1．A2.D3．A4.B5．C二、填空题1.操作系统文件数据库2.单关键字文件多关键字文件3.记录数据项4.第I-15.随机6.构造散列函数解决冲突的方法7.分配和释放存储空间重组对插入的记录 三、应用题1.在索引文件中，若（数据区）主文件中关键字有序，则文件称为索引顺序文件。索引顺序文件因主文件有序，一般用稀疏索引，占用空间较少。常用索

6、引顺序文件有ISAM和VSAM。ISAM采用静态索引结构，而VSAM采用B+树的动态索引结构。2．（1）顺序文件只能顺序查找，优点是批量检索速度快，不适于单个记录的检索。顺序文件不能象顺序表那样插入、删除和修改，因文件中的记录不能象向量空间中的元素那样“移动”，只能通过复制整个文件实现上述操作。（2）索引非顺序文件适合随机存取，不适合顺序存取，因主关键字未排序，若顺序存取会引起磁头频繁移动。索引顺序文件是最常用的文件组织，因主文件有序，既可顺序存取也可随机存取。索引非顺序文件是稠密索引，可以“预查找”，索引顺序文件是稀疏索引，不能“预查找”，但由于索引占空间较少，管理要求低，

7、提高了索引的查找速度。（34）散列文件也称直接存取文件，根据关键字的散列函数值和处理冲突的方法，将记录散列到外存上。这种文件组织只适用于像磁盘那样的直接存取设备，其优点是文件随机存放，记录不必排序，插入、删除方便，存取速度快，无需索引区，节省存储空间。缺点是散列文件不能顺序存取，且只限于简单查询。经多次插入、删除后，文件结构不合理，需重组文件，这很费时。3．[问题分析]在职务项中增加一个指针项，指向其领导者。因题目中未提出具体的隶属关系，如哪个系的系主任，哪个系哪个室的室主任，哪个室的教员等。这里假设每