习题六参考答案
一、选择题
1. 在一个有 个顶点的有向图中，若所有顶点的出度之和为 ，则所有顶点的入度之和为
（A）。
A. B. C. D.
2. 一个有向图有 个顶点，则每个顶点的度可能的最大值是（B）。
A. B. C. D.
3. 具有 6 个顶点的无向图至少应有（ A ）条边才能确保是一个连通图。
A.5 B.6 C.7 D.8
4. 一个有 n 个顶点的无向图最多有（ C ）条边。
A. B. C. D.
5. 对某个无向图的邻接矩阵来说，下列叙述正确的是（A）。
A.第 行上的非零元素个数和第 列上的非零元素个数一定相等
B.矩阵中的非零元素个数等于图中的边数
C.第 行与第 列上的非零元素的总数等于顶点 的度数
D.矩阵中非全零行的行数等于图中的顶点数
6. 已知一个有向图的邻接矩阵，要删除所有以第 个顶点为孤尾的边，应该（B）。
A.将邻接矩阵的第 行删除 B.将邻接矩阵的第 行元素全部置为 0
C.将邻接矩阵的第 列删除 D.将邻接矩阵的第 列元素全部置为 0
7. 下面关于图的存储的叙述中，哪一个是正确的？……（A）
A．用邻接矩阵存储图，占用的存储空间只与图中顶点数有关，而与边数无关
B．用邻接矩阵存储图，占用的存储空间只与图中边数有关，而与顶点数无关
C．用邻接表存储图，占用的存储空间只与图中顶点数有关，而与边数无关
D．用邻接表存储图，占用的存储空间只与图中边数有关，而与顶点数无关
8. 对图的深度优先遍历，类似于对树的哪种遍历？……（A）
A.先根遍历 B.中根遍历 C．后根遍历 D．层次遍历
9. 任何一个无向连通图的最小生成树（B）。
