高度为 5 的 3 阶 B 树含有的关键字个数至少是（ ）

B树

A. 15 B. 31 C. 62 D. 242

[tag_link]

正确答案：B

m阶 B 树 的基本性质：根结点以外的非叶结点最少含有⌈m/2⌉−1个关键字，代入m=3得到每个非叶结点中最少包含 1 个关键字，而根结点含有 1 个关键字，因此所有非叶结点都有两个孩子。此时其树形与 h=5 的满二叉树相同，可求得关键字最少为 31 个。