题目

给 7 个不同的关键字，能够构成不同 4 阶 B 树的个数为( )。

错因

A

凭"7 个关键字"直觉报 7。这与 B 树形态枚举无关，是单纯的同位思维：题里出现的某个数字直接当成答案。

B

只枚举到了高度为 1（根 + 直接叶子）的全部 8 种树形，漏掉高度为 2 的极小 B 树——根 1 关键字 + 中间 2 个 1 关键字内部节点 + 4 个 1 关键字叶子，恰好 7 个关键字，是高度 2 的唯一可能形态。少了这种就成了 8。

D

枚举高度 1 和高度 2 都对了（共 9 种），但额外多算了一种——常见误区是把"叶子里 4 个 1 关键字的排列"另外算一次（实际上 7 个不同关键字按 BST 序填入既定形态后唯一确定，没有"排列变体"），或在 (1,2,2) 类分布里多算了一种重复对称的情况。

总解析

思路：4 阶 B 树要求每个节点关键字数 ；根可放宽为 关键字，所有叶子在同一深度。给定 7 个不同关键字时，只要 B 树形状（每个节点容量 + 父子结构）确定，按 BST 序填入即唯一——故"形状数 = 不同 B 树数"。

按高度讨论。设根有 个孩子（，根含 个关键字）。

---

情况 A：高度 1（根 + 直接叶子）

设 个孩子（叶子），第 个叶子有 个关键字。总关键字 ，即 。

		满足 的有序分布	种数
2	6	(3,3)	1
3	5	(3,1,1)/(1,3,1)/(1,1,3) + (1,2,2)/(2,1,2)/(2,2,1)	6
4	4	(1,1,1,1)	1

合计：$1 + 6 + 1 = $ 8 种。

---

情况 B：高度 2（根 + 中间内部节点 + 叶子）

最小填充：根 1 关键字、 个中间节点各 1 关键字（每个中间节点带 个孩子）、 个叶子各 关键字。

总关键字 ，即 。

约束 给出 ，化简得 ；又 ，故 。

代入：， 个叶子各 1 关键字（唯一分布）。再看 ： 且 ，故 且 （唯一分布）。

合计：高度 2 仅 1 种。

---

总计：$8 + 1 = $ 9 种。

最终答案是 C。