首页
题库
面试
求职
学习
竞赛
More+
所有博客
搜索面经/职位/试题/公司
搜索
我要招人
去企业版
登录 / 注册
首页
>
试题广场
>
判断下列说法是否正确:高为5 (不含叶子层)的3阶B-树最少
[单选题]
判断下列说法是否正确:
高为5 (不含叶子层)的3阶B-树最少有31个关键字。
正确
错误
添加笔记
邀请回答
收藏(233)
分享
纠错
4个回答
添加回答
8
推荐
Jino.
选
A
。
一棵m阶B树是一棵
平衡的m路搜索树
。
它或者是空树,或者是满足下列性质的树:
1、
根结点至少有两个子女;
2、
每个非根节点所包含的关键字个数 j 满足:┌m/2┐ - 1 <= j <= m - 1;
3、除根结点以外的所有结点(不包括叶子结点)的度数正好是关键字总数加1,故
内部子树
个数 k 满足:┌m/2┐ <= k <= m ;
4、
所有的叶子结点都位于同一层。
由m阶B-树性质可知,
根结点至少有两棵子树,根结点之外的所有非终端结点至少有m/2棵子树
:则
三阶B-树的形状至少类似于一棵满二叉树
,也即高度为5的三阶B-树至少有(2
5
-1=)31个结点。
因此题中描述是正确的,选
A
。
编辑于 2019-12-18 14:12:29
回复(0)
1
天尊墨宇
选A
1970年,R.Bayer和E.mccreight提出了一种适用于外查找的
树
,它是一种平衡的多叉树,称为B树(或B-树、B_树)。
一棵m阶B树(balanced tree of order m)是一棵平衡的m路搜索树。它或者是空树,或者是满足下列性质的树:
1、根结点至少有两个子女;
2、每个非根节点所包含的关键字个数 j 满足:┌m/2┐ - 1 <= j <= m - 1;
3、除根结点以外的所有结点(不包括叶子结点)的度数正好是关键字总数加1,故
内部子树
个数 k 满足:┌m/2┐ <= k <= m ;
4、所有的叶子结点都位于同一层。
在B-树中,每个结点中关键字从小到大排列,并且当该结点的孩子是非叶子结点时,该k-1个关键字正好是k个孩子包含的关键字的值域的分划。
因为叶子结点不包含关键字,所以可以把叶子结点看成在树里实际上并不存在外部结点,指向这些外部结点的指针为空,叶子结点的数目正好等于树中所包含的关键字总个数加1。
B-树中的一个包含n个关键字,n+1个指针的结点的一般形式为: (n,P0,K1,P1,K2,P2,…,Kn,Pn)
其中,Ki为关键字,K1<K2<…<Kn, Pi 是指向包括Ki到Ki+1之间的关键字的子树的指针。
发表于 2020-07-03 17:54:19
回复(0)
9
白驹之过隙
选
A
。考察的是B-树的概念。
B-树是一种平衡的多路查找树,
由m阶B-树性质可知,根结点至少有两棵子树,根结点之外的所有非终端结点至少有m/2棵子树:则三阶B-树的形状至少类似于一棵满二叉树,也即高度为5的三阶B-树至少有(2
5
-1=)31个结点。
发表于 2019-12-17 21:09:13
回复(0)
0
早安!
m阶b-树不必存在度为m的结点
发表于 2022-12-08 09:35:09
回复(0)
这道题你会答吗?花几分钟告诉大家答案吧!
提交观点
问题信息
树
上传者:
zsw3
难度:
4条回答
233收藏
2689浏览
热门推荐
相关试题
明明的随机数
数组
评论
(3693)
来自
华为研发工程师编程题
分页系统的逻辑地址结构是一维的,分...
操作系统
评论
(1)
关于分段系统与分页系统的区别,描述...
操作系统
评论
(1)
已知a
40
=...
京东
职能
2019
财务
保险
评论
(1)
有20000人的就餐需求,现建了一...
评论
(1)
扫描二维码,关注牛客网
意见反馈
下载牛客APP,随时随地刷题