《數(shù)據(jù)結構》習題及答案 袁凌 - 第6-9章

第六章一、選擇題圖G為為。數(shù) 當圖G數(shù) 有5。有為4為為3為為2的為過。將n點e。。路 序 圖為。圖有9的動a5。6 8 圖點1。圖點1。序 拉 圖用點A。二、填空題有n個頂點的強連通圖至少有n條弧。有n個頂點的無向圖最多n(n-1)/2條邊。在有向圖的鄰接矩陣中，每一行包含的“1”的個數(shù)為對應頂點的__出度_____。n個頂點e條邊的有向圖采用鄰接表存儲，求某結點度的算法時間復雜度為O(n)。設有一個稀疏圖，則采用鄰接表存儲比較節(jié)省存儲空間。十字鏈表適用于有向圖（網(wǎng)），鄰接多重表適用于無向圖（網(wǎng)）。對n個頂點e條邊的無向連通圖進行深度優(yōu)先搜索遍歷的路徑上，經(jīng)過n-1條邊。圖的深度優(yōu)先遍歷類似于二叉樹的___先根____遍歷。按廣度優(yōu)先搜索遍歷圖的算法需要借助的輔助數(shù)據(jù)結構是隊列。可以借助于圖的遍歷算法算法求出無向圖的所有連通分量。Prim算法適用于稠密圖，Kruskal算法適用于稀疏圖?？梢越柚谕負渑判蛩惴ㄅ袛嘁粋€有向圖是否為DAG圖。三、問答題求解圖6.32所示有向圖的全部強連通分量答案：利用遍歷算法求出4個強連通分量已知無向圖G=（V，R），G的鄰接表如圖6.33所示。=1\*GB3①畫出該無向圖；=2\*GB3②根據(jù)該存儲結構保存的頂點和邊的次序，從頂點A出發(fā)，進行深度優(yōu)先搜索遍歷，依次寫出訪問到的頂點序列；=3\*GB3③進行廣度優(yōu)先搜索遍歷，依次寫出訪問到的頂點序列。圖6.33無向圖的鄰接表解答：=1\*GB3①=2\*GB3②ABDCEF=3\*GB3③ABCDEF簡述圖的廣度優(yōu)先搜索遍歷與二叉樹的按層遍歷的異同點。相同點：都需要借助隊列完成遍歷相異點：圖中可能存在回路，遍歷過程中可能再次到達已經(jīng)訪問過的頂點，所以需要visited數(shù)組，而二叉樹是不需要的。如圖6.34所示無向連通網(wǎng)，使用Prim算法，從頂點A出發(fā)，其最小生成樹。圖6.34無向連通網(wǎng)答案：如圖6.35所示有向網(wǎng)，試完成：=1\*GB3①使用Dijkstra算法求頂點A到其它頂點的最短路徑和長度；=2\*GB3②使用Floyed算法求每對頂點的最短路徑和長度；=3\*GB3③列出所有的拓撲排序。圖6.35有向網(wǎng)答案：=1\*GB3①源點終點最短路徑長度ABA->B3ACA->B->E20ADA->B->D31AEA->B->E11AF無無窮大=2\*GB3②ABCDEFAA->B（3）A->B->E（20）A->B->D（31）A->B->E（11）BB->E->C(17)B->D(28)B->E(8)CDD->E->C(15)D->E(6)EE->C(9)FF->C(10)F->E(8)=3\*GB3③FABDECAFBDECABFDECABDFEC試證明：=1\*GB3①如果一個有向圖的鄰角矩陣是下三角形或上三角形，則一定無回路；=2\*GB3②如果一個有向圖無回路，則通過調整頂點在頂點數(shù)組中的次序，一定能使其鄰接矩陣為下三角形或上三角形。=1\*GB3①假定鄰接矩陣為上三角形，則任意一條弧<i,j>,必滿足i<j；如果有回路，則存在頂點對序列<i1,i2><i2,i3>,….<in,i1>,滿足i<i2,i2<i3,….in<i1,產(chǎn)生矛盾，所以沒有匯通，同理下三角。=2\*GB3②如果沒有回路，則可進行拓撲排序，按拓撲排序的次序在頂點數(shù)組中存放頂點，對于序號為i的頂點vi和序號為j的頂點vj（i<j），按拓撲排序的定義，不可能出現(xiàn)vi到vj的弧，所以可能存在弧<i,j>，但不可能存在弧<j，i>，所以得到的鄰接矩陣是上三角形。如果按逆拓撲排序的次序在頂點數(shù)組中存放頂點，則所以得到的鄰接矩陣是下三角形。試證明Floyed算法的正確性。證明：以任意兩頂點路徑上的最大序號頂點為依據(jù)，進行數(shù)學歸納法證明，按算法步驟，任意兩個頂點間的最短路徑都是可以計算出來的：對于無中間頂點的最短路徑，在由鄰接矩陣初始化時就已得到了M-1，按算法流程，這類最短路徑都是可以求出的；對于某兩個頂點的最短路徑，如果是中間頂點最大序號為0的頂點v0的最短路徑，則按算法第一步即可求出M0，即完成了這類最短路徑的計算，但對于中間頂點序號大于0的最短路徑在M0中尚未確定；假定中間頂點最大序號為k的頂點vk這類最短路徑，按算法流程，在Mk中已經(jīng)求出，但對于中間頂點序號由大于k的最短路徑在Mk中尚未確定；對于中間頂點最大序號為k+1的頂點vk+1這類最短路徑，不妨假定為vi和vj的最短路徑屬于此類，按算法步驟，在第k步后，需要考察邊<vi，vk+1>和<vk+1，vj>的和，按歸納假設，<vi，vk+1>和<vk+1，vj>兩對頂點間的中間頂點序號都不大于k，所以兩對頂點間的最短路徑已經(jīng)計算出來，將這兩段最短路徑相加，這樣在第k+1步就能把中間頂點序號最大值為k+1的最短路徑就計算出來。綜上所述，對于任意兩個頂點，vi和vj，如果最短路徑上最大的頂點序號為k（0<=k<n），則在第k步就能計算該最短路徑長度，其值在矩陣Mk中。所以Floyed算法是正確的，能求出所有的最短路徑。如圖6.36所示AOE網(wǎng)，=1\*GB3①計算各頂點事件的最早和最遲發(fā)生時間；=2\*GB3②計算各條弧表示的活動的最早和最遲開始時間。圖6.36AOE網(wǎng)=1\*GB3①頂點最早發(fā)生時間最遲發(fā)生時間V100V2319V366V422V5518V61625V788V82828V91827V10632V113333=2\*GB3②頂點最早發(fā)生時間最遲發(fā)生時間a1016a200a300a4013a5319a6615a766a822a9521a10531a111626a121625a1388a14824a152828a161827a176326②畫出鄰接表；③寫出所有的拓撲排序頂點序列；④求有向網(wǎng)N的關鍵路徑。36∞∞∞57∞∞24∞∞1012答案：=1\*GB3①=2\*GB3②=3\*GB3③A,B,C,D,E,F和A,B,C,E,D,F=4\*GB3④<A,B><B,C><C,E><E,F>試證明當無向連通網(wǎng)的任意一個環(huán)中包含邊的權值均不相同時，其最小生成樹是唯一的。證明：假定無向連通網(wǎng)N存在一個生成樹T，則任意加上一條不屬于T，但屬于N的邊后，會形成一條回路。如果在此回路中，有權值相同的兩條邊，則去掉任意一條得到一棵最小生成樹，這樣就會出現(xiàn)多棵生成樹，所以只要給定條件：所有回路中的各邊互不相同，則一定存在唯一的最小生成樹。這個條件是充分條件，但不是必要條件。四、算法設計題以鄰接矩陣作為無向圖的存儲結構，輸入圖的所有頂點和邊的信息。試完成：=1\*GB3①創(chuàng)建圖；=2\*GB3②增加、刪除一個頂點；=3\*GB3③增加、刪除一條邊。#include"stdio.h"#include"stdlib.h"#include"string.h"#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2#defineMAX_VERTEX20typedefintstatus;typedefintKeyType;typedefenum{DG,DN,UDG,UDN}GraphKind;typedefstruct{KeyTypekey;charothers[20];}VertexType;//頂點類型定義typedefstruct{VertexTypevexs[MAX_VERTEX];//VertexType為頂點類型，類似ElemTypeintarcs[MAX_VERTEX][MAX_VERTEX];intvexnum,arcnum;GraphKindkind;}MGraph;statusGraphCreate(MGraph&G,VertexTypeV[],KeyTypeVR[][3],intvexnum,intarcnum,GraphKindkind){inti,j;G.vexnum=vexnum;G.arcnum=arcnum;G.kind=kind;for(i=0;i<G.vexnum;i++)//初始化各頂點未訪問狀態(tài) G.vexs[i]=V[i];if(kind==DN||kind==UDN)for(i=0;i<G.vexnum;i++)for(j=0;j<G.vexnum;j++)G.arcs[i][j]=INFINITY;elsememset(&G.arcs[0][0],0,sizeof(G.arcs));for(intk=0;k<G.arcnum;k++){ for(i=0;i<G.vexnum;i++)//查找頂點序號 if(G.vexs[i].key==VR[k][0])break; for(j=0;j<G.vexnum;j++) if(G.vexs[j].key==VR[k][1])break; if(i>G.vexnum||j>G.vexnum)returnERROR; G.arcs[i][j]=VR[k][2]; if(kind==UDG||kind==UDN)G.arcs[j][i]=VR[k][2];}returnOK;}intInsertVex(MGraph&G,VertexTypev)//插入頂點v{if(G.vexnum==MAX_VERTEX)returnOVERFLOW;for(inti=0;i<G.vexnum;i++)//判斷是否頂點重復if(G.vexs[i].key==v.key)returnERROR;G.vexs[G.vexnum++]=v;//頂點加入頂點數(shù)組for(inti=0;i<G.vexnum;i++)//對應鄰接矩陣行列設置為0G.arcs[G.vexnum-1][i]=G.arcs[i][G.vexnum-1]=0;returnOK;}intDeleteVex(MGraph&G,KeyTypeu){inti,j,k,n=0;for(i=0;i<G.vexnum;i++)//判斷頂點是否存在if(G.vexs[i].key==u)break;if(i>=G.vexnum)returnERROR;for(j=i+1;j<G.vexnum;j++){G.vexs[j-1]=G.vexs[j];//將刪除頂點后續(xù)頂點前移for(k=0;k<G.vexnum;k++){//鄰接矩陣中，將刪除頂點對應后續(xù)行列向前移動if(G.arcs[j-1][k])n++;G.arcs[j-1][k]=G.arcs[j][k];G.arcs[k][j-1]=G.arcs[k][j];}}G.vexnum--;G.arcnum-=n;returnOK;}InsertArc(MGraph&G,KeyTypeu,KeyTypew)//插入頂點u到頂點w的弧{inti,j,k,n=0;for(i=0;i<G.vexnum;i++)//判斷頂點u是否存在，存在獲取u的位序號iif(G.vexs[i].key==u)break;for(j=0;j<G.vexnum;j++)//判斷頂點w是否存在，存在獲取w的位序號jif(G.vexs[j].key==w)break;if(i>=G.vexnum||i>=G.vexnum)returnERROR;if(!G.arcs[i][j]){G.arcs[i][j]=G.arcs[j][i]=1;G.arcnum++;}returnOK;}DeleteArc(MGraph&G,KeyTypeu,KeyTypew){inti,j,k,n=0;for(i=0;i<G.vexnum;i++)//判斷頂點u是否存在，存在獲取u的位序號iif(G.vexs[i].key==u)break;for(j=0;j<G.vexnum;j++)//判斷頂點w是否存在，存在獲取w的位序號jif(G.vexs[j].key==w)break;if(i>=G.vexnum||i>=G.vexnum)returnERROR;if(G.arcs[i][j]){G.arcs[i][j]=G.arcs[j][i]=0;G.arcnum--;}returnOK;}以鄰接多重表作為無向圖的存儲結構，重做第（1）題。typedefintKeyType;typedefenum{DG,DN,UDG,UDN}GraphKind;typedefstruct{KeyTypekey;charothers[20];}VertexType;//頂點類型定義typedefstructEBox{//表結點類型定義intivex,jvex;//邊兩端頂點位置編號boolmark;structEBox*ilink,*jlink; //下一個表結點指針}EBox;typedefstructVexNode{ //頭結點及其數(shù)組類型定義VertexTypedata; //頂點信息EBox*firstarc; //指向第一條邊結點}VexNode,AdjMList[MAX_VERTEX];typedefstruct{//鄰接表的類型定義AdjMListvertices; //頭結點數(shù)組intvexnum,arcnum; //頂點數(shù)、弧數(shù)}AMLGraph;statusGraphCreate(AMLGraph&G,VertexTypeV[],KeyTypeVR[][3],\intvexnum,intarcnum){ G.vexnum=vexnum;G.arcnum=arcnum;for(inti=0;i<G.vexnum;i++)//初始化各頭結點數(shù)組{for(intj=0;j<i;j++)if(G.vertices[j].data.key==V[i].key)returnERROR;//關鍵字有重復G.vertices[i].data=V[i];G.vertices[i].firstarc=NULL;}for(inti,j,k=0;k<G.arcnum;k++){for(i=0;i<G.vexnum;i++)//查找頂點序號if(G.vertices[i].data.key==VR[k][0])break;for(j=0;j<G.vexnum;j++)if(G.vertices[j].data.key==VR[k][1])break;if(i>G.vexnum||j>G.vexnum)returnERROR;EBox*p=(EBox*)malloc(sizeof(EBox));p->ivex=i;p->jvex=j;p->ilink=G.vertices[i].firstarc;p->jlink=G.vertices[j].firstarc;G.vertices[i].firstarc=G.vertices[j].firstarc=p;}returnOK;}statusInsertVex(AMLGraph&G,VertexTypev)//插入頂點v{G.vertices[G.vexnum].data=v;G.vertices[G.vexnum++].firstarc=NULL;returnOK;}statusDeleteVex(AMLGraph&G,KeyTypeu){inti,j;for(i=0;i<G.vexnum;i++)if(G.vertices[i].data.key==u)break;if(i>=G.vexnum)returnERROR;for(EBox*q,*p=G.vertices[i].firstarc;p;p=q){j=p->ivex==i?p->jvex:p->ivex;q=p->ivex==i?p->ilink:p->jlink;//q指向下一條關聯(lián)i的邊EBox*p1=NULL,*p2=G.vertices[j].firstarc,*p3=p2->ivex==j?p2->ilink:p2->jlink;while(p2!=p){p1=p2;p2=p3;p3=p3->ivex==j?p3->ilink:p3->jlink;}if(p1==NULL)G.vertices[j].firstarc=p3;elseif(p1->ivex==j)p1->ilink=p3;elsep1->jlink=p3;free(p);G.arcnum--;}for(j=i+1;j<G.vexnum;j++){EBox*q,*p=G.vertices[j].firstarc;while(p){q=p->ivex==j?p->ilink:p->jlink;if(p->ivex==j)p->ivex--;elsep->jvex--;p=q;}}for(j=i+1;j<G.vexnum;j++)G.vertices[j-1]=G.vertices[j];G.vexnum--;returnOK;}statusInsertArc(AMLGraph&G,KeyTypeu,KeyTypew)//插入頂點u到頂點w的弧{inti,j;for(i=0;i<G.vexnum;i++)if(G.vertices[i].data.key==u)break;for(j=0;j<G.vexnum;j++)if(G.vertices[j].data.key==w)break;if(i>=G.vexnum||j>=G.vexnum)returnERROR;EBox*p=(EBox*)malloc(sizeof(EBox));p->ivex=i;p->jvex=j;p->ilink=G.vertices[i].firstarc;p->jlink=G.vertices[j].firstarc;G.vertices[i].firstarc=G.vertices[j].firstarc=p;G.arcnum++;returnOK;}statusDeleteArc(AMLGraph&G,KeyTypeu,KeyTypew){inti,j;for(i=0;i<G.vexnum;i++)if(G.vertices[i].data.key==u)break;for(j=0;j<G.vexnum;j++)if(G.vertices[j].data.key==w)break;if(i>=G.vexnum||j>=G.vexnum)returnERROR;EBox*p1=NULL,*p2=G.vertices[i].firstarc,*p3=p2->ivex==i?p2->ilink:p2->jlink;while(p2->ivex!=j&&p2->jvex!=j){p1=p2;p2=p3;p3=p3->ivex==i?p3->ilink:p3->jlink;}if(p1==NULL)G.vertices[i].firstarc=p3;elseif(p1->ivex==i)p1->ilink=p3;elsep1->jlink=p3;p1=NULL,p2=G.vertices[j].firstarc,p3=p2->ivex==j?p2->ilink:p2->jlink;while(p2->ivex!=i&&p2->jvex!=i){p1=p2;p2=p3;p3=p3->ivex==j?p3->ilink:p3->jlink;}if(p1==NULL)G.vertices[j].firstarc=p3;elseif(p1->ivex==j)p1->ilink=p3;elsep1->jlink=p3;G.arcnum--;returnOK;}以十字鏈表作為有向網(wǎng)的存儲結構，輸入圖的所有頂點和?。ò瑱嘀担┑男畔?。試完成：=1\*GB3①創(chuàng)建圖；=2\*GB3②增加、刪除一個頂點；=3\*GB3③增加、刪除一條弧。statusGraphCreate(OLGraph&G,VertexTypeV[],KeyTypeVR[][3],\intvexnum,intarcnum){ G.vexnum=vexnum;G.arcnum=arcnum;for(inti=0;i<G.vexnum;i++)//初始化各頭結點數(shù)組{for(intj=0;j<i;j++)if(G.xlist[j].data.key==V[i].key)returnERROR;//關鍵字有重復G.xlist[i].data=V[i];G.xlist[i].firstin=G.xlist[i].firstout=NULL;}for(inti,j,k=0;k<G.arcnum;k++){for(i=0;i<G.vexnum;i++)//查找頂點序號if(G.xlist[i].data.key==VR[k][0])break;for(j=0;j<G.vexnum;j++)if(G.xlist[j].data.key==VR[k][1])break;if(i>G.vexnum||j>G.vexnum)returnERROR;ArcBox*p=(ArcBox*)malloc(sizeof(ArcBox));p->tailvex=i;p->headvex=j;ArcBox*p1=NULL,*p2=G.xlist[i].firstout;while(p2&&j>p2->headvex)p1=p2,p2=p2->tlink;if(p1==NULL)G.xlist[i].firstout=p;elsep1->tlink=p;p->tlink=p2;p1=NULL,p2=G.xlist[j].firstin;while(p2&&i>p2->tailvex)p1=p2,p2=p2->hlink;if(p1==NULL)G.xlist[j].firstin=p;elsep1->hlink=p;p->hlink=p2;}returnOK;}statusInsertVex(OLGraph&G,VertexTypev)//插入頂點v{G.xlist[G.vexnum].data=v;G.xlist[G.vexnum].firstin=G.xlist[G.vexnum].firstout=NULL;G.vexnum++;returnOK;}statusDeleteVex(OLGraph&G,KeyTypeu){inti,j;for(i=0;i<G.vexnum;i++)if(G.xlist[i].data.key==u)break;if(i>=G.vexnum)returnERROR;for(ArcBox*q,*p=G.xlist[i].firstout;p;p=q){//刪除以u為狐尾的弧q=p->tlink;//q指向下一條以u為狐尾的弧ArcBox*p1=NULL,*p2=G.xlist[p->headvex].firstin;while(p2->tailvex!=i){p1=p2;p2=p2->hlink;}if(p1==NULL)G.xlist[p->headvex].firstin=p2->hlink;elsep1->hlink=p2->hlink;free(p);G.arcnum--;}for(ArcBox*q,*p=G.xlist[i].firstin;p;p=q){//刪除以u為狐頭的弧q=p->hlink;//q指向下一條以u為狐尾的弧ArcBox*p1=NULL,*p2=G.xlist[p->tailvex].firstout;while(p2->headvex!=i){p1=p2;p2=p2->tlink;}if(p1==NULL)G.xlist[p->tailvex].firstout=p2->tlink;elsep1->tlink=p2->tlink;free(p);G.arcnum--;}for(j=i+1;j<G.vexnum;j++)G.xlist[j-1]=G.xlist[j];G.vexnum--;for(j=0;j<G.vexnum;j++){ArcBox*p=G.xlist[j].firstout;while(p){//序號大于i的減一if(p->headvex>i)p->headvex--;if(p->tailvex>i)p->tailvex--;p=p->tlink;}}returnOK;}statusInsertArc(OLGraph&G,KeyTypeu,KeyTypew)//插入頂點u到頂點w的弧{inti,j;for(i=0;i<G.vexnum;i++)if(G.xlist[i].data.key==u)break;for(j=0;j<G.vexnum;j++)if(G.xlist[j].data.key==w)break;if(i>=G.vexnum||j>=G.vexnum)returnERROR;ArcBox*p=(ArcBox*)malloc(sizeof(ArcBox));p->tailvex=i;p->headvex=j;ArcBox*p1=NULL,*p2=G.xlist[i].firstout;while(p2&&j>p2->headvex)p1=p2,p2=p2->tlink;if(p1==NULL)G.xlist[i].firstout=p;elsep1->tlink=p;p->tlink=p2;p1=NULL,p2=G.xlist[j].firstin;while(p2&&i>p2->tailvex)p1=p2,p2=p2->hlink;if(p1==NULL)G.xlist[j].firstin=p;elsep1->hlink=p;p->hlink=p2;G.arcnum++;returnOK;}statusDeleteArc(OLGraph&G,KeyTypeu,KeyTypew){inti,j;for(i=0;i<G.vexnum;i++)if(G.xlist[i].data.key==u)break;for(j=0;j<G.vexnum;j++)if(G.xlist[j].data.key==w)break;if(i>=G.vexnum||j>=G.vexnum)returnERROR;ArcBox*p1=NULL,*p2=G.xlist[i].firstout;while(p2->headvex!=j){p1=p2;p2=p2->tlink;}if(p1==NULL)G.xlist[i].firstout=p2->tlink;elsep1->tlink=p2->tlink;p1=NULL,p2=G.xlist[j].firstin;while(p2->tailvex!=i){p1=p2;p2=p2->hlink;}if(p1==NULL)G.xlist[j].firstin=p2->hlink;elsep1->hlink=p2->hlink;free(p2);G.arcnum--;returnOK;}以鄰接矩陣作為無向圖的存儲結構，試設計算法實現(xiàn)，輸入起始和終點，求起始到終點的最短路徑和長度。算法思想：利用圖的廣度優(yōu)先遍歷算法，從起始點開始做深度優(yōu)先遍歷，當遇到終點時結束，輸出對應最短路徑，一次廣度優(yōu)先遍歷結束，沒訪問到終點，表示無路徑。為了能輸出對應最短路徑的頂點序列，在遍歷中維護了一個棧，記錄每次訪問時，對應邊的起始起始、終止的2個頂點序號，一旦遇到終點，分析該棧即可得到最短路徑頂點序列。voidBFSTraverse(MGraphG,intbegin,intend){intQ[100],f,r,flag=1,u,length=0;struct{intv[30][2],top;}s;//棧s存放訪問時經(jīng)過的邊頂點序號對boolvisited[MAX_VERTEX];for(u=0;u<G.vexnum;u++) visited[u]=false;f=r=0;//隊列Q初始化s.top=0;visited[begin]=true;Q[r++]=begin;//v入隊列Q;while(f!=r&&flag){u=Q[f++];//DeQueue(Q,u);for(intw=FirstAdjVex(G,u);w>=0;w=NextAdjVex(G,u,w))if(!visited[w]){visited[w]=true;Q[r++]=w;//EnQueue(Q,w);}s.v[s.top][0]=u;//邊的起點s.v[s.top++][1]=w;//邊的終點if(w==end){flag=0;break;}}}if(flag){printf("兩個頂點不可達\n");return;}u=s.v[--s.top][0];//u為最短路徑終點的前驅頂點序號printf("最短路徑:(%d,%s)",G.vexs[end].key,G.vexs[end].others);length=1;while(s.top){if(u==s.v[s.top-1][1]){printf("<--(%d,%s)",G.vexs[u].key,G.vexs[u].others);u=s.v[s.top-1][0];//修改u為最短路徑為前驅頂點序號length++;}s.top--;}printf("<--(%d,%s)\n路徑長度=%d\n",G.vexs[begin].key,G.vexs[begin].others,length);}假定以鄰接矩陣作為無向圖的存儲結構，試求出該無向圖的全部連通分量并輸出各連通分量的頂點集合與邊集合。算法思想：借助于遍歷算法（深度和廣度優(yōu)先遍歷都可以），每次遍歷訪問到的頂點集合與其該集合中的各頂點間關系構成一個連通分量。voidBFSTraverse(MGraphG){intQ[100],f,r,nums=0;boolvisited[MAX_VERTEX];struct{intv[30],length;}SList;//順序表存放連通分量的頂點集合for(intv=0;v<G.vexnum;v++) visited[v]=false;f=r=0; for(intv=0;v<G.vexnum;v++)//按頂點位置序號依次選擇頂點if(!visited[v])//遇到未訪問過的頂點開始遍歷{ visited[v]=true;Q[r++]=v;//EnQueue(Q,v);SList.length=0;SList.v[SList.length++]=v; while(f!=r){ intu=Q[f++];//DeQueue(Q,u); for(intw=FirstAdjVex(G,u);w>=0;w=NextAdjVex(G,u,w)) if(!visited[w]) {visited[w]=true;SList.v[SList.length++]=w;printf("%s",G.vexs[w].others);Q[r++]=w;//EnQueue(Q,w);} } } nums++; MGraphG1;G1.kind=G.kind;G1.vexnum=SList.length;G1.arcnum=0; for(inti=0;i<SList.length;i++){G1.vexs[i]=G.vexs[SList.v[i]];for(intj=i;j<SList.length;j++){inti1=SList.v[i],j1=SList.v[j];G1.arcs[i][j]=G.arcs[i1][j1];G1.arcs[i][j]=G.arcs[i1][j1];G1.arcnum++;}}printf("\n\n第%d個連通分量：\n頂點序列：",nums); for(inti=0;i<G1.vexnum;i++)printf("(%d%s)",G1.vexs[i].key,G1.vexs[i].others);printf("\n關系序列："); for(inti=0;i<G1.vexnum;i++)for(intj=i+1;j<G1.vexnum;j++)if(G1.arcs[i][j])printf("(%d%s,%d%s)",G1.vexs[i].key,G1.vexs[i].others,\G1.vexs[j].key,G1.vexs[j].others);}}假定以鄰接表作為無向圖的存儲結構，試求出頂點v出發(fā)，經(jīng)過一個長度為k的簡單路徑到達的頂點集合。算法思想：利用圖的深度優(yōu)先遍歷算法，增加一個長度的參數(shù)，以開始頂點出發(fā)，調用DFS進行一次深度優(yōu)先遍歷，每次遞歸調用時長度減一，當長度為0時，，并且該頂點不在結果集合中時，將當前訪問的頂點顯示出來。voidDFSTraverse(ALGraphG,intbegin,intlength){boolvisited[MAX_VERTEX];booldisplayed[MAX_VERTEX]; for(intv=0;v<G.vexnum;v++)//初始化各頂點未訪問狀態(tài) visited[v]=displayed[v]=false; DFS(G,begin,visited,displayed,length);}voidDFS(ALGraphG,intv,boolvisited[],booldisplayed[],intlength){visited[v]=true;//標注訪問過的標記if(!length&&!displayed[v]){printf("%d%s\n",G.vertices[v].data.key,G.vertices[v].data.others);displayed[v]=true;return;} for(ArcNode*p=G.vertices[v].firstarc;p;p=p->nextarc)if(!visited[p->adjvex])//處理所有未訪問的鄰接頂點{DFS(G,p->adjvex,visited,displayed,length-1);visited[p->adjvex]=false;}}假定以鄰接表作為有向圖的存儲結構，給定一個頂點v，判斷是否有含頂點v的簡單回路，是則輸出一條包含該頂點的回路。算法思想：從頂點v開始進行一次深度優(yōu)先遍歷，調用遞歸函數(shù)DFS，每次訪問到一個頂點，將頂點進棧，當遍歷中，如果當前訪問到的結點鄰接頂點有v，則找到回路，根據(jù)棧進行輸出回路結點。typedefstructSTACK{intv[30],top;}STACK;statusDFS(ALGraphG,intv,boolvisited[],STACK&s);voidDFSTraverse(ALGraphG,intv){boolvisited[MAX_VERTEX];STACKs;s.v[0]=v,s.top=1; for(intv=0;v<G.vexnum;v++) visited[v]=false; if(DFS(G,v,visited,s))for(inti=0;i<s.top;i++)printf("-(%d,%s)",G.vertices[s.v[i]].data.key,G.vertices[s.v[i]].data.others);elseprintf("無回路");}statusDFS(ALGraphG,intv,boolvisited[],STACK&s){visited[v]=true; for(ArcNode*p=G.vertices[v].firstarc;p;p=p->nextarc){s.v[s.top++]=p->adjvex;if(p->adjvex==s.v[0])returntrue;if(!visited[p->adjvex]){if(DFS(G,p->adjvex,visited,s))returntrue;visited[p->adjvex]=false;} s.top--;}returnfalse;}

第七章一、選擇題1．【2019統(tǒng)考真題】選擇一個排序算法時，除考慮算法的時空效率外，還需要考慮的是____。Ⅰ．數(shù)據(jù)的規(guī)模 Ⅱ．數(shù)據(jù)的存儲方式Ⅲ．算法的穩(wěn)定性 Ⅳ．數(shù)據(jù)的初始狀態(tài)A．僅ⅢB．僅Ⅰ、ⅡC．僅Ⅱ、Ⅲ、ⅣD．Ⅰ、Ⅱ、Ⅲ、Ⅳ答案：D2．下列排序算法中平均復雜度為O(nlogn)且穩(wěn)定的是______。A．插入排序B．歸并排序C．堆排序D．快速排序答案：B解釋：插入排序平均復雜度不為O(nlogn)，堆排序和快速排序不穩(wěn)定。3．【2019統(tǒng)考真題】排序過程中，對尚未確定最終位置的所有元素進行一遍處理稱為“趟”。下列序列中可能是快速排序算法第二趟結果的是______。A．5,2,16,12,28,60,32,72B．2,16,5,28,12,60,32,72C．2,12,16,5,28,32,72,60D．5,2,12,28,16,32,72,60答案：ABC解釋：每一趟快排，至少確認一個元素的最終位置。序列最終位置是：2,5,12,16,28,32,60,72，而選項中正確的位置有：A．5,2,16,12,28,60,32,72B．2,16,5,28,12,60,32,72C．2,12,16,5,28,32,72,60D．5,2,12,28,16,32,72,60第一趟排序，確定一個元素位置第二趟排序，有確定一個或者兩個元素位置當?shù)谝惶嗽卮_認的位置為最左或最右時，第二趟排序只能確認一個位置（A、B選項情況）當?shù)谝惶嗽卮_認不是最左或最右時，第二趟能確認2個位置（C選項情況）D選項：第一趟確認的元素不管是12還是32，第二次都應該能確認2個位置，兩趟下來共能確認3個元素，而D選項不符，所以錯誤。4．【2009統(tǒng)考真題】已知關鍵字序列5,8,12,19,28,20,15,22是小根堆（最小堆），插入關鍵字3，調整后得到的小根堆是______。A．3,5,12,8,28,20,15,22,19B．3,5,12,19,20,15,22,8,28C．3,8,12,5,20,15,22,28,19D．3,12,5,8,28,20,15,22,19答案：A解釋：插入3之后（5,8,12,19,28,20,15,22,3）的置換順序3--19，3--8，3--5。5.【2009統(tǒng)考真題】若數(shù)據(jù)元素序列11,12,13,7,8,9,23,4,5是采用下列排序算法之一得到第二趟排序后的結果，則該排序算法只能是______。A．冒泡排序B．插入排序C．選擇排序D．2路歸并排序答案：B解釋：對于冒泡排序和選擇排序，每一趟都能確定一個元素的最終位置，而題目中，前2個元素和后2個元素均不是最小或最大的2個元素并按序排列。選項D中的2路歸并排序，第一趟排序結束都可以得到若干個有序子序列，而此時的序列中并沒有兩兩元素有序排列。插入排序在每趟排序后能確定前面的若干元素是有序的，而此時第二趟排序后，序列的前三個元素是有序的，符合其特征。6.【2010統(tǒng)考真題】對一組數(shù)據(jù)(2,12,16,88,5,10)進行排序，若前3趟排序結果如下：第一趟排序結果為2,12,16,5,10,88，第二趟排序結果為2,12,5,10,16,88，第三趟排序結果為2,5,10,12,16,88，則采用的排序算法可能是______。A．冒泡排序B．希爾排序C．歸并排序D．基數(shù)排序答案：A解釋：冒泡排序每一趟都確定一個元素的最終位置，前三趟依次確定了序列倒數(shù)三位的元素。7.【2012統(tǒng)考真題】下列排序算法中，每一趟排序結束都至少能夠確定一個元素最終位置的算法是______。Ⅰ．簡單選擇排序Ⅱ．希爾排序Ⅲ．快速排序Ⅳ．堆排序Ⅴ．2路歸并排序A．僅Ⅰ、Ⅲ、ⅣB．僅Ⅰ、Ⅲ、ⅤC．僅Ⅱ、Ⅲ、ⅣD．僅Ⅲ、Ⅳ、Ⅴ答案：A解釋：每趟排序至少能確定一個元素最終位置的排序算法主要是兩類：選擇排序算法（簡單選擇、堆排序）和交換排序算法（冒泡排序、快速排序）。8.【2012統(tǒng)考真題】對一個待排序序列分別進行折半插入排序和直接插入排序，兩者之間可能的不同之處是______。A．排序的總趟數(shù)B．元素的移動次數(shù)C．使用輔助空間的數(shù)量D．元素之間的比較次數(shù)答案：D解釋：折半插入排序基本思想和直接插入排序一樣，區(qū)別在于尋找插入位置的方法不同，折半插入排序采用折半查找法來尋找插入位置。9.【2013統(tǒng)考真題】對給定的關鍵字序列110,119,007,911,114,120,122進行基數(shù)排序，則第二趟分配、收集后得到的關鍵字序列是______。A．007,110,119,114,911,120,122B．007,110,119,114,911,122,120C．007,110,911,114,119,120,122D．110,120,911,122,114,007,119答案：C解釋：第一趟按照個位排，得到：110,120,911,122,114,007,119。第二趟按照十位排，得到：007,110,911,114,119,120,122。10.【2013統(tǒng)考真題】用希爾排序算法對一個數(shù)據(jù)序列進行排序時，若第一趟排序結果為9,1,4,13,7,8,20,23,15，則該趟排序采用的增量（間隔）可能是______。A．2B．3C．4D．5答案：B解釋：假如增量為2，整個序列分為2組，[9,4,7,20,15]和[1,13,8,23]，可以看出這兩組元素不是有序的，因此增量不為2。同理代入其他選項，得到答案為B。11．在下列排序算法中，時間復雜度與待排序序列初始狀態(tài)無關的算法是______A．插入排序B．堆排序C．冒泡排序D．歸并排序答案：BD解釋：堆排序和歸并排序在最好情況、最壞情況以及平均情況下的時間復雜度均為O(nlogn)。12.【2013統(tǒng)考真題】下列選項中，不可能是快速排序算法第二趟排序結果的是______。A．2,3,5,4,6,7,9B．2,7,5,6,4,3,9C．3,2,5,4,7,6,9D．4,2,3,5,7,6,9答案：C解釋：每一趟快排，至少確認一個元素的最終位置，兩趟快排至少可以確認2個元素的最終位置。序列最終位置是：2,3,4,5,6,7,9，而選項中正確的位置有：A．2,3,5,4,6,7,9B．2,7,5,6,4,3,9C．3,2,5,4,7,6,9D．4,2,3,5,7,6,9因此，C選項不可能是第二趟快排結果。13.【2015統(tǒng)考真題】下列排序算法中，元素的移動次數(shù)與關鍵字的初始排列次序無關的是______。A．直接插入排序B．冒泡排序C．基數(shù)排序D．快速排序答案：C14．【2015統(tǒng)考真題】已知小根堆為8,15,10,21,34,16,12，刪除關鍵字8之后需重建堆。在此過程中，關鍵字之間的比較次數(shù)是______。A．1B．2C．3D．4答案：C解釋：刪除關鍵字8，需要將末尾的葉子結點12置換到根結點。（1）比較根結點12的兩個孩子15和10的大?。唬?）比較根結點12和它更小的孩子10的大?。▽?0和12進行交換）；（3）比較交換后結點12和它的孩子16的大?。ú话l(fā)生交換，完成堆重建）。15．堆是一種有用的數(shù)據(jù)結構，在以下排序序列中小根堆是______。A．16,72,31,23,94,53B．94,53,31,72,16,53C．16,53,23,94,31,72D．16,31,23,94,53,72答案：D 16.【2015統(tǒng)考真題】希爾排序算法的組內(nèi)排序采用的是______。A．直接插入排序B．折半插入排序C．快速排序D．歸并排序答案：A17．對數(shù)組存儲線性表(16,15,32,11,6,30)用快速排序算法進行由小到大排序，若排序下標范圍為0～5，選擇元素16作為支點，調用一趟快速排序算法后，元素16在數(shù)組中的下標位置為______。A．1B．2C．3D．4答案：C解釋：一趟快速排序算法后，元素16左邊有3個小于它的元素（分別對應數(shù)組下標0,1,2），所以元素16在數(shù)組中的下標位置為3。18.【2016統(tǒng)考真題】對10TB的數(shù)據(jù)文件進行排序，應使用的方法是______。A．希爾排序B．堆排序C．快速排序D．歸并排序答案：D解釋：對于10TB的海量數(shù)據(jù)，數(shù)據(jù)不可能一次全部載入內(nèi)存，傳統(tǒng)的排序方法就不適用了，需要用到外排序的方法。19.【2017統(tǒng)考真題】在內(nèi)部排序時，若選擇歸并排序而沒有選擇插入排序，則可能的理由是______。Ⅰ．歸并排序的程序代碼更短Ⅱ．歸并排序的占用空間更少Ⅲ．歸并排序的運行效率更高A．僅ⅡB．僅ⅢC．僅Ⅰ、ⅡD．僅Ⅰ、Ⅲ答案：B解釋：對并排序代碼量大。歸并排序的最壞情況和平均情況時間復雜度優(yōu)于插入排序。空間復雜度劣于插入排序。20．用某種排序算法對關鍵字序列(25,84,21,47,15,27,68,35,20)進行排序時，序列的變化情況如下：15,20,21,25,47,27,68,35,8415,20,21,25,35,27,47,68,8415,20,21,25,27,35,47,68,84則采用的排序算法是哪種？______A．希爾排序B．選擇排序C．快速排序D．歸并排序答案：C解釋：（1）第一步以元素25為基準，小于25的放在25的左邊，大于25的放在25的右邊，得到20,15,21,25,47,27,68,35,84；（2）第二步在25的兩邊分別進行快速排序，左邊以20為基準，右邊以47為基準，得到15,20,21,25,35,27,47,68,84；（3）第三步得到15,20,21,25,27,35,47,68,84。21.【2017統(tǒng)考真題】下列排序算法中，若將順序存儲更換為鏈式存儲，則算法的時間效率會降低的是______。Ⅰ．插入排序 Ⅱ．選擇排序 Ⅲ．冒泡排序 Ⅳ．希爾排序 Ⅴ．堆排序A．僅Ⅰ、ⅡB．僅Ⅱ、ⅢC．僅Ⅲ、ⅣD．僅Ⅳ、Ⅴ答案：D解釋：插入排序、選擇排序、起泡排序原本時間復雜度是O(n2)，更換為鏈式存儲后的時間復雜度還是O(n2)。希爾排序和堆排序都利用了順序存儲的隨機訪問特性，而鏈式存儲不支持這種性質，所以時間復雜度會增加，因此選D。22.【2018統(tǒng)考真題】對初始數(shù)據(jù)序列(8,3,9,11,2,1,4,7,5,10,6)進行希爾排序，若第一趟排序結果為(1,3,7,5,2,6,4,9,11,10,8)，第二趟排序結果為(1,2,6,4,3,7,5,8,11,10,9)，則兩趟排序采用的增量（間隔）依次是______。A．3,1B．3,2C．5,2D．5,3答案：D解釋：先看第一趟，1從最開始的5號位移動到0號位，說明第一趟增量是5，直接排除A,B。再看第二趟，2從第一趟排序結果的第4位移動到1號位，說明第二趟增量是3。23．一個元素序列為{46,79,56,38,40,84}，采用快速排序（以第一個元素為軸點）得到的結果為______。A．38,46,79,56,40,84B．38,79,56,46,40,84C．40,38,46,79,56,84D．38,46,56,79,40,84答案：C24.【2018統(tǒng)考真題】在將數(shù)據(jù)序列(6,1,5,9,8,4,7)建成大根堆時，正確的序列變化過程是______。A．6,1,7,9,8,4,5→6,9,7,1,8,4,5→9,6,7,1,8,4,5→9,8,7,1,6,4,5B．6,9,5,1,8,4,7→6,9,7,1,8,4,5→9,6,7,1,8,4,5→9,8,7,1,6,4,5C．6,9,5,1,8,4,7→9,6,5,1,8,4,7→9,6,7,1,8,4,5→9,8,7,1,6,4,5D．6,1,7,9,8,4,5→7,1,6,9,8,4,5→7,9,6,1,8,4,5→9,7,6,1,8,4,5→9,8,6,1,7,4,5答案：A25．下列排序算法中，平均時間復雜度為O(n2)的排序算法有哪些？______A．歸并排序B．插入排序C．冒泡排序D．快速排序答案：BC解釋：歸并排序和快速排序的平均時間復雜度均為O(nlogn)。二、問答題1．試證明2路歸并排序算法是穩(wěn)定的排序算法。解：在歸并排序中，如果兩個元素值相等，那么歸并的時候優(yōu)先選擇左邊的元素，這就保證了相同元素的相對位置不變，即使在不同的子數(shù)組中出現(xiàn)了相同元素也不會打亂它們的順序。因此，2路歸并排序算法是一種穩(wěn)定的排序算法。2．有如下12個整數(shù)：23,37,7,79,29,43,73,19,31,61,23,47。堆排序中，通過以下語句：for(inti=H->length/2;i>=1;i--)HeapAdjust(H,i,H->length);調用HeapAdjust()建立初始的堆。（1）畫出每次調用HeapAdjust()之后形成的堆結構圖。（2）試分析完成建立初始堆所需的時間。（3）在調用HeapAdjust()的for循環(huán)中，循環(huán)變量為什么是由length/2到1遞減，而不是由1到length/2遞增呢？解：（1）假設此堆為最小堆，編號從1開始，則每次調用HeapAdjust()后的結構圖如下所示：

（2）按最壞情況看，待建的堆為滿二叉樹，堆高為h，第k層結點最多需要向下移動h-k次，第k層最多有2k-1個結點。則最多移動次數(shù)tn=（3）在調用HeapAdjust()的for循環(huán)中，循環(huán)變量由length/2到1遞減，是從二叉樹中最后一個非葉子結點開始向前依次為每個非葉子結點向下調整。從而構建最?。ù螅┒?。從后往前遍歷，可以確保所有的子樹都是最?。ù螅┒眩?。但是循環(huán)變量由1到length/2遞增，即自頂向下選取結點進行調整，可能會導致已經(jīng)調整過的子樹被重復調整，從而降低算法的效率。因此，從后往前遍歷，是一種更常用的方法。3．高度為h的堆中，元素個數(shù)最多和最少分別為多少個？解：由于堆是一個完全二叉樹，因此，當高度為h的堆是滿二叉樹時，元素個數(shù)最多，為：2^h-1個；當堆最后一層結點個數(shù)只有一個時，元素個數(shù)最少，為：2^(h-1)個。4．使用數(shù)學歸納法證明，下列遞歸式的解是TnT解：（1）基礎步驟：遞歸式初始值n=2時，T2（2）歸納步驟：假設n=2k,k>1時，遞歸式的解成立，即T2k歸納完畢，命題得證。三、算法設計題1．【2016統(tǒng)考真題】已知由n（n≥2）個正整數(shù)構成的集合A={ak}（0≤k<n），將其劃分為兩個不相交的子集A1和A2，元素個數(shù)分別是n1和n2，A1和A2中元素之和分別為S1和S2。設計一個盡可能高效的劃分算法，滿足|n1-n2|最小且|S1-S2|最大。要求：（1）給出算法的基本設計思想。（2）根據(jù)設計思想，采用C或C++語言描述算法，關鍵之處給出注釋。（3）說明你所設計算法的平均時間復雜度和空間復雜度。解：（1）算法的基本設計思想：由題意知，將最小的n/2個元素放在A1中，其余的元素放在A2中，分組結果即可滿足題目要求。仿照快速排序的思想，基于主元將n個整數(shù)劃分為兩個子集。根據(jù)劃分后主元所在的位置i分別處理：=1\*GB3①若i=n/2，則分組完成，算法結束；=2\*GB3②若i<n/2，則主元及其之前的所有元素均屬于A1，繼續(xù)對i之后的元素進行劃分；=3\*GB3③若i>n/2，則主元及其之后的所有元素均屬于A2，繼續(xù)對i之前的元素進行劃分。（2）算法實現(xiàn)：intsetPartition(inta[],intn){intpivotkey;//主元intlow=0,low0=0,high=n-1,high0=n–1,intk=n/2;ints1=0,s2=0;//劃分出來的兩個子集各自元素和while(true){pivot=a[low];//選擇主元while(low<high)//快速排序確定主元位置{while(low<high&&a[high]>=pivotkey)--high;if(low!=high)a[low]=a[high];while(low<high&&a[low]<=pivotkey)++low;if(low!=high)a[high]=a[low];}a[low]=pivotkey;if(low==k-1)//如果是第n/2小的元素，劃分成功，結束循環(huán)break;//否則繼續(xù)劃分elseif(low<k-1)//右邊的繼續(xù)劃分{low0=+