图的遍历试题

一、单项选择题
01.下列关于广度优先算法的说法中，正确的是( ).
Ⅰ.当各边的权值相等时，广度优先算法可以解决单源最短路径问题
Ⅱ.当各边的权值不等时，广度优先算法可用来解决单源最短路径问题
Ⅲ.广度优先遍历算法类似于树中的后序遍历算法
Ⅳ.实现图的广度优先算法时，使用的数据结构是队列
A.Ⅰ、Ⅳ B.Ⅱ、Ⅲ、Ⅳ C.Ⅱ、Ⅳ D.Ⅰ、Ⅲ、Ⅳ

02.下列关于图的说法中，错误的是( )。
Ⅰ对一个无向图进行深度优先遍历时，得到的深度优先遍历序列是唯一的
Ⅱ.若有向图不存在回路，即使不用访问标志位，同一结点也不会被访问两次
Ⅲ.采用深度优先遍历或拓扑排序算法可以判断一个有向图中是否有环(回路)
IV．对任何非强连通图必须2次或以上调用广度优先遍历算法才可访问所有的顶点
A.Ⅰ、Ⅱ、Ⅲ B.Ⅱ、Ⅲ C.Ⅰ、Ⅱ D.Ⅰ、Ⅱ、Ⅳ

03.对于一个非连通无向图G，采用深度优先遍历访问所有顶点，在DFSTraverse函数
(见考点讲解 DFS部分）中调用DFS的次数正好等于( ).
A.点数 B.边数 C．连通分量数 D.不确定

04．对一个有n个顶点、e条边的图采用邻接表表示时，进行 DFS遍历的时间复杂度为
( )，空间复杂度为();进行BFS遍历的时间复杂度为（)，空间复杂度为（)。
A.O(n) B.O(e) C. O(n+e) D.O(1)

05．图的广度优先遍历算法中使用队列作为其辅助数据结构，那么在算法执行过程中，每
个顶点的入队次数最多为（ )
A.1 B.2 C. 3 D.4

06,对有n个顶点、e条边的图采用邻接矩阵表示时，进行DFS遍历的时间复杂度为(),进行BFS遍历的时间复杂度为（).
A. O(n2) B.O(e) C. O(n+e) D. O(e^2)

07．无向图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. 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

08.如下图所示，在下面的5个序列中，符合深度优先遍历的序列个数是()。

1. aebfdc 2. acfdeb 3. aedfcb 4. aefdbc 5. aecfdb
A. 5 B.4 C.3 D.2

09．用邻接表存储的图的深度优先遍历算法类似于树的( )，而其广度优先遍历算法类似于
树的().
A.中序遍历 B．先序遍历 C.后序遍历 D.按层次遍历

10.一个有向图G的邻接表存储如下图所示，从顶点1出发，对图G调用深度优先遍历所
得顶点序列是（);按广度优先遍历所得顶点序列是（)。

11．无向图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. acfdeb B. aebdfc C. aedfcb D. abecdf

12．判断有向图中是否存在回路，除拓扑排序外，还可以利用()。(注;涉及下节内容)
A.求关键路径的方法 B.求最短路径的Dijkstra算法
C.深度优先遍历算法 D.广度优先遍历算法

13.设无向图G=(V, E)和G'=(V', E')，若G'是G的生成树，则下列说法错误的是（)。
A.G'为G的子图 B.G'为G的连通分量
C.G'为G的极小连通子图且V= V' D.G'是G的一个无环子图

14.图的广度优先生成树的树高比深度优先生成树的树高（).
A.小或相等 B.小 C.大或相等 D.大

15.【2012统考真题】对有n个顶点、e条边且使用邻接表存储的有向图进行广度优先遍历，其算法的时间复杂度是().
A.O(n) B.Oe) C.O(n+e) D. O(ne)

16.【2013统考真题】下列选项中，不是如下无向图的广度优先遍历序列的是( ).

A. h, c, a, b, d, e,g,f B. e, a,f,g, b, h, c, d
C. d,b, c, a, h, e,f, g D. a, b, c,d, h, e,f, g