首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明、图和C代码。 [说明5-1] B树是一种多叉平衡查找树。一棵m阶的B树,或为空树,或为满足下列特性的m叉树: ①树中每个结点最多有m棵子树; ②若根结点不是叶子结点,则它至少有两棵子树; ⑧除根之外的所有非叶子结点至少有
阅读下列说明、图和C代码。 [说明5-1] B树是一种多叉平衡查找树。一棵m阶的B树,或为空树,或为满足下列特性的m叉树: ①树中每个结点最多有m棵子树; ②若根结点不是叶子结点,则它至少有两棵子树; ⑧除根之外的所有非叶子结点至少有
admin
2008-02-15
53
问题
阅读下列说明、图和C代码。
[说明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树如下图所示(结点中关键字的数目省略)。
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,ElemKcyTypeakey,BTreeNode:*pb)的功能是:在给定的一棵M阶B树中查找关键字akey所在结点,若找到则返回TRUE,否则返回 FALSE。其中,root是指向该M阶B树根结点的指针,参数ptr返回akey所在结点的指针,若akey不在该B树中,则ptr返回查找失败时空指针所在结点的指针。例如,在上图所示的4阶B树中查找关键字25时,ptr返回指向结点e的指针。
注;在结点中查找关键字akey时采用二分法。
[函数5-1]
bool SearchBtree(BTreeNode* root, ElemKeyType akey, BTreeNode **ptr)
{
int lw, hi, mid;
BTreeNode*p = root;
*ptr = NULL;
while ( p ) {
1w = 1; hi=(1);
while (1w <= hi) {
mid = (1w + hi)/2;
if (p -> K[mid] == akey) {
*ptr = p;
return TRUE;
}
else
if ((2))
hi=mid - 1;
else
1w = mid + 1;
}
*ptr = p;
p = (3);
}
return FALSE;
}
[说明5-2]
在M阶B树中插入一个关键字时,首先在最接近外部结点的某个非叶子结点中增加一个关键字,若该结点中关键字的个数不超过M-1,则完成插入;否则,要进行结点的“分裂”处理。所谓“分裂”,就是把结点中处于中间位置上的关键字取出来并插入其父结点中,然后以该关键字为分界线,把原结点分成两个结点。“分裂”过程可能会一直持续到树根,若树根结点也需要分裂,则整棵树的高度增加1。
例如,在上图所示的B树中插入关键字25时,需将其插入结点e中。由于e中已经有3个关键字,因此将关键字24插入结点e的父结点b,并以24为分界线将结点e分裂为e1和e2两个结点,结果如下图所示。
函数Isgrowing(BTreeNode*root,ElemKeyTypeakey)的功能是:判断在给定的M阶B树中插入关键字akey后,该B树的高度是否增加,若增加则返回TRUE,否则返回FALSE。其中,root是指向该M阶B树根结点的指针。
在函数Isgrwing中,首先调用函数SearchBtree(即函数5-1)查找关键字akey是否在给定的M阶B树中,若在,则返回FALSE(表明无需插入关键字akey,树的高度不会增加);否则,通过判断结点中关键字的数目考查插入关键字akey后该B树的高度是否增加。
[函数5-2]
bool Isgrowing(BTreeNode* root, ElernKeyType akey)
{ BTreeNode *t, *f;
if( !SearchBtree((4) ) ) {
t=f;
while ((5)) {
t=t -> parent;
}
if( !t )
return TRUE;
}
return FALSE;
}
选项
答案
(1)p->numkeys;或其等价形式 (2)p->K[mid]>akey,或其等价形式 (3)p->A[hi],或p->A[1w-1],或其等价形式 (4)root,akey,&f (5)t&&t->numkeys==M-1,或其等价形式
解析
本题考查C程序设计。
B树是一种多叉平衡查找树,由B树的定义可知,在B树上进行查找的过程是:首先在根结点所包含的关键字中查找给定的关键字,若找到则成功返回:否则确定待查找的关键字所在的子树并继续进行查找,直到查找成功或查找失败(指针为空)为止。树的内部结点中关键字存储在数组中并按照递增顺序排列,因此可以用二分法查找某个关键字是否在指定的结点中。
二分法查找元素的过程是:首先令待查找的元素与查找表中间位置上的元素进行比较,若相等,则查找成功,否则,根据待查元素与表中间位置元素的大小关系,下一步到查找表的前半区间或后半区间继续进行二分查找。如果在确定的任何一个子区间都找不到指定的元素,则确定查找失败。若查找区间用一对下标1w和hi确定,则1w≤hi表示有效的查找区间,查找失败时所确定的查找区间为1w>hi。
例如,上图中的结点c包含了关键字60、70、80,那么在c结点中找不到元素65,由于65介于60和70之间,因此下一步必将进入h结点继续查找。
每个结点中的关键字数目由BTreeNode中的numkeys域表示,结点中的查找表存储在数组K[]中,由于下标0未用,因此numkeys个关键字存储在K11)~K[numkeys]中。显然开始在p所指向的结点中进行查找时,确定查找表的下标为1和结点的numkeys域,因此函数5-1的空(1)处应填入“p->numkeys”。
若用1w和hi指示出查找区间,则由于查找表元素的递增排列特性,当待查找的元素小于表中间位置的元素时,下一步应在前半区间查找,即查找区间的一对下标为1w、 mid-1,也就是说函数5-1的空(2)处应填入“akey<p->K[mid]。
如果在当前结点中找不到指定的关键字akey,则1w>hi,由结点中的指针A[hi]或 A[1w-1]指示出下一层的子树结点,因此函数5-1的空(3)处应填入“p>A[hi]”或“p-> A[1w-1]”。
下面分析函数5-2的功能及运算过程。函数5-2用于判断在B树中插入一个关键字时,树的高度是否增加。若指定的关键字已经在B树的某结点中,就不需要插入该关键字,显然树也不会长高。
实现函数调用时实参要向形参传递信息,C语言采取传值调用方式,根据实参向形参的值传递原则,函数4-2中的空(4)处应填入“root,akey,&f"。
根据题目中给出的描述,在M阶B树中插入一个关键字时,首先在最接近外部结点的某个非叶子结点中增加一个关键字,若该结点中关键字的个数不超过M-1,则完成插入;否则,要进行结点的“分裂”处理。所谓“分裂”,就是把结点中处于中间位置上的关键字取出来并插入其父结点中,然后以该关键字为分界线,把原结点分成两个结点。“分裂”过程可能会一直持续到树根,若树根结点也需要分裂,则整棵树的高度增加1。
显然考查插入关键字akey后树的高度是否增加,只需沿其祖先结点关系一直考查直到树根为止,判断依据就是每个待考查的结点中目前已有的关键字个数,因此函数5-2中的空(5)处应填入“t&&t->numkeys==M-1”。
转载请注明原文地址:https://kaotiyun.com/show/DfDZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
在GB/T 17544中,软件包质量要求包括三部分,即产品描述要求、(53)、程序和数据要求。
针对以下程序段,对于变量c的取值,至少需要(61)个测试用例才能够满足语句覆盖的要求。c=((u8_t*)q->payload)[i];switch(c){caseSLIP_END:sio_send(SLIP_ESC,netif->state);
通过疲劳强度测试,最容易发现(55)问题。
为验证某音乐会订票系统是否能够承受大量用户同时访问,测试工程师一般采用(62)测试工具。
为了使软件测试更加高效,应遵循的原则包括______。①所有的软件测试都应追溯到用户需求,充分注意缺陷群集现象②尽早地和不断地进行软件测试、回归测试③为了证明程序的正确性,尽可能多地开发测试用例④应由不同的测试人员对测试所发
集成测试关注的问题不包括()。
在面向对象技术中,(43)是一组具有相同结构、相同服务、共同关系和共同语义的(44)集合,其定义包括名称、属性和操作。(43)
对某商店业务处理系统采用数据流图(DFD)进行功能建模,其中“检查订货单”是其中的一个①。由于在进行订货单检查时,需要根据客户的欠款情况、订单金额等多个条件判断是否采取发出催款单、准备货物、发出发货单等行为,此时适合采用②进行描述。①处
若要求对大小为n的数组进行排序的时间复杂度为O(nlog2n),且是稳定的(即如果待排序的序列中两个数据元素具有相同的值,在排序前后它们的相对位置不变),则可选择的排序方法是______。
以下关于数据流图的叙述中,不正确的是______。
随机试题
BX1-330型弧焊电源是()式弧焊变压器。
“流行”散谈(其二)“流行”在运动的过程中,有时也会回过头来看一看。流行不是天降之物。流行的源头是传统。没有源头,哪来潮头?无“源”无“根”的事物不可能存在。流行是传统的变异。任何能够称为传统的事物,在时代的演变中都要经受现实的检验。
直立位时血液流向下肢,长期卧床的患者易发生直立性低血压。其发生机制除重力作用还有
智齿冠周炎的治疗原则中,不包括
皮内注射常见的注射部位包括
甲将邻居交售粮站的稻米淋洒农药,取出部分作饵料,毒死麻雀后售与饭馆,非法获利5000元。关于甲行为的定性,下列哪一选项是正确的?()(2010/2/11)
在俄国伏特加酒市场,有一品牌为Smimoff,虽然产在美国,但其品名及广告形象均俄国化,并且定位专攻上层人士以及中高档价格的差异化产品。后来出现了以品牌名为Stolichnaya的伏特加酒,价格更高,并明确专为俄国人特别制作,更为独特。其效果是Stolic
当同学们获悉本班取得学校合唱比赛第一名的成绩时欣喜若狂。他们的情绪状态属于()。
100个骨牌整齐地排成一列,依次编号为1、2、3、4…99、100。如果第一次拿走所有偶数位置上的牌,第二次再从剩余牌中拿走所有偶数位置上的牌,第三次再从剩余牌中拿走所有奇数位置上的牌,第四次再从剩余牌中拿走所有奇数位置上的牌,第五次再从剩余牌中拿走所有偶
近日,英国剑桥大学医学院癌症研究所和美国冷泉港实验室的科学家宣布,他们在独立进行的研究活动中,从多种人体癌细胞中分离出了单独的基因,通过大量实验证明了这些基因可以使人体正常的健康细胞发生癌变。多年来,基因研究领域的科学家一直认为,可以通过改变这种基因的办法
最新回复
(
0
)