首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明、图和C代码,将应填入(n)处的字句写在对应栏内。 【说明5-1】 B树是一种多叉平衡查找树。一棵m阶的B树,或为空树,或为满足下列特性的m叉树: ①树中每个节点至多有m棵子树; ②若根节点不是叶子节点,则它至少有两棵子树;
阅读下列说明、图和C代码,将应填入(n)处的字句写在对应栏内。 【说明5-1】 B树是一种多叉平衡查找树。一棵m阶的B树,或为空树,或为满足下列特性的m叉树: ①树中每个节点至多有m棵子树; ②若根节点不是叶子节点,则它至少有两棵子树;
admin
2009-05-15
19
问题
阅读下列说明、图和C代码,将应填入(n)处的字句写在对应栏内。
【说明5-1】
B树是一种多叉平衡查找树。一棵m阶的B树,或为空树,或为满足下列特性的m叉树:
①树中每个节点至多有m棵子树;
②若根节点不是叶子节点,则它至少有两棵子树;
③除根之外的所有非叶子节点至少有[m/2]棵子树;
④所有的非叶子节点中包含下列数据信息(n,A0,K1,A1,K2,A2,…,Kn,An),其中:Ki(i=1,2,…,n)为关键字,且Ki<Ki+1(i=1,2,…,n-1),Ai(i=0,1,…,n)为指向子树根节点的指针,且指针Ai-1所指子树中所有节点的关键字均小于Ki,Ai+1所指子树中所有节点的关键字均大于Ki,n为节点中关键字的数目;
⑤所有的叶子节点都出现在同一层次上,并且不带信息(可以看成是外部节点或查找失败的节点,实际上这些节点不存在,指向这些节点的指针为空)。
例如,一棵4阶B树如图5-1所示(节点中关键字的数目省略)。
B树的阶M、bool类型、关键字类型及B树节点的定义如下:
#define M 4 /*B树的阶*/
typedef enum{FALSE=0,TRUE=1}bool;
typedef int ElemKeyType;
typedef struct BTreeNode{
int numkeys; /*节点中关键字的数目*/
struct BTreeNode *parent; /*指向父节点的指针,树根的父节点指针为空*/
struct BTreeNode *A[M]; /*指向子树节点的指针数组*/
ElemKeyType K[M]; /*存储关键字的数组,K[0]闲置不用*/
}BTreeNode;
函数SearchBtree(BTreeNode* root,ElemKeyType akey,BTreeNode **ptr)的功能是:在给定的一棵M阶B树中查找关键字akey所在节点,若找到则返回TRUE,否则返回FALSE。其中, root是指向该M阶B树根节点的指针,参数ptr返回akey所在节点的指针,若akey不在该B树中,则ptr返回查找失败时空指针所在节点的指针。例如,在如图5-1所示的4阶B树中查找关键字25时,ptr返回指向节点e的指针。
注:在节点中查找关键字akey时采用二分法。
【函数5-1】
bool SearchBtree(BTreeNode* root, ElemKeyType akey, BTreeNode **ptr)
{
int lw,hi,mid;
BTreeNode *p=root;
*pb=NULL;
while(p){
lw=1;hi=(1);
while(lw<=hi){
mid=(lw+hi)/2;
if(p->K[mid]==akey){
*Ptr=p;
return TRUE;
}else if((2))
hi=mid-1;
else
lw=mid+1;
}
*ptr=p;
p=(3);
}
return FALSE;
}
【说明5-2】
在M阶B树中插入一个关键字时,首先在最接近外部节点的某个非叶子节点中增加一个关键字,若该节点中关键字的个数不超过M-1,则完成插入;否则,要进行节点的“分裂”处理。所谓“分裂”,就是把节点中处于中间位置上的关键字取出来并插入其父节点中,然后以该关键字为分界线,把原节点分成两个节点。“分裂”过程可能会一直持续到树根,若树根节点也需要分裂,则整棵树的高度增1。
例如,在如图5-1所示的B树中插入关键字25时,需将其插入节点e中,由于e中已经有3个关键字,因此将关键字24插入节点e的父节点b,并以24为分界线将节点e分裂为e1和e2两个节点,结果如图5-2所示。
函数Isgrowing(BTreeNode* root,ElemKeyType akey)的功能是:判断在给定的M阶B树中插入关键字akey后,该B树的高度是否增加,若增加则返回TRUE,否则返回FALSE。其中, root是指向该M阶B树根节点的指针。
在函数Isgrowing中,首先调用函数SearchBtree(即函数5-1)查找关键字akey是否在给定的M阶B树中,若在则返回FALSE(表明无须插入关键字akey,树的高度不会增加);否则,通过判断节点中关键字的数目考察插入关键字akey后该B树的高度是否增加。
【函数5-2】
bool Isgrowing(BTreeNode* root,ElemKeyType akey)
{
BTreeNode *t,*f;
if(!SearchBtree((4))){
t=f;
while((5)){
t=t->parent;
}
if(!t)
return TRUE;
}
return FALSE;
}
选项
答案
(1) p->numkeys (2) akey<p->K[mid] (3) p->A[hi] (4) root,akey,&f (5) t && t->numkeys==M-1
解析
该题考查B树上的查找和插入操作,解题之前需要弄清楚B树的存储结构。
函数5-1采用二分法查找,先在根节点查找待查关键字,若找到则成功返回;否则,确定待查关键字所可能在的子树继续查找,直到找到或到达叶节点(查找失败)。如何确定子树是该题的难点。
根据二分法查找的思想,变量hi应该赋值为查找表中最后元素的下标,结合B树的存储结构,应该为p->numkeys,即查找表中的元素个数(因下标从1开始)。故空(1)应填p->numkeys。
接着通过while循环进行查找,循环体中分3种情况分别处理:找到时,记录待查关键字所在节点的指针,并返回;否则,若空(2)条件成立,则将hi赋值为mid-1(即表示继续在前半段查找),否则将1w赋值为mid+1(即表示继续在后半段查找),结合二分法查找思想很容易得空(2)条件应该为akey<p->K[mid]。故空(2)应填akey<p->K[mid]。
执行到空(3)处,结束了while循环,说明在当前节点处没找到待查关键字,需要继续在相应子树中查找,那么究竟应该在哪棵子树中继续查找呢?该空是比较难的一空,需要对题中 B树的存储结构有深刻的理解。显然该空该填p->A[下标],关键就是下标如何确定。根据B树的存储结构(n,A0,K1,A1,K2,A2,…,Kn,An),当hi、lw及mid相等时(while循环结束条件),如果待查关键字较小,则应该在A[mid-1]中查找,而此时正好有语句“hi=mid-1”;若待查关键字较大,则应该在A[mid]中查找,亦即A[hi]。综合可得应在A[hi]中继续查找。故空(3)应填p->A[hi]。
空(4)和空(5)相对比较简单。空(4)只要根据形参正确将实参传递即可。根据题意,此处显然是打算在B树root中查找关键字akey,再根据紧接的语句“t=f”可知第三个参数应该为&f。故空(4)应填“root,akey,&f”。
根据分裂的说明,若当前节点的关键字个数为M-1个时,其子节点的分裂将导致该节点的分裂。因此不难得到空(5)应填“t&&t->numkeys==M-1”。注意别填成“t->numkeys== M-1”,此处t是一个指针,首先得保证t不为空才能进行访问。
转载请注明原文地址:https://kaotiyun.com/show/n5xZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
DES加密算法采用的密码技术是(61),它采用(62)bit密钥对传输的数据进行加密,著名的网络安全系统Kerberos采用的是(63)加密技术。公钥密码是(64),常用的公钥加密算法有(65),它可以实现加密和数字签名。
EIARS-232C定义了DTE和DCE之间的接口,其机械特性规定RS-232C的D型连接器有(11)个插脚,其电气特性与CCITT的(12)兼容。DTE和DCE之间的接口信号线按功能一般可分为(13)4类,使用EIARS-232C接口进行数据通信时,至少
RSA算法的一个比较知名的应用是(41),其协商层利用RSA公钥进行身份认证,记录层涉及到对应用程序提供的信息的分段、压缩、数据认证和加密。
文件系统采用多重索引结构搜索文件内容。设块长为512字节,每个块号长3字节,如果不考虑逻辑块号在物理块中所占的位置,那么两级索引时可寻址的文件最大长度为(4)。
4台Linux主机通过如图5-2所示的方式互联,则实现PC1与PC4之间互访的步骤为:1.运行(61)命令关闭计算机,在PC2与PC3上添加第二块网卡(eth1),重新启动;2.在PC2与PC3上为第二块网卡分配IP地址,并激活该网络接口,对于PC3
TCP是互联网中的(6)协议,使用(7)次握手协议建立连接。当主动方发出SYN连接请求后,等待对方回答(8)。这种建立连接的方法可以防止(9)。TCP使用的流量控制协议是(10)。
Inthefollowingessay,eachblankhasfourchoices.Choosethebestanswerandwritedownontheanswersheet.Microwavecom
UML提供了一系列的图支持面向对象的分析与设计,其中(13)给出系统的静态设计视图;(14)对系统的行为进行组织和建模是非常重要的;(15)和(16)都是描述系统动态视图的交互图,其中(15)描述了以时间顺序组织的对象之间的交互活动,(16)强调收发消息的
Traditionalnetworklayerpacketforwardingreliesontheinformationprovidedbynetworklayer(71)protocols,orstaticrouting,
随机试题
驾驶人连续驾驶4小时以上,停车休息的时间不得少于多少?
关于“妊娠、分娩和产褥期(O00-099)”分类要点正确的是
患儿,女,5岁。面色萎黄,形体消瘦,不思饮食,烦躁啼哭,毛发稀疏,大便如米泔,舌苔黄腻,脉细。治疗应首选()
"腹中积块,固定不移,胀痛有定处,面黯形瘦,肌肤甲错,时有寒热"相应舌脉为
环境影响评价要求实行环境与经济协调发展的政策,其主要含义被归纳为“三建设、三同步、三统一”。其中“三同步”是指()。
会计职业道德修养的含义包括()。
某市甲独立矿山2018年4月发生如下经济业务:(1)开采原煤4万吨将其中1万吨原煤直接对外销售给乙公司,乙公司应付不含税金额200万元(不包括到车站、码头等的运输费用),甲煤矿采取分期收款方式,销售合同规定当月收取120万元,剩余款项下月收取。
我们每一个人,终其一生,都在不断受到新环境的生存挑战,我们必须不断增长智慧和能力。由于新环境的生存挑战完全不可预测,因此,我们的教育也完全不可预设,不可僵化,不可束缚,而应该成为最能够激发人智力的一种训练。如果不顾日新月异的社会发展和环境变化,一味执行因循
设四元齐次线性方程组若该方程组仅有零解,则λ().
Icouldn’tstopcrying.Monthsoflateeveningsanddemandingtravelhad【C1】______myprofessionalexterior.Itriedto【C2】______
最新回复
(
0
)