🏷️ 知识点：B树
下列关于非空 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 错误。
高度为 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 个。
在下图所示的5阶 B 树 T 中，删除关键字260 之后需要进行必要的调整，得到新的 B 树 T1 。下 列选项中，不可能是 T1 根结点中关键字序列的是()。
A.60,90,280
B.60,90,350
C.60,85,110,350 D.60,90,110,350
[tag_link]
正确答案：D
参考 B 树插入操作 ，在 5 阶 B 树中，除根结点外的非叶子结点的关键字数 k 需要满足 2 ≤ k ≤ 4。当被删关键字 x 不在终端结点（最底层非叶子结点）时，可以用 x 的前驱（或后继) 关键字 y 来替代 x，然后在相应结点中删除 y。情况①：删除 260，将其前驱 110 放入 260 处，删除 110 后的结点 不满足 5 阶 B 树定义，从左兄弟中借 85，将 85 放入根中，将根中的 90 移入结点 变为 <90, 100>。情况②：删除 260，将其后继 280 放入 260 处，结点 不满足 5 阶 B 树定义且左右兄弟都不够借，结点 可以和左兄弟 <100, 110> 以及关键字 280 合并成一个新的结点 <100, 110, 280, 300>。情况③：在情况②中，结点 也可以和右兄弟 <400, 500> 以及关键字 350 合并成一个新的结点 <300, 350, 400, 500>。综上，T1 根结点中的关键字序列可能是 <60, 85, 110, 350> 或 <60, 90, 350> 或 <60, 90, 280>，仅 D 不可能。
给 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 种可能的结构。
下列关于 m 阶 B-树的说法中，正确的有（ ）。 I. 每个结点至少有两棵非空子树 II. 非叶结点仅起索引作用，每次查找一定会查找到某个叶结点 III. 所有叶子在同一层上 IV. 插入一个数据项引起 B-树结点分裂后，树长高一层
A. I、II B. II、III C. III、IV D. III
[tag_link]
正确答案：D
本题考查 B-树的性质。
m 阶 B-树根结点至少有两棵子树（这两棵子树可以是空树），其他非叶结点至少有 棵子树，因此 I 错误。 II 是 B+ 树的性质。 B-树又称多路平衡查找树，叶结点都在同一层次上，可视为查找失败结点，因此 III 正确。 结点的分裂不一定会使树高增加 1，如图 1 所示； 只有当分裂传递到根结点并使根结点也分裂时，树高才会增加 1，如图 2 所示，因此 IV 错误。
已知一棵 3 阶 B 树，如下图所示。删除关键字 78 得到一棵新 B 树，其最右叶结点中的关键字是（）。
A. 60
B. 60, 62
C. 62, 65
D. 65
[tag_link]
正确答案：D本题考察 B 树的 删除 操作。对于上图所示的 3 阶 B 树，被删关键字 78 所在结点在删除前的关键字个数 = 1 = ⌈3/2⌉-1，且其左兄弟结点的关键字个数 = 2 ≥ ⌈3/2⌉，属于“兄弟够借”的情况，则需把该结点的左兄弟结点中最大的关键字上移到双亲结点中，同时把双亲结点中大于上移关键字的关键字下移到要删除关键字的结点中，这样就达到了新的平衡，如下图所示。
在一棵具有15个关键字的4阶 B 树中，含关键字的结点个数最多是()。
A.5
B.6
C.10
D.15
[tag_link]
正确答案：D
关键字数量不变，要求结点数量最多，那么即每个结点中含关键字的数最最少。根据 4 阶 B 树 的定义，根结点最少含 1 个关键字，非根结点中最少含 ⌈4/2⌉-1=1 个关键字，所以每个结点中，关键字数量最少都为 1 个，即每个结点都有 2 个分支，类似于排序二叉树，而 15 个结点正好可以构造一个 4 层的 4 阶 B 树，使得叶结点全在第四层，符合 B 树定义，因此选 D。
在一株高度为 2 的 5 阶 B 树中，所含关键字的个数最少是（）
A.5
B.7
C.8
D.14
[tag_link] 正确答案：A对于 5 阶 B 树 ，根结点只有达到 5 个关键字时才能产生分裂，成为高度为 2 的 B 树，因此高度为 2 的 5 阶 B 树所含关键字的个数最少是 5。
B+ 树不同于 B 树的特点之一是（）
A. 能支持顺序查找 B. 结点中含有关键字 C. 根结点至少有两个分支 D. 所有叶结点都在同一层上
[tag_link]
正确答案：A
由于 B+ 树 的所有叶结点中包含了全部的关键字信息，且叶结点本身依关键字从小到大顺序 链接，可以进行顺序查找，而 B 树不支持顺序查找（只支持多路查找）。
