数据结构之B树题解

选择题

题目 1：

下图所示是一棵( )。

选项： A. 4阶B树
B. 4阶B+树
C. 3阶B树
D. 3阶B+树

答案：A. 4阶B树

解释：
关键字数量比子树数量少1，所以不是 B+树，而是B树。又因为m阶B树结点关键字数最多为m-1，有一个结点关键字个数为3，所以不可能为3阶，因此答案是A。

题目 2：

下列关于 m 阶 B 树的说法中，错误的是( )。

选项：
A. 根结点至多有 m 棵子树
B. 所有叶结点都在同一层次上
C. 非叶结点至少有 $ $ (m 为偶数) 或 $ $ (m 为奇数) 棵子树
D. 根结点中的数据是有序的

答案：C

解释：

在 m 阶 B 树中，所有非叶结点的关键字数量和子树数量是有明确要求的：

A：根结点至多有 m 棵子树，这是正确的，因为根结点可以包含的子树数量不超过 m。
B：所有叶结点都在同一层次上，这是 B 树的基本特性之一，确保了树的平衡性。
C：此选项是错误的。非叶结点至少应该有 $ $ 棵子树，而不是 $ $。这是因为当 m 为偶数时，非叶结点的子树数至少为 $ $，当 m 为奇数时，至少为 $ $ 棵子树。根结点可以少于两个子树（例如在树的构造初期），但其他非叶结点不能少于这个数量。
D：根结点中的数据是有序的，这也是 B 树的特性之一，所有关键字按升序排列。

因此，正确答案是 C。

题目 3：

以下关于 m 阶 B 树的说法中，正确的是( )。

I. 每个结点至少有两棵非空子树
II. 树中每个结点至多有 $m-1$ 个关键字
III. 所有叶结点在同一层
IV. 插入一个元素引起 B 树结点分裂后，树长高一层

选项：
A. I、III
B. II、III
C. I、IV
D. I、II、IV

答案：B. II、III

解释：

I. 每个结点至少有两棵非空子树
- 错误。根结点的情况特殊，它可以只有一棵子树（在树的最初构造时），而且对于非根的内部结点，最少也需要 $ $ 棵子树。对于 m 阶 B 树，只有在根结点时，才可能存在少于两棵子树的情况。
II. 树中每个结点至多有 $m-1$ 个关键字
- 正确。这是 B 树的定义之一，每个结点最多可以包含 $m-1$ 个关键字。
III. 所有叶结点在同一层
- 正确。这是 B 树的重要特性，确保树的平衡性，即所有叶结点必须在同一层，以保证相同深度的访问时间。
IV. 插入一个元素引起 B 树结点分裂后，树长高一层
- 错误。只有在插入操作导致根结点分裂的情况下，树的高度才会增加。若在插入时，路径上的结点未满，则不会导致树长高。即使结点分裂，也不一定会影响树的高度，只有当分裂影响到根结点时，树才会增加一层。

综上所述，正确的选项是 B. II、III。

题目 4：

在一棵 m 阶 B 树中做插入操作前，若一个结点中的关键字个数等于( )，则必须分裂成两个结点；向一棵 m 阶的 B 树做删除操作前，若一个结点中的关键字个数等于( )，则可能需要同它的左兄弟或右兄弟结点合并成一个结点。

解析：

插入操作中的分裂条件：
- 在一棵 m 阶 B 树中，每个结点最多可以有 $m - 1$ 个关键字。当插入一个新关键字时，如果某个结点的关键字数量达到了 $m - 1$，再插入一个关键字就会导致该结点的关键字数量超过最大限制 $m - 1$。因此，必须将该结点分裂成两个结点，并将中间关键字上升到父结点中，以保持 B 树的性质。
删除操作中的合并条件：
- 每个结点在 B 树中至少需要保持 $ - 1 $ 个关键字（对于非根结点）。因此，如果在删除操作后某个结点的关键字数量少于 $ - 1 $，则可能需要进行合并操作。这意味着该结点可以选择与它的左兄弟或右兄弟结点合并，形成一个新的结点，从而保持 B 树的平衡性。

题目 5：

具有 n 个关键字的 m 阶 B 树，应有( )个叶结点。

选项： A. $ n+1 $
B. $ n-1 $
C. $ mn $
D. $ n/m $

答案：A. $ n+1 $

解释：

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

题目 6：

高度为 5 的 3 阶 B 树至少有( )个结点，至多有( )个结点。

选项： A. 32 B. 31
C. 120
D. 121

1. 至少有多少个结点：

高度为 5 的3阶B树，表示从根结点到叶结点的高度为5层，叶结点在第5层。
由于根结点（第1层）至少有2棵子树，所以结点数的最小值如下：
层数及结点计算：
- 第 1 层（根结点）：1 个结点
- 第 2 层：至少 2 个结点
- 第 3 层：至少 $2 \times 2 = 4$ 个结点
- 第 4 层：至少 $4 \times 2 = 8$ 个结点
- 第 5 层（叶结点）：至少 $8 \times 2 = 16$ 个结点

所以，至少有： $ 1 + 2 + 4 + 8 + 16 = 31 $

2. 至多有多少个结点：

在满 B 树中，每个结点最多有 3 棵子树，因此最多的结点数计算如下：
层数及结点计算：
- 第 1 层（根结点）：1 个结点
- 第 2 层：最多 3 个结点
- 第 3 层：最多 $3 \times 3 = 9$ 个结点
- 第 4 层：最多 $9 \times 3 = 27$ 个结点
- 第 5 层（叶结点）：最多 $27 \times 3 = 81$ 个结点

所以，最多有： $ 1 + 3 + 9 + 27 + 81 = 121 $

题目 7：

含有 $ n $ 个非叶结点的 $ m $ 阶 B 树中至少包含( )个关键字。

选项：

A. $ n(m+1) $
B. $ n $
C. $ n(m/2 - 1) $
D. $ (n-1)(m/2 - 1) + 1 $

答案：D

解释：

B树的基本性质：
- 在 $ m $ 阶 B 树中，每个非根的非叶结点至少有 $\lceil m/2 \rceil - 1$ 个关键字。
- 根结点至少有一个关键字（如果不是叶结点）。
非叶结点的关键字数量：
- 对于 $ n $ 个非叶结点，除根结点外，其他每个非叶结点至少有 $\lceil m/2 \rceil - 1$ 个关键字。因此，$ n-1 $ 个非叶结点（根结点除外）至少贡献的关键字数量为： $ (n-1)(m/2 - 1) $
根结点的关键字：
- 根结点至少有 1 个关键字。
计算总的关键字数量：
- 因此，B 树中至少包含的关键字总数为： $ (n-1)(m/2 - 1) + 1 $

题目 8：

已知一棵 5 阶 B 树中共有 53 个关键字，则树的最大高度为( )，最小高度为( )。

选项：
A. 2
B. 3
C. 4
D. 5

答案：
最大高度：C（4）
最小高度：B（3）

解释：

在 B 树中，5 阶意味着每个节点最多可以有 5 个子节点，并且每个节点至少有 $\lceil \frac{5}{2} \rceil = 3$ 个子节点（除根节点外）。根据 B 树的性质，我们可以使用以下公式来计算最大和最小高度：

最大高度：
- 最坏情况下，树的每个节点只包含最小关键字数，即每个节点有 2 个子节点。对于 $n$ 个关键字，最大高度 $H$ 的计算公式为： $ H { }(n + 1) $ 其中 $m$ 是阶数（在本例中为 5）。因此： $ H {2}(53 + 1) = _{2}(54) $ 取整后得到最大高度为 4。
最小高度：
- 最好情况下，树的每个节点都有最多的关键字（即每个节点有 5 个子节点）。因此，最小高度 $h$ 的计算公式为： $ h {m}(n + 1) $ 其中 $m$ 仍然是阶数（5）。因此： $ h {5}(53 + 1) = _{5}(54) $ 取整后得到最小高度为 3。

综上所述，树的最大高度为 4，最小高度为 3。

题目 9：

已知一棵 3 阶 B 树中有 2047 个关键字，则此 B 树的最大高度为( )，最小高度为( )。

选项： A. 11
B. 10
C. 8
D. 7

答案：A. 11（最大高度），D. 7（最小高度）

解释：

利用第8题的公式即可计算。

题目 10：

下列关于 B 树和 B+ 树的叙述中，不正确的是( )。

选项：
A. B 树和 B+ 树都能有效地支持顺序查找
B. B 树和 B+ 树都能有效地支持随机查找
C. B 树和 B+ 树都是平衡的多叉树
D. B 树和 B+ 树都可以用于文件索引结构

答案：
A. B 树和 B+ 树都能有效地支持顺序查找

解释：

B 树和 B+ 树的主要区别在于它们的结构和查找方式：

顺序查找：
- B+ 树：所有关键字都存储在叶节点中，且叶节点按关键字从小到大顺序连接，因此 B+ 树非常适合顺序查找。
- B 树：关键字存储在内部节点和叶节点中，且叶节点之间没有顺序链接，因此 B 树不支持有效的顺序查找。
随机查找：
- B 树和 B+ 树：两者都可以进行有效的随机查找，时间复杂度均为 $O(\log n)$。
结构：
- B 树和 B+ 树：两者都是平衡的多叉树，保持高度平衡，以便进行高效的查找。
索引结构：
- B 树和 B+ 树：均可以用于文件索引结构。

因此，选项 A 的叙述不正确，因为 B 树不能有效地支持顺序查找，而 B+ 树可以。

题目 11：【2009 统考真题】

下列叙述中，不符合 m 阶 B 树定义要求的是( )。

选项：
A. 根结点至多有 m 棵子树
B. 所有叶结点都在同一层上
C. 各结点内关键字均升序或降序排列
D. 叶结点之间通过指针链接

答案：D. 叶结点之间通过指针链接

解释：

A、B、C 都符合 m 阶 B 树的定义：
- 根结点的子树数最多为 m 棵。
- 所有叶子结点必须在同一层。
- 每个结点内的关键字按升序或降序排列。
选项 D 描述的特性是 B+ 树的特性，B 树并不要求叶结点之间通过指针链接。因此，D 不符合 B 树的定义。

题目 12：【2012 统考真题】

已知一棵 3 阶 B 树，如下图所示。删除关键字 78 得到一棵新 B 树，其最右叶结点中的关键字是( )。

选项：
A. 60
B. 60, 62
C. 62, 65

答案：C. 62, 65

解释：

题目 13：【2013 统考真题】

在一棵高度为 2 的 5 阶 B 树中，所含关键字的个数至少是( )。

选项：
A. 5
B. 7
C. 8
D. 14

答案：A

1.根节点至少有两个孩子节点，那么根节点的关键字至少为1 2.第二层节点（至少2个），每个节点至少有ceil(m/2)=3个孩子节点，那么其关键字至少为2 3.综上：高度为2的5阶B树，关键字个数至少为1+2+2=5

题目 14：【2014 统考真题】

在一棵有 15 个关键字的 4 阶 B 树中，含关键字的节点个数最多是( )。

选项：
A. 5
B. 6
C. 10
D. 15

答案：
D. 15

解释：

在 4 阶 B 树中，具有以下性质：

每个节点最多可以有 3 个关键字（即 $m - 1$）。
每个节点至少可以有 1 个关键字（根节点可以为 1，非根节点至少 $\lceil \frac{m}{2} \rceil - 1 = 1$）。
每个节点可以有最多 4 个子节点（即 $m$）。

为了最大化节点数量，我们需要使每个节点中包含的关键字数量最少。根据 B 树的性质，所有节点的关键字数量至少为 1，这意味着每个节点都有 2 个子节点（即使节点的分支尽可能多）。

计算节点个数

如果每个节点中有 1 个关键字，那么每个节点最多可以有 2 个子节点。
在这种情况下，包含 15 个关键字的 B 树的节点数量可以用以下方式计算：

根节点（1 个关键字）可以有 2 个子节点。
每个子节点（1 个关键字）也可以有 2 个子节点。

按照这样的结构，可以构造如下的节点：

第一层（根节点）：1 个节点，1 个关键字。
第二层：2 个节点，每个 1 个关键字，合计 2 个关键字。
第三层：4 个节点，每个 1 个关键字，合计 4 个关键字。
第四层：8 个节点，每个 1 个关键字，合计 8 个关键字。

总结

第一层（根节点）：1 个关键字
第二层：2 个关键字
第三层：4 个关键字
第四层：8 个关键字

这些关键字加起来刚好为 15 个关键字。这样构造的 B 树具有最多的节点数。

因此，含关键字的节点个数最多为 15，所以答案是 D. 15。

题目 15：【2016 统考真题】

B+ 树不同于 B 树的特点之一是( )。

选项：
A. 能支持顺序查找
B. 结点中含有关键字
C. 根结点至少有两个分支
D. 所有叶结点都在同一层上

答案：
A. 能支持顺序查找

解释：

B+ 树和 B 树有一些关键的区别，以下是它们的主要特点：

顺序查找：
- B+ 树：所有叶结点包含了全部的关键字信息，并且这些叶结点按关键字顺序相连，因此可以有效支持顺序查找。
- B 树：只支持多路查找，虽然也可以进行顺序查找，但效率较低，因为不是所有的关键字都在叶结点中。
结点中含有关键字：
- B 树 和 B+ 树：都包含关键字，选项 B 并不特别区分两者的特点。
根结点的分支：
- B 树：根节点可以只有一个分支，但必须至少有一个关键字。
- B+ 树：同样，根节点也可以只有一个分支，但通常要求至少有两个分支以保持树的平衡。选项 C 对于 B 树和 B+ 树都不适用。
叶结点的层次：
- B+ 树：所有的叶结点都在同一层上，而 B 树的叶结点可能在不同层次。因此，选项 D 是 B+ 树的一项特征。

综上所述，A 选项：B+ 树能支持顺序查找，确实是 B+ 树相较于 B 树的一个显著特点。因此，正确答案是 A. 能支持顺序查找。

题目 16：【2017 统考真题】

下列应用中，适合使用 B+ 树的是( )。

选项：
A. 编译器中的词法分析
B. 关系数据库系统中的索引
C. 网络中的路由表快速查找
D. 操作系统的磁盘空闲块管理

答案：
B. 关系数据库系统中的索引

解释：

B+ 树是一种广泛应用于数据库系统和文件系统的自平衡树结构，特别适合于需要频繁进行范围查询和顺序查找的场景，主要原因如下：

磁盘读写效率：
- B+ 树通过将所有关键字放在叶节点并通过指针链接叶节点，使得顺序查找更为高效，尤其是在数据库系统中，通常需要处理大量的记录查询。
查找性能：
- B+ 树的所有叶节点都在同一层，能够保证查询性能的一致性，尤其在需要频繁插入和删除操作的场景中，性能表现优越。
适用场景：
- 在关系数据库系统中，索引的设计通常需要支持高效的查询和数据检索，因此 B+ 树是常见的索引结构。

对比其他选项：

A. 编译器中的词法分析：
- 编译器的词法分析通常使用有限自动机和语法树来处理输入，不适合使用 B+ 树。
C. 网络中的路由表快速查找：
- 路由表查找一般依赖于哈希表和其他优化算法，而不是使用 B+ 树。
D. 操作系统的磁盘空闲块管理：
- 磁盘空闲块的管理通常使用链表或位图来跟踪空闲块，不使用 B+ 树。

因此，适合使用 B+ 树的应用是 B. 关系数据库系统中的索引。

题目 17：【2018 统考真题】

高度为 5 的 3 阶 B 树含有的关键字个数至少是( )。

选项：
A. 15
B. 31
C. 62
D. 242

答案：B. 31

解释：

3 阶 B 树中，每个结点至少有 $ m/2 - 1 = 1 $ 个关键字。
高度为 5 的 B 树中，根结点有 1 个关键字，非根结点至少包含 1 个关键字，树每层的结点数依次翻倍：
- 第 1 层：1 个关键字，1 个结点
- 第 2 层：2 个结点，2 个关键字
- 第 3 层：4 个结点，4 个关键字
- 第 4 层：8 个结点，8 个关键字
- 第 5 层：16 个结点，16 个关键字
关键字总数：$ 1 + 2 + 4 + 8 + 16 = 31 $。

题目 18：【2020 统考真题】

依次将关键字 5，6，9，13，8，2，12，15 插入初始为空的 4 阶 B 树后，根结点中包含的关键字是( )。

答案： 6.9。

解释：

题目 19：【2021 统考真题】

在一棵高度为 3 的 3 阶 B 树中，根为第 1 层，若第 2 层中有 4 个关键字，则该树的结点数最多是( )。

选项：
A. 11
B. 10
C. 8
D. 9

答案：A. 11

解释：

如图：

程序题

问题 01：给定一组关键字 {20, 30, 50, 52, 60, 68, 70}，给出创建一棵 3 阶 B 树的过程。

问题 02：对如下图所示的 3 阶 B 树，依次执行下列操作，画出各步操作的结果。

操作：

插入 90

插入 25

插入 45

删除 60

删除 80

问题03

利用 B 树做文件索引时，假设磁盘页块的大小是 4000B（实际应是 2 的次幂，此处是为了计算方便），指示磁盘地址的指针需要 5B。现有 20000000 个记录构成的文件，每个记录为 200B，其中包括关键字 5B。试问在这个采用 B 树作索引的文件中，B 树的阶数应为多少？假定文件数据部分未按关键字有序排列，则索引部分需要占用多少磁盘页块？

答案

B 树的阶数 $m$： $ 2 (m - 1) + m + 2 $ 简化得到： $ 10(m - 1) + 5m + 2 $ $ 15m - 8 $ $ 15m $ $ m $

因此，B 树的最大阶数为 267（取整）。
索引部分需要占用的磁盘页块：
- 一个索引结点最多可以存放 $m - 1 = 266$ 个索引项，最少可以存放 $\lceil \frac{m}{2} \rceil - 1 = 133$ 个索引项。
- 总记录数 $n = 20000000$。
- 每个页块可以存放的记录数为： $ = 20 $
- 总页块数为： $ = 1000000 $
- 最大磁盘页块需求： $ $
- 最小磁盘页块需求： $ $