首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明、图和C代码。 [说明5-1] B树是一种多叉平衡查找树。一棵m阶的B树,或为空树,或为满足下列特性的m叉树: ①树中每个结点最多有m棵子树; ②若根结点不是叶子结点,则它至少有两棵子树; ⑧除根之外的所有非叶子结点至少有
阅读下列说明、图和C代码。 [说明5-1] B树是一种多叉平衡查找树。一棵m阶的B树,或为空树,或为满足下列特性的m叉树: ①树中每个结点最多有m棵子树; ②若根结点不是叶子结点,则它至少有两棵子树; ⑧除根之外的所有非叶子结点至少有
admin
2008-02-15
52
问题
阅读下列说明、图和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
软件设计师下午应用技术考试
软考中级
相关试题推荐
在软件生命周期的不同阶段,需要实施不同类型的测试工作,单元测试是对程序设计进行验证,其中(39)不是单元测试的主要内容。在进行单元测试过程中,通常测试工程师都需要借助(40)来代替所测模块调用的子模块;在单元测试的基础上,需要将所有模块按照概要设计和详细设
为了解决进程间的同步和互斥问题,通常采用一种称为(21)机制的方法。若系统中有5个进程共享若干个资源R,每个进程都需要4个资源R,那么使系统不发生死锁的资源R的最少数目是(22)。
在“模型一视图一控制器(NVC)”模式中,(27)主要表现用户界面,(28)用来描述核心业务逻辑。
针对以下C语言程序段,对于(MaxNum,Type)的取值,至少需要(62)个测试用例能够满足判定覆盖的要求。while(MaxNum-->0){if(10==Type)x=y*2;elseif(100==Type)
负载压力性能测试需求分析时,应该选择(63)类型的业务作为测试案例。 ①高吞吐量的业务 ②业务逻辑复杂的业务 ③高商业风险的业务 ④高服务器负载的业务 ⑤批处理的业务
在数据库逻辑设计阶段,若实体中存在多值属性,那么将E-R图转换为关系模式时,___________,得到的关系模式属于4NF。
某个应用中,需要对输入数据进行排序,输入数据序列基本有序(如输入为1,2,5,3,4,6,8,7)。在这种情况下,采用(40)排序算法最好,时间复杂度为(41)。(41)
如果在查找路由表时发现有多个选项匹配,那么应该根据___________(25)原则进行选择。假设路由表有4个表项如下所示,那么与地址139.17.179.92匹配的表项是____________(26)。(26)
设数组a[0..n—1,0..m一1](n>1,m>1)中的元素以行为主序存放,每个元素占用4个存储单元,则数组元素a[i,j](0≤i
完成下列命令行,对网络接口进行地址初始化配置。firewall(config)#ipaddressinside(1)(2)firewall(config)#ipaddressoutside(3)(4)管道命令的作用是允许数据流从
随机试题
颜元在教育内容上提出了()学的主张,将漳南书院规划为()斋,分别为()斋、()斋、()斋、()斋、()斋、(
Infamilieswithtwoworkingparents,fathersmayhavemoreimpactonachild’slanguagedevelopmentthanmothers,anewstudys
哪种细菌是引起胃癌的危险因子
我国的土地权属性质分为()。
固定资产的大修理支出,是指修理支出达到取得固。定资产时的统计税基础()以上,且修理后固定资产的使用年限延长2年以上的支出。
关于消费税纳税义务发生时间的说法,正确的有()。
某县城一家房地产开发企业2叭1年度委托建筑公司承建住宅楼10栋,其中:80%的建筑面积直接对外销售。取得销售收入7648万元;其余部分暂时对外出租,本年度内取得租金收入63万元。与该住宅楼开发相关的成本、费用有:(1)支付土地使用权价款1400万元。(2)
公安专业工作具有( )的特点。
社会主义市场经济体制的微观基础是()。
5.对基础研究投入大量经费似乎作用不大,因为直接对生产起作用的是应用型技术。但是,应用技术发展需要基础理论研究作后盾。今天,纯理论研究可能暂时看不出有什么用处,但不能肯定它将来也不会带来巨大效益。下面哪项是上述论证的前提假设?
最新回复
(
0
)