阅读下列函数说明和C函数，将应填入(n)处的字句写在对应栏内。
[说明]
用链式存储结构实现的栈称为链栈。若链栈元素的数据类型为datatype，以LinkStack记链栈结构，其类型定义为：
typedef struct node
{ datatype data；
stmct node * next;
} StackNode, * LinkStack;
由于栈的主要操作都是在栈顶进行的，因此我们把链表的头部作为栈顶。设top为栈顶指针，即：LinkStack top。
下面各函数的功能说明如下：
(1)LinkStack Init_LinkStack()：建立并返回空的链栈；
(2)int Empty_LinkStack(LinkStack top)：判断top所指链栈是否空；
(3)LinkStack Push_LinkStack(LinkStacktop，datatypex)：将数据x压人top所指链栈的栈顶，返回新栈指针；
(4)LinkStack Pop_LinkStack (LinkStacktop, datatype*x)：弹出top所指链栈的栈顶元素x，返回新栈指针。
[函数]
LinkStaek Init_LinkStack( )
{ returnNULL;
int Empty_LinkStack ( LinkStaek top)
if(top = = NULL) return 1;
else return 0;
LinkStaek Push_LinkStaek( LinkStaektop, datatype X)
{ StaekNode *s;
s=malloc (sizeof(StaekNode) );
(1)= x;
(2)= top;
(3);
return top;
}
LinkStaek Pop_LinkStack (LinkStacktop, datatype * x)
{ StaekNode *p;
if(top = = NULL) return NULL;
else{
* x =(4);
p = top;
(5);
free (p);
return top;
}
}
第1题：
第2题：
试题三（共 15 分）
阅读以下说明和 C 程序，将应填入 （n） 处的字句写在答题纸的对应栏内。
第3题：
●试题二
阅读下列函数说明和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")；
}
}
第4题：
阅读以下函数说明和C语言函数，将应填入(n)处的字句写在对应栏内。
[说明]
已知r[1...n]是n个记录的递增有序表，用折半查找法查找关键字为k的记录。若查找失败，则输出“failure",函数返回值为0；否则输出“success”，函数返回值为该记录的序号值。
[C函数]
int binary search(struct recordtype r[],int n,keytype k)
{ intmid,low=1,hig=n;
while(low＜=hig){
mid=(1);
if(k＜r[mid].key) (2);
else if(k==r[mid].key){
printf("succesS\n");
(3);
}
else (4);
}
printf("failure\n");
(5);
}
第5题：
阅读以下说明，以及用C++在开发过程中所编写的程序代码，将应填入(n)处的字句写在对应栏内。
【说明】
在下面函数横线处填上适当的字句，使其输出结果为：
构造函数.
构造函数.
1，2
5，6
析构函数
析构函数.
【C++代码】
include "iostream.h"
class AA
{ public;
AA(int i,int j)
{A=i; B=j;
cout＜＜"构造函数.\n";
}
～AA(){(1);}
void print();
private:
int A, B;
};
void AA∷print()
{cout＜＜A＜＜","＜＜B＜＜endl;}
void main()
{
AA *a1, *a2;
(2)=new AA(1, 2);
a2=new AA(5, 6);
(3);
a2-＞print();
(4) a1;
(5) a2;
}
第6题：
阅读以下函数说明和C语言函数，将应填入(n)处的字句写在对应栏内。
【说明】
给定函数fun的功能是：将从键盘上输入的每个单词的第一个字母转换为大写字母，输入时各单词必须用空格隔开，用“.”结束输入。
【函数】
int fun(char *c,int status)
{
if((1)=='')
return 1;
else
{
if((2)&&(3)&&(4))
(5)='A'-'a';
return 0;
}
}
main()
{
int flag=1;
char ch;
printf("请输入一字符串，用点号结束输入!\n");
do {
ch=getchar();
flag=fun(&ch,flag);
putchar(ch);
}while(ch!='.');
printf("\n");
}
第7题：
阅读以下说明和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);
}
}
第8题：
阅读下列函数说明和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);
}
第9题：
●试题四
阅读下列函数说明和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)；
【解析】快速排序的思想是：任取待排序序列中的某个元素作为基准(一般取第一个元素)，通过一趟排序，将待排元素分为左右两个子序列，左子序列元素的排序码均小于或等于基准元素的排序码，右子序列的排序码则大于基准元素的排序码，然后分别对两个子序列继续进行排序，直至整个序列有序。快速排序是对冒泡排序的一种改进方法，算法中元素的比较和交换是从两端向中间进行的，排序码较大的元素一次就能够交换到后面单元，排序码较小的记录一次就能够交换到前面单元，记录每次移动的距离较远，因而总的比较和移动次数较少。