图练习题
-
图练习题
1.
设有
6
个结点的无向图，该图至少应有
( )
条边才能确保是一个连通图。
a.5 b.6 c.7 d.8
2.
设某完全无向图中有
n
个顶点，则该完全无向图中有（
）条边。
a.
n(n-1)/2 b. n(n-1) c. n d. n-1
3
．设某有向图中有
n
个顶点，则该有向图对应的邻接表
中有（
）个表头结点。
a. n-1 b. n c. n+1 d. 2n-1
4
．设无向图
g
中有
n
个顶点
e
条边，则其对应的邻接
表中的表头结点和表结点的个数分别为（
）
。
a.
n
，
e b
e
，
n c
2n
，
e d
n
，
2e
5
．设某强连通图中有
n
个顶点，则该强连通图中至少有（
）条边。
a.
n(n-1) b. n+1 c. n d. n(n+1)
6
．设某无向图中有
n
个顶点
e
条边，则该无向图中所有顶点的入度之和为（
）
。
a
.n b. e c. 2n d. 2e
7
．设某有向图的
邻接表中有
n
个表头结点和
m
个表结点，则该图中有（
）条有向边。
a. n b.
n-1 c. m d. m-1
8
．设连通图
g
中的边集
e={(a
，<
/p>
b)
，
(a
，<
/p>
e)
，
(a
，<
/p>
c)
，
(b
，<
/p>
e)
，
(e
，<
/p>
d)
，
(d
，<
/p>
f)
，
(f
，<
/p>
c)}
，则从顶点
a
出发可
以得到一种深度优先遍历的顶点序列为（
）
。
a.
abedfc b. acfebd c. aebdfc d. aedfcb
9<
/p>
．设某无向图中有
n
个顶点
e
条边，则建立该图邻接表的时间复杂度为（
）
。
a.
o(n+e) b. o(n2) c. o(ne) d. o(n3)
10
．设用邻接矩阵
a
表示有向图
g
的存储结构，则有向图
g
中
顶点
i
的入度为（
）
。
a.
第
i
行非
0<
/p>
元素的个数之和
b.
第
i
列非
0
元素的个数之和<
/p>
c.
第
i<
/p>
行
0
元素的个数之和
d.
第
i
列
< br>0
元素的个数之和
11
．设某无向图有
n
个顶点，则该无向图的邻接
表中有（
）个表头结点。
a. 2n b. n c. n/2 d. n(n-1)
12
．设无向图
g
中有
n
个顶点，则该无向图的最小生成树上有（
）条边。
a. n b. n-1
c. 2n d. 2n-1
13
．设无向图的顶点个数为<
/p>
n
，则该图最多有（）条边。
a
．
n-1
b
．
n(n-1)/2
c
．
n(n+1)/2
c
．
0
14
．设有向无环图
g
中的有向边集合
e=
{<1
，
2>
，
<2
，
3>
，
<3
，
4>
，
<1
，
4>}
，则下列属于该有向图
g
的一种拓扑
排序序列的是（
）
。
a. 1
，
2
，
3
，
4 b. 2
< br>，
3
，
4
，
1 c. 1
，
4
，
2
，
3 d. 1
，
2
，
4
，
3
15
．在一个具有<
/p>
n
个顶点的无向图中，要连通所有顶点则至少需要（
）条边。
a
．
n
b
．
2n
c
．
n-1
d
．
n+1
16
．在一个图中，所有顶点的度数之和等于所有边数的（
）倍。
a
．
2
b
．
1
c
．
3
d
．
4 1
17
．在用邻接表表示图时
,
对图进行深度优先搜索遍历的算法的时间复杂度为
______
。
a.
ｏ
(n) b.
ｏ
(n+e) c.
ｏ
(n2) d.
ｏ
(n3)
(b)
在用邻接表存储图时，
故整个算法的时间复杂度为
o(
n+e)
。
如果用邻接矩阵表示图，
则
算法的时间复杂度就
是
o(n2)
。<
/p>
18
．一个具有
n
个顶点的无向连通图，它所包含的连通分量数为（
）
a.0 b.1 c.n
d.
不确定
19
．下列说法中不正确的是（
）
．
．
．
a.
无向图的极大连通子图称为连通分量