第八章 查找(3)

第八章 查找

树都可以用于文件的索引结构
D．B-树和B+树都能有效地支持随机检索
(19)下面的命题中，不成立的是 。
A．m阶B-树中的每一个分支结点的子树的数量都小于或等于m。
B．m阶B-树中的每一个分支结点的子树的数量都大于或等于m／2上取整
C．m阶B-树中的任何一个结点的子树的深度都相等。
D．m阶B-树中有k个子树的分支结点包含k-1个关键字。
(20)评价散列函数质量好坏的标准是--。
A．函数是否简单 B．计算是否快
C．是否是解析式 D．函数的取值是否均匀
(21)在一个初始状态为空的散列表中依次插入关键字序列(MON，TUE，WED，THU，FRI， SAT，SUN)，散列函数为H(key)：i％7，其中，i为关键字key的第一个字母在英文字母表中的序号，地址值域为[0：6]，采用线性再散列法处理冲突。
(22)在具有n个元素的序列中进行查找，平均查找长度为O(n)的方法是--。
A．顺序查找方法 B．散列查找方法
C．分块查找方法 D．树型查找方法
9．3 填空题。
(1)文件的逻辑结构是指--，文件的物理结构是指--。
(2)文件在物理结构中通常有--、--和--三种组织方式。
(3)文件的关键字是--。
(4)文件最基本操作是 和 。
(5)对线性表采用折半查找方法，该线性表必须采用--存储结构，并且--。
(6)在按值有序的线性表(5，8，11，12，15，20，32，41，57)中采用折半查找法查找20需要进行--次元素间的比较。
(7)具有n个结点的判定树的深度h = -- 。
(8)若每个记录的查找概率相等，则在具有n个记录的顺序文件中采用顺序查找法的平均查 找长度ASL=--。
(9)在具有n个记录的排序连续顺序文件中采用折半查找法的平均查找长度ASL=？
(10)索引文件的索引表中的一个索引项是--之间的对照关系。
(11)索引文件包括--和--两个部分。
(12)索引表的特点是--，并且--。
(13)在索引文件中查找一个记录的过程是先查--，然后--。
(14)具有144项的表分成--块最好，若每块的最佳长度为8，则平均查找长度为--
(15)在3阶B-树上，每个分支结点包含的子树的数目最多为--，最少为--。
(16)一棵B+树上通常有两个头指针(即查找的人口指针)，其中一个指向--，另一个指向--。
(17)散列函数建立了--之间的对应关系。
(18)设计一个散列表通常应包括三个内容，分别是--、-
-和--。
(19)一个好的散列函数是指--。处理冲突的方法通常有--、--和--一O
(20)一个待散列存储的线性表为K二(18，25，63，50，42，32，9)，散列函数为H(k)：k％9，则与元素18发生冲突的元素有--个。
9．4 试叙述索引顺序文件与顺序文件相比较的优