首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列函数说明和C函数,将应填入(n)处的字句写在对应栏内。 【说明】 函数DeleteNode(Bitree*r,inte)的功能是:在树根节点指针为r的二叉查找(排序)树上删除键值为e的节点,若删除成功,则函数返回0,否则函数返回-1。二叉查
阅读下列函数说明和C函数,将应填入(n)处的字句写在对应栏内。 【说明】 函数DeleteNode(Bitree*r,inte)的功能是:在树根节点指针为r的二叉查找(排序)树上删除键值为e的节点,若删除成功,则函数返回0,否则函数返回-1。二叉查
admin
2013-05-11
69
问题
阅读下列函数说明和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
软件设计师上午基础知识考试
软考中级
相关试题推荐
在Linux操作系统中提供了大量的网络配置命令,其中不带参数的route命令用来查看本机的路由信息,(70)命令也可以完成该项功能。
现在具有加密/解密功能的路由器使人们通过互联网连接这些局域网成为可能,这就是我们通常所说的虚拟专用网(Virtual Private Network,VPN),下列各项属于VPN所采用的加密手段的是(7)。
下面关于IPv6单播地址的描述中,正确的是__________。(2013年上半年试题)
以太网中,当数据传输提高时,帧的发送时间要按比例缩短,这样有可能会影响冲突的检测。为了能有效地检测冲突,可以(1)或者(2)。快速以太网仍然遵循CSMA/CD,它采取(3)而将最大电缆长度减少到100m的方式,使以太网的数据传输速率提高到100Mb/s。
M软件公司的软件产品注册商标为M,为确保公司在市场竞争中占据优势,对员工进行了保密约束。此情形下该公司不享有__________。(2012年下半年试题)
内存按字节编址,地址从90000H~CFFFFH,若用存储容量为16Kx8bit的存储器芯片构成该内存,至少需要__________片。
某企业有生产部和销售部,生产部负责生产产品并送入仓库,销售部从仓库取出产品销售。假设仓库可存放n件产品。用PV操作实现它们之间的同步过程如下图所示。(2012年下半年试题)图中信号量S1和S2为同步信号量,初值分别为n和0;S是一个互斥信号量,初值为___
在Windows客户端运行nslookup命令,结果如下图所示。为www.softwaretest.com提供解析的是__________(33)。在DNS服务器中,ftp.softwaretest.com记录通过__________(34)方式建立。C
Network managers have long awaited practical voice-over-IP(VOIP)solutions. VOIP promises(71)network management and decreases cos
ExtremeProgramming(XP)isadisciplineofsoftwaredevelopmentwith(71)ofsimplicity,communication,feedbackandcourage.Successf
随机试题
A、She’llcallthemanintenminutes.B、She’llmeetthemanafterwork.C、Sheacceptshisinvitation.D、Sheforgetstobringher
就技术和财力而言,他的建议听起来可行。
下列有关弛豫的表述,正确的是
以下处方书写不正确的是()。
中国证监会于2006年8月发布了《关于基金管理公司提取风险准备金有关问题的通知》,要求公司每月计提风险准备金,用于赔偿因公司()等给基金财产或基金份额持有人造成的损失。
下列各项中,属于增值税低税率货物,按照11%缴纳增值税的有()。
【2016年河南许昌】受教育对公民来说,既是权利又是义务。()
我国实行()的代表机关组成方式。
(2016年第25题)从2013年3月到2015年7月,李克强总理主持召开了101次国务院常务会议,其中有46次会议部署简政放权,取消和下放了800多项行政审批事项。他还用“大道至简,有权不可任性”“用政府权力的‘减法’换取市场活力的‘乘法’”等生动而深刻
Frenchareelegantpeople.Theyareartistsineverydaylife,havingaverygoodtasteineverything.Theydon’tlikeAmericant
最新回复
(
0
)