首页 > 试题广场 >

题目来源于王道论坛 在一棵具有15个关键字的

[单选题]
题目来源于王道论坛

在一棵具有15个关键字的4阶B树中，含关键字的结点个数最多是 。 


  • 5
  • 6
  • 10
  • 15
查看答案及解析
添加回答
推荐
zsw3头像 zsw3

解析：

关键字数量不变，要求结点数量最多，那么即每个结点中含关键字的数量最少。根据4阶B树的定义，根结点最少含1个关键字，非根结点中最少含⌈4/2⌉-1=1个关键字，所以每个结点中，关键字数量最少都为1个，即每个结点都有2个分支，类似与排序二叉树，而15个结点正好可以构造一个4层的4阶B树，使得叶结点全在第四层，符合B树定义，因此选D。

发表于 2018-06-16 11:38:33 回复(1)
牛客374198732号头像 牛客374198732号
如果全部节点按照类似排序二叉树构建，请判定该B树的阶为多少？按照王道书上的定义，所有结点中孩子节点数的最大值为B树的阶，那么此树为二阶B树，与题目矛盾。
发表于 2018-08-27 10:17:08 回复(2)
GYT0313头像 GYT0313
m阶B树则每个节点的关键字数为 m/2 - 1 <= n <= m -1 ，本题中4阶，则每个节点的关键字数至少为1个，至多为3个，若要节点数最多，则每个节点的关键字最少为1即可。15 / 1 = 15，所以选D。相反，如果求最少节点数，为 15 / 3 = 5。
编辑于 2019-05-03 11:28:03 回复(1)
我的天鸭头像 我的天鸭
4阶B树，至少有一个结点分支有4个子树，包含3个关键字，答案是不是有问题啊...感觉应该是13才对
发表于 2019-02-16 19:26:33 回复(1)
ting9210120头像 ting9210120
一棵M阶(M>2)的B树，是一个平衡的M路平衡搜索树，可以是空树或者满足以下性质：
1.根节点至少有两个孩子。
2.每个非根结点至少有M/2（上取整）个孩子，至多有M个孩子。
3.每个分根结点至少有M/2-1（上取整）个孩子，至多有M个孩子。
4.key[i]和key[i+1]之间的孩子结点的值介于key[i]、key[i+1]之间。
5.所有的叶子结点都在同一层。
 
发表于 2018-10-02 14:39:56 回复(0)
特特卡了头像 特特卡了
还是没怎么懂
发表于 2018-10-01 10:50:45 回复(0)
lilinl头像 lilinl
4阶B树，根节点最少含一个关键字，非根节点最少含有[4/2]-1个关键字，每个结点的分支等于关键字个数+1
发表于 2018-09-23 15:10:55 回复(0)
提交观点

问题信息

树
上传者：zsw3
难度：
7条回答 3090浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号