首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列函数说明和C函数,将应填入(n)处的字句写在对应栏内。 【说明】 函数DeleteNode(Bitree*r,inte)的功能是:在树根节点指针为r的二叉查找(排序)树上删除键值为e的节点,若删除成功,则函数返回0,否则函数返回-1。二叉查
阅读下列函数说明和C函数,将应填入(n)处的字句写在对应栏内。 【说明】 函数DeleteNode(Bitree*r,inte)的功能是:在树根节点指针为r的二叉查找(排序)树上删除键值为e的节点,若删除成功,则函数返回0,否则函数返回-1。二叉查
admin
2013-05-11
51
问题
阅读下列函数说明和C函数,将应填入(n)处的字句写在对应栏内。
【说明】
函数DeleteNode(Bitree*r,inte)的功能是:在树根节点指针为r的二叉查找(排序)树上删除键值为e的节点,若删除成功,则函数返回0,否则函数返回-1。二叉查找树节点的类型定义为:
typedef struct Tnode{
int data;/*节点的键值*/
struct Tnode *Lchild,*Rchiid;/*指向左、右子树的指针*/
}*Bitree;
在二叉查找树上删除一个节点时,要考虑3种情况。
①若待删除的节点p是叶子节点,则直接删除该节点。
②若待删除的节点p只有一个子节点,则将这个子节点与待删除节点的父节点直接连接,然后删除节点。
③若待删除的节点p有两个子节点,则在其左子树上,用中序遍历寻找关键值最大的节点 s,用节点s的值代替节点p的值,然后删除节点s,节点s必属于上述①、②情况之一。
【函数5-5】
int DeleteNode(Bitree *r,int e){
Bitree p=*r,pp,s,c;
while( (1) {/*从树根节点出发查找键值为e的节点*/
pp=p;
if(e<p->data)p=p->Lchild;
else p=p->Rehild;
}
if(!p)retrn -1;/*查找失败*/
if(p->Lchild && p->Rchild){/*处理情况③*/
s=(2); pp=p;
while( (3)){pp=s;s=s->Rchild;}
p->data=s->data;p=s;
}
/* 处理情况①、②*/
if((4))c=p->Lchild;
else c=p->Rchild;
if(p== *r)*r=c;
else if((5))pp->Lchild=c;
else pp->Rchild=c;
free(p);
return 0;
}
选项
答案
(1) p&&p->data!=e或p&&(*p).data!=e (2) p->Lchild或(*p).Lchild (3) s->Rchild或(*s).Rchild (4) p->Lchild或(*p).Lchild (5) p==pp->Lchild或p==(*pp).Lchild
解析
本题考查二叉查找树上的删除操作,题中已清楚说明了删除操作的算法。
删除一个节点首先需要进行查找,只有找到了欲删除的节点才谈得上删除。程序首先让指针p指向根节点,通过while循环进行查找。循环体内,先用pp记录p,这样pp最终将记录p的父节点,然后如果得删关键字e小于当前节点p的键字值,则p赋值为p->Lchild,即往左子树继续查找,否则,p赋值为p->Rchild,即往右子树继续查找。显然,循环体内并未处理关键字正好等于当前节点p的键值的情况,因此该条件应体现在while循环的终止条件中。故空(1)应填“p&&p->data!=e”。
空(2)比较简单。此处是处理情况③,而根据算法描述,情况③要在左子树中寻找键值最大的节点,亦即左子树中最右的节点(右节点为NULL),并保存在s中。故空(2)应填 p->Lchild。空(3)所在while循环正是用来在p的左子树中查找右节点为NULL的节点的,故空(3)应填s->Rchild。
接下来处理情况①和情况②,这两种情况本身是比较简单的,但在此将两者合并在一起处理,增加了难度。首先用变量c来存储用来替换p的节点,然后分情况将c正确插入。
当要删除的节点为叶节点时(情况①),其p->Lchild和p->Rchild均为NULL;当要删除的节点只有一个子节点时(情况②),若仅有左子节点,则p->Rchild为NULL,若仅有右子节点,则p->Lchild为NULL。所以当p->Lchild不为NULL时,说明是情况②:仅有左节点情况,故c=p->Lchild。当p->Lchild为NULL时,则有两种可能:p->Rchild也为NULL,则对应情况①叶节点情况;p->Rchild不为NULL,则对应情况②仅有右节点情况。但这两种情况下,亦可以统一采用c=p->Rchild,因为当p是叶节点时用NULL代替其位置即可。所以空(4)应填“p->Lchild!=NULL”。
接下来就要将c正确插入到原二叉树中。上面已经提到,pp指向的是p节点的父节点。因此若p是pp的左节点,则将c作为pp的左子节点插入,因此空(5)应填“p==pp->Lchild”。
转载请注明原文地址:https://kaotiyun.com/show/CBRZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
GB/T19000.3—2000质量管理和质量保证标准第三部分:GB/T19001—1994在计算机软件开发、供应、安装和维护中的使用指南(idtISO9000-3:1997)。其中,“idt”是一种(8)关系。
利用结构化分析模型进行接口设计时,应以______为依据。
下面有关BGP4协议的描述中,不正确的是__________。(2008年上半年试题)
OSPF协议适用于4种网络。下面的选项中,属于广播多址网络(BroadcastMulti—Access)的是(1),属于非广播多址网络(NoneBroadcastMulti-Access)的是(2)。(2009年上半年试题)(2)
入侵检测系统(IDS)是一类专门面向网络入侵检测的网络安全监测系统,其基本功能包括:检测出(1);发现攻击活动的范围和后果;诊断并发现攻击者的入侵方式和入侵地点,并给出解决建议;收集并记录(2)。IDS系统还可以(3)。IDS系统的服务功能
在SNMP管理模型中,关于管理信息库MIB的说法,正确的是(1)。SNMP实现管理功能的方式是(2)。SNMP网络管理模型中关于管理代理与委托代理的说法正确的是(3)。SNMP将一个值存储到指明变量中去使用(4)命令,而有关get操作命令的目的是(5)。
网络由6个路由器互联而成,路由器之间的链路费用如下图所示,从PC到服务器的最短路径是(1),通路费用是(2)。(20lO年下半年试题)(1)
用作存储器的芯片有不同的类型。可随机读/写,且只要不断电,其中存储的信息就可一直保存的存储器,称为(38)。可随机读/写,但即使在不断电的情况下其存储的信息要定时刷新才不致丢失的存储器,称为(39)。所存信息由生产厂家用掩膜技术写好后就无法再改变的存储器称
下面是一个Applet程序,其功能是在绘图区域中通过鼠标的移动来绘制直线,并且有清除绘图区域按钮,用来清除已经绘制的图像。程序运行结果如图5所示。importjava.awt.*;importjava.applet.*;
Network managers have long awaited practical voice-over-IP(VOIP)solutions. VOIP promises(71)network management and decreases cos
随机试题
运输费、装卸费、包装费、保险费,以及为销售本公司产品而专设的销售机构的职工工资、福利费等属于营业费用。()
临床复查白细胞计数,评价其准确性的参考方法是
某药物进行中间体杂质检查:取该药0.2g,加水溶解并稀释至25.0ml,取此液5.0m1,稀释至25.0ml,摇匀,置1cm比色皿中,于320nm处测得吸收度为0.05。另取中间体对照品配成每1ml含8μg的溶液,在相同条件下测得吸收度是0.435,该药物
女孩,16岁,13岁初潮,月经周期不规律,7~15/35~65天,每次经量较多,一般用卫生巾2~3包,疲乏消瘦,面色黄白,学习紧张倍感劳累。基础体温呈单相。最可能诊断的疾病是
女,35岁。因慢性肾盂肾炎入院,第2天需做尿常规检查。王护士给了病人1个干燥的空瓶子,嘱其“第2天早晨起床留小便,约200ml"。王护士工作中的疏忽是()。
关于项目决策与造价的关系,下列说法中错误的是()。
按照合同的约定,2007年1月1日发包方应该向承包方支付工程款,但没有支付。2007年7月1日至8月1日之间,当地发生了特大洪水,导致承包方不能行使请求权。2007年12月3日,承包方向法院提起诉讼,请求发包方支付拖欠的工程款,2007年12月31日法院做
通常情况下,相比较而言,下列因素更值得投资者重视的是( )。
一般资料:求助者,女性,47岁,已婚,本科文化,公务员,处级干部。案例介绍:一年前求助者的父亲曾做过心脏手术,术后恢复良好。半年多来求助者经常觉得自己心前区不舒服,担心自己也患上心脏病,为此很紧张。经常对丈夫说:“我要是得了心脏病可怎么办啊!”晚上
Whydidthewomandecidetocancelhervacation?
最新回复
(
0
)