首页 > 试题广场 >

判断下列说法是否正确：高为5的3阶B-树至多包含240个关键

[单选题]
判断下列说法是否正确：高为5的3阶B-树至多包含240个关键字。（） 
  • 正确
  • 错误
添加回答
推荐
白驹之过隙头像 白驹之过隙
选B。
根据以下性质：
  • 3阶B-树每个节点至多有三个子节点，除叶子节点外其他节点至少有两个子节点。
  • 所有叶子节点都在同一层，叶结点可以有一个或两个关键码。
  • 三个子节点的非叶子节点含有两个关键码，有两个子节点的非叶子节点有一个关键码。

结合题目中的“至多”关键字可以得出每层节点1,3,9,27,81，2+3*2+9*2+27*2+81*2=242个关键字。

编辑于 2020-01-10 14:47:43 回复(0)
boker_lx头像 boker_lx
B树/B-树重要性质：
1.关于子树与关键字，m棵子树最多拥有M-1个关键字
2.任意一个非终端节点子树个数m/2向上取整
基于以上两个性质
对于任意一个m棵子树非终端节点关键字个数范围是m/2向上取整-1 ~ m-1
对于本题：
    3阶b树每个节点最多拥有三颗子树两个关键字，一共五层则节点数最多为1+3+9+27+81，每个节点又最多拥有两个关键字 则关键字最多为（1+3+9+27+81）*2 = 242
发表于 2021-10-21 14:55:57 回复(0)
Jino.头像 Jino.
选B。
一棵m阶B树是一棵平衡的m路搜索树。它或者是空树，或者是满足下列性质的树：
1、根结点至少有两个子女；
2、除了根节点和叶子节点之外，所有的节点最少有 m/2 个孩子节点，最多有 m 孩子个；
3、除根结点以外的所有结点（不包括叶子结点）的度数正好是关键字总数加1，故内部子树个数 k 满足：┌m/2┐ <= k <= m ；
4、所有的叶子结点都位于同一层。
最少：由m阶B-树性质可知，根结点至少有两棵子树，根结点之外的所有非终端结点至少有m/2棵子树：则三阶B-树的形状至少类似于一棵满二叉树，也即高度为5的三阶B-树至少有(25-1=)31个结点。
最多：由m阶B-树性质可知，根结点有三棵子树，五层结点数分别为1,3,9,27,81时最多为121个结点。
综上，题中描述错误，选B。

发表于 2020-01-09 20:02:15 回复(1)
学术废物头像 学术废物
每个节点关键字范围为1～2 最后得242
发表于 2022-03-18 15:49:50 回复(0)
YkekeY头像 YkekeY

注意，每个结点关键码数最大为n_max=m-1，则，在最多结点情况下，有最多的关键码数，为121*（3-1）=242

发表于 2021-04-24 15:35:12 回复(0)
天尊墨宇头像 天尊墨宇
选B。
根据以下性质：
  • 3阶B-树每个节点至多有三个子节点，除叶子节点外其他节点至少有两个子节点。
  • 所有叶子节点都在同一层，叶结点可以有一个或两个关键码。
  • 三个子节点的非叶子节点含有两个关键码，有两个子节点的非叶子节点有一个关键码。

结合题目中的“至多”关键字可以得出每层节点1,3,9,27,81，2+3*2+9*2+27*2+81*2=242个关键字。

发表于 2020-07-02 14:54:24 回复(0)
二营长达卡头像 二营长达卡
巧合？
3^5 - 1 = 242
发表于 2020-04-14 13:48:00 回复(0)
提交观点

问题信息

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

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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