2023西藏自治区C语言版入门

1、1、由二叉树的前序遍历和中序遍历序列能确定唯一的一棵二叉树，下面程序的作用是实现由某二叉树的前序遍历和中序遍历序列，生成一棵用二叉链表表示的二叉树并打印出后序遍历序列，请写出程序所缺的语句。#define MAX 100typedef struct Nodechar info; struct Node *llink, *rlink; TNODE;char predMAX,inodMAX; main(int argc,int *argv) TNODE *root;if(argc3) exit 0;strcpy(pred,argv1); strcpy(inod,argv2);root=restor

2、e(pred,inod,strlen(pred);postorder(root);TNODE *restore(char *ppos,char *ipos,int n) TNODE *ptr； char *rpos; int k;if(ninfo=(1)_;for(2)_ ; rposllink=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(pt

3、r-rlink); printf(“%c,ptr-info); 2、二叉树的层次遍历序列的第一个结点是二叉树的根。实际上，层次遍历序列中的每个结点都是“局部根。确定根后，到二叉树的中序序列中，查到该结点，该结点将二叉树分为“左根右三局部。假设左、右子树均有，那么层次序列根结点的后面应是左右子树的根；假设中序序列中只有左子树或只有右子树，那么在层次序列的根结点后也只有左子树的根或右子树的根。这样，定义一个全局变量指针R，指向层次序列待处理元素。算法中先处理根结点，将根结点和左右子女的信息入队列。然后，在队列不空的条件下，循环处理二叉树的结点。队列中元素的数据结构定义如下：typedef stru

4、ct int lvl; /层次序列指针，总是指向当前“根结点在层次序列中的位置int l,h; /中序序列的下上界int f; /层次序列中当前“根结点的双亲结点的指针int lr; / 1双亲的左子树 2双亲的右子树qnode; BiTree Creat(datatype in,level,int n)/由二叉树的层次序列leveln和中序序列inn生成二叉树。 n是二叉树的结点数if (ndata=level0; p-lchild=null; p-rchild=null; /填写该结点数据for (i=0; ilchild=null; s.lvl=+R; s.l=i+1; s.h=n-1;

5、 s.f=p; s.lr=2; enqueue(Q,s); else if (i=n-1) /根结点无右子树，遍历序列的1n-1是左子树p-rchild=null; s.lvl=+R; s.l=1; s.h=i-1; s.f=p; s.lr=1; enqueue(Q,s); else /根结点有左子树和右子树s.lvl=+R; s.l=0; s.h=i-1; s.f=p; s.lr=1;enqueue(Q,s);/左子树有关信息入队列s.lvl=+R; s.l=i+1;s.h=n-1;s.f=p; s.lr=2;enqueue(Q,s);/右子树有关信息入队列while (!empty(Q)

6、/当队列不空，进行循环，构造二叉树的左右子树 s=delqueue(Q); father=s.f; for (i=s.l; idata=levels.lvl; p-lchild=null; p-rchild=null; /填写该结点数据 if (s.lr=1) father-lchild=p; else father-rchild=p； /让双亲的子女指针指向该结点 if (i=s.l) p-lchild=null; /处理无左子女s.lvl=+R; s.l=i+1; s.f=p; s.lr=2; enqueue(Q,s); else if (i=s.h) p-rchild=null; /处理

7、无右子女 s.lvl=+R; s.h=i-1; s.f=p; s.lr=1; enqueue(Q,s); elses.lvl=+R; s.h=i-1; s.f=p; s.lr=1; enqueue(Q,s);/左子树有关信息入队列 s.lvl=+R; s.l=i+1; s.f=p; s.lr=2; enqueue(Q,s); /右子树有关信息入队列 /结束while (!empty(Q)return(p);/算法结束3、题目中要求矩阵两行元素的平均值按递增顺序排序，由于每行元素个数相等，按平均值排列与按每行元素之和排列是一个意思。所以应先求出各行元素之和，放入一维数组中，然后选择一种排序方法，

8、对该数组进行排序，注意在排序时假设有元素移动，那么与之相应的行中各元素也必须做相应变动。void Translationfloat *matrix，int n/本算法对nn的矩阵matrix，通过行变换，使其各行元素的平均值按递增排列。int i,j,k,l；float sum，min； /sum暂存各行元素之和float *p, *pi, *pk;for(i=0; in; i+) sum=0.0; pk=matrix+i*n; /pk指向矩阵各行第1个元素. for (j=0; jn; j+)sum+=*(pk); pk+; /求一行元素之和.*(p+i)=sum; /将一行元素之和存入一维

9、数组. /for ifor(i=0; in-1; i+) /用选择法对数组p进行排序 min=*(p+i); k=i; /初始设第i行元素之和最小.for(j=i+1;jn;j+) if(pjmin) k=j; min=pj; /记新的最小值及行号.if(i!=k) /假设最小行不是当前行,要进行交换(行元素及行元素之和) pk=matrix+n*k; /pk指向第k行第1个元素. pi=matrix+n*i; /pi指向第i行第1个元素. for(j=0;jn;j+) /交换两行中对应元素. sum=*(pk+j); *(pk+j)=*(pi+j); *(pi+j)=sum; sum=pi;

10、 pi=pk; pk=sum; /交换一维数组中元素之和. /if/for i free(p); /释放p数组./ Translation算法分析 算法中使用选择法排序,比较次数较多,但数据交换(移动)较少.假设用其它排序方法,虽可减少比较次数,但数据移动会增多.算法时间复杂度为O(n2).4、给出折半查找的递归算法，并给出算法时间复杂度性分析。5、编程实现单链表的就地逆置。23在数组 A1.n中有n个数据，试建立一个带有头结点的循环链表，头指针为h，要求链中数据从小到大排列，重复的数据在链中只保存一个.6、连通图的生成树包括图中的全部n个顶点和足以使图连通的n-1条边，最小生成树是边上权值之

11、和最小的生成树。故可按权值从大到小对边进行排序，然后从大到小将边删除。每删除一条当前权值最大的边后，就去测试图是否仍连通，假设不再连通，那么将该边恢复。假设仍连通，继续向下删；直到剩n-1条边为止。 void SpnTree (AdjList g) /用“破圈法求解带权连通无向图的一棵最小代价生成树。typedef struct int i,j,wnode; /设顶点信息就是顶点编号，权是整型数 node edge; scanf( %d%d,&e,&n) ; /输入边数和顶点数。 for (i=1;i=e;i+) /输入e条边：顶点，权值。 scanf(%d%d%d ,&edgei.i ,&e

12、dgei.j ,&edgei.w); for (i=2;i=e;i+) /按边上的权值大小，对边进行逆序排序。 edge0=edgei; j=i-1;while (edgej.w=n) /破圈，直到边数e=n-1. if (connect(k) /删除第k条边假设仍连通。 edgek.w=0; eg-; /测试下一条边edgek，权值置0表示该边被删除k+; /下条边 /while /算法结束。 connect()是测试图是否连通的函数，可用图的遍历实现，7、我们可用“破圈法求解带权连通无向图的一棵最小代价生成树。所谓“破圈法就是“任取一圈，去掉圈上权最大的边，反复执行这一步骤，直到没有圈为止

13、。请给出用“破圈法求解给定的带权连通无向图的一棵最小代价生成树的详细算法，并用程序实现你所给出的算法。注：圈就是回路。8、我们可用“破圈法求解带权连通无向图的一棵最小代价生成树。所谓“破圈法就是“任取一圈，去掉圈上权最大的边，反复执行这一步骤，直到没有圈为止。请给出用“破圈法求解给定的带权连通无向图的一棵最小代价生成树的详细算法，并用程序实现你所给出的算法。注：圈就是回路。9、对一般二叉树，仅根据一个先序、中序、后序遍历，不能确定另一个遍历序列。但对于满二叉树，任一结点的左右子树均含有数量相等的结点，根据此性质，可将任一遍历序列转为另一遍历序列即任一遍历序列均可确定一棵二叉树。void Pre

14、ToPost(ElemType pre ,post,int l1,h1,l2,h2)/将满二叉树的先序序列转为后序序列，l1,h1,l2,h2是序列初始和最后结点的下标。if(h1=l1)posth2=prel1; /根结点half=(h1-l1)/2; /左或右子树的结点数PreToPost(pre,post,l1+1,l1+half,l2,l2+half-1) /将左子树先序序列转为后序序列PreToPost(pre,post,l1+half+1,h1,l2+half,h2-1) /将右子树先序序列转为后序序列 /PreToPost32. .叶子结点只有在遍历中才能知道，这里使用中序递归遍

15、历。设置前驱结点指针pre，初始为空。第一个叶子结点由指针head指向，遍历到叶子结点时，就将它前驱的rchild指针指向它，最后叶子结点的rchild为空。LinkedList head,pre=null; /全局变量LinkedList InOrder(BiTree bt)/中序遍历二叉树bt，将叶子结点从左到右链成一个单链表，表头指针为head if(bt)InOrder(bt-lchild); /中序遍历左子树 if(bt-lchild=null & bt-rchild=null) /叶子结点 if(pre=null) head=bt; pre=bt; /处理第一个叶子结点 elsep

16、re-rchild=bt; pre=bt; /将叶子结点链入链表 InOrder(bt-rchild); /中序遍历左子树 pre-rchild=null; /设置链表尾 return(head); /InOrder时间复杂度为O(n),辅助变量使用head和pre,栈空间复杂度O(n)10、将顶点放在两个集合V1和V2。对每个顶点，检查其和邻接点是否在同一个集合中，如是，那么为非二部图。为此，用整数1和2表示两个集合。再用一队列结构存放图中访问的顶点。 int BPGraph (AdjMatrix g) /判断以邻接矩阵表示的图g是否是二部图。 int s; /顶点向量，元素值表示其属于那个

17、集合值1和2表示两个集合 int Q;/Q为队列，元素为图的顶点，这里设顶点信息就是顶点编号。 int f=0,r,visited; /f和r分别是队列的头尾指针,visited是访问数组 for (i=1;i=n;i+) visitedi=0;si=0; /初始化，各顶点未确定属于那个集合 Q1=1; r=1; s1=1;/顶点1放入集合S1while(fr) v=Q+f; if (sv=1) jh=2; else jh=1;/准备v的邻接点的集合号 if (!visitedv) visitedv=1; /确保对每一个顶点，都要检查与其邻接点不应在一个集合中for (j=1,j=n;j+)

18、if (gvj=1)if (!sj) sj=jh; Q+r=j; /邻接点入队列 else if (sj=sv) return(0); /非二部图 /if (!visitedv)/while return(1); /是二部图算法讨论 题目给的是连通无向图，假设非连通，那么算法要修改。11、由二叉树的前序遍历和中序遍历序列能确定唯一的一棵二叉树，下面程序的作用是实现由某二叉树的前序遍历和中序遍历序列，生成一棵用二叉链表表示的二叉树并打印出后序遍历序列，请写出程序所缺的语句。#define MAX 100typedef struct Nodechar info; struct Node *llin

19、k, *rlink; TNODE;char predMAX,inodMAX; main(int argc,int *argv) TNODE *root;if(argc3) exit 0;strcpy(pred,argv1); strcpy(inod,argv2);root=restore(pred,inod,strlen(pred);postorder(root);TNODE *restore(char *ppos,char *ipos,int n) TNODE *ptr； char *rpos; int k;if(ninfo=(1)_;for(2)_ ; rposllink=restore(

20、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); 12、证明由二叉树的中序序列和后序序列，也可以唯一确定一棵二叉树。当n=1时，只有一个根结点，由中序序列和后序序列可以确定这棵二叉树。设当n=m-1时结论成立，现证明当n=m时结论成立。设中序序列为S1，S2，Sm,后序序列是P1,P2,，Pm。因后

21、序序列最后一个元素Pm是根，那么在中序序列中可找到与Pm相等的结点设二叉树中各结点互不相同Si(1im)，因中序序列是由中序遍历而得，所以Si是根结点，S1，S2，Si-1是左子树的中序序列，而Si+1,Si+2,Sm是右子树的中序序列。假设i=1，那么S1是根，这时二叉树的左子树为空，右子树的结点数是m-1,那么S2，S3，Sm和P1，P2，Pm-1可以唯一确定右子树，从而也确定了二叉树。假设i=m,那么Sm是根，这时二叉树的右子树为空，左子树的结点数是m-1，那么S1，S2，Sm-1和P1，P2，Pm-1唯一确定左子树，从而也确定了二叉树。最后，当1ix，这情况下向j 小的方向继续查找；二是Ai,jx，下步应向i大的方向查找；三是Ai,j=x，查找成功。否那么，假设下标已超出范围，那么查找失败。void search(datatyp