2023青海省java版本高级

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、矩阵中元素按行和按列都已排序，要求查找时间复杂度为Om+n，因此不能采用常规的二层循环的查找。可以先从右上角i=a,j=d元素与x比较，只有三种情况：一是Ai,jx，这情况下向j 小的方向继续查找；二是Ai,jx，下步应向i大的方向查找；三是Ai,j=x，查找成功。否那么，假设下标已超出范围，那么查找失败。voi

6、d 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或向左当xlli

7、nk,flag；/ 中序遍历左子树 ifpre=nullpre=t；/ 中序遍历的第一个结点不必判断 else ifpre-datadatapre=t；/前驱指针指向当前结点 elseflag=flase； /不是完全二叉树 Judgebst t-rlink,flag；/ 中序遍历右子树/JudgeBST算法结束5、给出折半查找的递归算法，并给出算法时间复杂度性分析。6、数组A和B的元素分别有序，欲将两数组合并到C数组，使C仍有序，应将A和B拷贝到C，只要注意A和B数组指针的使用，以及正确处理一数组读完数据后将另一数组余下元素复制到C中即可。void union(int A,B,C,m,n)/

8、整型数组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(“%d,&x); /此题假定结点数据域为整

9、型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);QueueInit(Q); Queu

10、eIn(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; /whilereturn 1; /JudgeComplete

11、7、题目中要求矩阵两行元素的平均值按递增顺序排序，由于每行元素个数相等，按平均值排列与按每行元素之和排列是一个意思。所以应先求出各行元素之和，放入一维数组中，然后选择一种排序方法，对该数组进行排序，注意在排序时假设有元素移动，那么与之相应的行中各元素也必须做相应变动。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=matri

12、x+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; /记新的最小值及行号.if(i!=k) /假设最小行不是当前行,要进行交换(行元素及行元素之和) pk=matrix+n*k; /pk指向第k行第1个元素. pi=matrix+n*i; /p

13、i指向第i行第1个元素. for(j=0;jn;j+) /交换两行中对应元素. sum=*(pk+j); *(pk+j)=*(pi+j); *(pi+j)=sum; sum=pi; pi=pk; pk=sum; /交换一维数组中元素之和. /if/for i free(p); /释放p数组./ Translation算法分析 算法中使用选择法排序,比较次数较多,但数据交换(移动)较少.假设用其它排序方法,虽可减少比较次数,但数据移动会增多.算法时间复杂度为O(n2).8、设有一个数组中存放了一个无序的关键序列K1、K2、Kn。现要求将Kn放在将元素排序后的正确位置上，试编写实现该功能的算法，要

14、求比较关键字的次数不超过n。51. 借助于快速排序的算法思想，在一组无序的记录中查找给定关键字值等于key的记录。设此组记录存放于数组rl.h中。假设查找成功，那么输出该记录在r数组中的位置及其值，否那么显示“not find信息。请编写出算法并简要说明算法思想。9、二部图bipartite graph G=V，E是一个能将其结点集V分为两不相交子集V 1和V2=V-V1的无向图，使得：V1中的任何两个结点在图G中均不相邻，V2中的任何结点在图G中也均不相邻。1请各举一个结点个数为5的二部图和非二部图的例子。2请用C或PASCAL编写一个函数BIPARTITE判断一个连通无向图G是否是二部图，

15、并分析程序的时间复杂度。设G用二维数组A来表示，大小为n*nn为结点个数。请在程序中加必要的注释。假设有必要可直接利用堆栈或队列操作。【10、假设第n件物品能放入背包，那么问题变为能否再从n-1件物品中选出假设干件放入背包这时背包可放入物品的重量变为s-wn。假设第n件物品不能放入背包，那么考虑从n-1件物品选假设干件放入背包这时背包可放入物品仍为s。假设最终s=0,那么有一解；否那么，假设s0但物品数nx，这情况下向j 小的方向继续查找；二是Ai,jx，下步应向i大的方向查找；三是Ai,j=x，查找成功。否那么，假设下标已超出范围，那么查找失败。void search(datatype A

16、, 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或向左当xAi,j。向下最多是m，向左最多是n。最正确情

17、况是在右上角比较一次成功，最差是在左下角Ab,c，比较m+n次，故算法最差时间复杂度是O(m+n。12、编写一个过程，对一个nn矩阵，通过行变换，使其每行元素的平均值按递增顺序排列。13、此题要求建立有序的循环链表。从头到尾扫描数组A，取出Ai0=inext=h; /形成空循环链表for(i=0;inext; while(p!=h & p-datanext; /查找Ai的插入位置 if(p=h | p-data!=Ai) /重复数据不再输入 s=(LinkedList)malloc(sizeof(LNode); s-data=Ai; pre-next=s; s-next=p;/将结点s链入链表中/for return(h);算法结束14、给定n个村庄之间的交通图，假设村庄i和j之间有道路，那么将顶点i和j用边连接，边上的Wij表示这条道路的长度，现在要从这n个村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄