软考初级
阅读下列函数说明和C函数，将应填入(n)处的字句写在对应栏内。[说明]二叉树的二叉链表存储结构描述如下：lypedef struct BiTNode{ datatype data;street BiTNode *lchiht, *rchild; /*左右孩子指针*/ } BiTNode, *BiTree;下列函数基于上述存储结构，实现了二叉树的几项基本操作：(1) BiTree Creale(elemtype x, BiTree lbt, BiTree rbt)：建立并返回生成一棵以x为根结点的数据域值，
题目
阅读下列函数说明和C函数，将应填入(n)处的字句写在对应栏内。
[说明]
二叉树的二叉链表存储结构描述如下：
lypedef struct BiTNode
{ datatype data;
street BiTNode *lchiht, *rchild; /*左右孩子指针*/ } BiTNode, *BiTree;
下列函数基于上述存储结构，实现了二叉树的几项基本操作：
(1) BiTree Creale(elemtype x, BiTree lbt, BiTree rbt)：建立并返回生成一棵以x为根结点的数据域值，以lbt和rbt为左右子树的二叉树；
(2) BiTree InsertL(BiTree bt, elemtype x, BiTree parent)：在二叉树bt中结点parent的左子树插入结点数据元素x；
(3) BiTree DeleteL(BiTree bt, BiTree parent)：在二叉树bt中删除结点parent的左子树，删除成功时返回根结点指针，否则返回空指针；
(4) frceAll(BiTree p)：释放二叉树全体结点空间。
[函数]
BiTree Create(elemtype x, BiTree lbt, BiTree rbt) { BiTree p;
if ((p = (BiTNode *)malloc(sizeof(BiTNode)))= =NULL) return NULL;
p-＞data=x;
p-＞lchild=lbt;
p-＞rchild=rbt;
(1);
}
BiTree InsertL(BiTree bt, elemtype x,BiTree parent)
{ BiTree p;
if (parent= =NULL) return NULL;
if ((p=(BiTNode *)malloc(sizeof(BiTNode)))= =NULL) return NULL;
p-＞data=x;
p-＞lchild= (2);
p-＞rchild= (2);
if(parent-＞lchild= =NULL) (3);
else{
p-＞lchild=(4);
parent-＞lchild=p;
}
return bt;
}
BiTree DeleteL(BiTree bt, BiTree parent)
{ BiTree p;
if (parent= =NULL||parent-＞lchild= =NULL) return NULL;
p= parent-＞lchild;
parent-＞lchild=NULL;
freeAll((5));
return bt;
相似问题和答案
第1题：
阅读下列函数说明和C代码，将应填入(n)处的字句写在对应栏内。
【说明】
函数QuickSort是在一维数组A[n]上进行快速排序的递归算法。
【函数】
void QuickSort( int A[ ],int s,int t)
{ int i=s,j=t+1,temp;
int x=A[s];
do{
do i ++ ;while (1);
do j -- ;while(A[j]＞x);
if(i＜j){temp=A[i];(2);(3);}
}while(i＜j);
A[a] =A[j];A[j] =x;
if(s＜i-1) (4);
if(j+1＜t) (5);
}
(1)A[i]x (2)A[i]=A[j] 3)A[j]=temp (4)QuickSort(A，s，j-1) (5)QuickSort(A，j+1，t)； 解析：快速排序的思想是：任取待排序序列中的某个元素作为基准(一般取第一个元素)，通过一趟排序，将待排元素分为左右两个子序列，左子序列元素的排序码均小于或等于基准元素的排序码，右子序列的排序码则大于基准元素的排序码，然后分别对两个子序列继续进行排序，直至整个序列有序。快速排序是对冒泡排序的一种改进方法，算法中元素的比较和交换是从两端向中间进行的，排序码较大的元素一次就能够交换到后面单元，排序码较小的记录一次就能够交换到前面单元，记录每次移动的距离较远，因而总的比较和移动次数较少。
第2题：
阅读下列说明和C函数，将应填入(n)处的字句写在对应栏内。
【说明】
已知集合A和B的元素分别用不含头结点的单链表存储，函数Difference()用于求解集合A与B的差集，并将结果保存在集合A的单链表中。例如，若集合A＝{5，10， 20，15，25，30}，集合B＝{5，15，35，25}，如图(a)所示，运算完成后的结果如图(b)所示。
链表结点的结构类型定义如下：
typedef struct Node{
ElemType elem；
struct Node *next；
}NodeType；
【C函数】
void Difference(NodeType **LA，NodeType *LB)
{
NodeType *pa， *pb， *pre， *q；
pre＝NULL；
(1)；
while (pa) {
pb＝LB；
while((2))
pb＝pb-＞next；
if((3)) {
if(!pre)
*LA＝(4)；
else
(5)＝pa-＞next；
q ＝ pa；
pa＝pa-＞next；
free(q)；
}
else {
(6)；
pa＝pa-＞next；
}
}
}
(1)pa＝*LA (2)pb && pb-＞elem!＝pa-＞elem，或其等价表示 (3)pb或pb!=NULL (4)pa-＞next，或(*pa).next，或其等价表示 (5)pre-＞next，或(*pre)．next (6)pre＝pa 解析：本题考查链表结构上的基本运算。
集合A与B的差是指在集合A中而不在集合B中的元素。本题用链表表示集合并将运算结果用表示集合A的链表存储，因此涉及到链表上的查找、删除基本运算。
基本思路为：对于集合A中的每个元素，在集合B中进行查找，若找到，则应将该元素从集合A中去掉；否则保留，用两层循环实现，外层循环用于遍历集合A，内层循环遍历集合B。
代码中的指针pa用于指向集合A的元素；pb指向集合B的元素；临时指针q指向需要被删除的元素；pre用于实现删除时结点的链接，与pa保持所指结点的前后继关系。
显然，pa需要一个初始值，即指向集合A的第一个元素结点。由于参数LA是指向集合A第一个结点的指针的指针，因此空(1)处应填入pa＝*LA。
在内层循环中遍历集合B时，初始时令pb指向B的第一个元素(pb＝LB)，此后应在链表中查找与A中当前元素相同者，因此空(2)处应填入pb && pb-＞elem !＝ pa-＞elem。
此后，应判断在B中是否找到指定元素。显然，若找到(即pb-＞elem＝pa-＞elem)，则指针pb不为空，否则，pb为空。因此，空(3)处填入pb或pb!=NULL，空(6)处则填入pre＝pa。
由于链表不带头结点，因此，当需要删除集合A的第一个元素时，表示该集合的链表头指针会被修改。pre初始值为NULL，可标志删除的是否为A的第一个元素。因此查找成功时，pre为空(!pre成立)表示需要删除A的第一个元素(pa指针所指)，使得 A的头指针指向第二个元素，即应将*LA更新为pa-＞next，空(4)处填入pa-＞next。如果删除的不是第一个元素，则由于pa指向被删除的元素，而且pre与pa所指元素保持前后继关系，因此空(5)处应填入pre-＞next。
第3题：
●试题四
阅读下列函数说明和C代码，将应填入(n)处的字句写在答题纸的对应栏内。
【说明】
函数QuickSort是在一维数组A［n］上进行快速排序的递归算法。
【函数】
void QuickSort(int A［］，int s，int t)
{int i=s，j=t+1，temp；
int x=A［s］；
do{
do i＋＋；while (1) ；
do j--；while(A［j］>x)；
if(i<j){temp=A［i］； (2) ； (3) ；}
}while(i<j)；
A［a］=A［j］；A［j］=x；
if(s<i-1) (4) ；
if(j+1<t) (5) ；
}
●试题四
【答案】(1)A［i］<x(2)A［i］=A［j］(3)A［j］=temp(4)QuickSort(A，s，j-1)
(5)QuickSort(A，j+1，t)；
【解析】快速排序的思想是：任取待排序序列中的某个元素作为基准(一般取第一个元素)，通过一趟排序，将待排元素分为左右两个子序列，左子序列元素的排序码均小于或等于基准元素的排序码，右子序列的排序码则大于基准元素的排序码，然后分别对两个子序列继续进行排序，直至整个序列有序。快速排序是对冒泡排序的一种改进方法，算法中元素的比较和交换是从两端向中间进行的，排序码较大的元素一次就能够交换到后面单元，排序码较小的记录一次就能够交换到前面单元，记录每次移动的距离较远，因而总的比较和移动次数较少。
第4题：
试题三（共 15 分）
阅读以下说明和 C 程序，将应填入 （n） 处的字句写在答题纸的对应栏内。
第5题：
阅读以下说明和C语言函数，将应填入(n)处的字句写在对应栏内。
【说明】
下面的程序构造一棵以二叉链表为存储结构的二叉树算法。
【函数】
BTCHINALR *createbt ( BTCHINALR *bt )
{
BTCHINALR *q;
struct node1 *s [30];
int j,i;
char x;
printf ( "i,x =" ); scanf ( "%d,%c",&i,&x );
while (i!=0 && x!='$')
{ q = ( BTCHINALR* malloc ( sizeof ( BTCHINALR )); //生成一个结点
(1);
q-＞1child = NULL;
q-＞rchild = NULL;
(2);
if((3);)
{j=i/2 //j为i的双亲结点
if(i%2==0
(4) //i为j的左孩子
else
(5) //i为j的右孩子
}
printf ( "i,x =" ); scanf ( "%d,%c",&i,&x ); }
return s[1]
}
(1)q-＞data=x (2) s[i]=q (3) i!=1 (4) s[j]-＞1child=q (5) s[j]-＞rchild=q
第6题：
阅读以下说明和C语言函数，将应填入(n)处的字句写在对应栏内。
[说明]
完成以下中序线索化二叉树的算法。
[函数]
Typedef int datatype;
Typedef struct node {
Int ltag, rtag;
Datatype data;
*lchild,* rchild;
}bithptr;
bithptr pre;
void inthread ( p );
{if
{inthread ( p-＞lchild );
if ( p-＞lchild==unll ) (1);
if ( P-＞RCHILD=NULL) p-＞rtag=1;
if (2)
{if (3) pre-＞rchild=p;
if ( p-＞1tag==1 )(4);
}
INTHREAD ( P-＞RCHILD );
(5);
}
}
(1) P-＞LTAG=0 (2) (PRE) (3) (PRE-＞RTAG==1) (4) P-＞LCHILD=PRE (5) PRE=P
第7题：
阅读以下说明和C语言函数，将应填入(n)处的语句写在对应栏内。
【说明】
下面的程序构造一棵以二叉链表为存储结构的二叉树。
【函数】
BitTree *createbt(BitTree *bt)
{
BitTree *q;
struct node *s[30];
int j,i;
char x;
printf("i,x=");
scant("%d,%c",&i,&x);
while(i!=0 && x!='$')
{
q=(BitTree *}malloc(sizeof(BitTree));//生成一个结点
(1);
q-＞lchild=NULL;
q-＞rchild=NULL;
(2) ;
if ((3))
{
j=i/2; // j为i的双亲结点
if(i%2==0)
(4); //i为j的左孩子
else
(5); //i为j的右孩子
}
printf("i,x=");
scanf("%d,%c",&i,&x);
}
return s[i];
}
(1)q-＞data=x (2)s[i]=q (3)i!=1 (4)s[j]-＞lchild=q (5)s[j]->rchild=q 解析：本题考查二叉树的构造。
题目要求构造一棵二叉树，而二叉树的性质如下：如果对一棵有n个结点的完全二叉树的结点按层序编号(从第1层到第[log2n]+1层，每层从左到右)，则对任一结点i(1≤i≤n)，有：
(1)如果i=1，则结点i无双亲，是二叉树的根；如果i＞1，则其双亲是结点[i/2]。
(2)如果2i＞n，则结点i为叶子结点，无左孩子：否则，其左孩子是结点2i。
(3)如果2i+1＞n，则结点i无右孩子；否则，其右孩子是结点2i+1。
下面我们来看程序。程序中声明了一个结点指针数组，用来保存生成的树中结点。用从键盘输入的方式来确定要插入的字符x和此结点在二叉树中的位置i(这个位置是指在完全二叉树中编号的位置)。
第(1)空是在生成一个新结点后的操作，生成了一个新结点后，自然要将从键盘输入的字符x值存放进来，以及修改结点的两个指针域。程序中指针域都赋了空，因此，第(1)空的任务应该是将字符x写进来，因此，此空答案为q-＞data=x。
第(2)空是在对结点完成操作后的操作，根据题目意思，生成的结点应该要保存到数组s中，此数组是一个指针数组，保存结点时，是将结点的地址保存进数组中相应的位置，因此，此空答案为s[il=q。
第(3)空是条件判断语句的条件，结合下面的程序可以知道，此条件语句用来判断当前结点是不是根结点，如果不是，才执行条件语句中的内容。根据上面的分析，如果i=1，则结点i无双亲，是二叉树的根，因此，此空的答案为i!=1。
第(4)空处后面有注释，说明i是j的左孩子结点，这个时候我们应该让j结点的左孩子指针指向结点i，此空就是要实现这一功能。而结点，j被存放在数组s中的第j个位置，因此，此空答案为s[i]-＞lchild=q。
从程序中很容易看出，第(5)空与第(4)空功能相似，只是说i是j的右孩子结点，因此，让j结点的右孩子指针指向结点乙此空答案为s[j]-＞rchild=q。
第8题：
阅读以下说明和流程图，将应填入(n)处的字句写在对应栏内。
【说明】
已知头指针分别为La和lb的有序单链表，其数据元素都是按值非递减排列。现要归并La和Lb得到单链表Lc，使得Lc中的元素按值非递减排列。程序流程图如下所示：
(1)pa-＞data=pb-＞data (2)pc-＞next=pa (3)pc=pb (4)pb=pb-＞next (5)pc-＞next=pa?pa:pb 解析：本题考查程序流程图和有序链表的归并。
题目要求我们归并头指针分别为La和Lb的有序单链表，组成一个新的有序单链表 Lc，而Lc又是指向La的。首先，我们来了解一下单链表的结构。单链表中一般有两个域，一个是数据域，用来存放链表中的数据；另一个是指针域，用来存放指向下个结点的指针。其归并的过程应该是先比较链表La和Lb中第一个元素，将较小的从其链表中取出放到k中，再取下一个结点的值去比较，重复这个过程，直到一个链表被全部取完，再将另一个链表剩下的部分连接到Lc后面即可。
下面，我们来看程序流程图的内容。首先是用两个指针变量pa和pb分别指向La和Lb的当前待比较插入的结点，而pc指向Lc表中当前最后一个结点。再下面是一个条件判断语句，其作用是判断链表La和Lb是否为空，如果有一个为空，只要将另一个链表剩下的部分连接到Lc后面，程序应该就可以结束了。
第(1)空是条件判断语句的条件，根据我们上面的分析，再结合流程图下面的内容，我们可以知道，这个条件语句的作用是比较当前待插入的两个值的大小，而指针变量pa和pb分别指向La和Lb的当前待比较插入的结点，因此，此空的答案为 pa-＞data=pb-＞data。
第(2)空是在条件为真的情况下执行的语句，如果条件判断为真，应该将pa所指结点连接到pc所指结点后面，因此，pc所指结点的指针域应该存放pa所指结点的地址。所以，此空的答案为pc-＞next=pa。
第(3)空和第(4)空都是在条件为假的情况下执行的语句，如果条件为假，说明 pb所指结点的值小于pa所指结点的值，应该将pb所指结点连接到pc所指结点后面，图中已经实现这一功能，要我们完成的是在插入后的后继工作。由于pc指向的是Lc表中当前最后一个结点，在插入一个结点后，要修改pc的值。在将pb所指结点插入后，链表中的最后一个结点就是pb所指结点，第(3)空的答案应该为pc=pb。执行完这些功能后，指针pb应该要往后移动，即指向下一个结点，第(4)用来完成这个功能，所以答案为pb=pb-＞next。
在前面，我们已经讲到如果链表La和Lb有一个为空，只要将另一个链表剩下的部分连接到Lc后面即可。第(5)空就是用来完成这个功能的，但我们不知道具体是哪个链表为空，还需要判断，因此，此空答案为pc-＞next=pa?pa:pb。
第9题：
●试题二
阅读下列函数说明和C代码，将应填入(n)处的字句写在答题纸的对应栏内。
【说明】
该程序运行后，输出下面的数字金字塔
【程序】
include<stdio．h>
main ()
{char max，next；
int i；
for(max=′1′；max<=′9′；max＋＋)
{for(i=1；i<=20- (1) ；＋＋i)
printf(" ")；
for(next= (2) ；next<= (3) ；next＋＋)
printf("％c"，next)；
for(next= (4) ；next>= (5) ；next--)
printf("％c"，next)；
printf("＼n")；
}
}
●试题二【答案】(1)(max-′0′)(2)′1′(3)max(4)max-1(5)′1′【解析】该程序共有9行输出，即循环控制变量max的值是从1～9。每行输出分3部分，先用循环for语句输出左边空白，(1)空填"(max-′0′)"；再用循环输出从1到max-′0′的显示数字，即(2)空和(3)空分别填1和max；最后输出从max-′1′～1的显示数字，即(4)空和(5)空分别填和max-1和′1′。
第10题：
【说明】
阅读下列说明和?Java代码，将应填入?(n)?处的字句写在答题纸的对应栏内。
【说明】
某快餐厅主要制作并出售儿童套餐，一般包括主餐(各类比萨)、饮料和玩具，其餐品种
类可能不同，但其制作过程相同。前台服务员?(Waiter)?调度厨师制作套餐。现采用生成器?(Builder)?模式实现制作过程，得到如图?6-1?所示的类图。
