图练习题及答案
-
本文档如对你有帮助，请帮忙下载支持！
第七章
图
一、单选题
（
C
）
1.
在一个图中，所有顶点的度数之和等于图的边数的
倍。
A
．
1/2 B. 1
C. 2 D. 4
2.
在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（
B
）
倍。
A
．
1/2 B. 1
C. 2 D. 4
（
B
）
3.
有
8
个结点的无向图最多有
条边。
A
．
14 B. 28
C. 56 D. 112
（
A
）一个
n
个顶点的连通无向图，其边的个数至少为（
）
。
A
．
n-1
B
．
n
C
．
n+1 D
．
nlogn
；
（
C
）
5.
有
8
个结点的有向完全图有
条边。
A
．
14 B. 28
C. 56 D. 112
（
B
）
6.
用邻接表表示图进行广度优先遍历时，通常是采用
来实
现算法的。
A
．栈
B.
队列
C.
树
D.
图
（
A
）
7.
用邻接表表示图进行深度优先遍历时，通常是采用
来实
现算法的。
A
．栈
B.
队列
C.
树
D.
图
8.
下面关于求关键路径的说法不正确的是（
C
）。
A
．求关键路径是以拓扑排序为基础的
B<
/p>
．
一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时
间相
同
C
．
一个
事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与
该活动的持续时间的差<
/p>
D
．关键活动一定位于关键路径上
9.
已知图的邻接矩阵如下，根据算法思想，则从顶点
0
出发，按深度优先遍历
< br>0
1
1
1
1
0
1
1
1
1
1
0
1
0
< br>0
1
0
0
1
0
0
0
1
0
0
1
0
0
1
1
0
0
1
1
< br>0
1
0
0
0
1
1
0
1
1
0
0
0
1
0
的结点序列是（
D
）
A
．
0 2 4 3 1 5 6
B. 0 1 3 5 6 4 2 C. 0 4 2 3 1 6 5 D. 0
本文档如对你有帮助，请帮忙下载支持！
1 3 4 2 5 6
10
、设数
据结构
A=(D
，
R)
，其中
D={1
，
2
，
3
，
4}
，
R={r}
，
r={<
1
，
2>
，
<
2
，
3>
，
<
3
，
4>
，
<
4
，
1>
，
<
4,2>}
，则数据结构
A
是（
C
）
。
(A)
线性结构
(B)
树型结构
(C)
图型结构
(D)
集合
（
C
）
11.
已知图的邻接矩阵同
上题
9
，根据算法，则从顶点
0
出发，按广
度优先遍历的结点序列是
A
．
0 2 4 3 1 6 5
B. 0 1 3 5 6 4 2 C. 0 1 2 3 4 6 5 D. 0 1
2 3 4 5 6
12.
已知图
的邻接表如下所示，
根据算法，
则从顶点
0
出发按深度优先遍历的结
点序列是（
D
）
A
．
0 1 3 2
B.
0 2 3 1
C.
0 3 2 1
D.
0 1 2 3
（
A
）
13.
已知图的邻接表如下所示
，
根据算法，
则从顶点
0
出发按广度优
先遍历的结点序列是
A
．
0 3 2 1
B.
0
1 2 3
C.
0
1 3 2
D.
0 3 1 2
（
A
）
14.
深度优先遍历类似于二叉树的
A
．先序遍历
B.
中序遍历
C.
后序遍历
D.
层次遍历
（
D
）
15.
广度优先遍历类似于二叉树的
A
．先序遍历
B.
中序遍历
C.
后序遍历
D.
层次遍历
（
D
）
16
、下面结构中最适于表示
稀疏无向图的是。
A
．邻接矩阵
B
．逆邻接表
C
．十字链表
D
．邻接表
（
B
）
17
、下列哪一种图的邻接矩阵是对称矩阵？
A
．有向图
B
．无向图
C
．
AOV
网
D
．
AOE
网
18
、在含
n
个顶点和
e
条边的无向图的邻接矩阵中
,
零元素的个数为
(
Ｄ
)
A
．
e
B
．
2e
C
．
n
2
－
e
D
．
n
2
－
2e
19
、下列关于无向连通图特性的叙述中，正确的是
（
A
）
I
．所有顶点的度之和为偶数
II.
边数大于顶点个数减
1
III.
至少有一
个顶点的度为
1
A.
只有
I
B.
只有
II
C.I
和
II
D.I
和
III
20
、假
设一个有
n
个顶点和
e
条弧的有向图用邻接表表示
,
则删除与某个顶点
v
i
本文档如对你有帮助，请帮忙下载支持！
相关的所有弧的时间复杂度是
(
Ｃ
)
A
．
O(n)
B
．
O(e)
C
．
O(n+e)
D
．
O(n*e)
21
、无向图
G=(V,E),
其中：
V={a,b,c,d,e,f},
E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}
，
对该图进行深度优先遍历，
得到的顶点序列正确
的是（
）。
A
．
a,b,e,c,d,f
B
．
a,c,f,e,b,d
C
．
a,e,b,c,f,d
D
．
a
,e,d,f,c,b
22
、
在有向图
G<
/p>
的拓扑序列中，
若顶点
Vi
在顶点
Vj
之前，
则下列情
形不可能出
现的是（
D
）。
A
．
G<
/p>
中有弧
的路 、下列关于
，
Vj>
B<
/p>
．
G
中有一条从
Vi
到
Vj
的路径
C
．
G
中没有弧
D
．
G
中有
一条从
Vj
到
Vi
径
23
、下面哪一方法可以判断出一个
有向图是否有环（回路）
( B)
A
．深度优先遍历
B.
拓扑排序
C.
求最短路径
D.
求关键路径
24
AOE
网的叙述中，不正确的是（
B
）。
A
．关
键活动不按期完成就会影响整个工程的完成时间
B
．任何一个关键活动提前完成，那么整个工程将会提前完成
C
．所有的关键活动提前完成，那么整个工程将会提前完成
< br>
D
．某些关键活动提前完成，那么整个工程将会提前完
成
25
、
设
无向图
G
中有
n
个顶点
e
条边，则其对应的邻接表中的表头结点和表结点的个
数分
别为（
D
）
。
(A) n
，
e
(B) e
，
n
(C) 2n
，
e
(D) n
，
2e
二、填空题
1.
图有
邻接矩阵
、邻接表
、十字链表、邻接多重表等
存储结构，其中邻接矩
阵
、邻接表既用于存储有向图，也用于存储无向图。
遍历图
深度优先遍历、
广度优先遍历
等方法。
2.
有向图
G
用邻接表矩阵存储，其第
i
行的所有元素之和等于顶点
i
的
出
度
。
3.
拓扑排序算法是通过重复选择具有
0
个前驱顶点的过程来完成的。
4.
n
个顶点
e
条边的图，若采用邻接矩阵
存储，则空间复杂度为
O(n
2
)
，若采
用邻接表存储，则空间复杂度为
O(
n+e)
。
5.
n
个顶点
e
条边的图采用邻接矩阵存储，
广度优先遍历算法的时间复杂度为
O(n
2
)
；若采用邻接表存储，该算法的时间复杂度为
O(n+e)
。<
/p>
6.
设有一稀疏图
< br>G
，则
G
采用
< br>
邻接表
存储较省空间，设有
一稠密图
G
，则
G
采用邻接矩阵存储较省空间。
7.
n
个顶点的连通无向图，其边的条数至少为
__ n-1___
_
。若用
n
表示图中顶