图练习题(答案)
-
《图》练习题
一、单项选择题
1
、
在一个
具有
n
个顶点的有向图中，若所有顶点的出度数之和为
s
，则所有顶点的度
数之和为
< br>(
)
。
A.
s
B. s-1
C. s+1
D.
2s
2
、
在一个具有
n
个顶点的无向完全图中，
所含的边数为
(
)
。
A.
n
B. n(n-1)
C. n(n-1)/2
D. n(n+1)/2
3
、
在一个
无向图中，
若两顶点之间的路径长度为
k
，
则该路径上的顶点数为
(
)
。
A. k
B. k+1
C. k+2
D. 2k
4
、
对于一
个具有
n
个顶点的无向连通图，它包含的连通分量的个数为
( )
。
A. 0
B. 1
C. n
D. n+1
5
、
若一个
图中包含有
k
个连通分量，
若要按照深
度优先搜索的方法访问所有顶点，
则
必须调用
< br>( )
次深度优先搜索遍历的算法。
A. k
B. 1
C. k-1
D. k+1
6
、
若要把
n
个顶点连接为一个连通图，则至少需要
( )
条边。
A. n
B. n+1
C.
n-1
D. 2n
7
、
在一个
具有
n
个顶点和
e
条边的无向图的邻接矩阵中，
表示边存在的元素
（又称为<
/p>
有效元素）的个数为
(
)
。
A. n
(
)
。
A. n
B. n
e
C. e
D.
2
e
B. n
e
C. e
D.
2
e
8
、
在一个
具有
n
个顶点和
e
条边的有向图的邻接矩阵中，表示边存在的元素个数为
9
、
在一个有向图的邻接表中，每个顶点单链表中结点的个数等于
该顶点的
( )
。
A.
出边数
B.
入边数
C.
度数
D.
度数减
1
10
、
若一
个图的边集为
{(A,B),(A,C),(B,D),(C,F),(D,E),(D
,F)}
，则从顶点
A
开始对
该图进行深度优先搜索，得到的顶点序列可能为
(
)
。
A. A,B,C,F,D,E
C. A,B,D,C,F,E
B. A,C,F,D,E,B
D. A,B,D,F,E,C
11
、
若一
个图的边集为
{(A,B),(A,C),(B,D),(C,F),(D,E),(D
,F)}
，则从顶点
A
开始对
该图进行广度优先搜索，得到的顶点序列可能为
(
)
。
A. A,B,C,D,E,F
C. A,B,D,C,E,F
点序列可能为
(
)
。
B.
A,B,C,F,D,E
D.
A,C,B,F,D,E
12
、
若如
下图所示的无向连通图，
则从顶点
A
开
始对该图进行广度优先遍历，
得到的顶