2023海南省java版本入门

1、1、编写一个过程，对一个nn矩阵，通过行变换，使其每行元素的平均值按递增顺序排列。2、约瑟夫环问题Josephus问题是指编号为1、2、，n的nn0个人按顺时针方向围坐成一圈，现从第s个人开始按顺时针方向报数，数到第m个人出列，然后从出列的下一个人重新开始报数，数到第m的人又出列，如此重复直到所有的人全部出列为止。现要求采用循环链表结构设计一个算法，模拟此过程。3、编程实现单链表的就地逆置。23在数组 A1.n中有n个数据，试建立一个带有头结点的循环链表，头指针为h，要求链中数据从小到大排列，重复的数据在链中只保存一个.4、因为后序遍历栈中保存当前结点的祖先的信息，用一变量保存栈的最高栈顶指针

2、，每当退栈时，栈顶指针高于保存最高栈顶指针的值时，那么将该栈倒入辅助栈中，辅助栈始终保存最长路径长度上的结点，直至后序遍历完毕，那么辅助栈中内容即为所求。void LongestPath(BiTree bt)/求二叉树中的第一条最长路径长度BiTree p=bt,l,s; /l, s是栈，元素是二叉树结点指针，l中保存当前最长路径中的结点 int i，top=0,tag,longest=0; while(p | top0) while(p) s+top=p；tagtop=0; p=p-Lc; /沿左分枝向下 if(tagtop=1) /当前结点的右分枝已遍历 if(!stop-Lc & !st

3、op-Rc) /只有到叶子结点时，才查看路径长度if(toplongest) for(i=1;i0) tagtop=1; p=stop.Rc; /沿右子分枝向下 /while(p!=null|top0)/结束LongestPath5、后序遍历最后访问根结点，即在递归算法中，根是压在栈底的。采用后序非递归算法，栈中存放二叉树结点的指针，当访问到某结点时，栈中所有元素均为该结点的祖先。此题要找p和q 的最近共同祖先结点r ,不失一般性，设p在q的左边。后序遍历必然先遍历到结点p，栈中元素均为p的祖先。将栈拷入另一辅助栈中。再继续遍历到结点q时，将栈中元素从栈顶开始逐个到辅助栈中去匹配，第一个匹配即

4、相等的元素就是结点p 和q的最近公共祖先。typedef struct BiTree t;int tag;/tag=0 表示结点的左子女已被访问，tag=1表示结点的右子女已被访问stack;stack s,s1;/栈，容量够大BiTree Ancestor(BiTree ROOT,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) /

5、不失一般性，假定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);while(top!=0 & stop.tag=1) top-; /退栈if (top!=0)stop.tag=1;bt=stop.t-rchild; /沿右分枝向下遍历/结束while(bt!=null |top0)return(null);/、p无公共祖先/结束Ancestor6、假设以邻接矩阵作为图的存储结构，编

6、写算法判别在给定的有向图中是否存在一个简单有向回路，假设存在，那么以顶点序列的方式输出该回路找到一条即可。注：图中不存在顶点到自己的弧有向图判断回路要比无向图复杂。利用深度优先遍历，将顶点分成三类：未访问；已访问但其邻接点未访问完;已访问且其邻接点已访问完。下面用0，1，2表示这三种状态。前面已提到，假设dfsv结束前出现顶点u到v的回边，那么图中必有包含顶点v和u的回路。对应程序中v的状态为1，而u是正访问的顶点，假设我们找出u的下一邻接点的状态为1，就可以输出回路了。void Print(int v,int start ) /输出从顶点start开始的回路。for(i=1;i=n;i+)

7、if(gvi!=0 & visitedi=1 ) /假设存在边v,i，且顶点i的状态为1。 printf(“%d,v); if(i=start) printf(“n); else Print(i,start);break;/if /Printvoid dfs(int v) visitedv=1;for(j=1;j=n;j+ ) if (gvj!=0) /存在边(v,j) if (visitedj!=1) if (!visitedj) dfs(j); /if else cycle=1; Print(j,j); visitedv=2;/dfsvoid find_cycle() /判断是否有回路，有

8、那么输出邻接矩阵。visited数组为全局变量。 for (i=1;i=n;i+) visitedi=0; for (i=1;i=n;i+ ) if (!visitedi) dfs(i);/find_cycle7、此题要求建立有序的循环链表。从头到尾扫描数组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-nex

9、t=p;/将结点s链入链表中/for return(h);算法结束8、连通图的生成树包括图中的全部n个顶点和足以使图连通的n-1条边，最小生成树是边上权值之和最小的生成树。故可按权值从大到小对边进行排序，然后从大到小将边删除。每删除一条当前权值最大的边后，就去测试图是否仍连通，假设不再连通，那么将该边恢复。假设仍连通，继续向下删；直到剩n-1条边为止。 void SpnTree (AdjList g) /用“破圈法求解带权连通无向图的一棵最小代价生成树。typedef struct int i,j,wnode; /设顶点信息就是顶点编号，权是整型数 node edge; scanf( %d%d

10、,&e,&n) ; /输入边数和顶点数。 for (i=1;i=e;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()是测试图是否连通的函数，可

11、用图的遍历实现，9、根据二叉排序树中序遍历所得结点值为增序的性质，在遍历中将当前遍历结点与其前驱结点值比较，即可得出结论，为此设全局指针变量pre初值为null和全局变量flag，初值为true。假设非二叉排序树，那么置flag为false。#define true 1#define false 0typedef struct node datatype data; struct node *llink,*rlink; *BTree; void JudgeBSTBTree t,int flag/ 判断二叉树是否是二叉排序树，本算法结束后，在调用程序中由flag得出结论。 ift!=null &

12、 flag Judgebstt-llink,flag；/ 中序遍历左子树 ifpre=nullpre=t；/ 中序遍历的第一个结点不必判断 else ifpre-datadatapre=t；/前驱指针指向当前结点 elseflag=flase； /不是完全二叉树 Judgebst t-rlink,flag；/ 中序遍历右子树/JudgeBST算法结束10、连通图的生成树包括图中的全部n个顶点和足以使图连通的n-1条边，最小生成树是边上权值之和最小的生成树。故可按权值从大到小对边进行排序，然后从大到小将边删除。每删除一条当前权值最大的边后，就去测试图是否仍连通，假设不再连通，那么将该边恢复。假设

13、仍连通，继续向下删；直到剩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 ,&edgei.j ,&edgei.w); for (i=2;i=e;i+) /按边上的权值大小，对边进行逆序排序。 edge0=edgei; j=i-1;whi

14、le (edgej.w=n) /破圈，直到边数e=n-1. if (connect(k) /删除第k条边假设仍连通。 edgek.w=0; eg-; /测试下一条边edgek，权值置0表示该边被删除k+; /下条边 /while /算法结束。 connect()是测试图是否连通的函数，可用图的遍历实现，11、4、void LinkList_reverse(Linklist &L) /链表的就地逆置;为简化算法,假设表长大于2 p=L-next;q=p-next;s=q-next;p-next=NULL; while(s-next) q-next=p;p=q; q=s;s=s-next; /把L

15、的元素逐个插入新表表头 q-next=p;s-next=q;L-next=s;/LinkList_reverse12、设一棵二叉树的结点结构为 (LLINK,INFO,RLINK),ROOT为指向该二叉树根结点的指针，p和q分别为指向该二叉树中任意两个结点的指针，试编写一算法ANCESTORROOT，p,q,r,该算法找到p和q的最近共同祖先结点r。13、编程实现单链表的就地逆置。23在数组 A1.n中有n个数据，试建立一个带有头结点的循环链表，头指针为h，要求链中数据从小到大排列，重复的数据在链中只保存一个.14、我们用l代表最长平台的长度，用k指示最长平台在数组b中的起始位置下标。用j记住

16、局部平台的起始位置，用i指示扫描b数组的下标，i从0开始，依次和后续元素比较，假设局部平台长度i-j大于l时，那么修改最长平台的长度kl=i-j和其在b中的起始位置k=j，直到b数组结束，l即为所求。void Platform (int b , int N) /求具有N个元素的整型数组b中最长平台的长度。l=1;k=0;j=0;i=0;while(in-1)while(il) l=i-j+1;k=j; /局部最长平台i+; j=i; /新平台起点printf(“最长平台长度%d，在b数组中起始下标为%d，l，k)；/ Platform15、约瑟夫环问题Josephus问题是指编号为1、2、，n

17、的nn0个人按顺时针方向围坐成一圈，现从第s个人开始按顺时针方向报数，数到第m个人出列，然后从出列的下一个人重新开始报数，数到第m的人又出列，如此重复直到所有的人全部出列为止。现要求采用循环链表结构设计一个算法，模拟此过程。#includetypedef int datatype;typedef struct nodedatatype data; struct node *next;listnode;typedef listnode *linklist;void jose(linklist head,int s,int m)linklist k1,pre,p; int count=1; pre

18、=NULL; k1=head; /*k1为报数的起点*/ while (count!=s) /*找初始报数起点*/ pre=k1; k1=k1-next; count+; while(k1-next!=k1) /*当循环链表中的结点个数大于1时*/ p=k1; /*从k1开始报数*/ count=1; while (count!=m) /*连续数m个结点*/ pre=p; p=p-next; count+; pre-next=p-next; /*输出该结点，并删除该结点*/ printf(%4d,p-data); free(p); k1=pre-next; /*新的报数起点*/ printf(%4d,k1-data); /*输出最后一个结点*/ free(k1);main()linklist