2010青海省java版本高級(jí)

1、連通圖的生成樹包括圖中的全部n個(gè)頂點(diǎn)和足以使圖連通的n-1條邊，最小生成樹是邊上權(quán)值之和最小的生成樹。故可按權(quán)值從大到小對(duì)邊進(jìn)行排序，然后從大到小將邊刪除。每刪除一條當(dāng)前權(quán)值最大的邊后，就去測(cè)試圖是否仍連通，若不再連通，則將該邊恢復(fù)。若仍連通，繼續(xù)向下刪；直到剩n-1條邊為止。voidSpnTree(AdjListg)//用“破圈法”求解帶權(quán)連通無向圖的一棵最小代價(jià)生成樹。{typedefstruct{inti,j,w}node;//設(shè)頂點(diǎn)信息就是頂點(diǎn)編號(hào)，權(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)值大小，對(duì)邊進(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--;}//測(cè)試下一條邊edge[k]，權(quán)值置0表示該邊被刪除k++;//下條邊}//while}//算法結(jié)束。connect()是測(cè)試圖是否連通的函數(shù)，可用圖的遍歷實(shí)現(xiàn)，2、后序遍歷最后訪問根結(jié)點(diǎn)，即在遞歸算法中，根是壓在棧底的。采用后序非遞歸算法，棧中存放二叉樹結(jié)點(diǎn)的指針，當(dāng)訪問到某結(jié)點(diǎn)時(shí)，棧中所有元素均為該結(jié)點(diǎn)的祖先。本題要找p和q的最近共同祖先結(jié)點(diǎn)r,不失一般性，設(shè)p在q的左邊。后序遍歷必然先遍歷到結(jié)點(diǎn)p，棧中元素均為p的祖先。將?？饺肓硪惠o助棧中。再繼續(xù)遍歷到結(jié)點(diǎn)q時(shí)，將棧中元素從棧頂開始逐個(gè)到輔助棧中去匹配，第一個(gè)匹配（即相等）的元素就是結(jié)點(diǎn)p和q的最近公共祖先。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時(shí)，棧中元素均為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é)束Ancestor3、矩陣中元素按行和按列都已排序，要求查找時(shí)間復(fù)雜度為O（m+n），因此不能采用常規(guī)的二層循環(huán)的查找。可以先從右上角（i=a,j=d）元素與x比較，只有三種情況：一是A[i,j]>x，這情況下向j小的方向繼續(xù)查找；二是A[i,j]<x，下步應(yīng)向i大的方向查找；三是A[i,j]=x，查找成功。否則，若下標(biāo)已超出范圍，則查找失敗。voidsearch(datatypeA[][],inta,b,c,d,datatypex)//n*m矩陣A,行下標(biāo)從a到b,列下標(biāo)從c到d,本算法查找x是否在矩陣A中.{i=a;j=d;flag=0;//flag是成功查到x的標(biāo)志while(i<=b&&j>=c)if(A[i][j]==x){flag=1;break;}elseif(A[i][j]>x)j--;elsei++;if(flag)printf(“A[%d][%d]=%d”,i,j,x);//假定x為整型.elseprintf(“矩陣A中無%d元素”，x)；}算法search結(jié)束。[算法討論]算法中查找x的路線從右上角開始，向下（當(dāng)x>A[i,j]）或向左（當(dāng)x<A[i,j]）。向下最多是m，向左最多是n。最佳情況是在右上角比較一次成功，最差是在左下角（A[b,c]），比較m+n次，故算法最差時(shí)間復(fù)雜度是O(m+n）。4、根據(jù)二叉排序樹中序遍歷所得結(jié)點(diǎn)值為增序的性質(zhì)，在遍歷中將當(dāng)前遍歷結(jié)點(diǎn)與其前驅(qū)結(jié)點(diǎn)值比較，即可得出結(jié)論，為此設(shè)全局指針變量pre（初值為null）和全局變量flag，初值為true。若非二叉排序樹，則置flag為false。#definetrue1#definefalse0typedefstructnode{datatypedata;structnode*llink,*rlink;}*BTree;voidJudgeBST（BTreet,intflag）//判斷二叉樹是否是二叉排序樹，本算法結(jié)束后，在調(diào)用程序中由flag得出結(jié)論。{if（t!=null&&flag）{Judgebst（t->llink,flag）；//中序遍歷左子樹if（pre==null）pre=t；//中序遍歷的第一個(gè)結(jié)點(diǎn)不必判斷elseif（pre->data<t->data）pre=t；//前驅(qū)指針指向當(dāng)前結(jié)點(diǎn)else{flag=flase；}//不是完全二叉樹Judgebst（t->rlink,flag）；//中序遍歷右子樹}//JudgeBST算法結(jié)束選若干件放入背包（這時(shí)背包可放入物品仍為s）。若最終s=0,則有一解；否則，若s<0或雖然s>0但物品數(shù)n<1,則無解。（1）s-w[n],n-1//Knap(s-w[n],n-1)=true（2）s,n-1//Knap←Knap(s,n-1)11、矩陣中元素按行和按列都已排序，要求查找時(shí)間復(fù)雜度為O（m+n），因此不能采用常規(guī)的二層循環(huán)的查找?？梢韵葟挠疑辖牵╥=a,j=d）元素與x比較，只有三種情況：一是A[i,j]>x，這情況下向j小的方向繼續(xù)查找；二是A[i,j]<x，下步應(yīng)向i大的方向查找；三是A[i,j]=x，查找成功。否則，若下標(biāo)已超出范圍，則查找失敗。voidsearch(datatypeA[][],inta,b,c,d,datatypex)//n*m矩陣A,行下標(biāo)從a到b,列下標(biāo)從c到d,本算法查找x是否在矩陣A中.{i=a;j=d;flag=0;//flag是成功查到x的標(biāo)志while(i<=b&&j>=c)if(A[i][j]==x){flag=1;break;}elseif(A[i][j]>x)j--;elsei++;if(flag)printf(“A[%d][%d]=%d”,i,j,x);//假定x為整型.elseprintf(“矩陣A中無%d元素”，x)；}算法search結(jié)束。[算法討論]算法中查找x的路線從右上角開始，向下（當(dāng)x>A[i,j]）或向左（當(dāng)x<A[i,j]）。向下最多是m，向左最多是n。最佳情況是在右上角比較一次成功，最差是在左下角（A[b,c]），比較m+n次，故算法最差時(shí)間復(fù)雜度是O(m+n）。12、編寫一個(gè)過程，對(duì)一個(gè)n×n矩陣，通過行變換，使其每行元素的平均值按遞增順序排列。13、本題要求建立有序的循環(huán)鏈表。從頭到尾掃描數(shù)組A，取出A[i]（0<=i<n）,然后到鏈表中去查找值為A[i]的結(jié)點(diǎn)，若查找失敗，則插入。LinkedListcreat(ElemTypeA[],intn)//由含n個(gè)數(shù)據(jù)的數(shù)組A生成循環(huán)鏈表，要求鏈表有序并且無值重復(fù)結(jié)點(diǎn){LinkedListh;h=(LinkedList)malloc(sizeof(LNode));//申請(qǐng)結(jié)點(diǎn)h->next=h;//形成空循環(huán)鏈表for(i=0;i<n;i++){pre=h;p=h->next;while(p!=h&&p->data<A[i]){pre=p;p=p->next;}//查找A[i]的插入位置if(p==h||p->data!=A[i])//重復(fù)數(shù)據(jù)不再輸入{s=(LinkedList)malloc(sizeof(LNode));s->data=A[i];pre->next=s;s->next=p;//將結(jié)點(diǎn)s鏈入鏈表中}}//forreturn(h);}算法結(jié)束14、給定n個(gè)村莊之間的交通圖，若村莊i和j之間有道路，則將頂點(diǎn)i和j用邊連接，邊上的Wij表示這條道路的長(zhǎng)度，現(xiàn)在要從這n個(gè)村莊中選擇一個(gè)村莊建一所醫(yī)院，問這所醫(yī)院應(yīng)建在哪個(gè)村莊，才能使離醫(yī)院最遠(yuǎn)的村莊到醫(yī)院的路程最短?試設(shè)計(jì)一個(gè)解答上述問題的算法，并應(yīng)用該算法解答如圖所示的實(shí)例。（20分）15、假設(shè)以I和O分別表示入棧和出棧操作。棧