1、设一组有序的记录关键字序列为(13，18，24，35，47，50，62，83，90)，查找方法用二分查找，要求计算出查找关键字62时的比较次数并计算出查找成功时的平均查找长度。2、设T是一棵满二叉树，编写一个将T的先序遍历序列转换为后序遍历序列的递归算法。3、设一组有序的记录关键字序列为(13，18，24，35，47，50，62，83，90)，查找方法用二分查找，要求计算出查找关键字62时的比较次数并计算出查找成功时的平均查找长度。4、二部图（bipartite graph） G=（V，E）是一个能将其结点集V分为两不相交子集V 1和V2=V-V1的无向图，使得：V1中的任何两个结点在图G中均不相邻，V2中的任何结点在图G中也均不相邻。（1）．请各举一个结点个数为5的二部图和非二部图的例子。（2）．请用C或PASCAL编写一个函数BIPARTITE判断一个连通无向图G是否是二部图，并分析程序的时间复杂度。设G用二维数组A来表示，大小为n*n（n为结点个数）。请在程序中加必要的注释。若有必要可直接利用堆栈或队列操作。【5、假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，称可以操作的序列为合法序列，否则称为非法序列。（15分）（1）A和D是合法序列，B和C 是非法序列。（2）设被判定的操作序列已存入一维数组A中。int Judge(char A[])//判断字符数组A中的输入输出序列是否是合法序列。如是，返回true，否则返回false。{i=0; //i为下标。j=k=0; //j和k分别为I和字母O的的个数。while(A[i]!=‘\0’) //当未到字符数组尾就作。{switch(A[i]){case‘I’: j++; break; //入栈次数增1。case‘O’: k++; if(k>j){printf(“序列非法\n”)；exit(0);}}i++; //不论A[i]是‘I’或‘O’，指针i均后移。}if(j!=k) {printf(“序列非法\n”)；return(false);}else {printf(“序列合法\n”)；return(true);}}//算法结束。6、设一组有序的记录关键字序列为(13，18，24，35，47，50，62，83，90)，查找方法用二分查找，要求计算出查找关键字62时的比较次数并计算出查找成功时的平均查找长度。7、#define maxsize 栈空间容量 void InOutS(int s[maxsize])//s是元素为整数的栈，本算法进行入栈和退栈操作。{int top=0; //top为栈顶指针，定义top=0时为栈空。 for(i=1; i<=n; i++) //n个整数序列作处理。 {scanf(“%d”,&x); //从键盘读入整数序列。if(x!=-1) // 读入的整数不等于-1

时入栈。if(top==maxsize-1){printf(“栈满\n”);exit(0);}else s[++top]=x; //x入栈。 else //读入的整数等于-1时退栈。{if(top==0){printf(“栈空\n”);exit(0);} else printf(“出栈元素是%d\n”,s[top--])；} }}//算法结8、根据二叉排序树中序遍历所得结点值为增序的性质，在遍历中将当前遍历结点与其前驱结点值比较，即可得出结论，为此设全局指针变量pre（初值为null）和全局变量flag，初值为true。若非二叉排序树，则置flag为false。#define true 1#define false 0typedef struct node{datatype data; struct node *llink,*rlink;} *BTree;void JudgeBST（BTree t,int flag）// 判断二叉树是否是二叉排序树，本算法结束后，在调用程序中由flag得出结论。{ if（t!=null && flag）{ Judgebst（t->llink,flag）；// 中序遍历左子树if（pre==null）pre=t；// 中序遍历的第一个结点不必判断else if（pre->data<t->data）pre=t；//前驱指针指向当前结点else{flag=flase；} //不是完全二叉树 Judgebst （t->rlink,flag）；// 中序遍历右子树}//JudgeBST算法结束9、给定n个村庄之间的交通图，若村庄i和j之间有道路，则将顶点i和j用边连接，边上的Wij表示这条道路的长度，现在要从这n个村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄，才能使离医院最远的村庄到医院的路程最短?试设计一个解答上述问题的算法，并应用该算法解答如图所示的实例。（20分）10、由二叉树的前序遍历和中序遍历序列能确定唯一的一棵二叉树，下面程序的作用是实现由已知某二叉树的前序遍历和中序遍历序列，生成一棵用二叉链表表示的二叉树并打印出后序遍历序列，请写出程序所缺的语句。#define MAX 100typedef struct Node{char info; struct Node *llink, *rlink; }TNODE;char pred[MAX],inod[MAX];main(int argc,int **argv){ TNODE *root;if(argc<3) exit 0;strcpy(pred,argv[1]); strcpy(inod,argv[2]);root=restore(pred,inod,strlen(pred));postorder(root);}TNODE *restore(char *ppos,char *ipos,int n){ TNODE *ptr； char *rpos; int k;if(n<=0) return NULL;ptr->info=(1)_______;for((2)_______ ; rpos<ipos+n;rpos++) if(*rpos==*ppos) break;k=(3)_______;ptr->llink=restore(ppos+1, (4)_______,k );ptr->rlink=restore ((5)_______+k,rpos+1,n-1-k);return ptr;}postorder(TNODE*ptr){ if(ptr=NULL) return;postorder(ptr->llink); postorder(ptr->rlink); printf(“%c”,ptr->info);} 11、根据二叉排序树中序遍历所得结点值为增序的性质，在遍历中将当前遍历结点与其前驱结点值比较，即可得出结论，为此设全局指针变量pre（初值为null）和全局变量flag，初值为true。若非二叉排序树

，则置flag为false。#define true 1#define false 0typedef struct node{datatype data; struct node *llink,*rlink;} *BTree;void JudgeBST（BTree t,int flag）// 判断二叉树是否是二叉排序树，本算法结束后，在调用程序中由flag得出结论。{ if（t!=null && flag）{ Judgebst（t->llink,flag）；// 中序遍历左子树if（pre==null）pre=t；// 中序遍历的第一个结点不必判断else if（pre->data<t->data）pre=t；//前驱指针指向当前结点else{flag=flase；} //不是完全二叉树 Judgebst （t->rlink,flag）；// 中序遍历右子树}//JudgeBST算法结束12、设一棵树T中边的集合为{(A，B)，(A，C)，(A，D)，(B，E)，(C，F)，(C，G)}，要求用孩子兄弟表示法（二叉链表）表示出该树的存储结构并将该树转化成对应的二叉树。13、设t是给定的一棵二叉树，下面的递归程序count(t)用于求得:二叉树t中具有非空的左,右两个儿子的结点个数N2;只有非空左儿子的个数NL;只有非空右儿子的结点个数NR和叶子结点个数N0。N2、NL、NR、N0都是全局量，且在调用count(t)之前都置为0.typedef struct node{int data; struct node *lchild,*rchild;}node;int N2,NL,NR,N0;void count(node *t){if (t->lchild!=NULL) if (1)___ N2++; else NL++;else if (2)___ NR++; else (3)__ ;if(t->lchild!=NULL)(4)____; if (t->rchild!=NULL) (5)____;} 26.树的先序非递归算法。void example(b)btree *b;{ btree *stack[20], *p；int top;if (b!=null){ top=1; stack[top]=b;while (top>0) { p=stack[top]; top--;printf(“%d”,p->data);if (p->rchild!=null){(1)___; (2)___;}if (p->lchild!=null)(3)___; (4)__;}}}}14、假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，称可以操作的序列为合法序列，否则称为非法序列。（15分）（1）A和D是合法序列，B和C 是非法序列。（2）设被判定的操作序列已存入一维数组A中。int Judge(char A[])//判断字符数组A中的输入输出序列是否是合法序列。如是，返回true，否则返回false。{i=0; //i为下标。j=k=0; //j和k分别为I和字母O的的个数。while(A[i]!=‘\0’) //当未到字符数组尾就作。{switch(A[i]){case‘I’: j++; break; //入栈次数增1。case‘O’: k++; if(k>j){printf(“序列非法\n”)；exit(0);}}i++; //不论A[i]是‘I’或‘O’，指针i均后移。}if(j!=k) {printf(“序列非法\n”)；return(false);}else {printf(“序列合法\n”)；return(true);}}//算法结束。15、设有两个集合A和集合B，要求设计生成集合C=A∩B的算法，其中集合A、B和C用

链式存储结构表示。typedef struct node {int data; struct node *next;}lklist;void intersection(lklist *ha,lklist *hb,lklist *&hc){lklist *p,*q,*t;for(p=ha,hc=0;p!=0;p=p->next){ for(q=hb;q!=0;q=q->next) if (q->data==p->data) break;if(q!=0){ t=(lklist *)malloc(sizeof(lklist)); t->data=p->data;t->next=hc; hc=t;}}}16、题目中要求矩阵两行元素的平均值按递增顺序排序，由于每行元素个数相等，按平均值排列与按每行元素之和排列是一个意思。所以应先求出各行元素之和，放入一维数组中，然后选择一种排序方法，对该数组进行排序，注意在排序时若有元素移动，则与之相应的行中各元素也必须做相应变动。void Translation（float *matrix，int n）//本算法对n×n的矩阵matrix，通过行变换，使其各行元素的平均值按递增排列。{int i,j,k,l；float sum，min； //sum暂存各行元素之和 float *p, *pi, *pk;for(i=0; i<n; i++){sum=0.0; pk=matrix+i*n; //pk指向矩阵各行第1个元素.for (j=0; j<n; j++){sum+=*(pk); pk++;} //求一行元素之和.*(p+i)=sum; //将一行元素之和存入一维数组.}//for ifor(i=0; i<n-1; i++) //用选择法对数组p进行排序{min=*(p+i); k=i; //初始设第i行元素之和最小.for(j=i+1;j<n;j++) if(p[j]<min) {k=j; min=p[j];} //记新的最小值及行号.if(i!=k) //若最小行不是当前行,要进行交换(行元素及行元素之和){pk=matrix+n*k; //pk指向第k行第1个元素.pi=matrix+n*i; //pi指向第i行第1个元素.for(j=0;j<n;j++) //交换两行中对应元素.{sum=*(pk+j); *(pk+j)=*(pi+j); *(pi+j)=sum;}sum=p[i]; p[i]=p[k]; p[k]=sum; //交换一维数组中元素之和.}//if}//for ifree(p); //释放p数组.}// Translation[算法分析] 算法中使用选择法排序,比较次数较多,但数据交换(移动)较少.若用其它排序方法,虽可减少比较次数,但数据移动会增多.算法时间复杂度为O(n2).17、根据二叉排序树中序遍历所得结点值为增序的性质，在遍历中将当前遍历结点与其前驱结点值比较，即可得出结论，为此设全局指针变量pre（初值为null）和全局变量flag，初值为true。若非二叉排序树，则置flag为false。#define true 1#define false 0typedef struct node{datatype data; struct node *llink,*rlink;} *BTree;void JudgeBST（BTree t,int flag）// 判断二叉树是否是二叉排序树，本算法结束后，在调用程序中由flag得出结论。{ if（t!=null && flag）{ Judgebst（t->llink,flag）；// 中序遍历左子树if（pre==null）pre=t；// 中序遍历的第一个结点不必判断else if（pre->data<t->data）pre=t；//前驱指针指向当前结点else{flag=flase；} //不是完全二叉树 Judgebst （t->rlink,flag）；// 中序遍历右子