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

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 种可能的结构。