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

1、請?jiān)O(shè)計(jì)一個算法，要求該算法把二叉樹的葉子結(jié)點(diǎn)按從左到右的順序連成一個單鏈表，表頭指針為head。二叉樹按二叉鏈表方式存儲，鏈接時用葉子結(jié)點(diǎn)的右指針域來存放單鏈表指針。分析你的算法的時、空復(fù)雜度。2、將頂點(diǎn)放在兩個集合V1和V2。對每個頂點(diǎn)，檢查其和鄰接點(diǎn)是否在同一個集合中，如是，則為非二部圖。為此，用整數(shù)1和2表示兩個集合。再用一隊(duì)列結(jié)構(gòu)存放圖中訪問的頂點(diǎn)。intBPGraph(AdjMatrixg)//判斷以鄰接矩陣表示的圖g是否是二部圖。{ints[];//頂點(diǎn)向量，元素值表示其屬于那個集合（值1和2表示兩個集合）intQ[];//Q為隊(duì)列，元素為圖的頂點(diǎn)，這里設(shè)頂點(diǎn)信息就是頂點(diǎn)編號。intf=0,r,visited[];//f和r分別是隊(duì)列的頭尾指針,visited[]是訪問數(shù)組for(i=1;i<=n;i++){visited[i]=0;s[i]=0;}//初始化，各頂點(diǎn)未確定屬于那個集合Q[1]=1;r=1;s[1]=1;//頂點(diǎn)1放入集合S1while(f<r){v=Q[++f];if(s[v]==1)jh=2;elsejh=1;//準(zhǔn)備v的鄰接點(diǎn)的集合號if(!visited[v]){visited[v]=1;//確保對每一個頂點(diǎn)，都要檢查與其鄰接點(diǎn)不應(yīng)在一個集合中for(j=1,j<=n;j++)if(g[v][j]==1){if(!s[j]){s[j]=jh;Q[++r]=j;}//鄰接點(diǎn)入隊(duì)列elseif(s[j]==s[v])return(0);}//非二部圖}//if(!visited[v])}//whilereturn(1);}//是二部圖[算法討論]題目給的是連通無向圖，若非連通，則算法要修改。3、由二叉樹的前序遍歷和中序遍歷序列能確定唯一的一棵二叉樹，下面程序的作用是實(shí)現(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個頂點(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、連通圖的生成樹包括圖中的全部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[];typedefstruct{BiTreet;inttag;//tag=0表示結(jié)點(diǎn)的左子女已被訪問，tag=1表示結(jié)點(diǎn)的右子女已被訪問}stack;stacks[],s1[];//棧，容量夠大BiTreeAncestor(BiTreeROOT,p,q,r)//求二叉樹上結(jié)點(diǎn)p和q的最近的共同祖先結(jié)點(diǎn)r。{top=0;bt=ROOT;while(bt!=null||top>0){while(bt!=null&&bt!=p&&bt!=q)//結(jié)點(diǎn)入棧{s[++top].t=bt;s[top].tag=0;bt=bt->lchild;}//沿左分枝向下if(bt==p)//不失一般性，假定p在q的左側(cè),遇結(jié)點(diǎn)p時，棧中元素均為p的祖先結(jié)點(diǎn){for(i=1;i<=top;i++)s1[i]=s[i];top1=top;}//將棧s的元素轉(zhuǎn)入輔助棧s1保存if(bt==q)//找到q結(jié)點(diǎn)。for(i=top;i>0;i--)//；將棧中元素的樹結(jié)點(diǎn)到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組成的序列，稱可以操作的序列為合法序列，否則稱為非法序列。（15分）（1）下面所示的序列中哪些是合法的？A.IOIIOIOOB.IOOIOIIOC.IIIOIOIOD.IIIOOIOO（2）通過對（1）的分析，寫出一個算法，判定所給的操作序列是否合法。若合法，返回true，否則返回false（假定被判定的操作序列已存入一維數(shù)組中）。12、由二叉樹的前序遍歷和中序遍歷序列能確定唯一的一棵二叉樹，下面程序的作用是實(shí)現(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é)點(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)為后序序列PreToPost(pre,post,l1+half+1,h1,l2+half,h2-1)//將右子樹先序序列轉(zhuǎn)為后序序列}}//PreToPost32..葉子結(jié)點(diǎn)只有在遍歷中才能知道，這里使用中序遞歸遍歷。設(shè)置前驅(qū)結(jié)點(diǎn)指針pre，初始為空。第一個葉子結(jié)點(diǎn)由指針head指向，遍歷到葉子結(jié)點(diǎn)時，就將它前驅(qū)的rchild指針指向它，最后葉子結(jié)點(diǎn)的rchild為空。LinkedListhead,pre=null;//全局變量LinkedListInOrder(BiTreebt)//中序遍歷二叉樹bt，將葉子結(jié)點(diǎn)從左到右鏈成一個單鏈表，表頭指針為head{if(bt){InOrder(bt->lchild);//中序遍歷左子樹if(bt->lchild==null&&bt->rchild==null)//葉子結(jié)點(diǎn)if(pre==null){head=bt;pre=bt;}//處理第一個葉子結(jié)點(diǎn)else{pre->rchild=bt;pre=bt;}//將葉子結(jié)點(diǎn)鏈入鏈表InOrder(bt->rchild);//中序遍歷左子樹pre->rchild=null;//設(shè)置鏈表尾}return(head);}//InOrder時間復(fù)雜度為O(n),輔助變量使用head和pre,?？臻g復(fù)雜度O(n)14、因?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é)束LongestPath15、假設(shè)以鄰接矩陣作為圖的存儲結(jié)構(gòu)，編寫算法判別在給定的有向圖中是否存在一個簡單有向回路，若存在，則以頂點(diǎn)序列的方式輸出該回路（找到一條即可）。（注：圖中不存在頂點(diǎn)到自己的?。┯邢驁D判斷回路要比無向圖復(fù)雜。利用深度優(yōu)先遍歷，將頂點(diǎn)分成三類：未訪問；已訪問但其鄰接點(diǎn)未