首页 > 试题广场 >

已知一个5阶B树有53个关键字,并且每个节点的关键字都达到最

[单选题]
已知一个5阶B树有53个关键字,并且每个节点的关键字都达到最少状态,则它的深度是
  • 3
  • 4
  • 5
  • 6
选B
方法一:推导

根:最少有1个关键字

其它结点:最少有ceil(m/2)-1 ==> ceil(5/2)-1 = 2个关键字

所以:

第一层:1个结点,1个关键字

第二层:2个结点,4个关键字

第三层:6个结点,12个关键字

第四层:18个结点,36个关键字

总共53个关键字

 

方法二:

明显,每个结点内关键字数最少的时候,树高达到最高,所以使用第二个公式。

h = log(3, (53+1)/2) + 1 = log(3, 27) + 1 = 4
发表于 2020-06-29 10:44:33 回复(1)

方法一:推导

根:最少有1个关键字

其它结点:最少有ceil(m/2)-1 ==> ceil(5/2)-1 = 2个关键字

所以:

第一层:1结点,1个关键字

第二层:2结点4个关键字

第三层:6结点,12个关键字

第四层:18个结点,36个关键字

总共53个关键字

 

方法二:

明显,每个结点内关键字数最少的时候,树高达到最高,所以使用第二个公式。

h = log(3, (53+1)/2) + 1 = log(3, 27) + 1 = 4
【来自:数据结构考研冯强】
发表于 2020-05-17 11:05:05 回复(1)
答案 b 根结点最少一个关键字 非根结点最少m/2向上取整再-1个关键字 第一层:1 第二层:2*2 第三层:3*2*2 第四层:3*6*2 1+2*2+3*2*2+3*6*2=53,正好四层
发表于 2019-12-03 16:19:38 回复(0)