首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列C函数和函数说明,将应填入(n)处的字句写在对应栏内。 【说明】 函数DeleteNode (Bitree *r, int e)的功能是:在树根结点指针为r的二叉查找(排序)树上删除键值为e的结点,若删除成功,则函数返回0,否则函数返
阅读下列C函数和函数说明,将应填入(n)处的字句写在对应栏内。 【说明】 函数DeleteNode (Bitree *r, int e)的功能是:在树根结点指针为r的二叉查找(排序)树上删除键值为e的结点,若删除成功,则函数返回0,否则函数返
admin
2010-01-15
88
问题
阅读下列C函数和函数说明,将应填入(n)处的字句写在对应栏内。
【说明】
函数DeleteNode (Bitree *r, int e)的功能是:在树根结点指针为r的二叉查找(排序)树上删除键值为e的结点,若删除成功,则函数返回0,否则函数返回-1。二叉查找树结点的类型定义为:
typedef struct Tnode{
int data; /*结点的键值*/
struct Tnode *Lchild, *Rchild; /*指向左、右子树的指针*/
}*Bitree:
在二叉查找树上删除一个结点时,要考虑3种情况:
①若待删除的结点p是叶子结点,则直接删除该结点;
②若待删除的结点p只有一个子结点,则将这个子结点与待删除结点的父结点直接连接,然后删除结点p;
③若待删除的结点p有两个子结点,则在其左子树上,用中序遍历寻找关键值最大的结点s,用结点s的值代替结点p的值,然后删除结点s,结点s必属于上述①、②情况之一。
【函数】
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!=NULL&&p->data!=e或p&&(*p).data!=e (2)p->Lchild或(*p).Lchild (3)p->Rchild或(*p).Rchild (4)p->Lchild或(*p).Lchild (5)pp->Lchid=p或p=(*pp).child
解析
本程序的功能是删除二叉查找树的一个结点。题目中对怎样删除结点有着比较详细的说明。
第1种情况就是删除叶子结点,叶子结点可以直接删除,这一点很好理解,因为叶子结点删除后并不会打乱查找树的顺序。
第2种情况是删除只有一个子结点的结点,只需把其子结点代替父结点即可。若子结点下有子树,子树结构不变。
第3种情况要复杂一点,要用到二叉查找树的一些性质,就是结点右子树的所有结点都大于根结点,左子树所有结点都小于根结点。所以,当删除了有左右子树的结点时,要在左子树找最大的结点,来替换被删结点。
转载请注明原文地址:https://kaotiyun.com/show/w0DZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
在分布式数据库中有分片透明、复制透明、位置透明和逻辑透明等基本概念,其中:___________(19)是指局部数据模型透明,即用户或应用程序无须知道局部使用的是哪种数据模型;___________(20)是指用户或应用程序不需要知道逻辑上访问的表具体是怎
设系统中有R类资源m个,现有n个进程互斥使用。若每个进程对R资源的最大需求为w,那么当m、n、w取下表的值时,对于下表中的a~e五种情况,(26)两种情况可能会发生死锁。对于这两种情况,若将(27),则不会发生死锁。
下图为某设计模式的类图,类State和Context的关系为(49),类(50)是客户使用的主要接口。(49)
以下关于汇编语言的叙述中,错误的是______。A.汇编语言源程序中的指令语句将被翻译成机器代码B.汇编语言的指令语句必须具有操作码字段,可以没有操作数字段C.汇编程序以汇编语言源程序为输入,以机器语言表示的目标程序为输出D.汇编程序先将源程序中的
上海市标准化行政主管部门制定并发布的工业产品的安全、卫生要求的标准,在其行政区域内是(10)。
关于汇编语言,以下叙述中正确的是(20)。
在IPv4向IPv6的过渡期间,如果要使得两个IPv6结点可以通过现有的IPv4网络进行通信,则应该使用(27);如果要使得纯IPv6结点可以与纯IPv4结点进行通信,则需要使用(28)。(28)
在IPv4向IPv6的过渡期间,如果要使得两个IPv6结点可以通过现有的IPv4网络进行通信,则应该使用(27);如果要使得纯IPv6结点可以与纯IPv4结点进行通信,则需要使用(28)。(27)
某文件管理系统采用位示图(bitmap)记录磁盘的使用情况。如果系统的字长为32位,磁盘物理块的大小为4MB,物理块依次编号为:0、1、2、…,位示图字依次编号为:0、1、2、…,那么16385号物理块的使用情况在位示图中的第(24)个字中描述;如果磁盘的
______不是正确的软件测试目的。A.尽最大的可能找出最多的错误B.设计一个好的测试用例对用户需求的覆盖度达到100%C.对软件质量进行度量和评估,以提高软件的质量D.发现开发所采用的软件过程的缺陷,进行软件过程改进
随机试题
交流换向器电动机的调速方法是改变()。
著有“爱情三部曲”,并被誉为“二十世纪中国文学的良心”的是()
体温调节中枢内具有整合功能的部位是
下列哪项处理措施正确对胎儿、新生儿不会产生哪种影响
(2009年)已知氯电极的标准电极电势为1.358V,当氯离子浓度为0.1mol/L,氯气浓度为0.1×100kPa时,该电极的电极电势为()V。
下列观点正确的有()。
对于下列哪些犯罪可以进行无过当防卫?()
下列有关数据库的描述,正确的是
Theemployeestriedtoavoideveryriskthatmight______herdispleasureduringthefirstmonthaftershewasdivorcedbyherhus
"Makeadifference"Oneminutevideocompetition!Lookingforawaytomakeadifference?Createaone-minutevideototell
最新回复
(
0
)