2023福建省數(shù)據(jù)要領(lǐng)加強(qiáng)

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

2、top=1) /當(dāng)前結(jié)點的右分枝已遍歷 if(!stop-Lc & !stop-Rc) /只有到葉子結(jié)點時，才查看路徑長度if(toplongest) for(i=1;i0) tagtop=1; p=stop.Rc; /沿右子分枝向下 /while(p!=null|top0)/結(jié)束LongestPath2、此題應(yīng)使用深度優(yōu)先遍歷，從主調(diào)函數(shù)進(jìn)入dfs(v)時，開始記數(shù)，假設(shè)退出dfs()前，已訪問完有向圖的全部頂點設(shè)為n個，那么有向圖有根，v為根結(jié)點。將n個頂點從1到n編號，各調(diào)用一次dfs()過程，就可以求出全部的根結(jié)點。題中有向圖的鄰接表存儲結(jié)構(gòu)、記頂點個數(shù)的變量、以及訪問標(biāo)記數(shù)組等均設(shè)計

3、為全局變量。建立有向圖g的鄰接表存儲結(jié)構(gòu)參見上面第2題，這里只給出判斷有向圖是否有根的算法。 int num=0， visited=0 /num記訪問頂點個數(shù),訪問數(shù)組visited初始化。 const n=用戶定義的頂點數(shù); AdjList g ; /用鄰接表作存儲結(jié)構(gòu)的有向圖g。 void dfs(v) visited v=1; num+; /訪問的頂點數(shù)1 if (num=n) printf(“%d是有向圖的根。n,v); num=0;/if p=gv.firstarc; while (p) if (visiedp-adjvex=0) dfs (p-adjvex);p=p-next; /

4、while visitedv=0; num-; /恢復(fù)頂點v/dfsvoid JudgeRoot()/判斷有向圖是否有根，有根那么輸出之。 static int i ;for (i=1;i=n;i+ ) /從每個頂點出發(fā)，調(diào)用dfs()各一次。 num=0; visited1.n=0; dfs(i); / JudgeRoot算法中打印根時，輸出頂點在鄰接表中的序號下標(biāo)，假設(shè)要輸出頂點信息，可使用gi.vertex。3、設(shè)計一個盡可能的高效算法輸出單鏈表的倒數(shù)第K個元素。4、在有向圖G中，如果r到G中的每個結(jié)點都有路徑可達(dá)，那么稱結(jié)點r為G的根結(jié)點。編寫一個算法完成以下功能：1建立有向圖G的鄰接

5、表存儲結(jié)構(gòu)；2判斷有向圖G是否有根，假設(shè)有，那么打印出所有根結(jié)點的值。5、連通圖的生成樹包括圖中的全部n個頂點和足以使圖連通的n-1條邊，最小生成樹是邊上權(quán)值之和最小的生成樹。故可按權(quán)值從大到小對邊進(jìn)行排序，然后從大到小將邊刪除。每刪除一條當(dāng)前權(quán)值最大的邊后，就去測試圖是否仍連通，假設(shè)不再連通，那么將該邊恢復(fù)。假設(shè)仍連通，繼續(xù)向下刪；直到剩n-1條邊為止。 void SpnTree (AdjList g) /用“破圈法求解帶權(quán)連通無向圖的一棵最小代價生成樹。typedef struct int i,j,wnode; /設(shè)頂點信息就是頂點編號，權(quán)是整型數(shù) node edge; scanf( %d

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

7、，可用圖的遍歷實現(xiàn)，6、約瑟夫環(huán)問題Josephus問題是指編號為1、2、，n的nn0個人按順時針方向圍坐成一圈，現(xiàn)從第s個人開始按順時針方向報數(shù)，數(shù)到第m個人出列，然后從出列的下一個人重新開始報數(shù)，數(shù)到第m的人又出列，如此重復(fù)直到所有的人全部出列為止?，F(xiàn)要求采用循環(huán)鏈表結(jié)構(gòu)設(shè)計一個算法，模擬此過程。#includetypedef int datatype;typedef struct nodedatatype data; struct node *next;listnode;typedef listnode *linklist;void jose(linklist head,int s,in

8、t m)linklist k1,pre,p; int count=1; pre=NULL; k1=head; /*k1為報數(shù)的起點*/ while (count!=s) /*找初始報數(shù)起點*/ pre=k1; k1=k1-next; count+; while(k1-next!=k1) /*當(dāng)循環(huán)鏈表中的結(jié)點個數(shù)大于1時*/ p=k1; /*從k1開始報數(shù)*/ count=1; while (count!=m) /*連續(xù)數(shù)m個結(jié)點*/ pre=p; p=p-next; count+; pre-next=p-next; /*輸出該結(jié)點，并刪除該結(jié)點*/ printf(%4d,p-data); f

9、ree(p); k1=pre-next; /*新的報數(shù)起點*/ printf(%4d,k1-data); /*輸出最后一個結(jié)點*/ free(k1);main()linklist head,p,r; int n,s,m,i; printf(n=); scanf(%d,&n); printf(s=); scanf(%d,&s); printf(m=,&m); scanf(%d,&m); if (n1) printf(ndata=n; r=head; for (i=n-1;i0;i-) /*建立剩余n-1個結(jié)點*/ p=(linklist)malloc(sizeof(listnode); p-da

10、ta=i; p-next=head; head=p; r-next=head; /*生成循環(huán)鏈表*/ jose(head,s,m); /*調(diào)用函數(shù)*/ 7、設(shè)有一個數(shù)組中存放了一個無序的關(guān)鍵序列K1、K2、Kn?，F(xiàn)要求將Kn放在將元素排序后的正確位置上，試編寫實現(xiàn)該功能的算法，要求比較關(guān)鍵字的次數(shù)不超過n。51. 借助于快速排序的算法思想，在一組無序的記錄中查找給定關(guān)鍵字值等于key的記錄。設(shè)此組記錄存放于數(shù)組rl.h中。假設(shè)查找成功，那么輸出該記錄在r數(shù)組中的位置及其值，否那么顯示“not find信息。請編寫出算法并簡要說明算法思想。8、題目中要求矩陣兩行元素的平均值按遞增順序排序，由于每

11、行元素個數(shù)相等，按平均值排列與按每行元素之和排列是一個意思。所以應(yīng)先求出各行元素之和，放入一維數(shù)組中，然后選擇一種排序方法，對該數(shù)組進(jìn)行排序，注意在排序時假設(shè)有元素移動，那么與之相應(yīng)的行中各元素也必須做相應(yīng)變動。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 (

12、j=0; jn; j+)sum+=*(pk); pk+; /求一行元素之和.*(p+i)=sum; /將一行元素之和存入一維數(shù)組. /for ifor(i=0; in-1; i+) /用選擇法對數(shù)組p進(jìn)行排序 min=*(p+i); k=i; /初始設(shè)第i行元素之和最小.for(j=i+1;jn;j+) if(pjmin) k=j; min=pj; /記新的最小值及行號.if(i!=k) /假設(shè)最小行不是當(dāng)前行,要進(jìn)行交換(行元素及行元素之和) pk=matrix+n*k; /pk指向第k行第1個元素. pi=matrix+n*i; /pi指向第i行第1個元素. for(j=0;jn;j+)

13、/交換兩行中對應(yīng)元素. sum=*(pk+j); *(pk+j)=*(pi+j); *(pi+j)=sum; sum=pi; pi=pk; pk=sum; /交換一維數(shù)組中元素之和. /if/for i free(p); /釋放p數(shù)組./ Translation算法分析 算法中使用選擇法排序,比較次數(shù)較多,但數(shù)據(jù)交換(移動)較少.假設(shè)用其它排序方法,雖可減少比較次數(shù),但數(shù)據(jù)移動會增多.算法時間復(fù)雜度為O(n2).9、證明由二叉樹的中序序列和后序序列，也可以唯一確定一棵二叉樹。當(dāng)n=1時，只有一個根結(jié)點，由中序序列和后序序列可以確定這棵二叉樹。設(shè)當(dāng)n=m-1時結(jié)論成立，現(xiàn)證明當(dāng)n=m時結(jié)論成立。

14、設(shè)中序序列為S1，S2，Sm,后序序列是P1,P2,，Pm。因后序序列最后一個元素Pm是根，那么在中序序列中可找到與Pm相等的結(jié)點設(shè)二叉樹中各結(jié)點互不相同Si(1im)，因中序序列是由中序遍歷而得，所以Si是根結(jié)點，S1，S2，Si-1是左子樹的中序序列，而Si+1,Si+2,Sm是右子樹的中序序列。假設(shè)i=1，那么S1是根，這時二叉樹的左子樹為空，右子樹的結(jié)點數(shù)是m-1,那么S2，S3，Sm和P1，P2，Pm-1可以唯一確定右子樹，從而也確定了二叉樹。假設(shè)i=m,那么Sm是根，這時二叉樹的右子樹為空，左子樹的結(jié)點數(shù)是m-1，那么S1，S2，Sm-1和P1，P2，Pm-1唯一確定左子樹，從而也

15、確定了二叉樹。最后，當(dāng)1ij)printf(“序列非法n)；exit(0); i+; /不管Ai是I或O，指針i均后移。 if(j!=k) printf(“序列非法n)；return(false); else printf(“序列合法n)；return(true); /算法結(jié)束。11、4、void LinkList_reverse(Linklist &L) /鏈表的就地逆置;為簡化算法,假設(shè)表長大于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的元素逐個插入新表表頭

16、q-next=p;s-next=q;L-next=s;/LinkList_reverse12、設(shè)從鍵盤輸入一整數(shù)的序列：a1, a2, a3，an,試編寫算法實現(xiàn)：用棧結(jié)構(gòu)存儲輸入的整數(shù)，當(dāng)ai-1時，將ai進(jìn)棧；當(dāng)ai=-1時，輸出棧頂整數(shù)并出棧。算法應(yīng)對異常情況入棧滿等給出相應(yīng)的信息。設(shè)有一個背包可以放入的物品重量為S，現(xiàn)有n件物品，重量分別為W1，W2，.，Wn。問能否從這n件物品中選擇假設(shè)干件放入背包，使得放入的重量之和正好是S。設(shè)布爾函數(shù)Knap(S，n)表示背包問題的解，Wi(i=1,2,.，n)均為正整數(shù)，并已順序存儲地在數(shù)組W中。請在以下算法的下劃線處填空，使其正確求解背包問題

17、。Knap(S，n)假設(shè)S=0那么Knaptrue否那么假設(shè)S0且n1)個整數(shù)存放到一維數(shù)組R中。設(shè)計一個盡可能高效時間、空間的算法，將R中保存的序列循環(huán)左移p0p1) 層上葉子結(jié)點個數(shù)if(bt=null | k1) return(0); BiTree p=bt,Q; /Q是隊列，元素是二叉樹結(jié)點指針,容量足夠大int front=0,rear=1,leaf=0; /front 和rear是隊頭和隊尾指針, leaf是葉子結(jié)點數(shù)int last=1,level=1; Q1=p; /last是二叉樹同層最右結(jié)點的指針，level 是二叉樹的層數(shù)while(frontlchild & !p-rc

18、hild) leaf+; /葉子結(jié)點 if(p-lchild) Q+rear=p-lchild; /左子女入隊 if(p-rchild) Q+rear=p-rchild; /右子女入隊 if(front=last) level+; /二叉樹同層最右結(jié)點已處理,層數(shù)增1 last=rear; /last移到指向下層最右一元素if(levelk) return (leaf); /層數(shù)大于k 后退出運(yùn)行 /while /結(jié)束LeafKLevel15、對一般二叉樹，僅根據(jù)一個先序、中序、后序遍歷，不能確定另一個遍歷序列。但對于滿二叉樹，任一結(jié)點的左右子樹均含有數(shù)量相等的結(jié)點，根據(jù)此性質(zhì)，可將任一遍歷序列轉(zhuǎn)為另一遍歷序列即任一遍歷序列均可確定一棵二叉樹。void PreToPost(ElemType pre ,post,int l1,h1,l2,h2)/將滿二叉樹的先序序列轉(zhuǎn)為后序序列，l1,h1,l2,h2是序列初始和最后結(jié)點的下標(biāo)。if(h1=l1)posth2=prel1; /根結(jié)點half=(h1-l1)/2;