题6

题6

题目

Q:高度为 5 的 3 阶 B 树至少有 ( ) 个结点, 至多有 ( ) 个结点
A. 32
B. 31
C. 120
D. 121

分析

A:由 阶 树的性质可知,根结点至少有 2 棵子树;
根结点外的所有非终端结点至少有 棵子树
结点数最少时, 阶 树形状至少类似于一棵满二叉树（每个结点两个分支）,即高度为 5 的 树至少有 31 个结点。
由于每个结点最多有 棵子树,所以当结点数最多时,3 阶 B 树形状类似于满三叉树, 结点数为
(注意,这里求的是结点数而非关键字数,若求的是关键字数,则还应把每个结点中关键字数的上下界确定出来)。
和题7对比起来理解这个公式
这是关于二叉树结点和高度之间关系的题6

解

B、D