数据结构练习题（7章全填空版）答案.docx
需积分: 9 120 浏览量
2021-07-26
20:01:04
上传
评论 1
收藏 68KB DOCX 举报
数据结构练习题（7 章）
1. 在一个图中，所有顶点的度数之和等于所有边数的 ___2___ 倍。
2. 已知一个连通图的边集为 {(1,2)3, (1,3)6, (1,4)8, (2,3)4, (2,5)10, (3,5)12, (4,5)2} ，则
度为 3 的顶点个数有 __4____ 个。
3. 在一个具有 n 个顶点的无向图中，要连通所有顶点则至少需要 __ n-1______ 条边。
4. 在 n 个顶点的非空无向图中，最多有 n 个连通分量。
5. 第一个顶点和最后一个顶点相同的路径称为回路或者环，除第一个顶点和最后一个顶点外，其
余顶点都不重复的回路，称为__简单回路_____。
6. 设有向图 G 中有 n 个顶点 e 条有向边，所有的顶点入度数之和为 d，则 e 和 d 的关系为 e=d
。
7. 图中的一条路径长度为 k ，该路径所含的顶点数为 k+1 。
8. 若一个图的顶点集为 {a,b,c,d,e,f} ，边集为 {(a,b),(a,c),(b,c),(d,e)} ，则该图含有 3
个连通分量。
9. 在一个具有 10 个顶点的无向完全图中，包含有_____45__条边，在一个具有 n 个顶点的无向
完全图中，包含有_ n(n-1)/2____条边。在一个具有 10 个顶点的有向完全图中，包含 90
条弧，在一个具有 n 个顶点的有向完全图中，包含有_ n(n-1)____条弧。
10. 表示图的两种常用的存储结构为__邻接矩阵 __ 、__ 邻接表 _。
11. 用邻接矩阵存储图，占用存储空间数与图中顶点个数 有 关，与边数 无 关。用邻接表法存
储图，占用的存储空间大小与图中边数 有 关，而与结点个数 有 关
12. n 个顶点的无向连通图用邻接矩阵表示时，该矩阵至少有 2(n-1) 个非零元素。
13. 设某无向图 G 中有 n 个顶点，用邻接矩阵 A 作为该图的存储结构，则顶点 i 和顶点 j 互为邻接
点的条件是 A[i][j]=1 。
14. 用邻接矩阵表示有向图, 统计第 i 行中 1 的个数可得顶点 i 的 出度 ，统计第 j 列 1 的个数
可得顶点 j 的 入度 。
15. 无向图的邻接矩阵为__ 对称 矩阵。有向图的邻接矩阵为__ 非对称 矩阵。
16. 对于一个具有 n 个顶点和 e 条边的有向图和无向图，在其对应的邻接表中，所含边结点的个
数分别为 e 和 2e 。
17. 在有向图的邻接表和逆邻接表表示中，每个顶点邻接表分别链接着该顶点的所有 出边 和 入
边 结点。
18. 图的 深度 优先搜索遍历算法是一种递归算法，图的 广度 优先搜索遍历算法需要使用队列。
19. 一个图的边集为 {(a,c),(a,e),(b,e),(c,d),(d,e)} ，从顶点 a 出发进行深度优先搜索遍历得到
的顶点序列为 a,c,d,e,b ，从顶点 a 出发进行广度优先搜索遍历得到的顶点序列为
a,c,e,d,b 。 ( 答案不唯一 )
20. 对于一个具有 n 个顶点和 e 条边的连通图，其生成树中的顶点数和边数分别为 n 和 n-1
。
21. 已知一个连通图的边集为 {(1,2)3, (1,3)6, (1,4)8, (2,3)4, (2,5)10, (3,5)12, (4,5)2} ，若
从顶点 V 1 出发，按照普里姆算法生成的最小生成树的过程中，依次得到的各条边为
(1,3)3,(2,3)4,(1,4)8,(4,5)2 ，该图的最小生成树的权为 17 。
22. 对于含有 n 个顶点 e 条边的无向连通图，利用 prime 算法生成最小生成树的时间复杂度为
O(n
2
) ,Kruskal 算法的时间复杂度为 O(eloge) 。
23. 求图的最小生成树有两种算法， 普里姆 算法适合于求稠密图的最小生成树， 克鲁斯卡尔
算法适合于求稀疏图的最小生成树。
24. 若一个连通图中每个边上的权值均不同，则得到的最小生成树是 唯一 （唯一 / 不唯一）的。
评论0