第7章(图)-练习题.doc
需积分: 5 129 浏览量
2024-01-10
15:23:21
上传
评论
收藏 170KB DOC 举报
a
b e
d
c
f
1、判定 一 个 有向图 是 否 存在回 路 ， 除了利 用 拓 扑排序 方 法 外，还 可 以 利 用
（ ）。
A、求关键路径的方法 B、求最短路径的 Dijkstra 方法
C、宽度优先遍历算法 D、深度优先遍历算法
2．图中有关路径的定义是（ ）。
A．由顶点和相邻顶点序偶构成的边所形成的序列
B．由不同顶点所形成的序列
C．由不同边所形成的序列
D．上述定义都不是
3．一个 n 个顶点的连通无向图，其边的个数至少为（ ）。
A．n-1 B．n C．n+1 D．nlogn；
4．当一个有 N 个顶点的无向图用邻接矩阵 A 表示时，顶点 Vi 的度是（ ）。
A． B． C． D． +
5. 下列说法不正确的是（ ）。
A．图的遍历是从给定的源点出发每一个顶点仅被访问一次
B．遍历的基本算法有两种：深度遍历和广度遍历
C．图的深度遍历不适用于有向图
D．图的深度遍历是一个递归过程
6．无向图 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
7. 设图如右所示，在下面的 5 个序列中，符合深度优先遍历的序列有多少？（ ）
a e b d f c a c f d e b a e d f c b a e f d c b a e f d b c
A．5 个 B．4 个 C．3 个 D．2 个
8. 在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为( )。
A. O(n) B. O(n+e) C. O(n
2
) D. O(n
3
)
9．已知有向图 G=(V,E)，其中 V={V
1
,V
2
,V
3
,V
4
,V
5
,V
6
,V
7
}，
�
�
n
i
jiA
1
],[
� �
�
�
n
1j
j,iA
�
�
n
i
ijA
1
],[
�
�
n
i
jiA
1
],[
� �
�
�
n
1j
i,jA
资源评论
invincible_Tang
- 粉丝: 595
- 资源: 81
