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

习题十 文件一、单项选择题1索引无序文件是指（ ）。A. 主文件无序，索引表有序 B. 主文件有序，索引表无序 C. 主文件有序，索引表有序 D. 主文件无序，索引表无序2. 散列文件使用散列函数将记录的关键字值计算转化为记录的存放地址，因为散列函数是一对一的关系，则选择好的（ ）方法是散列文件的关键。A. 散列函数 B. 除余法中的质数 C. 冲突处理 D. 散列函数和冲突处理3下述文件中适合于磁带存储的是（ ）。 A. 顺序文件 B. 索引文件 C. 散列文件 D. 多关键字文件4. ISAM文件和VASM文件属于（ ）。 A. 索引非顺序文件 B. 索引顺序文件 C. 顺序文件 D. 散列文件5倒排文件的主要优点是（ ）。A. 便于进行插入和删除运算 B. 便于进行文件的合并 C. 能大大提高次关键字的查找速度 D. 能大大节省存储空间二、填空题1. 文件可按其记录的类型不同而分成两类，即_和_文件。2. 数据库文件按记录中关键字的多少可分成_和_两种文件。3. 文件由_组成；记录由_组成。4. 顺序文件中，要存取第I个记录，必须先存取_个记录。5. 索引顺序文件既可以顺序存取，也可以_存取。6. 散列检索技术的关键是_和 _。7. VSAM(虚拟存储存取方法)文件的优点是：动态地_，不需要文件进行_，并能较快地_进行查找。三、应用题1. 什么是索引顺序文件？ 2. 试比较顺序文件，索引非顺序文件，索引顺序文件，散列文件的存储代价，检索，插入，删除记录时的优点和缺点。3已知职工文件中包括职工号、职工姓名、职务和职称4个数据项（见下表）。职务有校长、系主任、室主任和教员；校长领导所有系主任，系主任领导他所在系的所有室主任，室主任领导他所在室的全体教员；职称有教授、副教授和讲师3种。请在职工文件的数据结构中设置若干指针和索引，以满足下列两种查找的需要：（1） 能够检索出全体职工间领导与被领导的情况；（2） 能够分别检索出全体教授、全体副教授、全体讲师。要求指针数量尽可能少，给出各指针项索引的名称及含义即可。表 职工文件职工号职工姓名职务职称001002003004005006007008009010张军沈灵叶明张莲叶宏周芳刘光黄兵李民赵松教员系主任校长室主任系主任教员系主任教员室主任教员讲师教授教授副教授教授教授教授讲师教授副教授参考文献1严蔚敏等 数据结构 北京：清华大学出版社，1997.42殷人昆 数据结构 北京：清华大学出版社，2001.33李春葆 数据结构习题与解析 北京：清华大学出版社，20034前沿考试研究室 计算机专业研究生入学考试全真题解-数据结构与程序设计分册 北京：人民邮电出版社，2003.65何军等 数据结构500题 北京：人民邮电出版社，2003.46徐孝凯 数据结构辅导与提高 北京：清华大学出版社，2003.12第十一章 文件一、单项选择题1A2. D3A4. B5C二、填空题1. 操作系统文件 数据库2. 单关键字文件 多关键字文件3. 记录 数据项4. 第I-15. 随机6. 构造散列函数 解决冲突的方法7. 分配和释放存储空间 重组 对插入的记录三、应用题1. 在索引文件中，若（数据区）主文件中关键字有序，则文件称为索引顺序文件。索引顺序文件因主文件有序，一般用稀疏索引，占用空间较少。常用索引顺序文件有ISAM和VSAM。ISAM采用静态索引结构，而VSAM采用B+树的动态索引结构。2（1）顺序文件只能顺序查找，优点是批量检索速度快，不适于单个记录的检索。顺序文件不能象顺序表那样插入、删除和修改，因文件中的记录不能象向量空间中的元素那样“移动”，只能通过复制整个文件实现上述操作。（2）索引非顺序文件适合随机存取，不适合顺序存取，因主关键字未排序，若顺序存取会引起磁头频繁移动。索引顺序文件是最常用的文件组织，因主文件有序，既可顺序存取也可随机存取。索引非顺序文件是稠密索引，可以“预查找”，索引顺序文件是稀疏索引，不能“预查找”，但由于索引占空间较少，管理要求低，提高了索引的查找速度。（3）散列文件也称直接存取文件，根据关键字的散列函数值和处理冲突的方法，将记录散列到外存上。这种文件组织只适用于像磁盘那样的直接存取设备，其优点是文件随机存放，记录不必排序，插入、删除方便，存取速度快，无需索引区，节省存储空间。缺点是散列文件不能顺序存取，且只限于简单查询。经多次插入、删除后，文件结构不合理，需重组文件，这很费时。3问题分析在职务项中增加一个指针项，指向其领导者。因题目中未提出具体的隶属关系，如哪个系的系主任，哪个系哪个室的室主任，哪个室的教员等。这里假设每个室主任隶属于他前边离他最近的那个系主任，每个教员隶属于他前边离他最近的那个室主任，见下面多重表文件。在职称项中增加一个指针项，指向同一职称的下一个职工，增加一个次关键字索引表： 关键字头指针长度讲师 001 2 副教授 004 2 教授 002 6 “职称”索引表记录号职工号职工姓名职务职称010203040506070809100010020030040050060070080