niusouti.com
●试题四阅读下列函数说明和C代码，将应填入(n)处的字句写在答题纸的对应栏内。【说明4．1】假设两个队列共享一个循环向量空间(如图1-2所示)，其类型Queue2定义如下：typedef struct{DateType data ［MaxSize］；int front［2］，rear［2］；}Queue2；对于i=0或1，front［i］和rear［i］分别为第i个队列的头指针和尾指针。函数EnQueue(Queue2*Q，int i，DateType x)的功能是实现第i个队列的入队操作。【函数4．1】
题目
●试题四
阅读下列函数说明和C代码，将应填入(n)处的字句写在答题纸的对应栏内。
【说明4．1】
假设两个队列共享一个循环向量空间(如图1-2所示)，其类型Queue2定义如下：
typedef struct{
DateType data ［MaxSize］；
int front［2］，rear［2］；
}Queue2；
对于i=0或1，front［i］和rear［i］分别为第i个队列的头指针和尾指针。函数EnQueue(Queue2*Q，int i，DateType x)的功能是实现第i个队列的入队操作。
【函数4．1】
int EnQueue(Queue2*Q，int i，DateType x)
{∥若第i个队列不满，则元素x入队列，并返回1；否则，返回0
if(i＜0‖i>1)return 0；
if(Q->rear［i］==Q->front［ (1) ］
return 0；
Q->data［ (2) ］=x；
Q->rear［i］=［ (3) ］；
return 1；
}
【说明4．2】
函数BTreeEqual(BinTreeNode*T1，BinTreeNode*T2)的功能是递归法判断两棵二叉树是否相等，若相等则返回1，否则返回0。函数中参数T1和T2分别为指向这两棵二叉树根结点的指针。当两棵树的结构完全相同，并且对应结点的值也相同时才被认为相等。
已知二叉树中的结点类型BinTreeNode定义为：
struct BinTreeNode{
char data；
BinTreeNode*left，*right；
}；
其中data为结点值域，left和right分别为指向左、右子女结点的指针域，
【函数4．2】
int BTreeEqual(BinTreeNode*T1，BinTreeNode*T2)
{
if(T1==NULL ＆＆ T2==NULL)return 1；∥若两棵树均为空，则相等
else if( (4) )return 0；∥若一棵为空一棵不为空，则不等
else if( (5) )return 1；∥若根结点值相等并且左、右子树
∥也相等，则两棵树相等，否则不等
else return 0；
}
相似考题
更多“●试题四阅读下列函数说明和C代码，将应填入(n)处的字句写在答题纸的对应栏内。【说明4．1】假设两个队列共享一个循环向量空间(如图1-2所示)，其类型Queue2定义如下：typedef struct{DateType data ［MaxSize］；int front［2］，rear［2］；}Queue2；对于i=0或1，front［i］和rear［i］分别为第i个队列的头指针和尾指针。函数EnQueue(Queue2*Q，int i，DateType x)的功能是实现第i个队列的入队操作。【函数4．1】”相关问题
-
第1题：
阅读下列程序说明和C代码，将应填入(n)处的字句写在对应栏内。
[说明]
函数Printprime(int UpBound)的功能是输出1到UpBound以内的全体素数。
[函数2.1]
void PrintPrime(int UpBound)
printf("2," );
for(i=3; i＜UpBound; i+ =2) {
int k = sqrt(i);
for(j=3; j＜= k;(1)) /*检查i是否有3到k以入的奇因数*/
if((2)) break;
fi((3)) printf("%d", i);
[函数2.2说明]
递归函数invert(int a[],int k)，int k)的功能是将数组a中的前k个元素逆置。
[函数2.2]
void invert(int a[ ], int k)
{ int t;
if ((4)) {
invert((5));
t=a[0];
a[0] =a[k-1];
a[k-l]=t;
}
}
正确答案：(1)j+=2 (2)i%j==0 (3)j＞k (4)k＞1 (5)a+1k-2
(1)j+=2 (2)i%j==0 (3)j＞k (4)k＞1 (5)a+1，k-2 解析：(1)～(3)由于(1)处循环只检查i是否能被3到k以内的奇数所整除，因此循环增量应该是2。并且一旦i被某个3到k以内的奇数整除，那么内层for应当立即终止，此时j<=k。相反的，若内层for循环结束后j>k，则表明i没有3到k以内的奇因数，即i是一素数，应该输出；
(4)由于函数递归的终止条件是k不大于1，于是仅在 k>1时需要继续进行递归；
(5)为了将数组a的前k个元素a[0]、……、a[k-1]置逆，只需先将a[1]、……、a[k-2]这k-2个元素置逆，即调用invert(a+1，k-2)，再交换a[0]和a[k-1]的值即可。 -
第2题：
阅读下列函举说明和C代码，将应填入(n)处的字句写在对应栏内。
【说明4.1】
假设两个队列共享一个循环向量空间(如图1-2所示)，其类型Queue2定义如下：
typedef struct {
DateType data [MaxSize];
int front[2],rear[2];
}Queue2;
对于i=0或1，front[i]和rear[i]分别为第i个队列的头指针和尾指针。函数．EnQueue (Queue2*Q，int i，DaleType x)的功能是实现第i个队列的入队操作。
【函数4.1】
int EnQueue(Queue2 * Q, int i, DateType x)
{ /*若第i个队列不满，则元素x入队列，并返回1；否则，返回0*/
if(i＜0‖i＞1) return 0;
if(Q-＞rear[i]==Q-＞front[(1)]
return 0;
Q-＞data[(2)]=x;
Q-＞rear[i]=[(3)];
return 1;
}
【说明4.2】
函数BTreeEqual(BinTreeNode*T1，BinTtneNode*T2)的功能是递归法判断两棵二叉树是否相等，若相等则返回1，否则返回0。函数中参数T1和T2分别为指向这两棵二叉树根结点的指针。当两棵树的结构完全相同，并且对应结点的值也相同时，才被认为相等。
已知二叉树中的结点类型BinTreeNode定义为：
struct BinTreeNode {
char data;
BinTreeNode * left, * right;
};
其中dau为结点值域，leR和risht分别为指向左、右子女结点的指针域，
【函数4.2】
int BTreeEqual(BinTreeNode * T1, BinTreeNode * T2)
{
if(Ti == NULL && T2 == NULL)return 1 /*若两棵树均为空，则相等*/
else if((4))return 0; /*若一棵为空一棵不为空，则不等*/
else if((5)) return 1; /*若根结点值相等并且左、右子树*/
/*也相等，则两棵树相等，否则不等*/
else return 0;
}
正确答案：(1)(i+1)%2(或1-i) (2)Q-＞rear[i] (3)(Q-＞rear[i]++)%Maxsize (4)T1==NULL‖T2==NULL (5)T1-＞data==T2-＞ data && BTreeEqual(T1-＞leftT2-＞left) && BTreeEqual (T1-＞right T2-＞right)
(1)(i+1)%2(或1-i) (2)Q-＞rear[i] (3)(Q-＞rear[i]++)%Maxsize (4)T1==NULL‖T2==NULL (5)T1-＞data==T2-＞ data && BTreeEqual(T1-＞left,T2-＞left) && BTreeEqual (T1-＞right, T2-＞right) 解析：这一题共有两个函数，第一个函数是一个循环共享队列入队的的问题，第二个函数是用递归法判断两棵二叉树是否相等的问题。
先分析第一个函数。(1)空所在if语句是判断是否能入队，当队列0入队时，如果队列0队尾指针与队列1队头指针相等时，说明队列 0无法入队；当队列1入队时，如果队列1队尾指针与队列0队头指针相等时，说明队列1无法入队。因此(1)空处应填写“(i+1)%2”或“1-i”。(2)、(3)空是入队操作，其操作步骤是先将元素x插入队列i队尾所指的位置，再将队尾“加1”。因此(2)空处应填写“Q-＞rear[i]”；由于是一个循环队列，(3)空处应填写“(Q-＞rear[i]+1)%Maxsize”。
再分析第二个函数。这一题比较简单，只需将程序注释转换成C语言即可得到答案。(4)空所处理的是若一棵为空，而一棵不为空则不相等，显然(4)空应填入“TI==NULL‖T2==NULL”。(5)空处是一个递归调用，处理若根结点值相等并且左、右子树也相等，则两棵树相等，因此(5)空应填入“T1-＞data=＝T2－＞data && BTreeEqual(T1-＞left, T2-＞left) &&BTreeEqual(Tl-＞right, T2-＞right)”及其等价形式。 -
第3题：
阅读下列函数说明和C函数，将应填入(n)处的字句写在对应栏内。
[说明]
循环队列的类型定义如下(其中队列元素的数据类型为datatype)：
typedef struct{
datatype data[MAXSIZE]; /*数据的存储区*/
int front,rear; /*队首、队尾指针*/
int num; /*队列中元素的个数*/
}c _ SeQueue; /*循环队*/
下面函数及其功能说明如下：
(1) c_SeQueue* Init_SeQueue()：新建队列；
(2) int ln_SeQueue( c_SeQueue *q, datatype x)：将元素x插入队列q，若成功返回1否则返回0；
(3) int Out_SeQueue (c_SeQueue *q, datatype *x)：取出队列q队首位置的元素，若成功返回1否则返回0。
[函数]
c_SeQueue* Init_SeQueue()
{ q=malloc(sizeof(c_SeQueue));
q-＞front=q-＞rear=MAXSIZE-1;
(1);
return q;
}
int In_SeQueue( c_SeQueue *q, datatype x)
{ if(q-＞num= =MAXSIZE) return 0; /*队满不能入队*/
else {
q-＞rear=(2);
q-＞data[q-＞rear]=x;
(3);
return 1; /*入队完成*/
}
}
int Out_SeQueue( c_SeQueue *q, datatype *x)
{ if (q-＞num= =0) return 0; /*队空不能出队*/
else{
*x=(4); /*读出队首元素*/
q-＞front=(5);
q-＞num- -;
return 1; /*出队完成*/
}
}
正确答案：(1) q-＞num=0 (2) (q-＞rear+1) % MAXSIZE (3) q-＞num++ (4) q-＞data[q-＞front] (5) (q-＞front+1)%MAXSIZE
(1) q-＞num=0 (2) (q-＞rear+1) % MAXSIZE (3) q-＞num++ (4) q-＞data[q-＞front] (5) (q-＞front+1)%MAXSIZE 解析：(1)新建的队列中元素个数应为0；
(2)向循环队列中添加新元素后，队尾指针应向后移动一位；
(3)向循环队列中添加新元素后，队列中元素个数应增1；
(4)取出队首位置的元素；
(5)从循环队列中取出一个元素后，队首指针应向后移动一位。 -
第4题：
阅读以下说明和C语言函数，将应填入(n)处的字句写在对应栏内。
[说明]
编写一个函数，输入为偶数时，调用函数求1/2+?/+…+1/n，当输入n为奇数时，调用函数1/1+1/3+…+1/n (利用指针函数)。
[函数]
include "stdio. h"，
main()
{
float peven ()，podd ()，dcall ()；
float sum；
int n；
while (1)
{
scanf("%d"，&n)；
if (n＞1)
break；
}
if(n%2==0)
{
printf("Even=")：
(1)；
}
else
{
pfinff("Odd=")；
(2)；
}
printf("%f",sum)；
}
float peven (int n)
{
float s；
int i
s=1；
for(i=2；i＜=n；i+=2)
(3)；
return (s)；
}
float podd (n)
int n；
{
float s；
int i；
s=0；
for(i=1 i＜=n；i+=2)
(4)；
return (s)；
}
float dcall(fp，n)
float (*fp) ()；
int n；
{
float s；
(5)；
returu (s)；
}
正确答案：(1)array+10 (2)array+1 (3)*p＞*max (4)k=*max (5)*p=array[0]
(1)array+10 (2)array+1 (3)*p＞*max (4)k=*max (5)*p=array[0] -
第5题：
阅读以下说明和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
(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。 -
第6题：
阅读下列函数说明和C函数，将应填入(n)处的字句写对应栏内。
[说明]
二叉树的二叉链表存储结构描述如下：
typedef struct BiTNode
{ datatype data;
struct BiTNode *lchild, * rchild; /*左右孩子指针*/
}BiTNode,* BiTree;
对二叉树进行层次遍历时，可设置一个队列结构，遍历从二叉树的根结点开始，首先将根结点指针入队列，然后从队首取出一个元素，执行下面两个操作：
(1) 访问该元素所指结点；
(2) 若该元素所指结点的左、右孩子结点非空，则将该元素所指结点的左孩子指针和右孩子指针顺序入队。
此过程不断进行，当队列为空时，二叉树的层次遍历结束。
下面的函数实现了这一遍历算法，其中Visit(datatype a)函数实现了对结点数据域的访问，数组queue[MAXNODE]用以实现队列的功能，变量front和rear分别表示当前队首元素和队尾元素在数组中的位置。
[函数]
void LevelOrder(BiTree bt) /*层次遍历二叉树bt*/
{ BiTree Queue[MAXNODE];
int front,rear;
if(bt= =NULL)return;
front=-1;
rear=0;
queue[rear]=(1);
while(front (2) ){
(3);
Visit(queue[front]-＞data); /*访问队首结点的数据域*/
if(queue[front]—＞lchild!：NULL)
{ rear++;
queue[rear]=(4);
}
if(queue[front]-＞rchild! =NULL)
{ rear++;
queue[rear]=(5);
}
}
}
正确答案：(1) bt (2) ! =rear (3) front+ + (4) queue [front]-＞lchild (5) queue[front]-＞rchild
(1) bt (2) ! =rear (3) front+ + (4) queue [front]-＞lchild (5) queue[front]-＞rchild 解析：(1)遍历开始时队列长度为1，其中只存放了根结点bt；
(2)遍历过程是一个循环访问队列的过程，其终止条件是队列为空，即front等于rear；
(3)遍历到某结点时，该结点应退出队列，因此队首元素的位置应该增1；
(4)此处应将队首结点的左孩子结点放入队列，即插在队尾；
(5)此处应将队首结点的右孩子结点放入队列，即插在队尾。 -
第7题：
阅读下列函数说明和C函数，将应填入(n)处的字句写在对应栏内。
[说明]
链式存储的队列称为链队。根据队列的FIFO原则，为了操作上的方便，可以使用带头指针front和尾指针rear的单链表来实现链队。若链队元素的数据类型为datatype，则链队结构描述如下：
typedef struct node
{ datatypedata;
structnode *next;
} QNode; /*链队结点的类型*/
typedef struct
{ QNnode *front,*rear;
} LQueue; /*将头尾指针封装在一起的链队*/
以下这种链队的几个例子：
设q是一个指向链队的指针，即LQueue *q。下面各函数的功能说明如下：
(1) LQueue *Init_LQueue()：创建并返回一个带头尾结点的空链队；
(2) intEmpty_LQueue( LQueue *q):判断链队q是否空；
(3) void In_LQueue(LQueue *q, datatypex):将数据x压入链队q；
(4) int Out_LQueue(LQuere *q, datatype *x):弹出链队q的第一个元素x，若成功则返回返回1否则返回0。
[函数]
LQueae *Init_LQueue()
{ LQueue *q, *p;
q=malloc(sizeof(LQueue)); /*申请链队指针*/
P=malloc(sized(QNode));/*申请头尾指针结点*/
p-＞next=NULL;
(1)=p;
return q;
}
int Empty_LQueue(LQueue *q)
{ if(q-＞front (2) q＞rear) return 0;
else return 1;
}
void In_LQueue(LQueue *q, datatype x)
{ QNoda *p;
p=malloc(sizeof(QNnode));/*申请新接点*/
p-＞data=x;
p-＞next=NULL;
(3)=p;
q-＞rear=p;
}
int Out_LQueue(LQueue *q, datatype *x)
{ QNnode *p;
if(Empty_LQueue(q)) return 0; /*队空,操作失败*/
else{
p=q-＞front-＞next;
*x=(4);
(5)=p-＞next;
free(p);
if (q-＞front-＞next= =NULL)q-＞rear=q-＞front;
return 1;
}
}
正确答案：(1) q-＞front=q-＞rear (2) = = (3)q-＞ rear-＞next (4) p-＞data (5) q-＞front-＞next
(1) q-＞front=q-＞rear (2) = = (3)q-＞ rear-＞next (4) p-＞data (5) q-＞front-＞next 解析：(1)初始化链队q时，需要初始化其头尾指针，空链队的头尾指针相等；
(2)链队头尾指针重合当且仅当链队为空；
(3)向链队插入新元素的操作是在链队末尾进行的，需要将新元素结点接在原链队队尾，再让新的尾指针指向这一新结点；
(4)～(5)：链队q的第一个元素存放在其头结点之后的第一个结点(即p=q-＞front-＞next)中。*x= p-＞data表示将这个元素取出，以参数*x的形式返回：q-＞front-＞next=p-＞next表示将结点p从链队中取出。 -
第8题：
阅读以下说明和 C 代码，填补代码中的空缺，将解答填入答题纸的对应栏内。 【说明】 函数 GetListElemPtr(LinkList L，int i)的功能是查找含头结点单链表的第i个元素。若找到，则返回指向该结点的指针，否则返回空指针。 函数DelListElem(LinkList L，int i，ElemType *e) 的功能是删除含头结点单链表的第 i个元素结点，若成功则返回 SUCCESS ，并由参数e 带回被删除元素的值，否则返回ERROR 。 例如，某含头结点单链表 L 如图 4-1 (a) 所示，删除第 3 个元素结点后的单链表如 图 4-1 (b) 所示。
图4-1define SUCCESS 0 define ERROR -1 typedef int Status; typedef int ElemType; 链表的结点类型定义如下: typedef struct Node{ ElemType data; struct Node *next; }Node ,*LinkList; 【C 代码】 LinkList GetListElemPtr(LinkList L ，int i) { /* L是含头结点的单链表的头指针，在该单链表中查找第i个元素结点: 若找到，则返回该元素结点的指针，否则返回NULL */ LinkList p; int k; /*用于元素结点计数*/ if (i<1 ∣∣ !L ∣∣ !L->next) return NULL; k = 1; P = L->next; / *令p指向第1个元素所在结点*/ while (p && （1） ) { /*查找第i个元素所在结点*/ （2） ; ++k; } return p; } Status DelListElem(LinkList L ，int i ，ElemType *e) { /*在含头结点的单链表L中，删除第i个元素，并由e带回其值*/ LinkList p，q; /*令p指向第i个元素的前驱结点*/ if (i==1) （3） ； else p = GetListElemPtr(L ，i-1); if (!p ∣∣ !p->next) return ERROR; /*不存在第i个元素*/ q = (4) ； /*令q指向待删除的结点*/ p->next = q->next; /*从链表中删除结点*/ (5) ； /*通过参数e带回被删除结点的数据*/ free(q); return SUCCESS; }
正确答案：(1) k<i
(2) p = p->next
(3) p=L
(4) p->next
(5) *e = q->data
-
第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题：
（）阅读下列说明和C语言程序，将应填入 （n）处的语句写在答题纸的对应栏内。[说明]有一个一维数组cj，内放20个学生成绩，求平均成绩。函数ave用来求20个学生的平均成绩。[C语言函数]float ave(float a[20]){ int i;float aver,sum= (1) ;for(i=1;i<20;i++) sum= (2) ;aver= (3) ;return( (4) );}main(){ float cj[20],aver;int i;printf(“input 20 cj:\n”);for(i=0;i<20;i++) scanf(“%f”,&cj[i]);printf(“\n”);aver= (5) ;printf(“average cj is %6.2f”,aver);}
正确答案：（）
（1）a[0] （2）sum+a[i] （3）sum/20 （4）aver （5）ave(cj)
sum是用来存放学生的总成绩的，所以又由于在下面的for循环里i是从1开始的，所以（1）应填a[0]，（2）应填sum+a[i]，aver是用来求平均成绩的，所以（3）应填sum/20，（4）应填返回的结果，因此应将平均值aver返回。所以（4）应填aver，（5）应该是调用函数ave求平均值，所以应填ave(cj)。
-
第11题：
试题四（共 15 分）阅读以下说明和 C 函数，填补函数中的空缺，将解答填入答题纸的对应栏内。【说明】简单队列是符合先进先出规则的数据结构，下面用不含有头结点的单向循环链表表示简单队列。函数 enqueue（queue *q，KeyType new_elem） 的功能是将元素new_elem 加入队尾。函数 Dnqueue（queue *q，KeyType *elem）的功能使将非空队列的队头元素出队（从队列中删除），并通过参数带回刚出队的元素。用单向循环链表表示的队列如图 4-1 所示。
图 4-1 单向循环链表表示的队列示意图队列及链表结点等相关类型定义如下:enum {errOr， OK};typedef int KeyType;typedef struct qNode﹛KeyType data;Struct qNode*next;﹜qNode，*Linkqueue; Typedef struct﹛int size;Link:queue rear;}queue; 【C 函数】int enqueue（queue*q,KeyType new_elem）﹛ ／／元素 new_elem 入队列qNode*p;P=（qNode*）malloc（sizeof（qNode））;if（!p）return errOr;P->data=new_elem;if（q->rear）﹛P->next=q->rear->next;（）;﹜elseP->next=p;﹙﹚;q->size++;return OK;﹜ int Dequeue（queue*q,KeyType*elem）﹛ ／／出队列qNode*p;if（0＝＝q->size） ／／是空队列return errOr；P=（）; ／／令 p 指向队头元素结点*elem =p->data;q->rear->next=（）; ／／将队列元素结点从链表中去除if（（）） ／／被删除的队头结点是队列中唯一结点q->rear=NULL ／／变成空队列free（p）;q->size--;return OK;﹜答案：解析：（1）Q→rear→next=p（2）Q→rear=p（3）Q→rear→next（4）p→next（5）Q→rear==p 或 Q→rear→next==p→next 或 Q→size==1
【解析】
本题考察C语言指针与链表的知识，为入队列和删除队列问题。对于入队列，那么当队列Q不为空时，P的队尾t要指向原Q的队尾指向的元素，即：P->next=Q->rear->next，Q的队尾要指向p，即：Q→rear→next=p。当队列Q为空时，插入p元素，则p的队尾指向p自身，即：p→next=p，且整个队列Q的队尾也是p，即：Q→rear=p。对于队列删除元素p，先判断Q是否为空，为空队列则返回 ERROR;If(0＝＝q->size) //是空队列Return ERROR；另p指向队头元素结点，队头元素结点可用Q→rear→next表示。此时，p转化为头结点，p出列，则需要Q的队尾指向p的下一个元素，因此第4空填：p→next。最后，判断被删除的队头结点是否是队列中的唯一结点，可采用：Q→rear==p 或 Q→rear→next==p→next 或 Q→size==1 等表示方法。 -
第12题：
链队列的存储结构为： struct nodetype {ELEMTP data； struct nodetype *next； } struct linkqueue {struct nodetype *front，*rear； } /*front和rear分别为队列的头指针和尾指针*/ 完成下列删除队头元素的算法。 delq（struct linkqueue *r，ELEMTP *x） {q=*r； if（q.front= =q.rear）printf（“QUEUE IS EMPTY/n“）； else{p=q.front->next； q.front->next=p->next； if（p->next= =NULL）q.rear=q.front； *x=（）；free（p）；
正确答案:p->data -
第13题：
阅读以下说明和C语言函数，将应填入(n)处的字句写在答题纸的对应栏内。
[说明]
求树的宽度，所谓宽度是指在二叉树的各层上，具有结点数最多的那一层的结点总数。本算法是按层次遍历二叉树，采用一个队列q，让根结点入队列，若有左右子树，则左右子树根结点入队列，如此反复，直到队列为空。
[函数]
int Width ( BinTree *T
{
int front=-1, rear=-1; /*队列初始化*/
int flag=0, count=0, p; /*p用于指向树中层的最右边的结点, flag 记录层中结点数的最大值*/
if ( T!=Null)
{
rear++;
(1);
flag=1;
p=rear;
}
while ((2))
{
front++;
T=q [front]];
if (T->lchild!=Null )
{
roar+-+;
(3);
count++;
}
if ( T-＞rchild!=Null )
{
rear++; q[rear]=T-＞rchild;
(4);
}
if (front==p ) // 当前层已遍历完毕
{
if((5))
flag=count;
count=0;
p=rear, //p 指向下一层最右边的结点
}
}
return ( flag );
}
正确答案：(1) q [rear]=T (2) frontp (3) q [rear]=T-＞lchild (4) count++ (5) flagcount
(1) q [rear]=T (2) frontp (3) q [rear]=T-＞lchild (4) count++ (5) flagcount -
第14题：
阅读下列函数说明和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(Asj-1) (5)QuickSort(Aj+1t)；
(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)； 解析：快速排序的思想是：任取待排序序列中的某个元素作为基准(一般取第一个元素)，通过一趟排序，将待排元素分为左右两个子序列，左子序列元素的排序码均小于或等于基准元素的排序码，右子序列的排序码则大于基准元素的排序码，然后分别对两个子序列继续进行排序，直至整个序列有序。快速排序是对冒泡排序的一种改进方法，算法中元素的比较和交换是从两端向中间进行的，排序码较大的元素一次就能够交换到后面单元，排序码较小的记录一次就能够交换到前面单元，记录每次移动的距离较远，因而总的比较和移动次数较少。 -
第15题：
阅读下列函数说明和C代码，将应填入(n) 处的字句写在对应栏内。
【说明】
函数print(BinTreeNode*t; DateType &x)的功能是在二叉树中查找值为x的结点，并打印该结点所有祖先结点。在此算法中，假设值为x的结点不多于一个。此算法采用后序的非递归遍历形式。因为退栈时需要区分右子树。函数中使用栈ST保存结点指针ptr以及标志tag，Top是栈顶指针。
【函数】
void print( BinTreeNode * t; DateType &x) {
stack ST; int i, top; top = 0;//置空栈
while(t! = NULL &&t-＞ data!= x || top!=0)
{ while(t!= NULL && t-＞ data!=x)
{
/*寻找值为x的结点*/
(1);
ST[top]. ptr = t；
ST[top]. tag = 0;
(2);
}
if(t!= Null && t -＞ data == x) { /*找到值为x的结点*/
for(i=1;(3);i ++)
printf("%d" ,ST[top]. ptr -＞data);
else {
while((4))
top--;
if(top＞0)
{
ST[top]. tag = 1;
(5);
}
}
}
正确答案：(1)top++ (2)t=t-＞leftChild (3)i=top (4)top＞0 && ST[top].tag=1 (5)t=ST[top].ptr-＞rightChild
(1)top++ (2)t=t-＞leftChild (3)i=top (4)top＞0 && ST[top].tag=1 (5)t=ST[top].ptr-＞rightChild 解析：这个程序是一个典型二叉树后序遍历非递归算法的应用。算法的实现思路是：先扫描根结点的所有左结点并入栈；当找到一个结点的值为x，则输入出栈里存放的数据，这些数据就是该结点所有祖先结点；然后判断栈顶元素的右子树是否已经被后序遍历过，如果是，或者右子树为空，将栈顶元素退栈，该子树已经全部后序遍历过；如果不是，则对栈顶结点的右子树进行后序遍历，此时应把栈顶结点的右子树的相结点放入栈中。再重复上述过程，直至遍历过树中所有结点。
(1)、(2)空年在循环就是扫描根结点的所有左结点并入栈，根据程序中的栈的定义，栈空时top=0，因此在入栈时，先将栈顶指针加1，因此(1)空处应填写“top++”或其等价形式，(2)空是取当前结点的左子树的根结点，因此应填写“t=t-＞leftChild”。
(3)空所在循环是处理找到值为x的结点，那么该结点的所有祖先结点都存放在栈中，栈中的栈底是二叉树的根，而栈顶元素是该结点的父结点，因此，(3)空处应填写“i=top”。
(4)空所在循环是判断栈顶元素的右子树是否已经被后序遍历过，如果是，或者右子树为空，将栈顶元素退栈，这里要填写判断条件。 tag=0表示左子树，tag=1表示右子树，因此，(4)空处应填写“top＞ 0&&ST [top].tag=1”。
(5)空所在语句块是处理栈顶元素的右子树没有被后序遍历情况，则将右子树入栈，因此(5)空处应填写“t=ST[top].ptr-＞rightChild”。 -
第16题：
阅读下列函数说明和C代码，将应填入 处的字句写在答题纸的对应栏内。
[函数1.1说明]
函数int factors(int n)的功能是判断整数n(n>=2)是否为完全数。如果n是完全数，则函数返回0，否则返回-1。
所谓“完全数”是指整数n的所有因子（不包括n)之和等于n自身。例如28的因子为1、2、4、7、14，而28=1+2+4+7+14，因此28是“完全数”。
[函数1.1]
int factors(int n)
{
int i,s;
for(i=1,s=0;i<=n/2;i++)
if(n%i==0) (1) ;
if( (2) )return 0;
return -1;
}
[函数1.2说明]
函数int maxint(int a[], int k)的功能是用递归方法求指定数组中前k个元素的最大值，并作为函数值返回。
[函数1.2]
int maxint(int a[],int k)
{
int t;
if( (3) ) return (4) ;
t=maxint(a+1, (5) );
return (a[0]>t)?a[0]:t;
正确答案：
-
第17题：
阅读以下函数说明和C语言函数，将应填入(n)处的字句填写在对应栏内。
[函数2.1说明]
函数fun1 (int m, int k, int xx [])的功能是：将大于整数m且紧靠m的k个素数存入数组xx中传回。例如：若输入17，5，则应输出：19，23，29，31，37。
[函数2.1]
fun1 (int m, int k, int xx [] )
{
inti, j, s=0;
for ( i=m+1; k＞0; i++ )
{for (j=2; j＜i; j++ )
if ( i %j=0 )
(1)
if( i==j )
{
(2)
k--; }
}
}
[函数2.2说明]
函数void fun 2 ()的功能是：打印出杨辉三角形(要求打印出10行)。
[函数2.2]
void fun2 ( )
{
int i, j;
int a[10][10];
printf ("\n" );
for (i=0; i＜10; i++
{a [i] [0]=1;
(3))
for (i=2; i＜l0; i++ )
for (j=1; j＜i; j++)
(4)
for (i=0; i＜10; i++ )
{for (j=0; j＜=i; j++ )
(5)
printf ( "\n" );
}
}
正确答案：(1)break； (2) xx [s++]=i； (3)a[i][i] =1； (4) a[i][j]=a[i-1] [j-1)+a[i-1][j]； (5) printf ("%5d"a[i] [j])；
(1)break； (2) xx [s++]=i； (3)a[i][i] =1； (4) a[i][j]=a[i-1] [j-1)+a[i-1][j]； (5) printf ("%5d"，a[i] [j])； -
第18题：
阅读以下说明和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
(1)q-＞data=x (2) s[i]=q (3) i!=1 (4) s[j]-＞1child=q (5) s[j]-＞rchild=q -
第19题：
设循环队列的结构是： const int MaxSize=100； typedef int Data Type； typedef struct { DataType data[MaxSize]； int front, rear； }Queue； 若有一个Queue类型的队列Q，试问判断队列满的条件应是(33)。
A．Q.front＝Q.rear；
B．Q.front-Q.rear==MaxSize；
C．Q.front+Q.rear＝MaxSize；
D．Q.front==(Q.rear+1)%MaxSize；
正确答案：D
解析：循环队列尾指针加1用循环区长度取模后等于头指针则表示队列满。 -
第20题：
阅读以下说明和C函数，填补函数代码中的空缺(1)～(5)，将解答填入答题纸
的对应栏内。
【说明】
队列是一种常用的数据结构，其特点是先入先出，即元素的插入在表头、删除在表
尾进行。下面采用顺序存储方式实现队列，即利用一组地址连续的存储单元存放队列元
素，同时通过模运算将存储空间看作一个环状结构（称为循环队列）。
设循环队列的存储空间容量为MAXQSIZE，并在其类型定义中设置base、rear和
lengtb三个域变量，其中’base为队列空间的首地址，rear为队尾元素的指针，length表
示队列的长度。
define maxqstze 100
typedef struct {
QElemType *base; /*循环队列的存储空间首地址*／
int rear; ／*队尾元素索引*／
int length; ／*队列的长度*／
) SqQueue;
例如，容量为8的循环队列如图3-1所示，初始时创建的空队列如图3一l(a)所示
经过一系列的入队、出队操作后，队列的状态如图3-1 (b)所示(队列长度为3)。
下面的C函数1、C函数2和C函数3用于实现队列的创建、插入和删除操作，请
完善这些代码。
【C函数1】创建一个空的循环队列。
int initQueue (SqQueue *Q)
／*创建容量为MAXQSIZE的空队列，若成功则返回1；否则返回0*／
{ Q-＞base = (QElemType*) malloc(MAXQSIZE* (1) )
if (!Q=＞base) return 0;。；
Q-＞length=O；
Q-’rear =O：
Return 1;
} /*InitQueue*/
【c函数2】元素插入循环队列。
int EnQueue(sqQueue *Q. QElemType e）／*元素e入队，若成功则返回1；否则返回0*/
{if ( Q-＞length＞=MAXQSIZE) return 0.;
Q-＞rear=(2)；
Q-＞base [Q-＞rear]=e;
(3) ;
Return 1
) /*EnQUeue*/
【c函数3】元素出循环队列。
int DeQueue (SqQueue *Q. QElemType *e)
／*若队列不空，则删除队头元素，由参数e带回其值并返回1；否则返回O*／
{1f‘(4)，return 0；
*e =O-＞base[ (Q=＞rear - Q-＞length+I+MAXQSTZE) %MAXQSIZE]
(5) ；
returnl；
} /*DeQueue*/
正确答案：
分析本题考查数据结构实现和C语言基本应用。队列是一种基本的数据结构，其基本操作有初始化、判断是否为空、八队列和出队列等。循环队列是一种采用顺序存储结构实现的队列，其特点是将队列存储空间的首尾单元在逻辑上连接起来，从而得到一个环形结构的队列空间。在循环队列的类型定义SqQueue中，指针成员base存放队列空间的首地址，存储空间应在队列的初始化操作中实现，对应的语句如下：Q-＞base=(QElemType*)malloc(MAXQSIZE*(1)),由于InitQueue(SqQueue*Q)的形参为指向结构体的指针，因此队列的参数可表示为“Q-＞base、Q-＞rear、Q-＞lengrh”或“(*Q).base、(*Q).rear、(*Q).length”，由于队列元素类型为QElemType、队列容量为MAXQSIZE，因此空(l)处应填入“sizeof(QElemType)”。入队列操作由EnQueue(SqQueue*Q，QElemTypee)实现。由于循环队列空间的容量为MAXQSIZE(也就是队满条件为“Q-＞length>=MAXQSLZE”），因此元素入队列时，需先判断是否队满，在队列中有空闲单元的情况下才能进行入队列操作。其次需确定新元素在队列空间中的位置，从图3—1(b)中可以看出，Q-＞rear指出了当前队尾元素，新元素应放入下一个位置，结合队列环形空间的要求，空(2)处应填入“(Q-＞rear+I)%。MAXQSIZE”或其等价形式。通过“Q-＞base[Q-＞rear]=e”将元素加入队列后，队列长度增加了，因此空(3)处应填入“Q-＞length++”或其等价形式。出队列操作由DeQueue(SqQueue*Q，QElemType*e)实现。元素出队列时，需要判断队列是否为空，显然，队列长度为0就直接表示了队空，因此空(4)处应填入“Q-＞length=0”或其等价形式，空(5)处应填入“Q-＞length--”或其等价形式。试题三参考答案(1)sizeoftQElemtype)(2)(Q-＞rear+1)%MAXQSIZE或等价表示(3)Q-＞length++或Q-＞length=Q-＞length+l或等价表示(4)Q-＞length=0或Q-＞length=0或等价表示(5)Q-＞length-，或Q-＞length=Q-＞length-1或等价表示 -
第21题：
阅读以下函数说明和C语言函数，将应填入(n)处的字句写在对应栏内。
[说明1]
函数int function(int a)的功能是判断指定的正整数是否为素数，若是，返回1，否则返回0。
[C函数1]
int function(int a)
{ int yes,i;
i=2;yes=1;
while(i＜=a/2 && (1) ){
if( (2) ) yes=0;
i++;
}
return yes;
}
[说明2]
函数int deleteARR(int*arr,intn)的功能是指定的有序数组压缩成各元素互不相同的有序数组，即相同数只保留一个，多余的被删除。函数返回值是互不相同的元素个数。
[C函数2]
int deleteARR(int*arr,int n)
{ int k,j;
k=0;j=1;
while(j＜n){
if( (3) )
(4)=arr[j];
j++;
}
return (5);
}
正确答案：(1) yes或yes==1或yes !=0 (2) a/i[*]i==a或a%i==0或!(a%i) (3) arr[k]!=arr[j] (4) arr[++k] (5) k+1或++k
(1) yes或yes==1或yes !=0 (2) a/i[*]i==a或a%i==0或!(a%i) (3) arr[k]!=arr[j] (4) arr[++k] (5) k+1或++k 解析：对于函数1，增加了一个判断的标志yes,开始进入素数判别循环时置yes=1，则(1)应填“yes”或“yes==1”或“yes !=0”；一旦数n能被某个不等于零的真因子整除，退出循环，则(2)应填“a/i[*]i==a”或“a%i==0”或“!(a%i)”。
对于函数2，用k记录数组arr[]中不同元素的个数，同时设置工作指针j，将arr[j]与已得到的互不相同元素的最后一个元素进行比较，若不相等，则将其作为已比较的互不相同元素的最后一个元素，所以(3)填“arr[k]!=art[j]”，(4)填“arr[++k]”。最后返回互不相同的元素个数k+1，即(5)填“k+1”或“++k”。 -
第22题：
如果希望循环队列中的向量单元都能得到利用，则可设置一个标志域tag，每当尾指针和头指针值相同时，以tag的值为O或1来区分队列状态是“空”还是“满”．请对下列函数填空，使其分别实现与此结构相应的入队列和出队列的算法．
intEnQueue(CirQueue*Q,DataType x)
{
if Q->tag==1 return 0；
Q->data[Q->rear]=x；
Q->rear=(Q->rear+1)%MAXQSIZE
if(Q->rear==Q->front)Q->tag=1
return1：
}
intDeQueue(CirQueue*Q,DataType*x)
{
if(（1）)return0；
*x=Q->data[Q->front];
Q->front= (2) ；
(3) ；
return1；
}
(1)
(2)
(3)
正确答案：
(1)Q->tag= =0(或者！Q->tag)／／如果标志域tag为0，则队空，无法出队，算法结束；
(2)(Q->front+l)% MAXQSIZE／／出队，头指针循环加1；
(3)if(Q->rear= =Q->front)Q->tag=0;／／出队后，则检查尾指针是否等于头指针，若相等，则队空，置标志域tag为0．
-
第23题：
阅读以下说明和C代码，填补代码中的空缺，将解答填入答题纸的对应栏内。
[说明]
函数GetListElemPtr(LinkList L，int i)的功能是查找含头结点单链表的第i个元素。若找到，则返回指向该结点的指针，否则返回空指针。
函数DelListElem(LinkList L,int i,ElemType *e)的功能是删除含头结点单链表的第i个元素结点，若成功则返回SUCCESS，并由参数e带回被删除元素的值，否则返回ERROR。
例如，某含头结点单链表L如下图(a)所示，删除第3个元素结点后的单链表如下图(b)所示。
1.jpg
#define SUCCESS 0 #define ERROR -1 typedef intStatus; typedef intElemType;
链表的结点类型定义如下：
typedef struct Node{ ElemType data; struct Node *next; }Node,*LinkList; [C代码] LinkListGetListElemPtr(LinkList L,int i) { /*L是含头结点的单链表的头指针,在该单链表中查找第i个元素结点; 若找到,则返回该元素结点的指针,否则返回NULL */ LinkList p; int k; /*用于元素结点计数*/ if(i＜1 || !L || !L-＞next) return NULL; k=1; p=L-＞next; /*令p指向第1个元素所在结点*/ while(p &&______){ /*查找第i个元素所在结点*/ ______; ++k; } return p; } StatusDelListElem(LinkList L,int i,ElemType *e) { /*在含头结点的单链表L中,删除第i个元素,并由e带回其值*/ LinkList p,q; /*令P指向第i个元素的前驱结点*/ if(i==1) ______; else p=GetListElemPtr(L,i-1); if(!P || !p-＞next) return ERROR; /*不存在第i个元素*/ q=______; /*令q指向待删除的结点*/ p-＞next=q-＞next; //从链表中删除结点*/ ______; /*通过参数e带回被删除结点的数据*/ free(q); return SUCCESS; }答案：解析：k＜i
p=p-＞next
p=L
p-＞next
*e=q-＞data
【解析】
本题考查C语言的指针应用和运算逻辑。
本问题的图和代码中的注释可提供完成操作的主要信息，在充分理解链表概念的基础上填充空缺的代码。
函数GetListElemPtr(LinkList L，int i)的功能是在L为头指针的链表中查找第i个元素，若找到，则返回指向该结点的指针，否则返回空指针。描述查找过程的代码如下，其中k用于对元素结点进行计数。
k=1; p=L-＞next; /*令p指向第1个元素所在结点*/