调用函数malloc,便能得到一个所需结点的空间,并返回这个结点的总大小。
第1题:
● 以下应用中,必须采用栈结构的是 (41) 。
(41)
A. 使一个整数序列逆转
B. 递归函数的调用和返回
C. 申请和释放单链表中的结点
D. 装入和卸载可执行程序
第2题:
试题四
阅读下列函数说明和C函数,将应填入 (n) 处的字句写在答题纸的对应栏内。
[函数说明]
函数DeleteNode(Bitree *r,int e)的功能是:在树根结点指针为r的二叉查找(排序)树上删除键值为e的结点,若删除成功,则函数返回0,否则函数返回-1。二叉查找树结点的类型定义为:
typedef struct Tnode{
int data;
struct Tnode *Lchild,*Rchild;
}*Bitree;
在二叉查找树上删除一个结点时,要考虑三种情况:
1若待删除的结点p是叶子结点,则直接删除该结点;
2若待删除的结点p只有一个子结点,则将这个子结点与待删除结点的父结点直接连接,然后删除结点p;
3若待删除的结点p有两个子结点,则在其左子树上,用中序遍历寻找关键值最大的结点s,用结点s的值代替结点p的值,然后删除结点s,结点s必属于上述1、2情况之一。
[函数代码]
int DeleteNode(Bitree *r,int e) {
Bitreep = *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) { /* 处理情况3 */
s = (2);pp = p;
while ( (3) ) { pp = s; s = s-> Rchild; }
p->data = s ->data; p = s;
}
/*处理情况1、2*/
if( (4) ) c = p -> Lchild;
elsec = p -> Rchild;
if(p == *r) *r = c;
elseif ( (5) ) pp -> Lchild = c;
elsepp->Rchild = c;
free(p);
return 0;
}
试题分析:
本程序的功能是删除二叉查找树的一个结点。首先,我们来了解一下什么是二叉查找树。
二叉查找树,又称二叉排序树(BinarySort Tree)。一棵二叉查找树,或者是一棵空树,或者满足以下递归条件:
①查找树的左、右子树各是一棵查找树。
②若查找树的左子树非空,则其左子树上的各结点值均小于根结点的值。
③若查找树的右子树非空,则其右子树上的各结点值均大于根结点的值。
例如下图就是一棵二叉查找树。
了解二叉查找树的概念以后,我们再来看题目会有事半功倍的效果。题目中对怎样删除结点有着比较详细的说明。
第一种情况就是删除叶子结节,叶子结节可以直接删除,这一点很好理解,因为叶子结节删除后并不会打乱查找树的顺序。也就是说把上图中的“20”结点删除,剩下的还是一棵查找树。
第二种情况是删除只有一个子结点的结点,只需把其子结点代替父结点即可,也就是说若要删除图中的“56”结点,只需把“51”移至“56”位置即可,若“51”下有子树,子树结构不变。
第三种情况要复杂一点,要用到二叉查找树的一些性质,就是结点右子树的所有结点都大于根结节,左子树所有结点都小于根结点。所以,当删除了有左右子树的结点时,要在左子树找最大的结节,来替换被删结点。也就是说若要删除图中的”89”结点,要把“56”搬到“89”的位置。再用第二种情况规则,把“51”调整到原来56的位置。
现在我们已经了解了算法流程,可以开始具体的分析程序了。
第一句是变量的声明,以及赋初值,p指向二叉查找树的根。接下来是一个循环,从注释部分可以知道,此循环的功能是查找键值为e的结点。循环内有判断条件当e < p->data 时,进入左子树查找,否则到右子树中查找。很明显没有关于找到结点的处理代码,也就是说,循环内部只处理了没找到结点的情况,所以循环条件应是当找到键值为e的结点时退出循环,同时应注意一个隐含的限制条件,就是当p=NULL时,表示已经查找完毕,也不用进入循环了。所以(1)应填 p && p->data != e。
接下来的if 程序段是处理第 ③种情况的,由循环中的“s = s-> Rchild;”可以看出,s用于在要删结点的左子树中查找键值最大的结点。所以s的初值应是:要删除结点的左子结点。所以,(2)应填:p->Lchild。
结合前面提到的对第③条规则的描述以及二叉查找树的规则,我们可知,要找的结点s应是左子树最右的结点,即右子结点为NULL的结节。所以(3)应填S->Rchild。
再下来就是对①、②的处理了,这里并没有把①、②处理分开进行,而是合在一起进行处理,这里引入了一个中间变量c,用c来存储用于替换p的结点。
我们现在来分析一下,怎样的条件可以使这两种情况合在一起,因为当要删除的结点为叶子结点时,p->Lchild与p->Rchild都为NULL,当要删除的结点有一个子结点时,如果有左子结点,则p->Rchild为Null;如果有右子结点,则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->Lchild。在程序中很多地方都出现了变量pp,其实只要仔细看一下前面的程序就知道,pp一直指向的是p结点的前一个结点,即p的父结点,所以(5)的作用是,判断p是其父结点的左子结点,还是右子结点,也就是说(5)应填 pp->Lchild == p。
参考答案:(每空3分)
(1)p && p->data != e 或者 p!=NULL && p->data != e
(2)p->Lchild
(3)s->Rchild
(4)p->Lchild
(5)pp->Lchild == p 或者 p == pp->Lchild
第3题:
A.在扩展结点处,先生成其所有的儿子结点(分支)
B.从当前的活结点表中选择上一个扩展结点。
C.为了有效地选择下一扩展结点,加速搜索的进程,在每一个活结点处,计算一个函数值(限界)
D.根据函数值,从当前活结点表中选择一个最有利的结点作为扩展结点,使搜索朝着解空间上有最优解的分支推进,以便尽快地找出一个最优解。
第4题:
阅读以下函数说明和C语言函数,将应填入(n)处的字句写在对应栏内。
[说明1]
L为一个带头结点的循环链表。函数LinkList deletenode(LinkList L,int c)的功能是删除L中数据域data的值大于C的所有结点,并由这些结点组建成一个新的带头结点的循环链表,其头指针作为函数的返回值。
[C函数1]
LinkList deletenode(LinkList L,int c)
{LinkList Lc,P,pre;
pre=L;
p=(1);
Lc=(LinkList)malloc(sizeof(Listnode));
Lc->next=Lc;
while(P!=L)
if(p->data>C){
(2);
(3);
Lc->next=p;
p=pre->next;
}
else{
pre=p;
p=pre->next;
}
return Lc;
}
[说明2]
递归函数dec_to_k_2(int n,int k)的功能是将十进制正整数n转换成k(2≤k≤9)进制数,并打印。
[C函数2]
dec to k 2(int n,int k)
{ if(n!=O){
dec to k 2( (4) ,k);
printf("%d", (5) );
}
}
第5题:
阅读下列函数说明和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;
}
第6题:
阅读下列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;
}
第7题:
A、被调用函数中可以不用return语句
B、被调用函数中可以使用多个return语句
C、被调用函数中,如果有返回值,就一定要有return语句
D、被调用函数中,一个return语句可返回多个值给调用函数
第8题:
●试题三
阅读下列函数说明和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]
【答案】(1)F0是长话业务档案F1是长话用户档案。(2)处理1:电话号码处理5:用户编码。
【解析】本题给出的流程图是长话计费管理的处理流程,用来生成长话缴费通知单。系统的数据源是记录在电信局程控交换机磁带上的原始计费数据,这些数据在处理之前需要先进行分类,以提高系统的效率。原始计费数据记录的是每次通话的数据,长话缴费通知单是针对每个电话用户的,因此在处理1中应该按照电话号码进行分类。F0是在处理4(出账)中用来生成长话帐单文件所要用到的"长话业务档案"。由试题的说明可知,月计费文件中含有各种通话类型的话费,所以处理4(出账)的功能是长话话费从月计费文件中分离出来,并进行数据的验证。根据以上的分析得知F0应该是长话业务档案。F1是在处理6中生成长话缴费通知单所要用到的"长话用户档案"。因为用户编码是用户在系统中的惟一标识,所以应该先将长话帐单文件按照用户编码进行分类,再根据F1长话用户档案,得到用户名和用户地址,产生长话缴费通知单。因此F1应该是长话用户档案。
[问题2]
【答案】(1)根据月计费文件中的电话号码,在长话业务档案中找不到相应的用户编码。(2)在月计费文件中,某电话号码有国内长途通话的话费,但在长话业务档案中,国内长途许可标志却不许可。(3)在月计费文件中,某电话号码有国际长途通话的话费,但在长话业务档案中,国际长途许可标志却不许可。
[问题3]
【答案】对长话帐单文件中的每个记录,根据用户编码查询长途电话用户档案,找到相应的用户名和用户地址,形成长话缴费通知单。
第9题:
malloc函数申请的空间位于哪一个段?
第10题:
阅读下列函数说明和C代码,将应填入(n)处的字句写在对应栏内。
【说明2.1】
L为一个带头结点的循环链表。函数deletenode(LinkList L, int c)的功能是删除L中数据域data的值大于c的所有结点,并由这些结点组建成一个新的带头结点的循环链表,其头指针作为函数的返回值。
【函数2.1】
LinkList deletenode(LinkList L, int c)
{
LinkList Lc,p,pre;
pre=L;
p=(1);
Lc=(LinkList)malloc(sizeof(ListNode) );
Lc->next=Lc
while(p!=L)
if(p->data>c)
{
(2);
(3);
Lc->next=p;
p=pre->next;
}
else
{
pre=p;
p=pre->next;
}
return Lc;
}
【说明2.2】
递归函数dec_to_k_2(int n, int k)的功能是将十进制正整数n转换成k<2≤k≤9)进制数,并打印。
【函数2.2】
dec_to_k_2(int n, int k)
{ /*将十进制正整数n转换成k(2≤k≤9)进制数*/
if(n!=0)
{
dec_to_k_2((4),k);
printf("%d",(5));
}
}