數(shù)據(jù)結(jié)構(gòu)1800題答案第

72.√××48.×2.不一定是連通圖，可能有若干連通分 11.對(duì)稱矩陣可上（下）三角矩 16.鄰接矩陣中元素值可以權(quán)21.只有無向連通圖才有生成樹 22.最小生成樹不唯一，但最小生成樹上26.45.AOE1.n，n-12.有向圖的極大強(qiáng)連同子圖3.生成樹5.n(n- 7. 10.N- 11.n- 13.N- 14 15. 16 17.2（N-1）18.19.第I零元素個(gè) 20.n21.(1)查找頂點(diǎn)的鄰接點(diǎn)的過 (2)O(n+e) (4)頂點(diǎn)的順序不(5)隊(duì)列和棧22.深度優(yōu) 25.因未給 結(jié)構(gòu)鄰接點(diǎn)按字典序排列A C

28.邊稠密邊稀 29.O(eloge）邊稀 31.(1（V，Vj） （2）1負(fù) （3）為負(fù)32.(1)n- (2)普里 34.遞增負(fù) 37.50，經(jīng)過中間頂點(diǎn) 38. 40.(1）活動(dòng)（2）活動(dòng)間的優(yōu)先關(guān)系（3）（4）活動(dòng) 41.關(guān)鍵路 42.（1）某項(xiàng)活動(dòng)以自己為先決條件（2）荒謬（3）死循43.（1）零（2）Vk度減1，若Vk入度己減到零，則Vk頂點(diǎn)入 44.（1）p<>nil (11)firstadj(g,v0)(12)notvisited[w] 48.（1）V1V4V3V6V2V5(盡管圖以鄰接表為結(jié)構(gòu)，但因沒規(guī)定鄰接點(diǎn)的排列，所以①top==- ② ③1（1）G1 (2)G2最多n(n-1)條邊，最少n條(3)G3最多n(n-1)條邊，最少n-1條邊(注：弱連通有向圖指把有向圖看作無向圖時(shí)， 0（）n(n≥0n2，即頂點(diǎn)個(gè)數(shù)的平方，與圖的邊7（1）n(n使用深度優(yōu)先遍歷，按退出dfs過程的先后順序記錄下的頂點(diǎn)是逆向拓?fù)溆行蛐蛄小?．(1) （321 5876321 58769（1） （a，(d)（h，10．圖G的具體結(jié)構(gòu)略。鄰接矩陣表示法，有n個(gè)頂點(diǎn)的圖占用n2個(gè)元素的單元，與邊的個(gè)數(shù)無關(guān)， 鄰接多重表是無向圖的另一種結(jié)構(gòu)，邊結(jié)點(diǎn)至少包括5個(gè)域：連接邊的兩個(gè)點(diǎn)。在這種查找過程中，若邊結(jié)點(diǎn)中有j，ilinkij。1n。之后，進(jìn)行調(diào)整，即若2813）（1）15（1）12V435V6 11 67 1 5圖 圖；遍歷不唯一的因素有：開始遍歷的頂點(diǎn)不同結(jié)構(gòu)不同；在鄰接表情況下鄰接點(diǎn)；19（1）（6*62123546165423（2）因未確定12354616542320．未確 AFBECD（2）AFBECD廣度優(yōu)先搜索序列 ADAB4C2D3G1FADAB4C2D3G1FA4B3C2DEGF1 DF3A22DABDG1F33GF3MSTPrimKruskalMST。ei2533469253425334692534即28（1）W E1G)={(42)（54（235（127}；E2(G)={(2（44（23}（G=（64（17（25（8（212（21}E（G）={（，8，2（4，72（34，3（58，3（25，46，7，4 （（7，8，3） （2，4， 32（1） Y2345678UV-①2①3①3②2④1④2④4④2④4⑤1⑤2⑤2⑥4⑦3voidCreatGraph(AdjList//建立有n個(gè)頂點(diǎn)和m條邊的無向圖的鄰接表結(jié){intn,m;for(i=1,i<=n;i++)//{scanf(&g[i].vertex);g[i].firstarc=null;}for(k=1;k<=m;k++)//輸入邊信息i=GraphLocateVertex(g,v1);j=GraphLocateVertex(g,v2);//頂點(diǎn)定位 ode*)malloc(sizeof( p->adjvex=j;p->next=g[i].firstarc;g[i].firstarc=p;//將邊結(jié)點(diǎn)鏈入 ode*)malloc(sizeof( p->adjvex=i;p->next=g[j].firstarc;}voidCreatAdjList(AdjList{intn;for(i=1;i<=n;j++){scanf(&g[i].vertexg[i].firstarc=null;}//輸入頂點(diǎn)信息while(v1&&v20 p->adjvex=j;p->next=g[i].firstarc;g[i].firstarc=p;}voidCreatMGraph(AdjMulist{intn,e; scanf(&g[i].vertex);g[i].firstedge=null;} i=GraphLocateVertex(g,v1);j=GraphLocateVertex(g,v2);p=(ENode*)malloc(sizeof(ENode)); g[i].firstedge=p;}voidCreatOrthList(OrthList{inti,j,v; {scanf(&g[i].vertex); g[i].firstin=null;g[i].firstout=null;}while(i&&j&& ode ode p->weight=v;//弧結(jié)點(diǎn)中權(quán)值域p->headlink=g[j].firstin;g[j].firstin=p;p->tailink=g[i].firstout;g[i].firstout=p;ijvoidInvertAdjList(AdjList{gin[i].vertex=gout[i].vertexgin.firstarc=null;for(i=1;i<=n;i++) while(p!=null){j=p- ode s->adjvex=i;s->next=gin[j].firstarc;gin[j].firstarc=s; voidAdjListToAdjMatrix(AdjListgl,AdjMatrix{for(i=1;i<=n;i++)nfor(j=1;j<=n;j++)gm[i][j]=0;for(i=1;i<=n;i++){p=gl[i].firstarc;while(p!=null){gm[i][p->adjvex]=1;p=p->next;}//forvoidAdjMatrixToAdjList(AdjMatrixgm,AdjListgl{for {scanf(&gl[i].vertex);gl[i].firstarc=null;}for(i=1;i<=n;i++)for(j=1;j<=n;j++)if ode*)malloc(sizeof( ode))p->adjvex=jIjp->next=gl[i].firstarc;gl[i].firstarc=p;i}[算法討論]算法中鄰接表中頂點(diǎn)在向量表中的下標(biāo)與其在鄰接矩陣中的行號(hào)相同。8.[ViVj（bfsflag=1。算法1：intvisited[]=0;//全局變量，數(shù)組初始intdfs(AdjListg,{ p=g[vi].firstarc;//第一個(gè)鄰接點(diǎn)。while(p!=null){j=p-if(vj==j)flag=1;return（1）;}/vivjif(visited[j]==0)dfs(g,j);p=p->next；}//whileif(!flag)vivjvj2：voiddfs(AdjListgint，，{inttop=0,stack[];//stack是存放頂點(diǎn)編號(hào)的棧 //visited數(shù)組在進(jìn)入dfs前已初始化。p=g[i].firstarcwhile(p){if(p-{stack[++top]=j;printf("頂點(diǎn)vi和vj的路徑為：\n");for(i=1i<=topi++)printf("%4d",stack[i]);exit(0); p=p->next;}//elseifintConnectij(AdjListg,vertypevi,vj0。{for(i=1;i<=n;i++)visited[i]=0;//標(biāo)記數(shù)組初始化。i=GraphLocateVertex(g,vivivjintstack[],top=0;stack[++top]=i;{k=stack[top--];while(p!=null&&visited[p->adjvex]==1)p=p->next;kif(p==null)top--;else{i=p-if(i==j)return(1);vivjelse{visited[i]=1;return(0);vivjvoidDeletEdge(AdjListg,int{p=g[i].firstarc;pre=nulli(i,j),prewhileif(p-{if(pre==null)g[i].firstarc=p->next;elsepre->next=p->next;else{pre=p;p=p->next;} p=g[j].firstarc;pre=null;j(j,i)while(p)if(p-{if(pre==null)g[j].firstarc=p->next;elsepre->next=p->next;else{pre=p;p=p }//[算法討論]算法中假定給的i，j均存在，否則應(yīng)檢查其。若未給頂點(diǎn)編號(hào)，而給出頂點(diǎn)信息，則先用頂點(diǎn)定位函數(shù)求出其在鄰接表頂點(diǎn)向量中的下標(biāo)ij。voidDeleteArc（AdjListg,vertype{i=GraphLocateVertex(g,vi);j=GraphLocateVertex(g,vj);p=g[i].firstarc;pre=null;whileif(p-{if(pre==null)g[i].firstarc=p->next;elsepre->next=p->next;else{pre=p;p=p-voidInsertArc(OrthListg,vertypei=GraphLocateVertex(g,vi ode p=headvex=jp=tailvex=i;//填寫弧結(jié)點(diǎn)信息并插入十字鏈表。p->headlink=g[j].firstin;g[j].firstin=p;p->taillink=g[i].firstout;intcount(AdjListg,intk{intcountfor //求頂點(diǎn)k {p=g[i].firstarc;/iwhile{if(p->adjvex==k)count++;return(count);k}；已但其鄰接點(diǎn)未完;已且其鄰接點(diǎn)已完。下面用0，1，2表示這三1，就可以輸出回路了。voidPrint(intv,intstartstartif(g[v][i]!=0&&visited[i]==1)//若存在邊（v,ii1 voiddfs(intfor(j=1;j<=n;j++)if(g[v][j]!=0if(visited[j]!=1){if(!visited[j])dfs(j);}//ifelse{cycle=1;Print(j,j);}voidfind_cycle()visited{for(i=1;i<=n;i++)for(i=1;i<=n;i++)if(!visited[i])鏈表，為方便運(yùn)算，在頂點(diǎn)結(jié)點(diǎn)中，再增加一個(gè)入度域indegree，存放頂點(diǎn)的入度。v,headvextailvex。intTopsor(OrthList 0{inttop=0; 點(diǎn)

{g[i].indegreeif(p->headvex==i)p=p->headlink;elsep=p->taillink;i}//while(p)for if(g[i].indegree==0{g[i].indegree=top;top=i;m=0;//mwhile{i=top;top=g[top].indegree; while(p)ig[k].indegreeif(g[k].indegree==0)g[k].indegree=toptop=k;}//入度為0if(p->headvex==i)p=p->headlink;elsep=p->taillink;//i

}//while}//whileif(m<n)retun(1);//有向圖存在環(huán)路elsereturn(0); intFirstAdj(AdjMuListg,vertype{i=GraphLocateVertex(g,v);vv if(p==null)return(0);else{if(ivex==i)return(jvex);elsereturn}//dfs(v接表結(jié)構(gòu)參見上面第2題，這里只給出判斷有向圖是否有根的算法。intnum=0，visited[]=0//num記頂點(diǎn)個(gè)數(shù),數(shù)組visited初始化constnAdjListg; voiddfs(v){visited[v]=1;num++;//的頂點(diǎn)數(shù)if(num==n){printf(“%dn”,v);num=0;}//ifwhile{if(visied[p->adjvex]==0)dfs(p->adjvex);p=p->next;}//whilevisited[v]=0;numvoid{staticintifor(i=1;i<=n;idfs{num=0;visited[1..n]=0;dfs(i);}//算法中打印根時(shí)，輸出頂點(diǎn)在鄰接表中的序號(hào)（下標(biāo)，若要輸出頂點(diǎn)信息，可使用dfsbfs到圖的通分量的所有頂點(diǎn)。voiddfs{visited[v]=1;printf3d”,v);while(p!=null){if（visited[p->adjvex==0]）dfs(p->adjvex);}//dfsvoidCount(){intk=0staticAdjListggnfor(i=1;i<=n;i++if(visited[i]==0)printf\nd\n",++kvisited[]數(shù)組是全程變量，每個(gè)連通分量的頂點(diǎn)集按遍歷順序輸出。這里設(shè)頂g[i].vertexvoidbfs(AdjListGL，vertypevprintf( QueueInit(Q);QueueIn(Q,v);vwhile{v=QueueOut(Q);p=GL[v].firstarc;//GLvwhile p=p-}//while {intcount=0;//記連通分量個(gè)數(shù)。for(i=1;i<=n;i++)visited[i]=0;for(i=1;i<=n;i++)if(visited[i]==0){printf("\n第%dn",++count);}voidTraver(AdjListg,vertype//圖g以鄰接表為結(jié)構(gòu)，算法從頂點(diǎn)v開始實(shí)現(xiàn)非遞歸深度優(yōu)先遍歷{structarc*stack[];visited[v]=1；printf(v);//輸出頂點(diǎn)vtop=0;p=g[v].firstarc;stack[++top]=p;while(top>0||p!=null){whileif(p&&visited[p->adjvex])p=p-else{printf(p->adjvex);visited[p->adjvex]=1;stack[++top]=p;p=g[p-if(top>0){p=stack[top--];p=p->next;}//while是for(vi=1;vi<=n;vi++)if(!visited[vi])（３）void{i=GraphLocateVertex(g,v);//定位頂點(diǎn)visited[i]=1;printf(v); while{if(visited[p->adjvex]==0)dfs(g[p->adjvex].vertex);voidtraver({for(i=1;i<=n;i++)visited[i]=0;//數(shù)組是全局變量初始化forif(visited[GraphLocateVertex(g，vi)]==0)PROCdfs(g:AdjList,TYPEstack=ARRAY[1..n]OFarcptr;ns:stack;top:integer;top:=0write(v0:4);WHILE(top>0||p!=NIL)DOBEGINWHILE(p!=NIL)IF(visited[p^.adjvex]=1)THENp:=p^.next;//的鄰接點(diǎn)ELSEBEGINw:=p^.adjvex;visited[w]:=1;top:=top+1;s[top]:=p;p:=g[w].firstarc;ENDIF(top>0)THENBEGINp:=s[top];top:=top-1;p:=p^.nextdfs（20-22voidTraver({for(i=1;i<=nodes(g);i++)visited[i]=0;//visitedforif(visied[i]==0){printf("(");dfs(i);printfvoidvisit(vertype voidinitqueue(vertypeQ[]) voidenqueue(vertypeQ[],v) //頂點(diǎn)v入隊(duì)列Ｑ。vertypedelqueue(vertypeQ[]) emptyQ) vertypefirstadj(graphg,vertypev)/gvvertypenextadj(graphg,vertypev,vertypewgvwvoidbfs(graphg,vertypeinitqueue(Q);enqueue(Q,v0);//v0while{v=delqueue(Q);//隊(duì)頭元素出隊(duì)列。w=firstadj(g,v);vwhile(w!=0)//w!=0表示w{if(visited[w]==0)//若鄰接點(diǎn)未{visit(w);visited[w]=1;enqueue(Q,w);}//ifw=nextadj(g,v,w);//求下一個(gè)鄰接點(diǎn)。}//whilevoidTraver(){for(i=1;i<=n;i++)visited[i]=0;for(i=1;i<=n;i++)if(visited[i]==0) NODES(G)path，pathvisitednum，均是全局變量，都已初始化。void{visited[v0]=1;if(num==nodes(G{for(i=1;i<=num;i++)printf("%3d",path[i]);printf("\n");

while(p){if(visited[p->adjvex]==0)SPathdfs(p->adjvex);p=p->next;visited[v0]=0;num--;//取消標(biāo)記，使該頂點(diǎn)可重新使用voidAllSPdfs(AdjListg,vertypeu,vertype{inttop=0,s[];s[++top]=u;visited[u]=1;while(top>0||p){p=g[s[top]].firstarc;while(p!=null&&visited[p->adjvex]==1)p=p->next;//下一

if(p==null)topelsei=p->adjvex;（編號(hào)if(i==v)uv printf(elsevisited[i]=1;s[++top]=i;else}//else}//題（1）[題目分析]D_BFS，只是用棧代替隊(duì)列，入出隊(duì)列改為入出棧。查某頂voidD_BFS(AdjListg,vertypeints[top=0;for(i=1,i<=n;i++)//對(duì)ngD_搜索。if(visited[i]==0){s[++top]=i;visited[i]=1;printf("%3d",i);while(top>0){i=s[top--];//退棧p=g[i].firstarc;while(p!=null){j=p-if(visited[j]==0)//未的鄰接點(diǎn)并入棧1 4751 475}（2）D_搜索序列：，生成樹如圖：voidAdjust(AdjMatrixg1,AdjMatrix的圖以鄰接矩陣g2。{typedefstructintvertex,out,countnodenodev[]; intc[]; for {v[i].vertex=i;v[i].out=0;v[i].count=1; for(i=1;i<=n;i++) for(j=1;j<=n;j++)v[i].out+=g1[i][j]; for(j=i-1;j>=1;j--if(v[i].count<=v[j].count)v[i].count++;elsefor(i=1;i<=n;i++)i,j>i>jjfor for(i=n;i>=2;ivv[i].countcountcfor(j=i-1;j>=1;j--if(v[i].count<v[j].count)c[j]++;elsefor(i=1;i<=n;i++)v[i].count=c[icountfor(i=1;i<=n;i++)for(j=1;j<=n;j++)二部 非二部intBPGraph(AdjMatrix{ints[（12intf=0,r,visited[];//f和r分別是隊(duì)列的頭尾指針,visited[]是數(shù)Q[1]=1;r=1s[1]=11{v=Q[++f];if(s[v]==1)jh=2elsejh=1;/vif{visited[v]=1;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);}//非二部圖}//ifreturn(1);n-1voidSpnTree(AdjList{typedefstruct{inti,j,w}node;nodeedge[];scanf"%d%d",&e,&n)for scanf("%d%d%d",&edge[i].i,&edge[i].jfor {edge[0]=edge[i];j=i-while(edge[j].w<edge[0].w)edge[j+1]=edge[j--];edge[j+1]=edge[0];}//fork=1;while {if(connect(k))k{edge[k].w=0;egedge[k]0k++;edgewn-1中的邊結(jié)點(diǎn)的定義：structnode{intadjvex,weight;structnode*next;}p;voidShortest_Dijkstra(AdjListcost,vertype{intdist[],s[];//dist，sfor(i=1;i<=n;i+{dist[i]=INFINITY;s[i]=0;，INFINITYwhile(p){dist[p->adjvex]=p->weight;p=p-for(i=1;i<n;i+uforif(s[j]==0&&dist[j]<mindis){u=j;mindis=dist[j];}//if uwhile(p)v0if(s[j]==0&&dist[j]>dist[u]+p->weight)dist[j]=dist[u]+p->weight;}}//forvoidShortPath_FLOYD(AdjMatrix{AdjMatrixlength;length[i][jvivjforfor(j=1;j<=n;j++)length[i][j]=g[i][j];for(k=1;k<=n;k++)for(i=1;i<=n;i++)for(j=1;j<=n;j++)ifnnn（村莊）就voidHospital(AdjMatrixw,int{for(k=1;k<=n;k++) for(i=1;i<=n;i++)forif(w[i][k]+w[k][j]<w[i][j])w[i][j]=w[i][k]+w[k][j]; mfor for(j=1;j<=n;ji（1<=i<=n）到其它村莊的最長(zhǎng)路徑。if(w[i][j]>s)s=w[i][j];if(s<=m)m=s;k=i;}//在最長(zhǎng)路徑中，取最短的一條。m，k9，9。這幾個(gè)最大數(shù)中最小者為6，故醫(yī)院應(yīng)建在第三個(gè)村莊中,離醫(yī)院最遠(yuǎn)的村莊到醫(yī)院6。 第33，11min=MAXINTk=1;//kfor{m=0for(i=1;i<=n;i++)if(min>mmin=m v0v0最短路徑長(zhǎng)度為K的頂點(diǎn)均在第K+1層?？捎藐?duì)列存放頂點(diǎn)，將遍歷頂點(diǎn)的操作改frlevelvoidbfs_K(graphg,intv0{intQ[];//Qintf=0,r=0,t=0;//fr，tintlevel=0,flag=0;//層數(shù)和成功標(biāo)記visited[v0]=1v0Q[++r]=v0;t=r;level=1;v0while(f<r&&level<=K+1)while //w!=0{if{Q[++r]=w;visited[w]=1;/if(level==K+1){printfv0最短路徑為k的頂點(diǎn)%d",w);w=GraphNextAdj(g,v,w);if(f==t){level++；t=rt}//while(f<r&&if(flag==0)printf(v0%dQueueInit(Q1)QueueInit(Q2);//Q1Q2visited[v0]=1;//數(shù)組初始化，置v0被標(biāo)記。level=1;flag=0KQueueIn(Q1,v0);QueueIn(Q2,level);while(!empty(Q1)&&level<=K+1){v=QueueOut(Q1);level=QueueOut(Q2);//頂點(diǎn)和層數(shù)出隊(duì)。while(w!=0){if(visited[w]==0)if(level==K+1){printf("v0K%d\n",w);visited[w]=1flag=1QueueIn(Q1,w);QueueIn(Q2,level+1);ifw=GraphNextAdj(g,v}//while(!empty(Q1)&&if(flag==0)printf(v0%dintdfs(Graphg,vertypeparent,vertypechild,int{current_len=len;maxlen=len;v=GraphFirstAdj(g,child);while(v!=0)//鄰接點(diǎn)存在。if{len=len+length(g,child,c);dfs(g,child,v,len);if(len>maxlen)maxlen=len;v=GraphNextAdj(g,child,v);len=current_len;}//ifintFind_Diamenter(Graph{maxlen1=0;maxlen2=0len=0;///深度優(yōu)先生成樹根到某葉結(jié)點(diǎn)間的距離 while(w!=0)//鄰接點(diǎn)存在。{len=length(g,1if(len>maxlen1)maxlen2=maxlen1;maxlen1=len;}elseif(len>maxlen2)maxlen2=len;w=GraphNextAdj(g,1,w)1printf(gd\n",maxlen1+maxlen2);算法主要過程是對(duì)圖進(jìn)行深度優(yōu)先遍歷。若以鄰接表為結(jié)構(gòu)，則時(shí)間復(fù)雜度O(n+e)voidFLOYD_PXD(AdjMatrix{AdjMatrixw=g; //將帶權(quán)鄰接矩陣到w。for(k=1;k<=n;k++) for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(w[i][j]>w[i][k]+w[k][j]) forfor(i=1;i<=n;i++)if(w[i][j]>s)s=w[i][j];if(s<dist){dist=s;v=j;PROCbfs_Longest(g://求以鄰接表表示的有向無環(huán)圖g的各個(gè)頂點(diǎn)的最長(zhǎng)路徑長(zhǎng)度。有關(guān)變量已在visited:ARRAY[1..n]OFinteger;//數(shù)組Q:ARRAY[1..n]OFinteger; //f,r是隊(duì)頭隊(duì)尾指針，t記為當(dāng)前隊(duì)尾，level層數(shù)。FORi:=1TOnDO [visited[1..n]:=0;f:=0;level:=0;//初始化。WHILE(f<r)[f:=f+1;v:=Q[f]; WHILE(p<>NIL)[j:=p^adjvex;IFvisited[j]=0THEN[visited[j]:=1;r:=r+1;Q[r]:=j;]IFf=tTHEN[level:=level+1t:=r;t]//WHILE點(diǎn)的雙息，源點(diǎn)為根，無雙親，向量中元素值用-1表示。voidShortest_PTree(AdjMatrixG,vertype

intp[] for{d[i]=G[v0][i];if(d[i]<MAXINT)p[i]=v0;//MAXINT，v0i（雙親elsep[i]=-1; s[v0]=1;d[v0]=0;p[v0]=-

forforif(s[j]==0&&d[j]<mindis)u=jmindis=d[j];} ufor if(s[j]==0&&d[j]>d[