试题二

阅读下列函数说明和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) ；

}

}

}

[试题]试题二阅读下列函数说明和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)处的字句写在答题纸的对应栏内。(说明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)处的字句写在答题纸的对应栏内。(说明)设有一个带表头结点的双向循环链表L，每个结点有4个数据成员：指向前驱结点的指针prior、指向后继结点的指针next、存放数据的成员data和访问频度freq。所有结点的freq初始时都为0。每当在链表上进行一次L．Locate(x)操作时，令元素值x的结点的访问频度freq加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］；

[试题]试题四阅读下列函数说明和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个队列的入队操作。(函数

[试题]试题八阅读下列函数说明和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)处的字句写在答题纸的对应栏内。(说明)函数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)处的字句写在答题纸的对应栏内。(说明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)处的字句写在答题纸的对应栏内。(函数2．1说明)函数palindrome(char s［］)的功能是，判断字符串s是否为回文字符串，若是，则返回0，否则返回-1。若一个字符串顺读和倒读都一样时，称该字符串是回文字符串，例如："LEVEL"是回文字符串，而"LEVAL"不是。(函数2．1)int palindrome(char s［］){char*pi，*pj；pi=s；pj=s+strlen(s)-1；while(pi＜pj &&