《2010青海省java版本高级》由会员分享，可在线阅读，更多相关《2010青海省java版本高级（6页珍藏版）》请在金锄头文库上搜索。
1、1、 连通图的生成树包括图中的全部n个顶点和足以使图连通的n-1条边，最小生成树是边上权值之和最小的生成树。故可按权值从大到小对边进行排序，然后从大到小将边删除。每删除一条当前权值最大的边后，就去测试图是否仍连通，若不再连通，则将该边恢复。若仍连通，继续向下删；直到剩n-1条边为止。 void SpnTree (AdjList g) /用“破圈法”求解带权连通无向图的一棵最小代价生成树。typedef struct int i,j,wnode; /设顶点信息就是顶点编号，权是整型数 node edge; scanf( %d%d,&e,&n) ; /输入边数和顶点数。 for (i=1;i=e;
2、i+) /输入e条边：顶点，权值。 scanf(%d%d%d ,&edgei.i ,&edgei.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()是测试图是否连通的函数，可用图的遍历实现，2、后序遍历最后访问根结点，即在递归算法中，根是压在栈
3、底的。采用后序非递归算法，栈中存放二叉树结点的指针，当访问到某结点时，栈中所有元素均为该结点的祖先。本题要找p和q 的最近共同祖先结点r ,不失一般性，设p在q的左边。后序遍历必然先遍历到结点p，栈中元素均为p的祖先。将栈拷入另一辅助栈中。再继续遍历到结点q时，将栈中元素从栈顶开始逐个到辅助栈中去匹配，第一个匹配（即相等）的元素就是结点p 和q的最近公共祖先。typedef struct BiTree t;int tag;/tag=0 表示结点的左子女已被访问，tag=1表示结点的右子女已被访问stack;stack s,s1;/栈，容量够大BiTree Ancestor(BiTree ROO
4、T,p,q,r)/求二叉树上结点p和q的最近的共同祖先结点r。top=0; bt=ROOT; while(bt!=null |top0)while(bt!=null & bt!=p & bt!=q) /结点入栈s+top.t=bt; stop.tag=0; bt=bt-lchild; /沿左分枝向下if(bt=p) /不失一般性，假定p在q的左侧,遇结点p时，栈中元素均为p的祖先结点for(i=1;i0;i-)/；将栈中元素的树结点到s1去匹配pp=si.t;for (j=top1;j0;j-)if(s1j.t=pp) printf(“p 和q的最近共同的祖先已找到”)；return (pp)
5、;while(top!=0 & stop.tag=1) top-; /退栈if (top!=0)stop.tag=1;bt=stop.t-rchild; /沿右分枝向下遍历/结束while(bt!=null |top0)return(null);/、p无公共祖先/结束Ancestor3、矩阵中元素按行和按列都已排序，要求查找时间复杂度为O（m+n），因此不能采用常规的二层循环的查找。可以先从右上角（i=a,j=d）元素与x比较，只有三种情况：一是Ai,jx， 这情况下向j 小的方向继续查找；二是Ai,jx，下步应向i大的方向查找；三是Ai,j=x，查找成功。否则，若下标已超出范围，则查找失败。
6、void search(datatype A , int a,b,c,d, datatype x) /n*m矩阵A,行下标从a到b,列下标从c到d,本算法查找x是否在矩阵A中. i=a; j=d; flag=0; /flag是成功查到x的标志 while(i=c) if(Aij=x) flag=1;break; else if (Aijx) j-; else i+; if(flag) printf(“A%d%d=%d”,i,j,x); /假定x为整型. else printf(“矩阵A中无%d 元素”，x)； 算法search结束。算法讨论算法中查找x的路线从右上角开始，向下（当xAi,j）或
7、向左（当xllink,flag）；/ 中序遍历左子树 if（pre=null）pre=t；/ 中序遍历的第一个结点不必判断 else if（pre-datadata）pre=t；/前驱指针指向当前结点 elseflag=flase； /不是完全二叉树 Judgebst （t-rlink,flag）；/ 中序遍历右子树/JudgeBST算法结束5、给出折半查找的递归算法，并给出算法时间复杂度性分析。6、数组A和B的元素分别有序，欲将两数组合并到C数组，使C仍有序，应将A和B拷贝到C，只要注意A和B数组指针的使用，以及正确处理一数组读完数据后将另一数组余下元素复制到C中即可。void union(
8、int A,B,C,m,n)/整型数组A和B各有m和n个元素，前者递增有序，后者递减有序，本算法将A和B归并为递增有序的数组C。i=0; j=n-1; k=0;/ i，j，k分别是数组A,B和C的下标，因用C描述，下标从0开始while(i=0) if(aibj) ck+=ai+ else ck+=bj-;while(i=0) ck+=bj-;算法结束4、要求二叉树按二叉链表形式存储。15分（1）写一个建立二叉树的算法。（2）写一个判别给定的二叉树是否是完全二叉树的算法。BiTree Creat() /建立二叉树的二叉链表形式的存储结构ElemType x；BiTree bt;scanf(“%
9、d”,&x); /本题假定结点数据域为整型if(x=0) bt=null;else if(x0) bt=(BiNode *)malloc(sizeof(BiNode);bt-data=x; bt-lchild=creat(); bt-rchild=creat(); else error(“输入错误”)；return(bt);/结束 BiTreeint JudgeComplete(BiTree bt) /判断二叉树是否是完全二叉树,如是，返回1，否则，返回0int tag=0; BiTree p=bt, Q; / Q是队列，元素是二叉树结点指针，容量足够大if(p=null) return (1
10、);QueueInit(Q); QueueIn(Q,p); /初始化队列，根结点指针入队while (!QueueEmpty(Q)p=QueueOut(Q); /出队 if (p-lchild & !tag) QueueIn(Q,p-lchild); /左子女入队 else if (p-lchild) return 0; /前边已有结点为空，本结点不空 else tag=1; /首次出现结点为空 if (p-rchild & !tag) QueueIn(Q,p-rchild); /右子女入队 else if (p-rchild) return 0; else tag=1; /whileretu
11、rn 1; /JudgeComplete7、题目中要求矩阵两行元素的平均值按递增顺序排序，由于每行元素个数相等，按平均值排列与按每行元素之和排列是一个意思。所以应先求出各行元素之和，放入一维数组中，然后选择一种排序方法，对该数组进行排序，注意在排序时若有元素移动，则与之相应的行中各元素也必须做相应变动。void Translation（float *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; /将一行元素之和存入一维数组. /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; /记新的最小值及行号.
