2023海南省java版本入門(mén)

1、1、編寫(xiě)一個(gè)過(guò)程，對(duì)一個(gè)nn矩陣，通過(guò)行變換，使其每行元素的平均值按遞增順序排列。2、約瑟夫環(huán)問(wèn)題Josephus問(wèn)題是指編號(hào)為1、2、，n的nn0個(gè)人按順時(shí)針?lè)较驀梢蝗?，現(xiàn)從第s個(gè)人開(kāi)始按順時(shí)針?lè)较驁?bào)數(shù)，數(shù)到第m個(gè)人出列，然后從出列的下一個(gè)人重新開(kāi)始報(bào)數(shù)，數(shù)到第m的人又出列，如此重復(fù)直到所有的人全部出列為止?，F(xiàn)要求采用循環(huán)鏈表結(jié)構(gòu)設(shè)計(jì)一個(gè)算法，模擬此過(guò)程。3、編程實(shí)現(xiàn)單鏈表的就地逆置。23在數(shù)組 A1.n中有n個(gè)數(shù)據(jù)，試建立一個(gè)帶有頭結(jié)點(diǎn)的循環(huán)鏈表，頭指針為h，要求鏈中數(shù)據(jù)從小到大排列，重復(fù)的數(shù)據(jù)在鏈中只保存一個(gè).4、因?yàn)楹笮虮闅v棧中保存當(dāng)前結(jié)點(diǎn)的祖先的信息，用一變量保存棧的最高棧頂指針

2、，每當(dāng)退棧時(shí)，棧頂指針高于保存最高棧頂指針的值時(shí)，那么將該棧倒入輔助棧中，輔助棧始終保存最長(zhǎng)路徑長(zhǎng)度上的結(jié)點(diǎn)，直至后序遍歷完畢，那么輔助棧中內(nèi)容即為所求。void LongestPath(BiTree bt)/求二叉樹(shù)中的第一條最長(zhǎng)路徑長(zhǎng)度BiTree p=bt,l,s; /l, s是棧，元素是二叉樹(shù)結(jié)點(diǎn)指針，l中保存當(dāng)前最長(zhǎng)路徑中的結(jié)點(diǎn) int i，top=0,tag,longest=0; while(p | top0) while(p) s+top=p；tagtop=0; p=p-Lc; /沿左分枝向下 if(tagtop=1) /當(dāng)前結(jié)點(diǎn)的右分枝已遍歷 if(!stop-Lc & !st

3、op-Rc) /只有到葉子結(jié)點(diǎn)時(shí)，才查看路徑長(zhǎng)度if(toplongest) for(i=1;i0) tagtop=1; p=stop.Rc; /沿右子分枝向下 /while(p!=null|top0)/結(jié)束LongestPath5、后序遍歷最后訪問(wèn)根結(jié)點(diǎn)，即在遞歸算法中，根是壓在棧底的。采用后序非遞歸算法，棧中存放二叉樹(shù)結(jié)點(diǎn)的指針，當(dāng)訪問(wèn)到某結(jié)點(diǎn)時(shí)，棧中所有元素均為該結(jié)點(diǎn)的祖先。此題要找p和q 的最近共同祖先結(jié)點(diǎn)r ,不失一般性，設(shè)p在q的左邊。后序遍歷必然先遍歷到結(jié)點(diǎn)p，棧中元素均為p的祖先。將?？饺肓硪惠o助棧中。再繼續(xù)遍歷到結(jié)點(diǎn)q時(shí)，將棧中元素從棧頂開(kāi)始逐個(gè)到輔助棧中去匹配，第一個(gè)匹配即

4、相等的元素就是結(jié)點(diǎn)p 和q的最近公共祖先。typedef struct BiTree t;int tag;/tag=0 表示結(jié)點(diǎn)的左子女已被訪問(wèn)，tag=1表示結(jié)點(diǎn)的右子女已被訪問(wèn)stack;stack s,s1;/棧，容量夠大BiTree Ancestor(BiTree ROOT,p,q,r)/求二叉樹(shù)上結(jié)點(diǎn)p和q的最近的共同祖先結(jié)點(diǎn)r。top=0; bt=ROOT; while(bt!=null |top0)while(bt!=null & bt!=p & bt!=q) /結(jié)點(diǎn)入棧s+top.t=bt; stop.tag=0; bt=bt-lchild; /沿左分枝向下if(bt=p) /

5、不失一般性，假定p在q的左側(cè),遇結(jié)點(diǎn)p時(shí)，棧中元素均為p的祖先結(jié)點(diǎn)for(i=1;i0;i-)/；將棧中元素的樹(shù)結(jié)點(diǎn)到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; /沿右分枝向下遍歷/結(jié)束while(bt!=null |top0)return(null);/、p無(wú)公共祖先/結(jié)束Ancestor6、假設(shè)以鄰接矩陣作為圖的存儲(chǔ)結(jié)構(gòu)，編

6、寫(xiě)算法判別在給定的有向圖中是否存在一個(gè)簡(jiǎn)單有向回路，假設(shè)存在，那么以頂點(diǎn)序列的方式輸出該回路找到一條即可。注：圖中不存在頂點(diǎn)到自己的弧有向圖判斷回路要比無(wú)向圖復(fù)雜。利用深度優(yōu)先遍歷，將頂點(diǎn)分成三類：未訪問(wèn)；已訪問(wèn)但其鄰接點(diǎn)未訪問(wèn)完;已訪問(wèn)且其鄰接點(diǎn)已訪問(wèn)完。下面用0，1，2表示這三種狀態(tài)。前面已提到，假設(shè)dfsv結(jié)束前出現(xiàn)頂點(diǎn)u到v的回邊，那么圖中必有包含頂點(diǎn)v和u的回路。對(duì)應(yīng)程序中v的狀態(tài)為1，而u是正訪問(wèn)的頂點(diǎn)，假設(shè)我們找出u的下一鄰接點(diǎn)的狀態(tài)為1，就可以輸出回路了。void Print(int v,int start ) /輸出從頂點(diǎn)start開(kāi)始的回路。for(i=1;i=n;i+)

7、if(gvi!=0 & visitedi=1 ) /假設(shè)存在邊v,i，且頂點(diǎn)i的狀態(tà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數(shù)組為全局變量。 for (i=1;i=n;i+) visitedi=0; for (i=1;i=n;i+ ) if (!visitedi) dfs(i);/find_cycle7、此題要求建立有序的循環(huán)鏈表。從頭到尾掃描數(shù)組A，取出Ai0=inext=h; /形成空循環(huán)鏈表for(i=0;inext; while(p!=h & p-datanext; /查找Ai的插入位置 if(p=h | p-data!=Ai) /重復(fù)數(shù)據(jù)不再輸入 s=(LinkedList)malloc(sizeof(LNode); s-data=Ai; pre-next=s; s-nex

9、t=p;/將結(jié)點(diǎn)s鏈入鏈表中/for return(h);算法結(jié)束8、連通圖的生成樹(shù)包括圖中的全部n個(gè)頂點(diǎn)和足以使圖連通的n-1條邊，最小生成樹(shù)是邊上權(quán)值之和最小的生成樹(shù)。故可按權(quán)值從大到小對(duì)邊進(jìn)行排序，然后從大到小將邊刪除。每刪除一條當(dāng)前權(quán)值最大的邊后，就去測(cè)試圖是否仍連通，假設(shè)不再連通，那么將該邊恢復(fù)。假設(shè)仍連通，繼續(xù)向下刪；直到剩n-1條邊為止。 void SpnTree (AdjList g) /用“破圈法求解帶權(quán)連通無(wú)向圖的一棵最小代價(jià)生成樹(shù)。typedef struct int i,j,wnode; /設(shè)頂點(diǎn)信息就是頂點(diǎn)編號(hào)，權(quán)是整型數(shù) node edge; scanf( %d%d

10、,&e,&n) ; /輸入邊數(shù)和頂點(diǎn)數(shù)。 for (i=1;i=e;i+) /輸入e條邊：頂點(diǎn)，權(quán)值。 scanf(%d%d%d ,&edgei.i ,&edgei.j ,&edgei.w); for (i=2;i=e;i+) /按邊上的權(quán)值大小，對(duì)邊進(jìn)行逆序排序。 edge0=edgei; j=i-1;while (edgej.w=n) /破圈，直到邊數(shù)e=n-1. if (connect(k) /刪除第k條邊假設(shè)仍連通。 edgek.w=0; eg-; /測(cè)試下一條邊edgek，權(quán)值置0表示該邊被刪除k+; /下條邊 /while /算法結(jié)束。 connect()是測(cè)試圖是否連通的函數(shù)，可

11、用圖的遍歷實(shí)現(xiàn)，9、根據(jù)二叉排序樹(shù)中序遍歷所得結(jié)點(diǎn)值為增序的性質(zhì)，在遍歷中將當(dāng)前遍歷結(jié)點(diǎn)與其前驅(qū)結(jié)點(diǎn)值比較，即可得出結(jié)論，為此設(shè)全局指針變量pre初值為null和全局變量flag，初值為true。假設(shè)非二叉排序樹(shù)，那么置flag為false。#define true 1#define false 0typedef struct node datatype data; struct node *llink,*rlink; *BTree; void JudgeBSTBTree t,int flag/ 判斷二叉樹(shù)是否是二叉排序樹(shù)，本算法結(jié)束后，在調(diào)用程序中由flag得出結(jié)論。 ift!=null &

12、 flag Judgebstt-llink,flag；/ 中序遍歷左子樹(shù) ifpre=nullpre=t；/ 中序遍歷的第一個(gè)結(jié)點(diǎn)不必判斷 else ifpre-datadatapre=t；/前驅(qū)指針指向當(dāng)前結(jié)點(diǎn) elseflag=flase； /不是完全二叉樹(shù) Judgebst t-rlink,flag；/ 中序遍歷右子樹(shù)/JudgeBST算法結(jié)束10、連通圖的生成樹(shù)包括圖中的全部n個(gè)頂點(diǎn)和足以使圖連通的n-1條邊，最小生成樹(shù)是邊上權(quán)值之和最小的生成樹(shù)。故可按權(quán)值從大到小對(duì)邊進(jìn)行排序，然后從大到小將邊刪除。每刪除一條當(dāng)前權(quán)值最大的邊后，就去測(cè)試圖是否仍連通，假設(shè)不再連通，那么將該邊恢復(fù)。假設(shè)

13、仍連通，繼續(xù)向下刪；直到剩n-1條邊為止。 void SpnTree (AdjList g) /用“破圈法求解帶權(quán)連通無(wú)向圖的一棵最小代價(jià)生成樹(shù)。typedef struct int i,j,wnode; /設(shè)頂點(diǎn)信息就是頂點(diǎn)編號(hào)，權(quán)是整型數(shù) node edge; scanf( %d%d,&e,&n) ; /輸入邊數(shù)和頂點(diǎn)數(shù)。 for (i=1;i=e;i+) /輸入e條邊：頂點(diǎn)，權(quán)值。 scanf(%d%d%d ,&edgei.i ,&edgei.j ,&edgei.w); for (i=2;i=e;i+) /按邊上的權(quán)值大小，對(duì)邊進(jìn)行逆序排序。 edge0=edgei; j=i-1;whi

14、le (edgej.w=n) /破圈，直到邊數(shù)e=n-1. if (connect(k) /刪除第k條邊假設(shè)仍連通。 edgek.w=0; eg-; /測(cè)試下一條邊edgek，權(quán)值置0表示該邊被刪除k+; /下條邊 /while /算法結(jié)束。 connect()是測(cè)試圖是否連通的函數(shù)，可用圖的遍歷實(shí)現(xiàn)，11、4、void LinkList_reverse(Linklist &L) /鏈表的就地逆置;為簡(jiǎn)化算法,假設(shè)表長(zhǎng)大于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、的元素逐個(gè)插入新表表頭 q-next=p;s-next=q;L-next=s;/LinkList_reverse12、設(shè)一棵二叉樹(shù)的結(jié)點(diǎn)結(jié)構(gòu)為 (LLINK,INFO,RLINK),ROOT為指向該二叉樹(shù)根結(jié)點(diǎn)的指針，p和q分別為指向該二叉樹(shù)中任意兩個(gè)結(jié)點(diǎn)的指針，試編寫(xiě)一算法ANCESTORROOT，p,q,r,該算法找到p和q的最近共同祖先結(jié)點(diǎn)r。13、編程實(shí)現(xiàn)單鏈表的就地逆置。23在數(shù)組 A1.n中有n個(gè)數(shù)據(jù)，試建立一個(gè)帶有頭結(jié)點(diǎn)的循環(huán)鏈表，頭指針為h，要求鏈中數(shù)據(jù)從小到大排列，重復(fù)的數(shù)據(jù)在鏈中只保存一個(gè).14、我們用l代表最長(zhǎng)平臺(tái)的長(zhǎng)度，用k指示最長(zhǎng)平臺(tái)在數(shù)組b中的起始位置下標(biāo)。用j記住

16、局部平臺(tái)的起始位置，用i指示掃描b數(shù)組的下標(biāo)，i從0開(kāi)始，依次和后續(xù)元素比較，假設(shè)局部平臺(tái)長(zhǎng)度i-j大于l時(shí)，那么修改最長(zhǎng)平臺(tái)的長(zhǎng)度kl=i-j和其在b中的起始位置k=j，直到b數(shù)組結(jié)束，l即為所求。void Platform (int b , int N) /求具有N個(gè)元素的整型數(shù)組b中最長(zhǎng)平臺(tái)的長(zhǎng)度。l=1;k=0;j=0;i=0;while(in-1)while(il) l=i-j+1;k=j; /局部最長(zhǎng)平臺(tái)i+; j=i; /新平臺(tái)起點(diǎn)printf(“最長(zhǎng)平臺(tái)長(zhǎng)度%d，在b數(shù)組中起始下標(biāo)為%d，l，k)；/ Platform15、約瑟夫環(huán)問(wèn)題Josephus問(wèn)題是指編號(hào)為1、2、，n

17、的nn0個(gè)人按順時(shí)針?lè)较驀梢蝗?，現(xiàn)從第s個(gè)人開(kāi)始按順時(shí)針?lè)较驁?bào)數(shù)，數(shù)到第m個(gè)人出列，然后從出列的下一個(gè)人重新開(kāi)始報(bào)數(shù)，數(shù)到第m的人又出列，如此重復(fù)直到所有的人全部出列為止?，F(xiàn)要求采用循環(huán)鏈表結(jié)構(gòu)設(shè)計(jì)一個(gè)算法，模擬此過(guò)程。#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為報(bào)數(shù)的起點(diǎn)*/ while (count!=s) /*找初始報(bào)數(shù)起點(diǎn)*/ pre=k1; k1=k1-next; count+; while(k1-next!=k1) /*當(dāng)循環(huán)鏈表中的結(jié)點(diǎn)個(gè)數(shù)大于1時(shí)*/ p=k1; /*從k1開(kāi)始報(bào)數(shù)*/ count=1; while (count!=m) /*連續(xù)數(shù)m個(gè)結(jié)點(diǎn)*/ pre=p; p=p-next; count+; pre-next=p-next; /*輸出該結(jié)點(diǎn)，并刪除該結(jié)點(diǎn)*/ printf(%4d,p-data); free(p); k1=pre-next; /*新的報(bào)數(shù)起點(diǎn)*/ printf(%4d,k1-data); /*輸出最后一個(gè)結(jié)點(diǎn)*/ free(k1);main()linklist