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

1、因?yàn)楹笮虮闅v棧中保留當(dāng)前結(jié)點(diǎn)的祖先的信息，用一變量保存棧的最高棧頂指針，每當(dāng)退棧時，棧頂指針高于保存最高棧頂指針的值時，則將該棧倒入輔助棧中，輔助棧始終保存最長路徑長度上的結(jié)點(diǎn)，直至后序遍歷完畢，則輔助棧中內(nèi)容即為所求。voidLongestPath(BiTreebt)//求二叉樹中的第一條最長路徑長度{BiTreep=bt,l[],s[];//l,s是棧，元素是二叉樹結(jié)點(diǎn)指針，l中保留當(dāng)前最長路徑中的結(jié)點(diǎn)inti，top=0,tag[],longest=0;while(p||top>0){while(p){s[++top]=p；tag[top]=0;p=p->Lc;}//沿左分枝向下if(tag[top]==1)//當(dāng)前結(jié)點(diǎn)的右分枝已遍歷{if(!s[top]->Lc&&!s[top]->Rc)//只有到葉子結(jié)點(diǎn)時，才查看路徑長度if(top>longest){for(i=1;i<=top;i++)l[i]=s[i];longest=top;top--;}//保留當(dāng)前最長路徑到l棧，記住最高棧頂指針，退棧}elseif(top>0){tag[top]=1;p=s[top].Rc;}//沿右子分枝向下}//while(p!=null||top>0)}//結(jié)束LongestPath2、本題應(yīng)使用深度優(yōu)先遍歷，從主調(diào)函數(shù)進(jìn)入dfs(v)時，開始記數(shù)，若退出dfs()前，已訪問完有向圖的全部頂點(diǎn)（設(shè)為n個），則有向圖有根，v為根結(jié)點(diǎn)。將n個頂點(diǎn)從1到n編號，各調(diào)用一次dfs()過程，就可以求出全部的根結(jié)點(diǎn)。題中有向圖的鄰接表存儲結(jié)構(gòu)、記頂點(diǎn)個數(shù)的變量、以及訪問標(biāo)記數(shù)組等均設(shè)計(jì)為全局變量。建立有向圖g的鄰接表存儲結(jié)構(gòu)參見上面第2題，這里只給出判斷有向圖是否有根的算法。intnum=0，visited[]=0//num記訪問頂點(diǎn)個數(shù),訪問數(shù)組visited初始化。constn=用戶定義的頂點(diǎn)數(shù);AdjListg;//用鄰接表作存儲結(jié)構(gòu)的有向圖g。voiddfs(v){visited[v]=1;num++;//訪問的頂點(diǎn)數(shù)＋1if(num==n){printf(“%d是有向圖的根。\n”,v);num=0;}//ifp=g[v].firstarc;while(p){if(visied[p->adjvex]==0)dfs(p->adjvex);p=p->next;}//whilevisited[v]=0;num--;//恢復(fù)頂點(diǎn)v}//dfsvoidJudgeRoot()//判斷有向圖是否有根，有根則輸出之。{staticinti;for(i=1;i<=n;i++)//從每個頂點(diǎn)出發(fā)，調(diào)用dfs()各一次。{num=0;visited[1..n]=0;dfs(i);}}//JudgeRoot算法中打印根時，輸出頂點(diǎn)在鄰接表中的序號（下標(biāo)），若要輸出頂點(diǎn)信息，可使用g[i].vertex。3、設(shè)計(jì)一個盡可能的高效算法輸出單鏈表的倒數(shù)第K個元素。4、在有向圖G中，如果r到G中的每個結(jié)點(diǎn)都有路徑可達(dá)，則稱結(jié)點(diǎn)r為G的根結(jié)點(diǎn)。編寫一個算法完成下列功能：（1）．建立有向圖G的鄰接表存儲結(jié)構(gòu)；（2）．判斷有向圖G是否有根，若有，則打印出所有根結(jié)點(diǎn)的值。5、連通圖的生成樹包括圖中的全部n個頂點(diǎn)和足以使圖連通的n-1條邊，最小生成樹是邊上權(quán)值之和最小的生成樹。故可按權(quán)值從大到小對邊進(jìn)行排序，然后從大到小將邊刪除。每刪除一條當(dāng)前權(quán)值最大的邊后，就去測試圖是否仍連通，若不再連通，則將該邊恢復(fù)。若仍連通，繼續(xù)向下刪；直到剩n-1條邊為止。voidSpnTree(AdjListg)//用“破圈法”求解帶權(quán)連通無向圖的一棵最小代價生成樹。{typedefstruct{inti,j,w}node;//設(shè)頂點(diǎn)信息就是頂點(diǎn)編號，權(quán)是整型數(shù)nodeedge[];scanf("%d%d",&e,&n);//輸入邊數(shù)和頂點(diǎn)數(shù)。for(i=1;i<=e;i++)//輸入e條邊：頂點(diǎn)，權(quán)值。scanf("%d%d%d",&edge[i].i,&edge[i].j,&edge[i].w);for(i=2;i<=e;i++)//按邊上的權(quán)值大小，對邊進(jìn)行逆序排序。{edge[0]=edge[i];j=i-1;while(edge[j].w<edge[0].w)edge[j+1]=edge[j--];edge[j+1]=edge[0];}//fork=1;eg=e;while(eg>=n)//破圈，直到邊數(shù)e=n-1.{if(connect(k))//刪除第k條邊若仍連通。{edge[k].w=0;eg--;}//測試下一條邊edge[k]，權(quán)值置0表示該邊被刪除k++;//下條邊}//while}//算法結(jié)束。connect()是測試圖是否連通的函數(shù)，可用圖的遍歷實(shí)現(xiàn)，6、約瑟夫環(huán)問題（Josephus問題）是指編號為1、2、…，n的n（n>0）個人按順時針方向圍坐成一圈，現(xiàn)從第s個人開始按順時針方向報(bào)數(shù)，數(shù)到第m個人出列，然后從出列的下一個人重新開始報(bào)數(shù)，數(shù)到第m的人又出列，…，如此重復(fù)直到所有的人全部出列為止。現(xiàn)要求采用循環(huán)鏈表結(jié)構(gòu)設(shè)計(jì)一個算法，模擬此過程。#include<stdlib.h>typedefintdatatype;typedefstructnode{datatypedata;structnode*next;}listnode;typedeflistnode*linklist;voidjose(linklisthead,ints,intm)當(dāng)n=1時，只有一個根結(jié)點(diǎn)，由中序序列和后序序列可以確定這棵二叉樹。設(shè)當(dāng)n=m-1時結(jié)論成立，現(xiàn)證明當(dāng)n=m時結(jié)論成立。設(shè)中序序列為S1，S2，…，Sm,后序序列是P1,P2,…，Pm。因后序序列最后一個元素Pm是根，則在中序序列中可找到與Pm相等的結(jié)點(diǎn)（設(shè)二叉樹中各結(jié)點(diǎn)互不相同）Si(1≤i≤m)，因中序序列是由中序遍歷而得，所以Si是根結(jié)點(diǎn)，S1，S2，…，Si-1是左子樹的中序序列，而Si+1,Si+2,…,Sm是右子樹的中序序列。若i=1，則S1是根，這時二叉樹的左子樹為空，右子樹的結(jié)點(diǎn)數(shù)是m-1,則{S2，S3，…，Sm}和{P1，P2，…，Pm-1}可以唯一確定右子樹，從而也確定了二叉樹。若i=m,則Sm是根，這時二叉樹的右子樹為空，左子樹的結(jié)點(diǎn)數(shù)是m-1，則{S1，S2，…，Sm-1}和{P1，P2，…，Pm-1}唯一確定左子樹，從而也確定了二叉樹。最后，當(dāng)1<i<m時，Si把中序序列分成{S1，S2，…，Si-1}和{Si+1,Si+2,…，Sm}。由于后序遍歷是“左子樹—右子樹—根結(jié)點(diǎn)”，所以{P1,P2,…,Pi-1}和{Pi,Pi+1,…Pm-1}是二叉樹的左子樹和右子樹的后序遍歷序列。因而由{S1，S2，…，Si-1}和{P1，P2，…，Pi-1}可唯一確定二叉樹的左子樹，由{Si+1,Si+2,…，Sm}和{Pi,Pi+1,…，Pm-1}可唯一確定二叉樹的右子樹。10、假設(shè)以I和O分別表示入棧和出棧操作。棧的初態(tài)和終態(tài)均為空，入棧和出棧的操作序列可表示為僅由I和O組成的序列，稱可以操作的序列為合法序列，否則稱為非法序列。（15分）（1）A和D是合法序列，B和C是非法序列。（2）設(shè)被判定的操作序列已存入一維數(shù)組A中。intJudge(charA[])//判斷字符數(shù)組A中的輸入輸出序列是否是合法序列。如是，返回true，否則返回false。{i=0;//i為下標(biāo)。j=k=0;//j和k分別為I和字母O的的個數(shù)。while(A[i]!=‘\0’)//當(dāng)未到字符數(shù)組尾就作。{switch(A[i]){case‘I’:j++;break;//入棧次數(shù)增1。case‘O’:k++;if(k>j){printf(“序列非法\n”)；exit(0);}}i++;//不論A[i]是‘I’或‘O’，指針i均后移。}if(j!=k){printf(“序列非法\n”)；return(false);}else{printf(“序列合法\n”)；return(true);}}//算法結(jié)束。11、4、 voidLinkList_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的元素逐個插入新表表頭}q->next=p;s->next=q;L->next=s;}//LinkList_reverse12、設(shè)從鍵盤輸入一整數(shù)的序列：a1,a2,a3，…，an,試編寫算法實(shí)現(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件物品中選擇若干件放入背包，使得放入的重量之和正好是S。設(shè)布爾函數(shù)Knap(S，n)表示背包問題的解，Wi(i=1,2,...，n)均為正整數(shù)，并已順序存儲地在數(shù)組W中。請?jiān)谙铝兴惴ǖ南聞澗€處填空，使其正確求解背包問題。Knap(S，n)若S=0則Knap←true否則若（S<0）或(S>0且n<1)則Knap←false否則若Knap(1),_=true則print(W[n])；Knap←true否則Knap←Knap(2)_,_設(shè)有一個順序棧S，元素s1,s2,s3,s4,s5,s6依次進(jìn)棧，如果6個元素的出棧順序?yàn)閟2,s3,s4,s6,s5,s1，則順序棧的容量至少應(yīng)為多少？畫出具體進(jìn)棧、出棧過程。假定采用帶頭結(jié)點(diǎn)的單鏈表保存單詞，當(dāng)兩個單詞有相同的后綴時，則可共享相同的后綴存儲空間。例如：設(shè)str1和str2是分別指向兩個單詞的頭結(jié)點(diǎn)，請?jiān)O(shè)計(jì)一個盡可能的高效算法，找出兩個單詞共同后綴的起始位置，分析算法時間復(fù)雜度。將n(n>1)個整數(shù)存放到一維數(shù)組R中。設(shè)計(jì)一個盡可能高效（時間、空間）的算法，將R中保存的序列循環(huán)左移p（0<p<n）個位置，即將R中的數(shù)據(jù)（x0,x1,x2,…,xn-1），變換為(xp，xp＋1,…,xn-1,x0,x1,…,xp-1)。13、二部圖（bipartitegraph）G=（V，E）是一個能將其結(jié)點(diǎn)集V分為兩不相交子集V1和V2=V-V1的無向圖，使得：V1中的任何兩個結(jié)點(diǎn)在圖G中均不相鄰，V2中的任何結(jié)點(diǎn)在圖G中也均不相鄰。（1）．請各舉一個結(jié)點(diǎn)個數(shù)為5的二部圖和非二部圖的例子。（2）．請用C或PASCAL編寫一個函數(shù)BIPARTITE判斷一個連通無向圖G是否是二部圖，并分析程序的時間復(fù)雜度。設(shè)G用二維數(shù)組A來表示，大小為n*n（n為結(jié)點(diǎn)個數(shù)）。請?jiān)诔绦蛑屑颖匾淖⑨尅Ｈ粲斜匾芍苯永枚褩；蜿?duì)列操作?！?4、對二叉樹的某層上的結(jié)點(diǎn)進(jìn)行運(yùn)算，采用隊(duì)列結(jié)構(gòu)按層次遍歷最適宜。intLeafKlevel(BiTreebt,intk)//求二叉樹bt的第k(k>1)層上葉子結(jié)點(diǎn)個數(shù){if(bt==null||k<1)return(0);BiTreep=bt,Q[];//Q是隊(duì)列，元素是二叉樹結(jié)點(diǎn)指針,容量足夠大intfront=0,rear=1,leaf=0;//front和rear是隊(duì)頭和隊(duì)尾指針,leaf是葉子結(jié)點(diǎn)數(shù)intlast=1,level=1;Q[1]=p;//last是二叉樹同層最右結(jié)點(diǎn)的指針，level是二叉樹的層數(shù)while(front<=rear){p=Q[++front];if(level==k&&!p->lchild&&!p->rchild)leaf++;//葉子結(jié)點(diǎn)if(p->lchild)Q[++rear]=p->lchild;//左子女入隊(duì)if(p->rchild)Q[++rear]=p->rchild;//右子女入隊(duì)if(front==last){level++;//二叉樹同層最右結(jié)點(diǎn)已處理,層數(shù)增1last=rear;}//last移到指向下層最右一元素if(level>k)return(leaf);//層數(shù)大于k后退出運(yùn)行}//while}//結(jié)束LeafKLevel15、對一般二叉樹，僅根據(jù)一個先序、中序、后序遍歷，不能確定另一個遍歷序列。但對于滿二叉樹，任一結(jié)點(diǎn)的左右子樹均含有數(shù)量相等的結(jié)點(diǎn)，根據(jù)此性質(zhì)，可將任一遍歷序列轉(zhuǎn)為另一遍歷序列（即任一遍歷序列均可確定一棵二叉樹）。voidPreToPost(ElemTypepre[],post[],intl1,h1,l2,h2)//將滿二叉樹的先序序列轉(zhuǎn)為后序序列，l1,h1,l2,h2是序列初始和最后結(jié)點(diǎn)的下標(biāo)。{if(h1>=l1){post[h2]=pre[l1];//根結(jié)點(diǎn)half=(h1-l1)/2;//左或右子樹的結(jié)點(diǎn)數(shù)PreToPost(pre,post,l1+1,l1+half,l2,l2+half-1)//將左子樹先序序列轉(zhuǎn)為后序序列Pre