2007年11月软件设计师模拟试题（4）下午试卷

 
图 3
s
●试题三
阅读下列函数说明和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;
}

2007计算机软件水平考试冲刺专题

2007计算机软件水平考试模拟试题汇总

希望与其他软考考生进行交流？点击进入软考论坛>>>

进入考试吧博客记录下自己的备考历程吧

更多信息请访问：考试吧软件水平考试栏目