🏷️ 知识点：B 树
2023 年第 7 题
数据结构
选择题
下列关于非空 B 树的叙述中，正确的是（ ）
I. 插入操作可能增加树的高度
II. 删除操作一定会导致叶结点的变化
III. 查找某关键字一定是要查找到叶结点
IV. 插入的新关键字最终位于叶结点中
A. 仅 I B. 仅 I、II C. 仅 III、IV D. 仅 I、II、IV
[tag_link]
正确答案：B
在 B 树 中，插入 操作可能导致节点分裂。如果根节点已满，插入新键会触发根节点分裂，生成一个新的根节点，从而增加树的高度。因此，插入操作确实可能（但不一定）增加树的高度。选项 I 正确。删除 操作可能涉及以下情况：
- 删除的键在叶子结点：直接从叶子结点移除该键，导致叶子结点内容变化。
- 删除的键在非叶子结点：B 树会用前驱或后继键（通常位于叶子结点）替换该键，然后删除前驱或后继键。这仍然会导致叶子结点的变化。
- 删除后触发合并或借键：如果删除键后某个节点键数低于最小要求（通常 ⌈m / 2⌉ − 1），可能需要从兄弟节点借键或与兄弟节点合并。这些操作可能涉及叶子结点（例如，合并两个叶子结点或调整叶子结点的键）。在所有删除场景中，无论是直接删除键还是通过替换、合并、借键，操作最终都会影响叶子结点（键的移除或调整发生在叶子结点）。选项 II 正确。查找关键字并不一定需要查找到叶子结点。例如，如果目标键位于根节点或中间节点，查找会在这些非叶子结点停止。选项 III 错误。新关键字在 B 树中开始总是被插入到叶子结点中，但是可能随着分裂上溢到非叶子结点，选项 IV 错误。
2018 年第 8 题
数据结构
选择题
高度为 5 的 3 阶 B 树含有的关键字个数至少是（ ）
A. 15 B. 31 C. 62 D. 242
[tag_link]
正确答案：B
m阶 B 树 的基本性质：根结点以外的非叶结点最少含有⌈m/2⌉−1个关键字，代入m=3得到每个非叶结点中最少包含 1 个关键字，而根结点含有 1 个关键字，因此所有非叶结点都有两个孩子。此时其树形与 h=5 的满二叉树相同，可求得关键字最少为 31 个。
2025 年第 8 题
数据结构
选择题
给 7 个不同的关键字，能够构成不同 4 阶 B 树的个数为（ ）。
A. 7 B. 8 C. 9 D. 10
[tag_link]
正确答案：C
- 树高为 3：每个节点内关键字个数最少取 1 时，B 树 高度为 3（类似满二叉树）——仅一种结构；
- 树高为 2:
- 根节点关键字个数取 1，第二层两节点关键字个数均取 3——一种结构；
- 根节点关键字个数取 2，则第二层内三个节点关键字个数分别可取 221、212、122、311、131、113 共计六种结构；
- 根节点关键字个数取 3，则第二层显然只有四个节点各含一个关键字此一种结构。综上，共计 9 种可能的结构。
2013 年第 10 题
数据结构
选择题
在一株高度为 2 的 5 阶 B 树中，所含关键字的个数最少是（）
A.5
B.7
C.8
D.14
[tag_link] 正确答案：A对于 5 阶 B 树 ，根结点只有达到 5 个关键字时才能产生分裂，成为高度为 2 的 B 树，因此高度为 2 的 5 阶 B 树所含关键字的个数最少是 5。
