25版王道数据结构课后习题详细分析第七章 7.4 B树和B+树

本文主要是介绍25版王道数据结构课后习题详细分析第七章 7.4 B树和B+树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、单项选择题

————————————————————

解析：关键字数目比子树数目少1，首先可排除B+树。对于4阶B树，根结点至少有⒉棵子树(关键字数至少为1)，其他非叶结点至少有n/2]=2棵子树(关键字数至少为1)至多有4棵子树(关键字数至多为3)。5阶B树和6阶B树的分析也类似。题目所示的B树，同时满足4阶B树、5阶B树和6阶B树的要求，因此不能确定是哪种类型的B树。

正确答案：

————————————————————

解析：除根结点外的所有非叶结点至少有m/2]棵子树。对于根结点，最多有m棵子树，若其不是叶结点，则至少有⒉棵子树。

正确答案：

————————————————————

解析：

正确答案：

————————————————————

解析：由于B树每个结点内的关键字个数最多为m-1，所以当关键字个数大于m-1时，则应该分裂。每个结点内的关键字个数至少为m/27-1个，所以当关键字个数少于「m/27-1时，则可能与其他结点合并（除非只有根结点)。若将本题题干改为B+树，请读者思考上述问题的解答。

正确答案：

————————————————————

解析：B树的叶结点对应查找失败的情况，对有n个关键字的查找集合进行查找，失败可能性有n+1种。

正确答案：

————————————————————

解析：由m阶B树的性质可知,根结点至少有2棵子树;根结点外的所有非终端结点至少有[m/2棵子树，结点数最少时，3阶B树形状至少类似于一棵满二叉树，即高度为5的B树至少有23-1=31个结点。由于每个结点最多有m棵子树，所以当结点数最多时,3阶B树形状类似于满三叉树，结点数为(35-1)/2=121(注意，这里求的是结点数而非关键字数，若求的是关键字数，则还应把每个结点中关键字数的上下界确定出来)。

正确答案：

————————————————————

解析：除根结点外，m阶B树中的每个非叶结点至少有「m/2]-1个关键字，根结点至少有一个关键字，所以总共包含的关键字最少个数=(n- 1)(「m/2-1)+1。

正确答案：

————————————————————

解析：5阶B树中共有53个关键字，由最大高度公式≤logmo]((n +1)/2)+Ⅰ得最大高度H≤loga[(53+1)/2]+1=4，即最大高度为4;由最小高度公式h≥log(n+l)得最小高度h≥log;54=25.从而最小高度为3。

正确答案：

————————————————————

解析：

正确答案：

————————————————————

解析：

B树和B+树的差异主要体现在:①结点关键字和子树的个数:②B+树非叶结点仅起索引作用;③B树叶结点关键字和其他结点包含的关键字是不重复的;④B+树支持顺序查找和随机查找，而B树仅支持随机查找。由于 B+树的所有叶结点中包含了全部的关键字信息，且叶结点本身依关键字从小到大顺序链接，因此可以进行顺序查找，而B树不支持顺序查找。B树和B+树都可用于文件索引结构，但B+树更适合做数据库索引和文件索引，因为它的磁盘读/写代价更低。

正确答案：

————————————————————

解析：

正确答案：

————————————————————

解析：m阶B树不要求将各叶结点之间用指针链接。选项D描述的实际上是B+树。

正确答案：

————————————————————

解析：

正确答案：

————————————————————

解析：

正确答案：

————————————————————

解析：关键字数量不变，要求结点数量最多，即要求每个结点中含关键字的数量最少。根据4阶B树的定义，根结点最少含1个关键字，非根结点中最少含[4/2]-1=1个关键字，所以每个结点中关键字数量最少都为1个，即每个结点都有2个分支，类似于排序二叉树，而15个结点正好可以构造一个4层的4阶B树，使得终端结点全在第四层，符合B树的定义，因此选D。

正确答案：

————————————————————

解析：由于B+树的所有叶结点中包含了全部的关键字信息，且叶结点本身依关键字从小到大顺序链接，因此可以进行顺序查找，而B树不支持顺序查找（只支持多路查找)。

正确答案：

————————————————————

解析：B+树是应文件系统所需而产生的B树的变形，前者比后者更加适用于实际应用中的操作系统的文件索引和数据库索引，因为前者的磁盘读/写代价更低，查询效率更加稳定。编译器中的词法分析使用有穷自动机和语法树。网络中的路由表快速查找主要靠高速缓存、路由表压缩技术和快速查找算法。系统一般使用空闲空间链表管理磁盘空闲块。

正确答案：

————————————————————

解析：m阶B树的基本性质:根结点以外的非叶结点最少含有m/27-1个关键字，代入m=3得到每个非叶结点中最少包含1个关键字，而根结点含有1个关键字，因此所有非叶结点都有两个孩子。此时其树形与h=5的满二叉树相同，可求得关键字最少为31个。

正确答案：

————————————————————

解析：

正确答案：

————————————————————

解析：

正确答案：

————————————————————

解析：在5阶B树中，除根结点外的非叶结点的关键字数k需要滴足2≤k≤4。当被删关键字罥不在终端结点（最底层非叶结点〉时，可以用x的前驱（或后继）关键字y来替代x，然后在相应结点中删除y。情况①:删除260，将其前驱110放入260处。删除110后的结点<100>不滴足5阶B树定义，从左兄弟中借85，将85放入根中，将根中的90移入结点<100>变为<90,100>。情况②:删除260，将其后继280 放入260处，结点<00>不满足5阶B树定义且左右兄弟都不够借，结点<300>可以和左兄弟<100,110>以及关键字280合并成一个新的结点<100.110,280.300>。情况③:在情况②中，结点<300>也可以和右兄弟<400,500>以及关键字350合并成一个新的结点<300,350,400,500>。综上，T根结点中的关键字序列可能是<60,85,110,350>或<60,90.350>或<60,90, 280>，仅D不可能。
快速解法:假如选项D的60,90,110,350作为根结点，则在90和110之间只有100这一个数据，显然不符合5阶B树的定义，因此D项不可能。

正确答案：

————————————————————

解析：B树的插入操作可能导致叶结点分裂，而叶结点分裂可能导致父结点分裂，若这个分裂过程传导到根结点，则会导致B树高度增1，Ⅰ正确。若被删结点是叶结点，则显然会导致叶结点变化;若被删结点不是叶结点，则要先将被删结点和它的前驱或后继交换，最终转换为删除叶结点,还是导致叶结点变化，正确。若在非叶结点中查找到了给定的关键字，则不用向下继续查找，IⅢ错误。插入关键字的初始位置是最底层叶结点，但可能因结点分裂而被转移到父结点中，IⅣ错误。

正确答案：

二、综合应用题

————————————————————