一、单项选择题
01.下列关于广度优先算法的说法中，正确的是( A ).
Ⅰ.当各边的权值相等时，广度优先算法可以解决单源最短路径问题
Ⅱ.当各边的权值不等时，广度优先算法可用来解决单源最短路径问题
Ⅲ.广度优先遍历算法类似于树中的后序遍历算法
Ⅳ.实现图的广度优先算法时，使用的数据结构是队列
A.Ⅰ、Ⅳ B.Ⅱ、Ⅲ、Ⅳ C.Ⅱ、Ⅳ D.Ⅰ、Ⅲ、Ⅳ
解析：广度优先搜索以起始结点为中心，一层一层地向外层扩展遍历图的顶点，因此无法考虑到边权值，只适合求边权值相等的图的单源最短路径。广度优先搜索相当于树的层序遍历，Ⅲ错误，广度优先搜索需要用到队列，深度优先搜索需要用到栈，选项Ⅳ正确
02.下列关于图的说法中，错误的是(D )。
Ⅰ对一个无向图进行深度优先遍历时，得到的深度优先遍历序列是唯一的
Ⅱ.若有向图不存在回路，即使不用访问标志位，同一结点也不会被访问两次
Ⅲ.采用深度优先遍历或拓扑排序算法可以判断一个有向图中是否有环(回路)
IV．对任何非强连通图必须2次或以上调用广度优先遍历算法才可访问所有的顶点
A.Ⅰ、Ⅱ、Ⅲ B.Ⅱ、Ⅲ C.Ⅰ、Ⅱ D.Ⅰ、Ⅱ、Ⅳ
03.对于一个非连通无向图G，采用深度优先遍历访问所有顶点，在DFSTraverse函数
(见考点讲解 DFS部分）中调用DFS的次数正好等于( C ).
A.点数 B.边数 C．连通分量数 D.不确定
解析：DFS(或BFS)可用来计算无向图的连通分量数，因为依次遍历必然会将一个连通图中的所有顶点都访问到，所以计算图的连通分量数正好是DFSTraverse()中DFS被调用的次数
04．对一个有n个顶点、e条边的图采用邻接表表示时，进行 DFS遍历的时间复杂度为
( C )，空间复杂度为(A);进行BFS遍历的时间复杂度为（C)，空间复杂度为（A)。
A.O(n) B.O(e) C. O(n+e) D.O(1)
解析：深度优先遍历时，每个顶点表结点和每个边表结点均查找一次，每个顶点递归调用一次，需要借助一个递归工作栈，而广度优先遍历时，也是每个顶点表结点和每个边表结点均查找一次，需要借助一个辅助队列，因此时间复杂度都是O(n+e),空间复杂度都是O(n)
05．图的广度优先遍历算法中使用队列作为其辅助数据结构，那么在算法执行过程中，每
个顶点的入队次数最多为（A )
A.1 B.2 C. 3 D.4
解析：在图的广度优先遍历算法中，每个顶点被访问后立即做访问标记并入队。若队列不空，则队首顶点出队，若该顶点的邻接顶点未被访问，则访问之，做访问标记并入队;若被访问过，则跳过，如此反复，直至队空。因此，在广度优先遍历过程中，每个顶点最多入队一次。
06,对有n个顶点、e条边的图采用邻接矩阵表示时，进行DFS遍历的时间复杂度为(A),进行BFS遍历的时间复杂度为（A).
A. O(n^2) B.O(e) C. O(n+e) D. O(e^2)
解析：采用邻接矩阵表示时，查找有关顶点所有出边的时间复杂度为O(n),共有n各顶点，所以时间复杂度均为O(n^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开始进行深度优先遍历，得到的顶点序列正确的是（D).
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个序列中，符合深度优先遍历的序列个数是(D)。
1. aebfdc 2. acfdeb 3. aedfcb 4. aefdbc 5. aecfdb
A. 5 B.4 C.3 D.2
解析：仅1和4正确
09．用邻接表存储的图的深度优先遍历算法类似于树的(B )，而其广度优先遍历算法类似于树的(D).
A.中序遍历 B．先序遍历 C.后序遍历 D.按层次遍历
10.一个有向图G的邻接表存储如下图所示，从顶点1出发，对图G调用深度优先遍历所
得顶点序列是（A);按广度优先遍历所得顶点序列是（B)。
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 )}。对该图进行深度优先遍历，不能得到的序列是(D)。
A. acfdeb B. aebdfc C. aedfcb D. abecdf
12．判断有向图中是否存在回路，除拓扑排序外，还可以利用(C)。(注;涉及下节内容)
A.求关键路径的方法 B.求最短路径的Dijkstra算法
C.深度优先遍历算法 D.广度优先遍历算法
解析：对无向图来说，若深度优先遍历过程中遇到了回边，则必定存在环，对于有向图来说，这条回边可能是指向深度优先森林中另一棵生成树上的顶点的弧，但是，从有向图的某个顶点v出发进行深度优先遍历时，若在DFS(v)结束之前出现一条从顶点u到顶点v的回边，则u在生成树上是v的子孙，则有向图必定存在包含顶点v和顶点u的环
13.设无向图G=(V, E)和G'=(V', E')，若G'是G的生成树，则下列说法错误的是（B)。
A.G'为G的子图 B.G'为G的连通分量
C.G'为G的极小连通子图且V= V' D.G'是G的一个无环子图
解析：连通分量是无向图的极大连通子图，其中极大的含义是将依附于连通分量重顶点的所有边都加上，所以连通分量重可能存在问题，这样就不是树了
14.图的广度优先生成树的树高比深度优先生成树的树高（A).
A.小或相等 B.小 C.大或相等 D.大
15.【2012统考真题】对有n个顶点、e条边且使用邻接表存储的有向图进行广度优先遍历，其算法的时间复杂度是(C).
A.O(n) B.O(e) C.O(n+e) D. O(ne)
解析：广度优先遍历需要借助队列实现。采用邻接表存储方式对图进行广度优先遍历时，每个顶点均需入队一次(顶点表遍历)，所以时间复杂度为 O(n)，在搜索所有顶点的邻接点的过程中，每条边至少访问一次（出边表遍历)，所以时间复杂度为O(e)，算法总的时间复杂度为O(n+e)。
16.【2013统考真题】下列选项中，不是如下无向图的广度优先遍历序列的是(D ).
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
17.【2015统考真题】设有向图G=(V, E)，顶点集V={V0,V1,V2,V3}，边集E={<v0,v1>，<v0,v2>，<v0,v3>，<v1,v3>}。若从顶点V0开始对图进行深度优先遍历，则可能得到的不同遍历序列个数是(D)。
A.2 B.3 C.4 D. 5
18. 【2016统考真题】下列选项中，不是下图深度优先搜索序列的是（D)。