图习题参考答案

1、习题六参考答案一、选择题1. 在一个有个极点的有向图中，若所有极点的出度之和为，则所有极点的人度之和为（A）。A.B.-1C.+1D.2. 一个有向图有个极点，则每一个极点的度可能的最大值是（B）oA.n1B.2（n1）C.nD.2n3 .具有6个极点的无向图至少应有（A）条边才能确保是一个连通图。4 .一个有n个极点的无向图最多有（C）条边。A.nB.n（n1）C.n（n-1）/2D.2n5 .对某个无向图的邻接矩阵来讲，下列叙述正确的是（A）。A.第i行上的非零元素个数和第i列上的非零元素个数必然相等B.矩阵中的非零元素个数等于图中的边数C.第i行与第i列上的非零元素的总数等于极点%的度数

2、D.矩阵中非全零行的行数等于图中的极点数6 .已知一个有向图的邻接矩阵，要删除所有以第i个顶点为孤尾的边，应该（B）。A.将邻接矩阵的第i行删除B.将邻接矩阵的第i行元素全数置为0C.将邻接矩阵的第i列删除D.将邻接矩阵的第i列元素全数置为07 .下面关于图的存储的叙述中，哪个是正确的？（A）A.用邻接矩阵存储图，占用的存储空间只与图中顶点数有关，而与边数无关B.用邻接矩阵存储图，占用的存储空间只与图中边数有关，而与顶点数无关C.用邻接表存储图，占用的存储空间只与图中顶点数有关，而与边数无关D.用邻接表存储图，占用的存储空间只与图中边数有关，而与顶点数无关8 .对图的深度优先遍历，类似于对树的

3、哪一种遍历？（A）A.先根遍历B.中根遍历C.后根遍历D.层次遍历9 .任何一个无向连通图的最小生成树（B）。A.只有一棵B.有一棵或多棵C.必然有多棵D.可能不存在10 .下面是三个关于有向图运算的叙述：（1）求两个指向结点间的最短路径，其结果一定是唯一的（2）求有向图结点的拓扑序列，其结果一定是唯一的（3）求AOE网的关键路径，其结果一定是唯一的其中哪个（些）是正确的？（D）A,只有B. (1)和(2)C.都正确D.都不正确二、填空题1 .若用n表示图中极点数，则有九江1)/2条边的无向有称为完全图。2 .若一个无向图有100条边，则其极点总数最少为15个.3 . n个极点的连通无向图至少

4、有4 .如有向图G的邻接矩阵为:n -1条边,最多有一%必%(01 01 °%10 11 1v201 01 1%00 00 1%1o0 10 0/n(n -1)/2 条边。则极点做的入度是35 .对于一个有向图，若一个极点的度为kl,出度为k2,则对应逆邻接表中该极点单链表中的边结点数为kl一k2.6 .图的遍历算法BFS顶用到辅助队列，每一个极点最多进队1次。7 .在求最小生成树的两种算法中，克鲁斯卡尔算法适合于稀疏图。8 .数据结构中的迪杰斯特拉算法是用来求某个源点到其余各极点的最短路径。9 .除利用拓扑排序的方式，还有深度优先搜索方式能够判断出一个有向图是不是有回路。10 .在

5、用邻接表表示图时，拓扑排序算法的时刻复杂度为O(n+e),三、应用题(1)每一个极点的出/入度:(2)邻接矩阵；(3)邻接表：(4)逆邻接表。答：(1)每一个极点的出/入度是:出度入度1032223214315126321234561/00000021001003010001400101151000006110010)邻接矩阵:邻接表:(4)逆邻接表:0123450123452.试对如图所示的非连通图，画出其广度优先生成丛林。答:图错误!文档中没有指定样式的文字.非连通图3.己知图的邻接矩阵如图所示。试别离画出自极点A动身进行遍历所得的深度优先生成树和广度优先生成树。ABCDEFGHIJABC

6、/O00OOI000000000110001100000100D0010000100E0001000010FGHIJ010100100000100000101000100000000010001001001J10000/图错误!文档中没有指定样式的文字邻接矩阵答:4.请对如图所示的无向网:(1)写出它的邻接矩阵，并按克鲁斯卡尔算法求其最小生成树:(2)写出它的邻接表，并按普里姆算法求其最小生成树。图错误!文档中没有指定样式的文字.无向网ABCDEFGH43co004 3oooo05595 05co55079oo70cooo63cocosooco54oo克鲁斯卡尔算法求其最小生成树0123456

7、7©oo©A二DcHEBAD一普里姆算法求其最小生成树,从A开始A5.试列出图中全数可能的拓扑有序序列。ac图有向图答：abcdef>abcef、abecdfxbacdefxbacedf>baecdfbeacdf四、算法设计题1.编写算法，从键盘读入有向图的极点和弧，创建有向图的邻接表存储结构。参考答案：publicstaticALGraphcreateDGOScannersc=newScanner;"请别离输入有向图的极点数和边数:")；intvexNum=();intarcNum=();VNodevexs=newVNodevexNum;&

8、quot;请别离输入有向图的各个极点门；for(intv=0;v<vexNum;v+)错误味定义书签。H叫KqKetKey()>heapArrayj+l.getKey()j+；)if()<=hcapArrayfjJ.getKeyO)etKeyO<=()ength);)publicbooleandiffer(Objectu.Objectv)booleanisDiffer=false;intcount=0;for(inti=0;i<i+)if(Vi!=null&&(Vi.equals(u)IIVi.equals(v)+count;if(count=0I

9、Icount=2)isDiffer=true;returnisDiffer;)publicvoidunion(Objectu,Objectv)booleanisHaveU=false:quals(u)isHaveU=true;elseif(Si.equals(v)isHaveV=true;)if(JisHaveU)Si=u;if(JisHaveV)Si=v;)克鲁斯卡尔算法只需取所有边中知足条件的v-1条边组成最小生成树。因此可用最小堆存储所有的边，从最小堆上掏出知足条件的V-1条边即可，其时刻复杂度接近最坏情形下也为°(山陪©)。另外，判断新加入的边是不是会形成回路，则可

10、转化为判断边的两个极点是不是在同一等价类中。五、上机实践题1.在邻接矩阵存储结构上实现图的大体操作：InsertArc(Gvw),DeleteArc(Gv,w)o参考答案：packagechO6Exercise;import;import;publicclassExercise5_lpublicfinalstaticintINFINITY=;voidinsertArc(MGraphG,Objectv.Objectw,intP)intiv=(v);intiw=(w);intarcs=();arcsiviw=P：(arcs);()+1);)voiddeleteArc(MGraphGObjectv,

11、Objectw)intiv=(v);intiw=(w);arcs=();arcsiviw=INFINITY;(arcs);()-1)；publicstaticvoidmain(Stringargs)throwsExceptionObjectvexs=Mv0nv2Hv3M,Hv4Hv5,f);arcs=0.7,1,5,INFINITY.INFINITY),7,0,6,INFINITY,3JNFINITY),1,6,0,7,6,4,5,INFINITY.7,0,INFINITY.2,INFINITY,3,6,INFINITY,0,7,INFINITY.INFINITY.4,2,7,0);MGrap

12、hG=newMGraph,6.10.vexs.arcs);”修改前图的边数为：”+()；Exercise5_lexercise5_l=newExercise5_l();(Gnv0'HvlM);"删除V0-V1边后，图的边数为："+();(G7);"增加V0-V1边后,图的边数为："+();)(1)求最短路径的迪杰斯特拉算法。(2)设计一个测试主函数，使其实际运行来求从某个源点到其余各个极点的最短路径。参考答案：packagechO6Exercise;import;import;import;publicclassExercise5_2(privatebooleanP：ength);Pww=true;publicint|getD()returnD;)publicbooleangctP()returnP:publicstaticvoidmain(Stringargs)th