判断题

1.如果无向图G必须进行两次广度优先搜索才能访问其所有顶点，则G一定有2个连通分量。 (3分)

T	F

解析：一个连通分量需要一次广搜。

2.如果无向图G必须进行两次广度优先搜索才能访问其所有顶点，则G中一定有回路。 (3分)

T	F

解析：可能有两个连通分量。

3.图的深度优先遍历非递归算法通常采用队列实现，广度优先遍历非递归算法通常采用堆栈实现。 (2分)

T	F

解析：深搜用堆栈，广搜用队列。

选择题

1.给定一有向图的邻接表如下。从顶点V1出发按深度优先搜索法进行遍历，则得到的一种顶点序列为：(2分)

	选项
A	V1,V5,V4,V7,V6,V2,V3
B	V1,V5,V4,V7,V6,V3,V2
C	V1,V2,V3,V4,V7,V6,V5
D	V1,V5,V6,V4,V7,V2,V3

解析：1→5→4→7→6→3→2

2.给定一有向图的邻接表如下。从顶点V1出发按深度优先搜索法进行遍历，则得到的一种顶点序列为： (2分)

	选项
A	V1,V2,V3,V5,V4
B	V1,V3,V4,V5,V2
C	V1,V4,V3,V5,V2
D	V1,V2,V4,V5,V3

解析：1→3→4→5→2

3.给定一有向图的邻接表如下。从顶点V1出发按广度优先搜索法进行遍历，则得到的一种顶点序列为： (2分)

	选项
A	V1,V2,V3,V4,V5
B	V1,V2,V3,V5,V4
C	V1,V3,V2,V4,V5
D	V1,V4,V3,V5,V2

解析：1→3→2→4→5

4.给定一有向图的邻接表如下。若从v1开始利用此邻接表做广度优先搜索得到的顶点序列为：{v1, v3, v2, v4, v5}，则该邻接表中顺序填空的结果应为： (3分)

	选项
A	v2, v3, v4
B	v3, v2, v4
C	v3, v4, v2
D	v4, v3, v2

解析：第二个点为v3，空1为v3，第三个点为v2，空3为v2，回到空1后的点为第四个点v4。

5.在图中自a点开始进行深度优先遍历算法可能得到的结果为： (2分)

	选项
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

解析：a→e→d→f→c/→b。

6.在图中自a点开始进行广度优先遍历算法可能得到的结果为： (2分)

	选项
A	a, e, d, f, c, b
B	a, c, f, e, b, d
C	a, e, b, c, f, d
D	a, b, e, c, d, f

解析：a/→b→e→c/→d→f。

7.在图中自c点开始进行广度优先遍历算法可能得到的结果为： (2分)

	选项
A	c,a,b,e,f,d
B	c,a,f,d,e,b
C	c,f,a,d,e,b
D	c,f,a,b,d,e

解析：c/→f→a/→d→e→b。

8.在图中自d点开始进行深度优先遍历算法可能得到的结果为： (2分)

	选项
A	d,a,c,f,e,b
B	d,a,e,b,c,f
C	d,e,a,c,f,b
D	d,f,c,e,a,b

解析：d→e→a→c→f/→b。

9.已知一个图的邻接矩阵如下，则从顶点V1出发按深度优先搜索法进行遍历，可能得到的一种顶点序列为： (2分)

	选项
A	V1,V2,V3,V4,V5,V6
B	V1,V2,V4,V5,V6,V3
C	V1,V3,V5,V2,V4,V6
D	V1,V3,V5,V6,V4,V2

解析：1→2→4/→5→6/→3。

10.已知一个图的邻接矩阵如下，则从顶点V1出发按广度优先搜索法进行遍历，可能得到的一种顶点序列为： (2分)

	选项
A	V1,V2,V3,V5,V4,V6
B	V1,V2,V4,V5,V6,V3
C	V1,V3,V5,V2,V4,V6
D	V1,V3,V5,V6,V4,V2

解析：1/→2→3/→5→4→6。

11.

	选项
A	V1V2V3V4
B	V1V3V2V4
C	V1V2V4V3
D	V1V4V2V3

解析：1→2→4/→3。

12.若某图的深度优先搜索序列是{V1, V4, V0, V3, V2}，则下列哪个图不可能对应该序列？ (4分)

	选项
A
B
C
D

解析：4不可能直接跳到0。

13.若某图的深度优先搜索序列是{V2, V0, V4, V3, V1}，则下列哪个图不可能对应该序列？ (4分)

	选项
A
B
C
D

解析：0不可能直接跳到4。

14.下列选项中，不是下图深度优先搜索序列的是：(2分)

	选项
A	V1,V5,V4,V3,V2
B	V1,V3,V2,V5,V4
C	V1,V2,V5,V4,V3
D	V1,V2,V3,V4,V5

解析：D是广搜。

15.图的广度优先遍历类似于二叉树的：(1分)

	选项
A	先序遍历
B	中序遍历
C	后序遍历
D	层次遍历

解析：一层一层搜索，类似层次遍历。

16.图的深度优先遍历类似于二叉树的： (1分)

	选项
A	先序遍历
B	中序遍历
C	后序遍历
D	层次遍历

解析：往下搜索到底部，类似先序遍历。

17.给定无向图G，从V0出发进行深度优先遍历访问的边集合为： {(V0,V1), (V0,V4), (V1,V2), (V1,V3), (V4,V5), (V5,V6)}。则下面哪条边不可能出现在G中？ (3分)

	选项
A	(V0,V2)
B	(V0,V6)
C	(V1,V5)
D	(V4,V6)

解析：

18.如果从无向图的任一顶点出发进行一次深度优先搜索可访问所有顶点，则该图一定是： (2分)

	选项
A	连通图
B	完全图
C	有回路的图
D	一棵树

解析：连通图可一次访问。

19.如果无向图G必须进行两次广度优先搜索才能访问其所有顶点，则下列说法中不正确的是： (2分)

	选项
A	G肯定不是完全图
B	G中一定有回路
C	G一定不是连通图
D	G有2个连通分量

解析：回路不确定。

20.下列说法不正确的是： (2分)

	选项
A	图的遍历是从给定的源点出发每一个顶点仅被访问一次
B	遍历的基本算法有两种：深度遍历和广度遍历
C	图的深度遍历是一个递归过程
D	图的深度遍历不适用于有向图

解析：有向图也可用深搜。

21.在图的广度优先遍历算法中用到一个队列，每个顶点最多进队____次。(2分)

	选项
A	1
B	2
C	3
D	不确定

解析：进队一次，当层遍历完后出队。

22.在用邻接表表示有N个结点E条边的图时，深度优先遍历算法的时间复杂度为： (2分)

	选项
A	O(N)
B	O(N+E)
C	O(N2)
D	O(N​2×E)

解析：要考虑边和点的个数。