第十章索引与散列

1、第十章索引与散列一、填空题1. 若一个待散列存储的线性表长度为n，用于散列的散列表长度为m，则m应 n，装填因子为 。2. 在散列存储中，装填因子的值越大，存取元素时发生冲突的可能性就 ，当的值越小，存取元素时发生冲突的可能性就 。3. 在线性表的散列存储中，处理冲突有 和 两类。当装填子一定时，采用链地址法解决冲突比采用开放定址法处理冲突的平均搜索长度要 。4. 已知一个待散列存储的线性表为(18、34、58、26、75、67、48、93、81)，散列函数为h(k)=k%11,若采用线性探查法解决冲突，则平均搜索长度为 ：若采用链地址法解决冲突，则平均搜索长度为 。5. 在个10阶的B-树上

2、，每个树根结点中所含的关键字数门最多允许为 个，最少允许为 个。6. 棵深度为h的B-树上,任个叶子结点所处的层数为 ，当向该B-树插入个新关键字时，为搜索插入位置需读取 个结点。7. 当向B-树中插入关键字时，可能引起结点的 ，最终可能导致整个B树的高度 ，当从B树中删除关键字时，可能引起结点 ，最终可导致整个B-树的高度 。 二、选择题 1索引顺序文件既能进行 存取，又能进行 存取，因而是最常用的文件组织方法之一，通常用 结构来组织索引。 (A)顺序 (B)分块 (C)随机 (D)二分 · (A)链表 (B)顺序表 (C)数组· (D)树 2倒排文件的主要优点是。 (A

3、)便于进行插入和删除运算 (B)便于节省存储空间 (C)便于进行文件的合并 (D)能大大地提高基于非关键字的检索速度 3对于一个大文件进行排序，要研究在外设上的排序技术，即。 (A)快速排序法 (B)内排序法 (C) 外排序法 (D)交叉排序法 4散列文件使用散列函数将记录的关键字值计算转化为记录的存放地址，因为散列函数是一对一的关系，则选择好的方法是散列文件(Hash)的关键。 (A)散列函数 (B)除余法中的质数 (C)冲突处理 (D)散列函数和冲突处理 5倒排文件包含有若干个倒排表，倒排表的内容是，倒排文件检索速度快，但修改维护较难。 (A)一个关键字值和该关键字的记录地址 (B)一个属

4、性值和该属性的一个记录地址 (C)一个属性值和该属性的全部记录的地址 (D)多个关键字值和它们相对应的某个记录的地址 6顺序文件采用顺序结构实现文件的存储，对大型文件的少量修改要求重新复制整个文件，代价很高，采用方法可降低所需的代价。 (A)附加文件 (B)按关键字大小排序 (C)按记录输入的先后排序 (D)连续存取7存放在磁盘上的链文件，也称为 表，此表指出索引文件中各记录的物理位置。 (A)关联 (B)关键字 (C)控制 (D)索引 9对于一个线性表，既要求能够进行较快的插入和删除，又要求存储结构能够反映数据元素之间的逻辑关系，则应该。(A)以顺序方式存储 (B)以链接方式存储；(C)以散

5、列方式存储 (D)以上均可10在一个3阶的B-树上，每个结点包含的子树相同，最多为 个，最少为 个。 (A)1 (B)2 (C)3 (D)411当向一棵m阶的B-树做插入操作时，若一个结点中的关键字个数等于 1 ,则必顷分裂成两个结点；当向一棵m阶的B-树做删除操作时，若一个结点的关键字个数等于 2 ，则可能需要用它的左兄弟或右兄弟结点合并成一个结点。(A)m (B)m-1 (C)m+1 (D)m+1(A)m/2 (B) m/2-1 (C) m/2+1 (D) m/2-212设散列地址空间为0-(m-1)，k为关键字，用P去除k，将余数作为k的散列地址即:h(k)=kP，为了减少发生冲突的可能

6、性，一般取P为 。 (A)小于m的最大奇数 (B)小于m的最大素数 (C)小于m的最大偶数 (D)小于m的最大合数 13设散列表表长m=14，散列函数为h(k)=k11，表中已有4个记录，如果用二次探测再散列处理冲突，关键字为49的记录的存储地址是。如果用二次探 (A)8 (B)3 (C)5 (D)9二、判断正误题 1。在磁带上的顺序文件的最后添加新的记录，不必复制整个文件。 () 2。由于磁带的价格比磁盘便宜，用磁带实现直接访问文件较为合理。 () 3。在磁带上的顺序文件中插入新的记录时，必须复制整个文件。 () 4。记录的物理结构是数据在物理存储介质上存储的方式，是数据的物理表示和组织。

7、() 5。对于满足折半检索和分块检索条件的文件而言，无论它放在何种介质上，都能进行顺序检索，折半检索和分块检索。 () 6文件是记录的集合，每个记录由一个或多个数据项组成，因而一个文件可看作由多个记录组成的数据结构。 () 7存放在磁带，磁盘上的文件，既可以是顺序文件也可以是索引结构或其他结构类型的文件。 () 8直接访问文件也可以顺序访问，但一般效率较差。 () 9索引顺序文件是一种特殊的顺序文件，因此通常放在磁带上。 () 10记录的逻辑结构是指记录在用户或用户应用程序员面前呈现的方式，是用户对数据的表示和存取方式。 ()11索引顺序文件既可以随机访问，也可以顺序访问。 ()12顺序文件是

8、利用磁带的特有性质实现的，因此顺序文件只可以存放在磁带中。 ()四、应用1设有一个职工文件： 记录地址 职工号 姓 名 性别 职 业 年龄 籍贯 月工资(元) 10032 034 刘激扬 男 教 师 29 山东720.00 10068 064 蔡晓莉 女 教 师 32 辽宁1200.00 10104 073 朱 力 男 实验员 26 广东480.00 10140 081 洪 伟 男 教 师 36 北京1400.00 10176 092 卢声凯 男 教 师 28 湖北720.00 10212 123 林德康 男 行政秘书 33 江西480.00 10248 140 熊南燕 女 教 师 27 上海 780.00 10284 175 吕 颖 女 实验员 28 江苏480.00 10320 209 袁秋慧 女 教 师 24 广东720.00其中，关键码为职工号。试根据此文件，对下列查询组织主索引和倒排索引，再写出搜索结果关键码。(1) 男性职工；(2) 月工资超过800元的职工；(3) 月工资超过平均工资的职工；(4)