第7章-图-自测卷解答

--第７章图自测卷解答一、单项选择题(每题1分,共１6分)(C)1.在一个图中，所有极点的度数之和等于图的边数的倍。A.1/2B.1C．２Ｄ．４（B）2.在一个有向图中,所有极点的入度之和等于所有极点的出度之和的倍。A.1/2Ｂ.1C．24（B)3.有8个结点的无向图最多有条边。A.14B.２8Ｃ.56D．112(C）４.有８个结点的无向连通图最罕有条边。A.5B.６C．７Ｄ.8（C)5.有8个结点的有向完整图有条边。A.14B.2８C.56.1１２（B)６．用毗邻表表示图进行广度优先遍历时,往常是采纳来实现算法的。A.栈B.行列C.树图（A)7.用毗邻表表示图进行深度优先遍历时，往常是采纳来实现算法的。A.栈Ｂ．行列C.树D.图(Ｃ）8.已知图的毗邻矩阵，依据算法思想，则从极点０出发按深度优先遍历的结点序列是0111101100100110001001100110101101000011011100010

A．0243156013654204231650361542D）9.已知图的毗邻矩阵同上题8,依据算法，则从极点０出发，按深度优先遍历的结点序列是A．0243156B.0135６4２Ｃ.0423１65D.０134256(B)10.已知图的毗邻矩阵同上题8,依据算法，则从极点0出发,按广度优先遍历的结点序列是Ａ.0２４３６5１B.013642５C.0423１５６Ｄ.０1342５6(C）1１.已知图的毗邻矩阵同上题8，依据算法，则从极点0出发,按广度优先遍历的结点序列是----A.０243165B.013564２C．0123４６5D.0１23456(D）１2.已知图的毗邻表以下所示,依据算法，则从极点0出发按深度优先遍历的结点序列是A．0132B.0231C.0321D.0123（Ａ）13．已知图的毗邻表以下所示，依据算法,则从极点0出发按广度优先遍历的结点序列是A．0321B.0123C.0132D.0312(A）1４.深度优先遍历近似于二叉树的A．先序遍历B.中序遍历Ｃ．后序遍历D．层次遍历（Ｄ)１５.广度优先遍历近似于二叉树的A.先序遍历B.中序遍历Ｃ.后序遍历D．层次遍历(A)16.任何一个无向连通图的最小生成树A.只有一棵Ｂ.一棵或多棵Ｃ.必定有多棵Ｄ.可能不存在（注,生成树不独一,但最小生成树独一，即边权之和或树权最小的状况独一）二、填空题(每空1分，共2０分）１.图有毗邻矩阵、毗邻表等储存构造，遍历图有深度优先遍历、广度优先遍历等方法。２．有向图G用毗邻表矩阵储存,其第ｉ行的所有元素之和等于极点i的出度。3.假如n个极点的图是一个环，则它有ｎ棵生成树。(以随意一极点为起点,获得ｎ－1条边)4．n个极点e条边的图，若采纳毗邻矩阵储存，则空间复杂度为Ｏ(n2)。5.ｎ个极点e条边的图,若采纳毗邻表储存，则空间复杂度为O(ｎ＋e)。６.设有一稀少图Ｇ，则G采纳毗邻表储存较省空间。７.设有一浓密图G，则G采纳毗邻矩阵储存较省空间。8.图的逆毗邻表储存构造只合用于有向图。9.已知一个图的毗邻矩阵表示，删除所有从第ｉ个极点出发的方法是将毗邻矩阵的第i行所有置０。10．图的深度优先遍历序列不是唯一的。11．ｎ个极点e条边的图采纳毗邻矩阵储存,深度优先遍历算法的时间复杂度为O(n2）；若采纳毗邻表储存时,该算法的时间复杂度为O（n＋ｅ)。12．ｎ个极点e条边的图采纳毗邻矩阵储存,广度优先遍历算法的时间复杂度为O（n2）;若采纳毗邻表储存,该算法的时间复杂度为O(n＋e)。１3.图的BFS生成树的树高比DFS生成树的树高小或相等。----用普里姆(Ｐrｉm）算法求拥有n个极点e条边的图的最小生成树的时间复杂度为O(n2）;用克鲁斯卡尔(Kｒｕskaｌ)算法的时间复杂度是Ｏ（eｌoｇ２e)。15.若要求一个稀少图G的最小生成树，最好用克鲁斯卡尔（Kruskal）算法来求解。１6.若要求一个浓密图G的最小生成树,最好用普里姆(Pｒim)算法来求解。１7.用Dijkｓtra算法求某一极点到其余各极点间的最短路径是按路径长度递加的序次来获得最短路径的。1８.拓扑排序算法是经过重复选择拥有０个前驱极点的过程来达成的。三、简答题(每题６分,共24分)1.已知以下图的有向图，请给出该图的:（1）每个极点的入/出度;极点123456（2）毗邻矩阵；入度（3）毗邻表；出度（4）逆毗邻表。答案:.请对以下图的无向带权图:1）写出它的毗邻矩阵,并按普里姆算法求其最小生成树；2）写出它的毗邻表，并按克鲁斯卡尔算法求其最小生成树。解:设起点为a。能够直接由原始图画出最小生成树,并且最小生成树只有一种(类)!毗邻矩阵为：04340559535055507654最小生成树→703630252065460ＰＲIM算法（横向变化）:VbcdeｆghＵV-ＵVexaaaaａaa｛a}{b，c,d,e,f，lｏ４3∞∞∞∞∞g,h}----wcosｔVｅxa0caaａc{ａ，c}{b,d，e,ｆ,ｌowc４５∞∞∞5ｇ，h｝ｏstVeｘ０0cbaac{ａ，c,b}{ｄ,e,f,g,h}ｌowc59∞∞５ｏstVex0００ｄddd{a,c，b，{ｅ,f，g,h｝lｏwc76５4ｄ}ｏstＶｅx000ddd0｛a,｛e，ｆ,g｝ｌow７6５ｃ,b,d,hｃｏs}ｔＶex000dg０0{a，c,ｂ,d,{ｆ,ｅ｝loｗc72ｈ,ｇ｝ｏstVｅｘ000f０00{a,ｃ,b，{e}lｏ３d,h，g,wcostｆ}Ｖｅｘ00０000０{a,c,b,d,h{}ｌ,g,f，owcoste}毗邻表为:→b４→c3ｂ→a4→c5→d5→e9^c→ａ3→ｂ５→d5→h5^d→b5→ｃ5→e7→ｆ6→ｇ5→h４^e→b9→d７→f3＾ｆ→d6→e3→ｇ2^g→ｄ5→f2→h6^ｈ→c5→d４→g６^克鲁斯卡尔算法步骤(按边合并，堆排序):先排列:ｆ--－2－--ｇa—３－-cｆ—3—eａ—４－-－bd—4—h(a,b,c)（ｅ，f，ｇ)（ｄ，h)取b—5—d,g—5--d就把三个连通重量连结起来了。3．已知二维数组表示的图的毗邻矩阵以以下图所示。试分别画出自极点1出发进行遍历所得的深度优先生成树和广度优先生成树。----4．试利用Dijkstｒａ算法求图中从极点a到其余各极点间的最短路径,写出履行算法过程中各步的状态。解：最短路径为：（a,c,ｆ,ｅ，d,g,b)四、给定以下网G：(1０分)１试着找出网G的最小生成树，画出其逻辑构造图;２用两种不一样的表示法画出网G的储存构造图；3用C语言(或其余算法语言）定义此中一种表示法(储存构造)的数据种类。解:1.最小生成树可直接画出,如右图所示。2.可用毗邻矩阵和毗邻表来描绘:1241220892015121510486961210

描绘储存构造的数据种类可参赐教材或电子教学设计：注：用两个数组分别储存极点表和毗邻矩阵#defineINFINITYINT_MAX//最大值∞#defineMAX_VERTEX_NUM20//假定的最大极点数（可取为7）Typedefenum{DG,DN,AG,AN}GraphKind;//有向/无向图，有向/无向网TypedefstructArcCell{//弧（边）结点的定义VRTypeadj;//极点间关系，无权图取1或0；有权图取权值种类InfoType*info;//该弧有关信息的指针}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];Typedefstruct{//图的定义VertexTypevexs[MAX_VERTEX_NUM];//极点表，用一维向量即可AdjMatrixarcs;//毗邻矩阵IntVernum,arcnum;//极点总数（7），弧（边）总数（9）--//图的种类标记GraphKindkind;}Mgraph;--毗邻表为:a→b12→e4^b→a12→c2→ｅ８→f9^０AB———————Cc→b２→d１→g１^0５２d→c１→ｇ1^E————FG————D５０e→a4→b8→f6^f→b9→e6^g→ｃ１→d１20五、算法设计题(每题10分,共30分）1．编写算法，由挨次输入的极点数量、弧的数量、各极点的信息和各条弧的信息成立有向图的毗邻表。解:StatｕsBuiｌｄ_AdｊList（ALGraph＆G)／/输入有向图的极点数,边数，极点信息和边的信息成立毗邻表｛InitALGraph（G);sｃａｎf("%ｄ",＆v);iｆ(v<0）rｅturnEＲＲOR;//极点数不可以为负G.vｅxnum=v;scａnｆ(＂%d",&a);if(a<0)returｎERRＯR;／/边数不可以为负G.aｒcnum＝a;foｒ（m=0;m＜ｖ;m++)G．veｒｔｉces［m].data=geｔｃhaｒ(）;/／输入各极点的符号oｒ(m=１;m＜＝ａ;m++)｛ｔ=geｔchaｒ( );h＝gｅtchａr( );／／ｔ为弧尾，h为弧头if((ｉ＝ＬocateVex(G,ｔ）)<０)ｒetuｒnEＲRＯR;if((j=LocａteVex(Ｇ,ｈ））<0)returｎEＲRＯR；／/极点未找到----p=(AｒcNode*)malloc(ｓｉzeoｆ（ArｃNode))；if（！Ｇ.ｖertices.[i].firstarc）Ｇ．ｖertices[i].firstarｃ=ｐ;else{for（q=Ｇ.vｅｒticｅｓ[i].firstarc;q->nextaｒc；q=q->ｎeｘｔaｒc);q－＞nｅxtarc=p;}ｐ－>adjvex=j；p－>nextarc＝NULL;}／/whileretｕrｎＯＫ；}//Build_AｄjＬｉsｔ2.试在毗邻矩阵储存构造上实现图的基本操作:DeleteAｒc（G,v,w），即删除一条边的操作。（假如要删除所有从第ｉ个极点出发的边呢？提示：将毗邻矩阵的第i行所有置0)解://本题中的图G均为有向无权图。ＳtatusDｅletｅ_Arc(MＧｒaｐh&G，cｈarv，charw)／/在毗邻矩阵表示的图G上删除边(v,ｗ){if((i=LocateVeｘ（G,v))<0)reｔｕrnERROR;if（(j=LocaｔeVex(G，w))<0)returnERＲOR;if(G．aｒcs[i][ｊ］.adj){G．arcs[i][j].aｄj＝０;Ｇ.aｒcnum--;}reｔｕrnOK;}／／Ｄeleｔe＿Aｒc3．试鉴于图的深度优先搜寻策略写一算法,鉴别以毗邻表方式储存的有向图中能否存在由极点vi到极点ｖｊ的路径(i≠j）。注意:算法中波及的图的基本操作一定在此储存构造上实现。intvisiｔｅｄ[MAＸＳIZE];／/指示极点能否在目前路径上intexiｓt_paｔh＿ＤFS(ALＧraｐhＧ，intｉ,ｉntj)／/深度优先判断有向图G中极点i到顶点j能否有路径,是则返回1,不然返回0{iｆ(i=＝j)return1；//i就是jelse{ｖisiｔeｄ[i]=1;for（p=Ｇ．vertiｃeｓ[ｉ］.firstaｒc;p;p=p->nｅxtarｃ)｛k＝p-＞ａdjvｅｘ;iｆ(!viｓitｅd[k]&&eｘist＿pａｔh（k,j))reｔurn1;//i下游的极点到j有路径｝/／for｝/／ｅlse----}/／ｅxｉsｔ_path_DFＳ解2：(以上算法仿佛有问题：假如不存在路径，则原程序不可以返回0。我的解决方式是在原程序的中引入一变量levｅl来控制递归进行的层数。详细的方法我在程序顶用红色标记出来了。）intｖｉｓiｔeｄ[MAXSＩZE];//指示极点能否在目前路径上intleｖel＝1;／/递归进行的层数ｉntexisｔ_ｐath_DＦS(ＡLGraphG，inti,inｔj)／／深度优先判断有向图G中极点i到顶点ｊ能否有路径,是则返回１,不然返回０｛iｆ(i=＝j）return1;//i就是ｊｅlsｅ｛visｉteｄ［i]=1;for（ｐ=Ｇ.veｒtices[i].ｆiｒｓｔarc;p;p=ｐ->ｎextarc,levｅｌ－-）{leｖel++;k＝ｐ－>aｄjvｅx;if（!visiｔed［k]＆&exｉｓt_pａth（k,ｊ)）retｕｒｎ１;／/i下游的极点到ｊ有路径}//for}／/ｅlsｅif(ｌevel==1）retｕｒn0;}//eｘisｔ＿path＿ＤＦＳ附带题:采纳毗邻表储存构造,编写一个鉴别无向图中随意给定的两个极点之间能否存在一条长度为k的简单路径的算法。(注1:一条路径为简单路径指的是其极点序列中不含有重现的极点。注2:本题可拜见严题集P207-2０8中有关按“路径”遍历的算法基本框架。)intvisｉted[MAXＳＩZE];ｉｎtｅxｉｓｔ_pａth＿ｌeｎ（ALGrａphG，inti，intj，inｔk)／/判断毗邻表方式存储的有向图G的极点ｉ到ｊ能