数据结构-图的遍历

判断题

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

    
T
    
F

深度优先是堆栈，广度优先是队列。

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

    
T
    
F

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

    
T
    
F

选择题

1.下列说法不正确的是：

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

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

    A.O(N)
    B.O(N+E)
    C.O(N²)
    D.O(N²×E)

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

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

4.图的广度优先遍历类似于二叉树的：

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

5.图的深度优先遍历类似于二叉树的：

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

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

    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

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

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

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

    A.V1,V2,V3,V5,V4
    B.V1,V3,V4,V5,V2
    C.V1,V4,V3,V5,V2
    D.V1,V2,V4,V5,V3

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

    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

这些题目意思可能有点歧义，这道题的可能指的是不一定要按邻接矩阵顺序深度优先搜索。而这里的很多题的意思是要严格按照邻接矩阵顺序。

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

    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

11.下列选项中，不是下图深度优先搜索序列的是：

    A.V1, V5, V4, V3, V2
    B.V1, V3, V2, V5, V4
    C.V1, V2, V5, V4, V3
    D.V1, V2, V3, V4, V5

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

    A.
    B.
    C.
    D.

13.

    A.V1V2V3V4
    B.V1V3V2V4
    C.V1V2V4V3
    D.V1V4V2V3

14.在图中 自a点开始进行深度优先遍历算法可能得到的结果为。

    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

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

    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

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

    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

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

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

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

    A.V1,V2,V3,V4,V5
    B.V1,V2,V3,V5,V4
    C.V1,V3,V2,V4,V5
    D.V1,V4,V3,V5,V2

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

    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

注意是广搜

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

    A.1
    B.2
    C.3
    D.不确定