《数据结构练习(答案)》由会员分享，可在线阅读，更多相关《数据结构练习(答案)（7页珍藏版）》请在金锄头文库上搜索。
1、第8章 图一、单项选择题 1. 在一个具有n个顶点的有向图中，若所有顶点的出度数之和为s，则所有顶点的入度数之和为(A)。AsBs-1Cs+1Dn2. 在一个具有n个顶点的无向图中，若具有e条边，则所有顶点的度数之和为（ D ）。An BeCn+eD2e3. 在一个具有n个顶点的无向完全图中，所含的边数为（ C ）。AnBn(n-1)Cn(n-1)/2 Dn(n+1)/24. 在一个具有n个顶点的有向完全图中，所含的边数为（ B ）。An Bn(n-1)Cn(n-1)/2 Dn(n+1)/25. 在一个无向图中，若两顶点之间的路径长度为k，则该路径上的顶点数为（ B ）。AkBk+1Ck+2D
2、2k6. 对于一个具有n个顶点的无向连通图，它包含的连通分量的个数为（ B ）。A0B1CnDn+17. 若一个图中包含有k个连通分量，若要按照深度优先搜索的方法访问所有顶点，则必须调用（ A ）次深度优先搜索遍历的算法。AkB1Ck-1Dk+18. 若要把n个顶点连接为一个连通图，则至少需要（ C ）条边。AnBn+1Cn-1D2n9. 在一个具有n个顶点和e条边的无向图的邻接矩阵中，表示边存在的元素（又称为有效元素）的个数为（ D ）。An BneCeD2e10. 在一个具有n个顶点和e条边的有向图的邻接矩阵中，表示边存在的元素个数为（ C ）。AnBneCeD2e11. 在一个具有n个顶
3、点和e条边的无向图的邻接表中，边结点的个数为（ D ）。AnBneCeD2e12. 在一个具有n个顶点和e条边的有向图的邻接表中，保存顶点单链表的表头指针向量的大小至少为（ A ）。An B2nCeD2e13. 在一个无权图的邻接表表示中，每个边结点至少包含（ B ）域。A1B2C3D414. 对于一个有向图，若一个顶点的度为k1，出度为k2，则对应邻接表中该顶点单链表中的边结点数为（ B ）。Ak1Bk2Ck1-k2 Dk1+k215. 对于一个有向图，若一个顶点的度为k1，出度为k2，则对应逆邻接表中该顶点单链表中的边结点数为（ C ）。Ak1Bk2Ck1-k2Dk1+k216. 对于一个
4、无向图，下面（ A ）说法是正确的。A每个顶点的入度等于出度B每个顶点的度等于其入度与出度之和C每个顶点的入度为0D每个顶点的出度为017. 在一个有向图的邻接表中，每个顶点单链表中结点的个数等于该顶点的（ A ）。A出边数 B入边数C度数 D度数减118. 若一个图的边集为(A, B), (A, C), (B, D), (C, F), (D, E), (D, F)，则从顶点A开始对该图进行深度优先搜索，得到的顶点序列可能为（ B ）。AA, B, C, F, D, EBA, C, F, D, E, BCA, B, D, C, F, EDA, B, D, F, E, C19. 若一个图的边集为
5、(A, B), (A, C), (B, D), (C, F), (D, E), (D, F)，则从顶点A开始对该图进行广度优先搜索，得到的顶点序列可能为（ D ）。AA, B, C, D, E, FBA, B, C, F, D, ECA, B, D, C, E, FDA, C, B, F, D, E20. 若一个图的边集为, , , , , ，则从顶点1开始对该图进行深度优先搜索，得到的顶点序列可能为（ A ）。A1,2,5,4,3 B1,2,3,4,5 C1,2,5,3,4 D1,4,3,2,521. 若一个图的边集为, , , , , ，则从顶点1开始对该图进行广度优先搜索，得到的顶点序列
6、可能为（ C ）。A1,2,3,4,5 B1,2,4,3,5 C1,2,4,5,3 D1,4,2,5,322. 由一个具有n个顶点的连通图生成的最小生成树中，具有（ B ）条边。AnBn-1Cn+1D2n23. 已知一个有向图的边集为, , , , , ，则由该图产生的一种可能的拓扑序列为（ A ）。Aa, b, c, d, eBa, b, d, e, bCa, c, b, e, dDa, c, d, b, e二、填空题 1. 在一个图中，所有顶点的度数之和等于所有边数的 2 倍。2. 在一个具有n个顶点的无向完全图中，包含有 n(n - 1)/2 条边，在一个具有n个顶点的有向完全图中，包含
7、有 n(n - 1) 条边。3. 假定一个有向图的顶点集为a,b,c,d,e,f，边集为, , , , , ，则出度为0的顶点个数为 2 ，入度为1的顶点个数为 4 。4. 在一个具有n个顶点的无向图中，要连通所有顶点则至少需要 n - 1 条边。5. 表示图的三种种存储结构为 邻接矩阵 、 邻接表 和 邻接多重表 。6. 在一个连通图中存在着 1 个连通分量。7. 图中的一条路径长度为k，该路径所含的顶点数为 k+1 。8. 若一个图的顶点集为a, b, c, d, e, f，边集为(a, b), (a, c), (b, c), (d, e)，则该图含有 3 个连通分量。9. 对于一个具有n
8、个顶点的图，若采用邻接矩阵表示，则矩阵大小至少为 n n 。10. 对于具有n个顶点和e条边的无向图，在它们对应的邻接表中，所含顶点个数和边结点的个数分别为 n 和 2e 。11. 对于具有n个顶点和e条边的有向图，在它们对应的邻接表中，所含顶点个数和边结点的个数分别为 n 和 e 。12. 在有向图的邻接表和逆邻接表表示中，每个顶点邻接表分别链接着该顶点的所有 出边 和 入边 结点。13. 对于一个具有n个顶点和e条边的无向图，当分别采用邻接矩阵和邻接表表示时，求任一顶点度数的时间复杂度分别为 O(n) 和 O(e) 。14. 假定一个图具有n个顶点和e条边，则采用邻接矩阵和邻接表表示时，其
9、相应的空间复杂度分别为 O(n2) 和 O(n+2e) 。15. 图的 深度 优先搜索遍历算法是一种递归算法，图的 广度 优先搜索遍历算法需要使用队列。16. 对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数和边数分别为 n 和 n-1 。17. 若一个连通图中每个边上的权值均不同，则得到的最小生成树是 唯一 （唯一/不唯一）的。根据图的存储结构进行某种次序的遍历，得到的顶点序列是 不唯一 （唯一/不唯一）的。18. 假定一个有向图的边集为, , , , , ，对该图进行拓扑排序得到的顶点序列为 aebdcf 。三、应用题1. 对于一个无向图，假定采用邻接矩阵表示，试分别写出从顶点0出
10、发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。注：每一种序列都是唯一的，因为都是在存储结构上得到的。解答：深度优先搜索序列：0, 2, 3, 5, 6, 1, 4广度优先搜索序列：0, 2, 3, 5, 6, 1, 42. 对于一个有向图，假定采用邻接表表示，并且假定每个顶点单链表中的边结点是按出边邻接点序号从大到小的次序链接的，试分别写出从顶点0出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。注：每一种序列都是唯一的，因为都是在存储结构上得到的。解答：深度优先搜索序列：0, 3, 6, 4, 1, 5, 2广度优先搜索序列：0, 3, 2, 6
11、, 5, 4, 13. 已知下图所示的一个网，（1）按照Prim方法，从顶点1 出发，求该网的最小生成树的产生过程。（2）按照Kruskal方法，求该网的最小生成树的产生过程。V1V2V3V4V5V6V760506540457050524230解答：（1）V1V2V3V4V5V6V7(a) V1V2V3V4V5V6V750(b) V1V2V3V4V5V6V75040(c)V1V2V3V4V5V6V7504050(d) V1V2V3V4V5V6V750405030(e)V1V2V3V4V5V6V75040504230(f)V1V2V3V4V5V6V7504045504230(g)（2）V1V2V
12、3V4V5V6V7(a)V1V2V3V4V5V6V7(b)30V1V2V3V4V5V6V7(c)3040V1V2V3V4V5V6V7(d)304042V1V2V3V4V5V6V7(e)30404245V1V2V3V4V5V6V7(f)3040424550V1V2V3V4V5V6V7(g)3040424550504. 下图所示为一个有向网图及其带权邻接矩阵，要求对有向图采用Dijkstra算法，求从V0 到其余各顶点的最短路径。(a) 有向带权图V1V0V5V4V3V25106030100502010 10 30 100 5 50 10 20 60 (b) 带权邻接矩阵解答：终点从v0到各终点的D值和最短路径的求解过程i = 1i = 2i = 3i = 4i = 5V1无V210(v0,v2)V360(v0,v2,v3)50(v0,v4,v3)V430(v0,v4)30(v0,v4)V5100(v0,v5)100(v0,v5)90(v0,v4,v5)60(v0,v4,v3,v5)VjV2V4V3V5Sv0,v2v0,v2,v4v0,v2,v3,v4v0,v2,v3,v4,v5
