试题四

阅读下列函数说明和C代码，将应填入(n)处的字句写在答题纸的对应栏内。

(说明4．1)

假设两个队列共享一个循环向量空间(如图1-2所示)，其类型Queue2定义如下：

typedef struct{

D．ateType 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；

B．inTreeNode*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)处的字句写在答题纸的对应栏内。(说明)函数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］；

[试题]试题二阅读下列函数说明和C代码，将应填入(n)处的字句写在答题纸的对应栏内。(说明2．1)以下C语言函数用二分插入法实现对整型数组a中n个数的排序功能。(函数2．1)void fun1(int a［］){int i，j，k，r，x，m；for(i=2；i<=n；i＋＋){ (1) ；k=1；r=i-1；while(k<=r){m=(k+r)/2；if(x<a［m］)r=m-1；else (2) ；}for(j=i-1；j>=k；j--)a［j+1］=a［j］；(3) ；}}

[试题]试题三阅读下列函数说明和C代码，将应填入(n)处的字句写在答题纸的对应栏内。(说明)设有一个带表头结点的双向循环链表L，每个结点有4个数据成员：指向前驱结点的指针prior、指向后继结点的指针next、存放数据的成员data和访问频度freq。所有结点的freq初始时都为0。每当在链表上进行一次L．Locate(x)操作时，令元素值x的结点的访问频度freq加1，并将该结点前移，链接到现它的访问频度相等的结点后面，使得链表中所有结点保持按访问频度递减的顺序排列，以使频繁访问的结点总是靠近表头。(函

[试题]试题八阅读下列函数说明和C代码，将应填入(n)处的字句写在答题纸的对应栏内。(说明)以下程序的功能是：从键盘上输入一个字符串，把该字符串中的小写字母转换为大写字母，输出到文件test．txt中，然后从该文件读出字符串并显示出来。(程序)#include<stdio．h>main(){FILE*fp；charstr［100］；inti=0；if((fp=fopen("text．txt" (1) ))==NULL){printf("can't open this file．＼n"

[试题]试题二阅读下列函数说明和C代码，将应填入(n)处的字句写在答题纸的对应栏内。(说明)函数print(BinTreeNode*t；DateType ＆x)的功能是在二叉树中查找值为x的结点，并打印该结点所有祖先结点。在此算法中，假设值为x的结点不多于一个。此算法采用后序的非递归遍历形式。因为退栈时需要区分右子树。函数中使用栈ST保存结点指针ptr以及标志tag，Top是栈顶指针。(函数)void print(BinTreeNode*t；DateType ＆x){stack ST；int i，top；

[试题]试题三阅读下列函数说明和C代码，将应填入(n)处的字句写在答题纸的对应栏内。(说明)函数diff的功能是：根据两个由整数(都大于-32768)按升序构成的单链表L1和L2(分别由A，B指向)构造一个单链表L3(由*r指向)，要求L3中的所有整数都是L1，并且不是L2中的整数，还要求L3中的所有整数都两两不等。(函数)#include＜malloC．h>typedef struct node{int d；struct node *next}Node；void diff(Node *A，Node

[试题]试题二阅读下列函数说明和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(siz

[试题]试题三阅读下列函数说明和C代码，将应填入(n)处的字句写在答题纸的对应栏内。(说明3．1)假设以带头结点的单循环链表作非递减有序线性表的存储结构。函数deleteklist(LinkList head)的功能是删除表中所有数值相同的多余元素，并释放结点空间。例如：链表初始元素为：(7，10，10，21，30，42，42，42，51，70)经算法操作后变为：(7，10，21，30，42，51，70)(函数3．1)void deleteklist(LinkList head){LinkNode*p，*

[试题]试题三阅读下列函数说明和C代码，将应填入(n)处的字句写在答题纸的对应栏内。(说明)函数move(int*a，int n)用于整理数组a［］的前n个元素，使其中小于0的元素移到数组的前端，大于0的元素移到数组的后端，等于0的元素留在数表中间。令a［0］~a［low-1］小于0(初始为空)；a［low］~a［i-1］等于0(初始为空)；a［i］~a［high］还未考察，当前考察元素为a［i］。a［high+1］～a［n-1］大于0(初始为空)。(函数)move(int*a，int n){int i，

[试题]试题四阅读下列函数说明和C函数，将应填入 （n） 处的字句写在答题纸的对应栏内。[函数说明]函数DeleteNode(Bitree *r,int e)的功能是：在树根结点指针为r的二叉查找（排序）树上删除键值为e的结点，若删除成功，则函数返回0，否则函数返回-1。二叉查找树结点的类型定义为：typedef struct Tnode{int data;struct Tnode *Lchild,*Rchild;}*Bitree;在二叉查找树上删除一个结点时，要考虑三种情况：1若待删除的结点p是叶子结点