2010香港特別行政區(qū)java版本高級

1、請設(shè)計一個算法，要求該算法把二叉樹的葉子結(jié)點按從左到右的順序連成一個單鏈表，表頭指針為head。二叉樹按二叉鏈表方式存儲，鏈接時用葉子結(jié)點的右指針域來存放單鏈表指針。分析你的算法的時、空復(fù)雜度。2、將頂點放在兩個集合V1和V2。對每個頂點，檢查其和鄰接點是否在同一個集合中，如是，則為非二部圖。為此，用整數(shù)1和2表示兩個集合。再用一隊列結(jié)構(gòu)存放圖中訪問的頂點。intBPGraph(AdjMatrixg)//判斷以鄰接矩陣表示的圖g是否是二部圖。{ints[];//頂點向量，元素值表示其屬于那個集合〔值1和2表示兩個集合〕intQ[];//Q為隊列，元素為圖的頂點，這里設(shè)頂點信息就是頂點編號。intf=0,r,visited[];//f和r分別是隊列的頭尾指針,visited[]是訪問數(shù)組for(i=1;i<=n;i++){visited[i]=0;s[i]=0;}//初始化，各頂點未確定屬于那個集合Q[1]=1;r=1;s[1]=1;//頂點1放入集合S1while(f<r){v=Q[++f];if(s[v]==1)jh=2;elsejh=1;//準(zhǔn)備v的鄰接點的集合號if(!visited[v]){visited[v]=1;//確保對每一個頂點，都要檢查與其鄰接點不應(yīng)在一個集合中for(j=1,j<=n;j++)if(g[v][j]==1){if(!s[j]){s[j]=jh;Q[++r]=j;}//鄰接點入隊列elseif(s[j]==s[v])return(0);}//非二部圖}//if(!visited[v])}//whilereturn(1);}//是二部圖[算法討論]題目給的是連通無向圖，假設(shè)非連通，則算法要修改。3、由二叉樹的前序遍歷和中序遍歷序列能確定唯一的一棵二叉樹，下面程序的作用是實現(xiàn)由已知某二叉樹的前序遍歷和中序遍歷序列，生成一棵用二叉鏈表表示的二叉樹并打印出后序遍歷序列，請寫出程序所缺的語句。#defineMAX100typedefstructNode{charinfo;structNode*llink,*rlink;}TNODE;charpred[MAX],inod[MAX];main(intargc,int**argv){TNODE*root;if(argc<3)exit0;strcpy(pred,argv[1]);strcpy(inod,argv[2]);root=restore(pred,inod,strlen(pred));postorder(root);}TNODE*restore(char*ppos,char*ipos,intn){TNODE*ptr；char*rpos;intk;if(n<=0)returnNULL;ptr->info=(1)_______;for((2)_______;rpos<ipos+n;rpos++)if(*rpos==*ppos)break;k=(3)_______;ptr->llink=restore(ppos+1,(4)_______,k);ptr->rlink=restore((5)_______+k,rpos+1,n-1-k);returnptr;}postorder(TNODE*ptr){if(ptr=NULL)return;postorder(ptr->llink);postorder(ptr->rlink);printf(“%c”,ptr->info);}4、請編寫一個判別給定二叉樹是否為二叉排序樹的算法，設(shè)二叉樹用llink-rlink法存儲。5、連通圖的生成樹包括圖中的全部n個頂點和足以使圖連通的n-1條邊，最小生成樹是邊上權(quán)值之和最小的生成樹。故可按權(quán)值從大到小對邊進行排序，然后從大到小將邊刪除。每刪除一條當(dāng)前權(quán)值最大的邊后，就去測試圖是否仍連通，假設(shè)不再連通，則將該邊恢復(fù)。假設(shè)仍連通，繼續(xù)向下刪；直到剩n-1條邊為止。voidSpnTree(AdjListg)//用“破圈法”求解帶權(quán)連通無向圖的一棵最小代價生成樹。{typedefstruct{inti,j,w}node;//設(shè)頂點信息就是頂點編號，權(quán)是整型數(shù)nodeedge[];scanf("%d%d",&e,&n);//輸入邊數(shù)和頂點數(shù)。for(i=1;i<=e;i++)//輸入e條邊：頂點，權(quán)值。scanf("%d%d%d",&edge[i].i,&edge[i].j,&edge[i].w);for(i=2;i<=e;i++)//按邊上的權(quá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條邊假設(shè)仍連通。{edge[k].w=0;eg--;}//測試下一條邊edge[k]，權(quán)值置0表示該邊被刪除k++;//下條邊}//while}//算法結(jié)束。connect()是測試圖是否連通的函數(shù)，可用圖的遍歷實現(xiàn)，6、連通圖的生成樹包括圖中的全部n個頂點和足以使圖連通的n-1條邊，最小生成樹是邊上權(quán)值之和最小的生成樹。故可按權(quán)值從大到小對邊進行排序，然后從大到小將邊刪除。每刪除一條當(dāng)前權(quán)值最大的邊后，就去測試圖是否仍連通，假設(shè)不再連通，則將該邊恢復(fù)。假設(shè)仍連通，繼續(xù)向下刪；直到剩n-1條邊為止。voidSpnTree(AdjListg)//用“破圈法”求解帶權(quán)連通無向圖的一棵最小代價生成樹。{typedefstruct{inti,j,w}node;//設(shè)頂點信息就是頂點編號，權(quán)是整型數(shù)nodeedge[];scanf("%d%d",&e,&n);//輸入邊數(shù)和頂點數(shù)。for(i=1;i<=e;i++)//輸入e條邊：頂點，權(quán)值。scanf("%d%d%d",&edge[i].i,&edge[i].j,&edge[i].w);for(i=2;i<=e;i++)//按邊上的權(quá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條邊假設(shè)仍連通。{edge[k].w=0;eg--;}//測試下一條邊edge[k]，權(quán)值置0表示該邊被刪除k++;//下條邊}//while}//算法結(jié)束。connect()是測試圖是否連通的函數(shù)，可用圖的遍歷實現(xiàn)，7、設(shè)從鍵盤輸入一整數(shù)的序列：a1,a2,a3，…，an,試編寫算法實現(xiàn)：用棧結(jié)構(gòu)存儲輸入的整數(shù)，當(dāng)ai≠-1時，將ai進棧；當(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中。請在以下算法的下劃線處填空，使其正確求解背包問題。Knap(S，n)假設(shè)S=0則Knap←true否則假設(shè)〔S<0〕或(S>0且n<1)則Knap←false否則假設(shè)Knap(1),_=true則print(W[n])；Knap←true否則Knap←Knap(2)_,_設(shè)有一個順序棧S，元素s1,s2,s3,s4,s5,s6依次進棧，如果6個元素的出棧順序為s2,s3,s4,s6,s5,s1，則順序棧的容量至少應(yīng)為多少？畫出具體進棧、出棧過程。假定采用帶頭結(jié)點的單鏈表保存單詞，當(dāng)兩個單詞有相同的后綴時，則可共享相同的后綴存儲空間。例如：設(shè)str1和str2是分別指向兩個單詞的頭結(jié)點，請設(shè)計一個盡可能的高效算法，找出兩個單詞共同后綴的起始位置，分析算法時間復(fù)雜度。將n(n>1)個整數(shù)存放到一維數(shù)組R中。設(shè)計一個盡可能高效〔時間、空間〕的算法，將R中保存的序列循環(huán)左移p〔0<p<n〕個位置，即將R中的數(shù)據(jù)〔x0,x1,x2,…,xn-1〕，變換為(xp，xp＋1,…,xn-1,x0,x1,…,xp-1)。8、題目中要求矩陣兩行元素的平均值按遞增順序排序，由于每行元素個數(shù)相等，按平均值排列與按每行元素之和排列是一個意思。所以應(yīng)先求出各行元素之和，放入一維數(shù)組中，然后選擇一種排序方法，對該數(shù)組進行排序，注意在排序時假設(shè)有元素移動，則與之相應(yīng)的行中各元素也必須做相應(yīng)變動。voidTranslation〔float*matrix，intn〕//本算法對n×n的矩陣matrix，通過行變換，使其各行元素的平均值按遞增排列。{inti,j,k,l；floatsum，min；//sum暫存各行元素之和float*p,*pi,*pk;for(i=0;i<n;i++){sum=0.0;pk=matrix+i*n;//pk指向矩陣各行第1個元素.for(j=0;j<n;j++){sum+=*(pk);pk++;}//求一行元素之和.*(p+i)=sum;//將一行元素之和存入一維數(shù)組.}//forifor(i=0;i<n-1;i++)//用選擇法對數(shù)組p進行排序{min=*(p+i);k=i;//初始設(shè)第i行元素之和最小.for(j=i+1;j<n;j++)if(p[j]<min){k=j;min=p[j];}//記新的最小值及行號.if(i!=k)//假設(shè)最小行不是當(dāng)前行,要進行交換(行元素及行元素之和){pk=matrix+n*k;//pk指向第k行第1個元素.pi=matrix+n*i;//pi指向第i行第1個元素.for(j=0;j<n;j++)//交換兩行中對應(yīng)元素.{sum=*(pk+j);*(pk+j)=*(pi+j);*(pi+j)=sum;}sum=p[i];p[i]=p[k];p[k]=sum;//交換一維數(shù)組中元素之和.}//if}//forifree(p);//釋放p數(shù)組.}//Translation[算法分析]算法中使用選擇法排序,比較次數(shù)較多,但數(shù)據(jù)交換(移動)較少.假設(shè)用其它排序方法,雖可減少比較次數(shù),但數(shù)據(jù)移動會增多.算法時間復(fù)雜度為O(n2).9、設(shè)有一個數(shù)組中存放了一個無序的關(guān)鍵序列K1、K2、…、Kn?，F(xiàn)要求將Kn放在將元素排序后的正確位置上，試編寫實現(xiàn)該功能的算法，要求比較關(guān)鍵字的次數(shù)不超過n。51.借助于快速排序的算法思想，在一組無序的記錄中查找給定關(guān)鍵字值等于key的記錄。設(shè)此組記錄存放于數(shù)組r[l..h]中。假設(shè)查找成功，則輸出該記錄在r數(shù)組中的位置及其值，否則顯示“notfind”信息。請編寫出算法并簡要說明算法思想。10、后序遍歷最后訪問根結(jié)點，即在遞歸算法中，根是壓在棧底的。采用后序非遞歸算法，棧中存放二叉樹結(jié)點的指針，當(dāng)訪問到某結(jié)點時，棧中所有元素均為該結(jié)點的祖先。此題要找p和q的最近共同祖先結(jié)點r,不失一般性，設(shè)p在q的左邊。后序遍歷必然先遍歷到結(jié)點p，棧中元素均為p的祖先。將?？饺肓硪惠o助棧中。再繼續(xù)遍歷到結(jié)點q時，將棧中元素從棧頂開始逐個到輔助棧中去匹配，第一個匹配〔即相等〕的元素就是結(jié)點p和q的最近公共祖先。typedefstruct{BiTreet;inttag;//tag=0表示結(jié)點的左子女已被訪問，tag=1表示結(jié)點的右子女已被訪問}stack;stacks[],s1[];//棧，容量夠大BiTreeAncestor(BiTreeROOT,p,q,r)//求二叉樹上結(jié)點p和q的最近的共同祖先結(jié)點r。{top=0;bt=ROOT;while(bt!=null||top>0){while(bt!=null&&bt!=p&&bt!=q)//結(jié)點入棧{s[++top].t=bt;s[top].tag=0;bt=bt->lchild;}//沿左分枝向下if(bt==p)//不失一般性，假定p在q的左側(cè),遇結(jié)點p時，棧中元素均為p的祖先結(jié)點{for(i=1;i<=top;i++)s1[i]=s[i];top1=top;}//將棧s的元素轉(zhuǎn)入輔助棧s1保存if(bt==q)//找到q結(jié)點。for(i=top;i>0;i--)//；將棧中元素的樹結(jié)點到s1去匹配{pp=s[i].t;for(j=top1;j>0;j--)if(s1[j].t==pp){printf(“p和q的最近共同的祖先已找到”)；return(pp);}｝while(top!=0&&s[top].tag==1)top--;//退棧if(top!=0)｛s[top].tag=1;bt=s[top].t->rchild;｝//沿右分枝向下遍歷}//結(jié)束while(bt!=null||top>0)return(null);//ｑ、p無公共祖先｝//結(jié)束Ancestor11、假設(shè)以I和O分別表示入棧和出棧操作。棧的初態(tài)和終態(tài)均為空，入棧和出棧的操作序列可表示為僅由I和O組成的序列，稱可以操作的序列為合法序列，否則稱為非法序列?！?5分〕〔1〕下面所示的序列中哪些是合法的？A.IOIIOIOOB.IOOIOIIOC.IIIOIOIOD.IIIOOIOO〔2〕通過對〔1〕的分析，寫出一個算法，判定所給的操作序列是否合法。假設(shè)合法，返回true，否則返回false〔假定被判定的操作序列已存入一維數(shù)組中〕。12、由二叉樹的前序遍歷和中序遍歷序列能確定唯一的一棵二叉樹，下面程序的作用是實現(xiàn)由已知某二叉樹的前序遍歷和中序遍歷序列，生成一棵用二叉鏈表表示的二叉樹并打印出后序遍歷序列，請寫出程序所缺的語句。#defineMAX100typedefstructNode{charinfo;structNode*llink,*rlink;}TNODE;charpred[MAX],inod[MAX];main(intargc,int**argv){TNODE*root;if(argc<3)exit0;strcpy(pred,argv[1]);strcpy(inod,argv[2]);root=restore(pred,inod,strlen(pred));postorder(root);}TNODE*restore(char*ppos,char*ipos,intn){TNODE*ptr；char*rpos;intk;if(n<=0)returnNULL;ptr->info=(1)_______;for((2)_______;rpos<ipos+n;rpos++)if(*rpos==*ppos)break;k=(3)_______;ptr->llink=restore(ppos+1,(4)_______,k);ptr->rlink=restore((5)_______+k,rpos+1,n-1-k);returnptr;}postorder(TNODE*ptr){if(ptr=NULL)return;postorder(ptr->llink);postorder(ptr->rlink);printf(“%c”,ptr->info);}13、對一般二叉樹，僅根據(jù)一個先序、中序、后序遍歷，不能確定另一個遍歷序列。但對于滿二叉樹，任一結(jié)點的左右子樹均含有數(shù)量相等的結(jié)點，根據(jù)此性質(zhì)，可將任一遍歷序列轉(zhuǎn)為另一遍歷序列〔即任一遍歷序列均可確定一棵二叉樹〕。voidPreToPost(ElemTypepre[],post[],intl1,h1,l2,h2)//將滿二叉樹的先序序列轉(zhuǎn)為后序序列，l1,h1,l2,h2是序列初始和最后結(jié)點的下標(biāo)。{if(h1>=l1){post[h2]=pre[l1];//根結(jié)點half=(h1-l1)/2;//左或右子樹的結(jié)點數(shù)PreToPost(pre,post,l1+1,l1+half,l2,l2+half-1)//將左子樹先序序列轉(zhuǎn)為后序序列PreToPost(pre,post,l1+half+1,h1,l2+half,h2-1)//將右子樹先序序列轉(zhuǎn)為后序序列}}//PreToPost32..葉子結(jié)點只有在遍歷中才能知道，這里使用中序遞歸遍歷。設(shè)置前驅(qū)結(jié)點指針pre，初始為空。第一個葉子結(jié)點由指針head指向，遍歷到葉子結(jié)點時，就將它前驅(qū)的rchild指針指向它，最后葉子結(jié)點的rchild為空。LinkedListhead,pre=null;//全局變量LinkedListInOrder(BiTreebt)//中序遍歷二叉樹bt，將葉子結(jié)點從左到右鏈成一個單鏈表，表頭指針為head{if(bt){InOrder(bt->lchild);//中序遍歷左子樹if(bt->lchild==null&&bt->rchild==null)//葉子結(jié)點if(pre==null){head=bt;pre=bt;}//處理第一個葉子結(jié)點else{pre->rchild=bt;pre=bt;}//將葉子結(jié)點鏈入鏈表InOrder(bt->rchild);//中序遍歷左子樹pre->rchild=null;//設(shè)置鏈表尾}return(head);}//InOrder時間復(fù)雜度為O(n),輔助變量使用head和pre,?？臻g復(fù)雜度O(n)14、因為后序遍歷棧中保留當(dāng)前結(jié)點的祖先的信息，用一變量保存棧的最高棧頂指針，每當(dāng)退棧時，棧頂指針高于保存最高棧頂指針的值時，則將該棧倒入輔助棧中，輔助棧始終保存最長路徑長度上的結(jié)點，直至后序遍歷完畢，則輔助棧中內(nèi)容即為所求。voidLongestPath(BiTreebt)//求二叉樹中的第一條最長路徑長度{BiTreep=bt,l[],s[];//l,s是棧，元素是二叉樹結(jié)點指針，l中保留當(dāng)前最長路徑中的結(jié)點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é)點的右分枝已遍歷{if(!s[top]->Lc&&!s[top]->Rc)//只有到葉子結(jié)點時，才查看路徑長度if(top>longest){for(i=1;i<=top;i++)l[i]=s[i];longest=top;top--;