2014福建省數(shù)據(jù)要領加強

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