首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列函数说明和C函数,将应填入(n)处。 【函数3说明】 函数DeleteNode(Bitree * r,int e)的功能是:在树根结点指针为r的二叉查找(排序)树上删除键值为e的结点,若删除成功,则函数返回0,否则函数返回-1。二叉查
阅读下列函数说明和C函数,将应填入(n)处。 【函数3说明】 函数DeleteNode(Bitree * r,int e)的功能是:在树根结点指针为r的二叉查找(排序)树上删除键值为e的结点,若删除成功,则函数返回0,否则函数返回-1。二叉查
admin
2009-02-15
44
问题
阅读下列函数说明和C函数,将应填入(n)处。
【函数3说明】
函数DeleteNode(Bitree * r,int e)的功能是:在树根结点指针为r的二叉查找(排序)树上删除键值为e的结点,若删除成功,则函数返回0,否则函数返回-1。二叉查找树结点的类型定义为:
typedef struct Tnode{
int data; /*结点的键值*/
struct Tnode * Lchild,*Rchild; /*指向左、右子树的指针*/
} * Bitree;
在二叉查找树上删除一个结点时,要考虑三种情况:
①若待删除的结点p是叶子结点,则直接删除该结点;
②若待删除的结点p只有一个子结点,则将这个子结点与待删除结点的父结点直接连接,然后删除结点P;
③若待删除的结点p有两个子结点,则在其左子树上,用中序遍历寻找关键值最大的结点s,用结点s的值代替结点p的值,然后删除结点s,结点s必属于上述①、②情况之一。
【函数3】
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->Rchild;
{
if(!p)return-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
解析
(1)程序的第一条语句是变量的声明及赋初值,p指向二叉查找树的根。接下来从while循环的注释部分可以看出,该循环的功能是查找键值为e的结点。当循环的判断条件e<p->data时,进入左子树查找,否则到右子树查找。程序中没有关于找到结点的处理代码,即循环内部只处理了没找到结点的情况,所以循环条件应该是当找到键值为e的结点时退出循环。另外,应注意一个隐含的限制条件“p’ NULL”时,表示已经查找完毕,无需进入循环。通过分析,(1)应填p &&p->data!=e。(2)if程序段是处理第三种情况的,由循环中的语句“s=s->Rchild;”可看出,s用于要删结点的左子树中查找键值最大的结点,所以s的初值应是要删除结点的左子结点。可见,(2)应填写 p->Lchild。(3)根据前面所述的二叉树规则可知,要找的结点s应是左子树中查找键值最大的结点,所以,的初值应是要删除结点的左子结点。可见,(3)应填p->Rehild。本题把①、②结合在一起进行处理,所以引入了一个中间变量c,用c来存储用于替换p的结点。现在的关键问题是什么条件可以使这两种情况和在一起,因为若删除的结点为叶子结点时,p->Rchild与p->Lchild都为NULL;若删除的结点有一个子结点时,如果有左子结点,则p->Rchild为p->Rchild;如果有右子结点,则p->Lchild为NULL。当p->Lchild不为NULL时,说明是第二种情况,p结点含左子结点,所以c=p->Lchild;当p->Lchild为 NULL时,说明有两种可能:
第一:p->Rchild也为NULL,则p是叶子结点。
第二:p->Rchild不为NULL,则p是有右子结点的结点。
这两种情况都可以用c=p->Rchild,因为当p是叶子结点的时候用NULL代替p的位置即可,所以第(4)应填p->Lehild。在程序中很多地方都出现了变量pp,其实只要仔细看一下前面的程序就知道,pp一直指向的是p结点的前一个结点,即p的父结点,所以(5)的作用是判断p是其父结点的左子结点还是右子结点,(5)应填pp->Lchild =p。
转载请注明原文地址:https://kaotiyun.com/show/GuDZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
程序描述语言(PDL)是软件开发过程中用于______阶段的描述工具。A.需求分析B.概要设计C.详细设计D.编程
A模块通过简单数据类型(如整型)参数访问B模块,该参数在B模块内用于数据计算,则A、B模块之间存在______。
以下关于软件质量和度量的说法,错误的是()。
使用质量是从用户的角度来看待的产品质量,其属性不包括()。
已知函数f()、g()的定义如下所示,执行表达式“x=f(5)”的运算时,若函数调用g(a)是引用调用(callbyreference)方式,则执行“x:f(5)”后x的值为(7);若函数调用g(a)是值调用(callbyvalue)方式,
兼容性测试的测试范围包括___________。①硬件兼容性测试②软件兼容性测试③数据兼容性测试④平台兼容性测试
已知函数f()、g()的定义如下所示,调用函数f时传递给形参x的值是5。若g(a)采用引用调用(callbyreference)方式传递参数,则函数f的返回值为(12);若g(a)采用值调用(callbyvalue)的方式传递参数,则函数f
以下所示程序控制流程图中有(59)条线性无关的基本路径。
在计算机系统中,系统的______可以用MTTF/(1+MTTF)来度量,其中MTTF为平均无故障时间。
软件设计阶段一般又可分为______。A.逻辑设计与功能设计B.概要设计与详细设计C.概念设计与物理设计D.模型设计与程序设计
随机试题
(2019年招远)德育中对人的陶冶,其内涵就是环境陶冶。()
牙釉质为覆盖于牙冠表面的一层硬组织,其厚度
一山羊,因发热、食欲减退乃至不食,已发病2天而来医院就治。人院后查体温41.1℃,结膜潮红,在唇、鼻、颊、眼周围、四肢和尾内面,阴唇、阴囊包皮和乳房的皮肤上有红斑或淡红色或灰白色突出于皮肤表面的丘疹、脓疱。对该病的防控措施不当的是
25公斤小儿体表面积为
某投资项目工程费用为2000万元。建设期为2年,分年的工程费用比例为第1年45%,第2年55%,建设期内年平均价格上涨指数为4%,则第2年的涨价预备费为()万元。
燃气管与给水管的水平净距以及燃气管顶与路面的距离有何要求?B公司对事故应该怎么负责?
个人转让无形资产的,以受让人为营业税扣缴义务人。()
“SMART”原则是管理学中的一个重要原则。下列对其理解正确的一项是()。
下列最接近完全竞争市场的是:
下列说法中正确的是()。
最新回复
(
0
)