第7章-图-自测卷解答.docx
第7章图自测卷解答、单选题(每题1分，共16分)(C)1.在一个图中，A.1/2所有顶点的度数之和等于图的边数的倍。B.1C.2D.4(B)2.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的倍。A.1/2B.1C.2D.4(B)3.有8个结点的无向图最多有条边。A.14B.28C.56D.112(C)4.有8个结点的无向连通图最少有条边。A.5B.6C.7D.8(C)5.有8个结点的有向完全图有条边。A.14B.28C.56D.112(B)6.用邻接表表示图进行广度优先遍历时，通常是采用来实现算法的。A.栈B.队列C.树D.图(A)7.用邻接表表示图进行深度优先遍历时，通常是采用来实现算法的。A.栈B.队列C.树D.图(C)列是8.已知图的邻其-OllllO100100110001001100110101101000011011100010W矩阵，根据算法思想，则从顶点O出发按深度优先遍历的结点序A.0243156B. 0136542C. 0423165D. 0361542(D)9.已知图的邻接矩阵同上题8,根据算法，则从顶点O出发，按深度优先遍历的结点序列是A.0243156B.0135642C.0423165D.0134256(B)10.已知图的邻接矩阵同上题8,根据算法，则从顶点O出发，按广度优先遍历的结点序列是A.0243651B.0136425C.0423156D.0134256(C)11.已知图的邻接矩阵同上题8,根据算法，则从顶点O出发，按广度优先遍历的结点序列是A.0243165B.0135642C.0123465D.0123456(D)12.已知图的邻接表如下所示，根据算法，则从顶点O出发按深度优先遍历的结点序列是-I1I2I-H11T"三一E3E111三T。I-Hll411T11-3Z2-3A.0132C.0321B.0231D.0123(A)13.已知图的邻接表如下所示，根据算法，则从顶点O出发按广度优先遍历的结点序列是A.0321B.0123C.0132D.0312(A)14.深度优先遍历类似于二叉树的C.后序遍历D.层次遍历C.后序遍历D.层次遍历A.先序遍历B.中序遍历(D)15.广度优先遍历类似于二叉树的A.先序遍历B.中序遍历(A)16.任何一个无向连通图的最小生成树A.只有一棵B.一棵或多棵C.一定有多棵D.可能不存在(注，生成树不唯一，但最小生成树唯一，即边权之和或树权最小的情况唯一)二、填空题(每空1分，共20分)1 .图有邻接矩阵、邻接表等存储结构,遍历图有深度优先遍历、广度优先遍历等方法。2 .有向图G用邻接表矩阵存储，其第i行的所有元素之和等于顶点i的出度。3 .如果Ii个顶点的图是一个环，则它有H棵生成树。(以任意一顶点为起点，得到n-1条边)4 .n个顶点e条边的图，若采用邻接矩阵存储，则空间复杂度为OS?)。5 .n个顶点e条边的图，若采用邻接表存储，则空间复杂度为O(n+e)。6 .设有一稀疏图G,则G采用邻接表存储较省空间。7 .设有一稠密图G,则G采用邻接矩阵存储较省空间。8 .图的逆邻接表存储结构只适用于有向图。9 .已知一个图的邻接矩阵表示,删除所有从第i个顶点出发的方法是将邻接矩阵的第i行全部置0。10 .图的深度优先遍历序列惟一的。11 .n个顶点e条边的图采用邻接矩阵存储,深度优先遍历算法的时间复杂度为若采用邻接表存储时，该算法的时间复杂度为O(n+e)。12 .n个顶点e条边的图采用邻接矩阵存储，广度优先遍历算法的时间复杂度为O(112);若采用邻接表存储，该算法的时间复杂度为O(Il+e)。13 .图的BFS生成树的树高比DFS生成树的树高小或相。14 .用普里姆(Prim)算法求具有n个顶点e条边的图的最小生成树的时间复杂度为O(112);用克鲁斯卡尔(KnlSkaI)算法的时间复杂度是CHelo&e)。15 .若要求一个稀疏图G的最小生成树，最好用克鲁斯卡尔(KrUSkaD算法来求解。16 .若要求一个稠密图G的最小生成树，最好用普里姆(Prim)算法来求解。17 .用Dijkstra算法求某一顶点到其余各顶点间的最短路径是按路径长度递增的次序来得到最短路径的。18 .拓扑排序算法是通过重复选择具有_个前驱顶点的过程来完成的。三、简答题(每题6分，共24分)1.已知如图所示的有向图，请给出该图的:（1） 每个顶点的入/出度;（2） 邻接矩阵；（3） 邻接表；（4） 逆邻接表。7.1（1）顶点123456入度出度（2）邻接矩阵答案:iTlTl76I)17。II5*l-13IAI三-HziS1113-3-IZ11J3-11Z2.请对下图的无向带权图：（1）写出它的邻接矩阵，并按普里姆算法求其最小生成树；（2）写出它的邻接表，并按克鲁斯卡尔算法求其最小生成树。解：设起点为ao可以直接由原始图画出最小生成树，而且最小生成树只有一种（类）！邻接矩阵为：0430000004055900000035050050055076540090070300000000006302000000005206000054000060最小生成树fPRIM算法（横向变化）：VbCdefghUV-UVexaaaaaaaab,c,d,e,f,g,hIowcost43OOOOOOOOOO)Vexa0CaaaCa,cb,d,e,f,g,hIowcost45OOOOOO5Vex00CbaaCa,c,bd,e,f,g,hIowcost59OOOO5Vex000dddda,c,b,de,fghIowcost7654Vex000ddd0a,c,b,d,he,f,g)Iowcost765)Vex000dg00a,c,b,d,hf,eIowcost72,gVexIowcost000f3000a,c,b,d,hgfeVexIowcost0000000a,c,b,d,hgf,e()邻接表为:b4a4a3b5b9d6d5C5C3C5b5C5d7e3f2d4d5d5e7f3g2h6g6克鲁斯卡尔算法步骤(按边归并，堆排序):先罗列：f2ga3-cf3ea4bd4h(a,b,c)(e,f,g)(d9h)取b5d,g5-d就把三个连通分量连接起来了。3 .已知二维数组表示的图的邻接矩阵如下图所示。试分别画出自顶点1出发进行遍历所得的,c,.°°»深度优先生成树和广度优先生成树。1000000101020010001000300010001004000010001050000010001611000000007001000000181001000010900001010011010000100004 .试利用DijkStra算法求图中从顶点a到其他各顶点间的最短路径，写出执行算法过程中各步的状态。解：最短路径为：(a,c,f,e,d,g,b)终点DistbCdefgS(终点集)K=I15(a,b)2(a»c)12(a,d)a,cK=215(a,b)12(a,d)10(a*c,e)6(a,c,f)a,c,f)K=315(a,b)11(a,c,f,d)10(a,c,e)16(a,c,f,g)a,c,f»eK=415(a,b),11(a,c,f,d)16(a,c,f,g)a,c,f,e,dK=515(a>b)14(a,c,f,d,g)a,c,f,e,d,gK=615(a,b)a,c,f,e,d,g,b四、给定下列网G:（Io分）2.可用邻接矩阵和邻接表来描述:124OOOO12208920151215Oo1048OO69OO6OOOO1210OO1试着找出网G的最小生成树，画出其逻辑结构图；2用两种不同的表示法画出网G的存储结构图；3用C语言（或其他算法语言）定义其中一种表示法（存储结构）的数据类型。解：L最小生成树可直接画出，如右图所示。描述存储结构的数据类型可参见教材或电子教案：注：用两个数组分别存储顶点表和邻接矩阵#defineINFINITYINT_MAX最大值8#defineMAX_VERTEX_NUM20/假设的最大顶点数（可取为7）TypedefenumDG,DN,AGANGraphKind;有向/无向图，有向/无向网Typed
