习题7图及其答案

习题7一、单项选择题1.在一个具有n个顶点的有向图中，若所有顶点的出度数之和为s，则所有顶点的入度数之和为()。A.sB.s-1C.s+1D.n2.在一个具有n个顶点的有向图中，若所有顶点的出度数之和为s，则所有顶点的度数之和为()。A.sB.s-1C.s+1D.2s3.在一个具有n个顶点的无向图中，若具有e条边，则所有顶点的度数之和为()。A.nB.eC.n+eD.2e4.在一个具有n个顶点的无向完全图中，所含的边数为()。A.nB.n(n-1)C.n(n-1)/2D.n(n+1)/25.在一个具有n个顶点的有向完全图中，所含的边数为()。A.nB.n(n-1)C.n(n-1)/2D.n(n+1)/26.在一个无向图中，若两顶点之间的路径长度为k，则该路径上的顶点数为()。A.kB.k+1C.k+2D.2k7.对于一个具有n个顶点的无向连通图，它包含的连通分量的个数为()。A.0B.1C.nD.n+18.若一个图中包含有k个连通分量，若要按照深度优先搜索的方法访问所有顶点，则必须调用()次深度优先搜索遍历的算法。A.kB.1C.k-1D.k+19.若要把n个顶点连接为一个连通图，则至少需要()条边。A.nB.n+1C.n-1D.2n10.在一个具有n个顶点和e条边的无向图的邻接矩阵中，表示边存在的元素（又称为有效元素）的个数为()。A.nB.neC.eD.2e11.在一个具有n个顶点和e条边的有向图的邻接矩阵中，表示边存在的元素个数为()。A.nB.neC.eD.2e12.在一个具有n个顶点和e条边的无向图的邻接表中，边结点的个数为()。A.nB.neC.eD.2e13.在一个具有n个顶点和e条边的有向图的邻接表中，保存顶点单链表的表头指针向量的大小至少为()。A.nB.2nC.eD.2e14.在一个无权图的邻接表表示中，每个边结点至少包含()域。A.1B.2C.3D.415.对于一个有向图，若一个顶点的度为k1，出度为k2，则对应邻接表中该顶点单链表中的边结点数为()。A.k1B.k2C.k1-k2D.k1+k216.对于一个有向图，若一个顶点的度为k1，出度为k2，则对应逆邻接表中该顶点单链表中的边结点数为()。A.k1B.k2C.k1-k2D.k1+k217.对于一个无向图，下面()种说法是正确的。A.每个顶点的入度等于出度B.每个顶点的度等于其入度与出度之和C.每个顶点的入度为0D.每个顶点的出度为018.在一个有向图的邻接表中，每个顶点单链表中结点的个数等于该顶点的()。A.出边数B.入边数C.度数D.度数减119.若一个图的边集为{(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)}，则从顶点A开始对该图进行深度优先搜索，得到的顶点序列可能为()。A.A,B,C,F,D,EB.A,C,F,D,E,BC.A,B,D,C,F,ED.A,B,D,F,E,C20.若一个图的边集为{(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)}，则从顶点A开始对该图进行广度优先搜索，得到的顶点序列可能为()。A.A,B,C,D,E,FB.A,B,C,F,D,EC.A,B,D,C,E,FD.A,C,B,F,D,E21.若一个图的边集为{1,2,1,4,2,5,3,1,3,5,4,3}，则从顶点1开始对该图进行深度优先搜索，得到的顶点序列可能为()。A.1,2,5,4,3B.1,2,3,4,5C.1,2,5,3,4D.1,4,3,2,522.若一个图的边集为{1,2,1,4,2,5,3,1,3,5,4,3}，则从顶点1开始对该图进行广度优先搜索，得到的顶点序列可能为()。A.1,2,3,4,5B.1,2,4,3,5C.1,2,4,5,3D.1,4,2,5,323.由一个具有n个顶点的连通图生成的最小生成树中，具有()条边。A.nB.n-1C.n+1D.2n24.已知一个有向图的边集为{a,b,a,c,a,d,b,d,b,e,d,e}，则由该图产生的一种可能的拓扑序列为()。A.a,b,c,d,eB.a,b,d,e,bC.a,c,b,e,dD.a,c,d,b,e二、填空题1.在一个图中，所有顶点的度数之和等于所有边数的________倍。2.在一个具有n个顶点的无向完全图中，包含有________条边，在一个具有n个顶点的有向完全图中，包含有________条边。3.假定一个有向图的顶点集为{a,b,c,d,e,f}，边集为{a,c,a,e,c,f,d,c,e,b,e,d}，则出度为0的顶点个数为________，入度为1的顶点个数为________。4.在一个具有n个顶点的无向图中，要连通所有顶点则至少需要________条边。5.表示图的两种存储结构为__________和__________。6.在一个连通图中存在着________个连通分量。7.图中的一条路径长度为k，该路径所含的顶点数为________。8.若一个图的顶点集为{a,b,c,d,e,f}，边集为{(a,b),(a,c),(b,c),(d,e)}，则该图含有________个连通分量。9.对于一个具有n个顶点的图，若采用邻接矩阵表示，则矩阵大小至少为________________。10.对于具有n个顶点和e条边的有向图和无向图，在它们对应的邻接表中，所含边结点的个数分别为________和________。11.在有向图的邻接表和逆邻接表表示中，每个顶点邻接表分别链接着该顶点的所有________和________结点。12.对于一个具有n个顶点和e条边的无向图，当分别采用邻接矩阵和邻接表表示时，求任一顶点度数的时间复杂度分别为________和________。13.假定一个图具有n个顶点和e条边，则采用邻接矩阵和邻接表表示时，其相应的空间复杂度分别为________和________。14.一个图的边集为{(a,c),(a,e),(b,e),(c,d),(d,e)}，从顶点a出发进行深度优先搜索遍历得到的顶点序列为____________，从顶点a出发进行广度优先搜索遍历得到的顶点序列为____________。15.一个图的边集为{a,c,a,e,c,f,d,c,e,b,e,d}，从顶点a出发进行深度优先搜索遍历得到的顶点序列为____________，从顶点a出发进行广度优先搜索遍历得到的顶点序列为____________。16.图的________优先搜索遍历算法是一种递归算法，图的________优先搜索遍历算法需要使用队列。17.对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数和边数分别为________和________。18.若一个连通图中每个边上的权值均不同，则得到的最小生成树是________（唯一/不唯一）的。19.根据图的存储结构进行某种次序的遍历，得到的顶点序列是__（唯一/不唯一）的。20.假定一个有向图的边集为{a,c,a,e,c,f,d,c,e,b,e,d}，对该图进行拓扑排序得到的顶点序列为________。三、应用题1.对于一个无向图6-11(a)，假定采用邻接矩阵表示，试分别写出从顶点0出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。注：每一种序列都是唯一的，因为都是在存储结构上得到的。2.对于一个有向图6-11(b)，假定采用邻接表表示，并且假定每个顶点单链表中的边结点是按出边邻接点序号从大到小的次序链接的，试分别写出从顶点0出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。注：每一种序列都是唯一的，因为都是在存储结构上得到的。3.已知一个无向图的邻接矩阵如图6-12(a)所示，试写出从顶点0出发分别进行深度优先和广度优先搜索遍历得到的顶点序列。4.已知一个无向图的邻接表如图6-12(b)所示，试写出从顶点0出发分别进行深度优先和广度优先搜索遍历得到的顶点序列。图6-110165948372(a)603451278(b)5.已知图6-13所示的一个网，按照Prim方法，从顶点1出发，求该网的最小生成树的产生过程。6.已知图6-13所示的一个网，按照Kruskal方法，求该网的最小生成树的产生过程。7.图6-14所示为一个有向网图及其带权邻接矩阵，要求对有向图采用Dijkstra算法，求从V0到其余各顶点的最短路径。8.图6-15给出了一个具有15个活动、11个事件的工程的AOE网，求关键路径。(a)(b)图6-12v1v5v3v8v11v9v1001a2=4a5=3a9=4a13=10a14=1a15=6v6v7v4v2图6-15a1=3a3=2a4=1a7=6a8=8a11=7a12=4a6=5a10=2(a)有向带权图V1V0V5V4V3V25106030100502010∞∞10∞30100∞∞5∞∞∞∞∞∞50∞∞∞∞∞∞∞10∞∞∞20∞60∞∞∞∞∞∞(b)带权邻接矩阵图6-14有向带权图及其邻接矩阵图6-13V1V2V3V4V5V6V760506540457050524230四、算法设计题1.编写一个算法，求出邻接矩阵表示的无向图中序号为numb的顶点的度数。intdegree1(Graph&ga,intnumb)2.编写一个算法，求出邻接矩阵表示的有向图中序号为numb的顶点的度数。intdegree2(Graph&ga,intnumb)3.编写一个算法，求出邻接表表示的无向图中序号为numb的顶点的度数。intdegree3(GraphL&gl,intnumb)4.编写一个算法，求出邻接表表示的有向图中序号为numb的顶点的度数。intdegree4(GraphL&gl,intnumb)习题6参考答案一、单项选择题1.A2.D3.D4.C5.B6.B7.B8.A9.C10.D11.C12.D13.A14.B15.B16.C17.A18.A19.B20.D21.A22.C23.B24.A二、填空题1.22.n(n-1)/2，n(n-1)3.2，44.n-15.邻接矩阵，邻接表6.17.k+18.39.n，n10.2e，e11.出边，入边12.O（n），O（e/n）13.O（n2），O（n+e）14.acdeb，acedb（答案不唯一）15.acfebd，acefbd（答案不唯一）16.深度，广度17.n，n-118.唯一19.唯一20.aebdcf（答案不唯一）三、应用题1.深度优先搜索序列：0,1,2,8,3,4,5,6,7,9广度优先搜索序列：0,1,4,2,7,3,8,6,5,92.深度优先搜索序列：0,4,7,5,8,3,6,1,2广度优先搜索序列：0,4,3,1,7,5,6,2,83.深度优先搜索序列：0,2,3,5,6,1,4广度优先搜索序列：0,2,3,5,6,1,44.深度优先搜索序列：0,3,6,4,1,5,2广度优先搜索序列：0,3,2,6,5,4,15.过程如图6-16所示V1V2V3V4V5V6V7605065404550524230V1V2V3V4V5V6V750V1V2V3V4V5V6V76.求解过程如图6-17所示。7.求解过程如下表所示。终点从v0到各终点的D值和最短路径的求解过程i=1i=2i=3i=4i=5V1∞∞∞∞∞无V210V1V2V3V4V5V6V7504045504230(h)图6-16V1V2V3V4V5V6V75040504230(g)V1V2V3V4V5V6V750405030(f)V1V2V3V4V5V6V75040(d)V1V2V3V4V5V6V7504050(e)V1V2V3V4V5V6V7(a)30V1V2V3V4V5V6V7(b)3040V1V2V3V4V5V6V7(c)304042图6-17V1V2V3V4V5V6V7(e)3040424550V1V2V3V4V5V6V7(f)