第七章 图 试题
一、单项选择题
1.
在无向图中定义顶点的度为与它相关联的（
）的数目。
A. 顶点
B. 边
C. 权
D. 权值
2.
在无向图中定义顶点 v i 与 vj 之间的路径为从 v i 到达 v j 的一个（
）。
A. 顶点序列
B. 边序列
C. 权值总和
D. 边的条数
3. 图的简单路径是指（
）不重复的路径。 A. 权值
B. 顶点
C. 边
D. 边与顶点均
4. 设无向图的顶点个数为
n，则该图最多有（
）条边。 A. n-1
B. n(n-1)/2
C. n(n+1)/2
D. n(n-1)
5.
n 个顶点的连通图至少有（
）条边。 A. n-1
B. n
C. n+1
D. 0 6. 在一个无向图中，所有顶点的度数之和等于所有边数的
( )
倍。
A. 3
B. 2
C. 1
D. 1/2 7. 若采用邻接矩阵法存储一个
n 个顶点的无向图，则该邻接矩阵是一个
(
)
。
A. 上三角矩阵
B. 稀疏矩阵 C. 对角矩阵 D. 对称矩阵
8. 图的深度优先搜索类似于树的（
）次序遍历。 A. 先根
B. 中根
C. 后根 D. 层次
9. 图的广度优先搜索类似于树的（
）次序遍历。 A. 先根
B. 中根
C. 后根
D. 层次 10. 在用 Kruskal
算法求解带权连通图的最小（代价）生成树时，通常采用一个（
）辅助结构，判断一条边的两个端点是否在同一个连通分量上。
A. 位向量
B. 堆
C. 并查集
D. 生成树顶点集合
11. 在用 Kruskal
算法求解带权连通图的最小（代价）生成树时，选择权值最小的边的原则是该边不能
在图中构成（
）。
A. 重边
B. 有向环
C. 回路
D. 权值重复的边
12. 在用 Dijkstra
算法求解带权有向图的最短路径问题时，要求图中每条边所带的权值必须是
（
）。 A. 非零
B. 非整
C. 非负
D. 非正
13. 在一个连通图中进行深度优先搜索得到一棵深度优先生成树，树根结点是关节点的充要条件是它至少
有（
）子女。
1
A. 1 B. 2 C. 3 D. 0
14. 设 有向图有 n 个顶点和 e 条边，采用邻接表作为其存储表示，在进行拓扑排序时，总的计算时间为
（
）。
2
A. O(nlog 2e) B. O(n+e) C. O(ne) D. O(n )
15. 设 有向图有 n 个顶点和 e 条边，采用邻接矩阵作为其存储表示，在进行拓扑排序时，总的计算时间为
（ ）。
A. O(nlog
2e)
B. O(n+e) C. O(ne)
D. O(n 2
)
16. 设 G1 = (V1, E1) 和 G2 = (V2, E2) 为两个图，如果 V1 V2 ，E1 E2 ，则称（ A. G1 是 G2 的子图 B. G2 是 G1 的子图 C. G1 是 G2 的连通分量
D. G2 是 G1 的连通分量 17. 有向图的一个顶点的度为该顶点的（
）。 A. 入度
B. 出度
C. 入度与出度之和
D. ( 入度﹢出度 )) ／ 2
18. 一个连通图的生成树是包含图中所有顶点的一个（
）子图。 A. 极小
B. 连通
C. 极小连通
D. 无环
19. n (n ＞1) 个顶点的强连通图中至少含有（
）条有向边。 A. n-1
B. n
n(n-1)/2
D. n(n-1) 20. 在 一个带权连通图 G 中，权值最小的边一定包含在
G 的（
）生成树中。 A. 某个最小
B. 任何最小
C. 广度优先
D. 深度优先
21. 对 于具有 e 条边的无向图，它的邻接表中有（
）个边结点。
A. e-1
B. e
C. 2(e-1)
D. 2e
22. 对于如图所示的带权有向图，从顶点
1 到顶点 5 的最短路径为（
）。
A.1, 4, 5
B. 1, 2, 3, 5
C. 1, 4, 3, 5
D. 1, 2, 4, 3, 5
1 4
6 9 2
3 1
5
8
2
3
5
23. 具有 n 个顶点的有向无环图最多可包含（
）条有向边。
A. n-1
B. n
C. n(n-1)/2
D.n(n-1)
24. 一个有 n 个顶点和 n 条边的无向图一定是（
）。 A. 连通的
B. 不连通的
C. 无环的
D. 有环的 25. 在 n 个顶点的有向无环图的邻接矩阵中至少有（
）个零元素。 A. n
B. n(n-1)/2
C. n(n+1)/2
D. n(n-1) 。2
）
26. 对于有向图，其邻接矩阵表示比邻接表表示更易于（
）。
A. 求一个顶点的度 B. 求一个顶点的邻接点 C. 进行图的深度优先遍历
D. 进行图的广度优先遍历
27. 在一个有向图的邻接矩阵表示中，删除一条边
需要耗费的时间是（
）。
A. O(1)
B. O(i)
C. O(j)
D. O(i+j)
28. 与邻接矩阵相比，邻接表更适合于存储（
）图。
A. 无向
B. 连通
C. 稀疏
D. 稠密图
29. 设 一个有 n 个顶点和 e 条边的有向图采用邻接矩阵表示，要计算某个顶点的出度所耗费的时间是（ ）。
A. O(n)
B. O(e)
C. O(n+e)
D. O(n 2
)
30. 为 了实现图的广度优先遍历，
BFS 算法使用的一个辅助数据结构是（ ）。
A. 栈
B. 队列 C. 二叉树 D. 树 参考答案：
1. B 2. A 3. B 4. B 5. A 6. B 7. D 8. A 9. D
10. C
11.C 12. C
13. B 14. B 15. D 16. A 17. C 18. C 19. B 20. A 21. D 22. D 23. C 24. D 25. C 26. A
27. A
28. C
29. A
30. B
二、填空题
1. 图的定义包含一个顶点集合和一个边集合。其中，顶点集合是一个有穷 ________ 集合。
2. 用邻接矩阵存储图，占用存储空间数与图中顶点个数
________ 关，与边数 ________ 关。
3. n (n ﹥0) 个顶点的无向图最多有 ________ 条边，最少有 ________ 条边。 4.
n (n ﹥0) 个顶点的连通无向图最少有 ________ 条边。
0 1 0 1 0 0 0 1 0
5.
若 3 个顶点的图 G的邻接矩阵为
，则图 G 一定是 ________ 向图。
6. n (n ﹥0) 个顶点的连通无向图各顶点的度之和最少为 ________ 。
7.
设图 G = (V, E)
，V = {V0, V1, V2, V3}, E = {(V0, V1), (V0, V2), (V0, V3), (V1,
V3)} ，则从顶点 V0 开始的图 G 的不同深度优先序列有 ________ 种，例如 ______________ 8.
设图 G = (V, E)
，V = {P, Q, R, S, T}, E = {
，3
。
从顶点 P 出发，对图 G进行广度优先搜索所得的所有序列为 9.
n (n ﹥0) 个顶点的无向图中顶点的度的最大值为
________ 。
__________ 和___________ 。
________ 。
10. 在 重连通图中每个顶点的度至少为
11. 在 非重连通图中进行深度优先搜索，则深度优先生成树的根为关节点的充要条件是它至少有
________ 个子女。
12. ( n﹥0) 个顶点的连通无向图的生成树至少有
________ 条边。
的边各
13. 1 01 个顶点的连通网络 N 有 100 条边，其中权值为 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
10 条，则网络 N的最小生成树各边的权值之和为 14. 在使用 Kruskal
_________ 。
算法构造连通网络的最小生成树时，只有当一条候选边的两个端点不在同一个
________ 上，才有可能加入到生成树中。 15. 深度优先生成树的高度比广度优先生成树的高度 16. 求 解带权连通图最小生成树的
________ 图的情形。 17. 求 解最短路径的 Dijkstra
算法适用于各边上的权值 ________ 的情形。若设图的顶点数为
n，则该
Prim
________ 。
Kruskal
算法适合于
算法适合于 ________ 图的情形，而
算法的时间复杂度为 ________ 。
18. 若对一个有向无环图进行拓扑排序，再对排在拓扑有序序列中的所有顶点按其先后次序重新编号，则
在相应的邻接矩阵中所有 ________ 元素将集中到对角线以上。 参考答案：
1. 非空 4. n-1
8. PQRST 和 PRQTS 11. 2
14. 连通分量 17. 非负， O(n2)
2. 有, 无 5. 有 9. n-1
12. n-1 15. 高
18. 非零（或值为 1 的）
3. n(n-1)/2, 0 6. 2(n-1)
） 13. 550 16. 稠密，稀疏 10. 2
7. 4 ，V0V1V3V2 （或 V0V2V1V3, V0V2V3V1, V0V3V1V2
三、判断题
1. 2. 3. 4.
一个图的子图可以是空图，顶点个数为
0。
存储图的邻接矩阵中，矩阵元素个数不但与图的顶点个数有关，而且与图的边数也有关。 一个有 1000 个顶点和 1000 条边的有向图的邻接矩阵是一个稀疏矩阵。 对一个连通图进行一次深度优先搜索（
depth first search
）可以遍访图中的所有顶点。
4
相关推荐：
loading