5.2 动态查找法

5.2 动态查找法

考试大纲涉及本节的知识点有：B-树、二叉排序树和平衡二叉树。

选择题

　　1．选择题题目部分
　　● 下列关于B-树的描述中错误的是 （1） 。
　　（1）A．m阶B-树每个节点的后件数都小于等于m
　　　　 B．m阶B-树每个节点的后件数都小于等于[m/2]
　　　　 C．m阶B-树具有k个后件的非叶子节点含有k-1个键值
　　　　 D．m阶B-树的任意一个节点的左右子树都相等
　　● 在一棵含有n个关键字的m阶B-树中进行查找，至多读盘 （2） 次。
　　（2）A．O( log₂ⁿ) B．O(log₂ⁿ )+1 C．1+log_[m/2]^n+1/2 D． 1+log_[n/2]^m+1/2
　　● 下面关于B-和B+树的叙述中，不正确的是 （3） 。
　　（3）A．B-树和B+树都是平衡的多叉树
　　　　 B．B-树和B+树都可用于文件的索引结构
　　　　 C．B-树和B+树都能有效地支持顺序检索
　　　　 D．B-树和B+树都能有效地支持随机检索
　　● 在平衡二叉树中插入一个节点后造成了不平衡，设最低（最接近叶子）的不平衡节点为A，并已知A的左孩子的平衡因子为0，右孩子的平衡因子为1，则应作 （4） 型调整以使其平衡。
　　（4）A．LL　B．LR　C．RL　D．RR
　　● 如果按关键码值递增的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为 （5） 。
　　（5）A．n/2　B．(n+1)/2　C．(log₂ⁿ⁺¹) 　D．log₂ⁿ
　　2．选择题练习的答案与分析
　　题号 （1）
　　答案 B
　　习题分析：
　　根据B-树的定义，m阶B-树中，除根节点和叶子节点外，每个节点的后件数都大于等于[m 2]。但是，叶子节点没有后件，根节点至少有两个后件，除非它同时又是叶子节点。
　　题号 （2）
　　答案 C
　　习题分析：
　　B-树一般用于文件系统的存储，通常每个节点的数据在磁盘上以一个块来存储，每个块读盘一次。根据B-树的查找分析，在含有n个关键码的B-树上进行查找时，从根节点到关键码所在节点的路径上涉及的节点数不超过log_[m/2]^n+1/2+1。
　　题号 （3）
　　答案 C
　　习题分析：
　　B+树的叶子节点中包含了全部关键码信息，且按增序排序，而B-树并不支持顺序检索。
　　题号 （4）
　　答案 C
　　习题分析：
　　平衡因子是左子树深度减去右子树的深度的差值。根据题意分析，在插入后A的右孩子平衡因子为1（即右孩子的左子树要比右子树深1），节点A的平衡因子为-1，在A节点的右孩子的左子树上插入一个节点，使得节点A右孩子的平衡因子由1变成2，从而造成节点A的平衡因子由-1变成-2，破坏了原来的平衡，因此要做先右后左旋（RL）型调整。
　　题号 （5）
　　答案 B
　　习题分析：
　　根据题意，以关键码递增的顺序将关键码插入二叉排序树中，则构造的是一棵右单支的树，这时的检索退变成有序表的顺序查找，平均比较次数为(n+1)/2。
　　3．训练自测表（如表5-3所示）

表5-3 应用题练习自测表