设计一个非递归的深度优先遍历算法，最合适的数据结构是（ ）。
目标
- 辨析 DFS 与 BFS 的辅助结构、访问顺序与标记时机；
- 能手推给定邻接表上的 DFS/BFS 访问序列；
- 掌握 DFS 的边分类、括号化定理与生成树高度关系；
- 理解两种遍历在邻接表与邻接矩阵下的复杂度，以及"什么时候选谁"。
前置知识
建议先阅读第 7.1 节 图的遍历：DFS 与 BFS，再开始本组练习。其中第 6、8 题涉及的括号化定理与 DFS 边分类，已在 7.1 正文的"DFS 时间戳与边分类"小节讲解。
环境、输入与预期输出
- 环境：任意现代浏览器。
- 输入：15 道四选一选择题，部分题目含图或邻接表。
- 预期输出：一份独立作答记录，以及每道错题的完整推理过程。
作答方法
- 先独立判断并记录依据，再点击"提交答案"；
- 提交后核对正确答案和解析，做错的题使用"重新作答"；
- 对含图的题目，先在草稿纸上手推访问顺序或队列/栈变化，再对照选项；
- 对重复考查同一性质的题，说明它们在不同语境下分别考查了什么。
选择题
答题进度已答 0/15正确 0
用邻接表存储的图的深度优先遍历算法类似于树的（ ），广度优先遍历算法类似于树的（ ）。
对于同一张图，从同一顶点出发，若打破平局时均按顶点编号升序选择，则深度优先搜索得到的访问序列与广度优先搜索得到的访问序列相比（ ）。
给定有向图如下，邻接表为 adj(s)=[a,c,d]、adj(a)=[]、adj(c)=[e,b]、adj(b)=[d]、adj(d)=[c]、adj(e)=[s]。从 s 出发，按邻接表顺序进行 BFS，得到的顶点访问序列是（ ）。
adj(s) = [a, c, d]
adj(a) = []
adj(c) = [e, b]
adj(b) = [d]
adj(d) = [c]
adj(e) = [s]
对于同一无向连通图，从同一顶点出发进行遍历，以下关于 BFS 生成树高度与 DFS 生成树高度的说法，正确的是（ ）。
在有向图的同一棵 DFS 树中，若顶点 u 的发现时间 d[u] 小于顶点 v 的发现时间 d[v]，且 u 的完成时间 f[u] 大于 v 的完成时间 f[v]，则以下结论正确的是（ ）。
在具有 V 个顶点和 E 条边的图上，使用邻接表进行 DFS 的时间复杂度为 O(V+E)，使用邻接矩阵则为（ ）。
在有向图的深度优先搜索过程中，若从顶点 u 访问到一条指向顶点 v 的边，且 v 此时已处于“已完成”（黑色）状态，则这条边 (u, v) 的类型（ ）。
若对一个有向图进行 DFS，其 DFS 森林中不存在后向边，则该图（ ）。
若从无向图的任意一个顶点出发进行一次深度优先搜索可以访问图中所有顶点，则该图一定是（ ）。
在无权图中，若使用 BFS 求从源点 s 到目标点 t 的最短路径，并在搜索过程中一旦发现 t 即停止，则该算法（ ）。
在下面的 3×3 迷宫中寻找从起点 S(0,0) 到终点 T(2,2) 的最短路径（# 为障碍物）。如果迷宫规模很大且要求路径长度最短，应优先选择（ ）。
下列关于 BFS 和 DFS 的叙述中，错误的是（ ）。
在广度优先搜索中，顶点 v 被赋予的距离值（即从源点到 v 的最短路径长度）与邻接表中顶点的排列顺序（ ）。
以下哪个问题不能通过一次完整的 BFS 或 DFS 遍历（从任意未访问顶点反复启动搜索，直到覆盖全部顶点，每个顶点至多访问一次）直接解决？（ ）
答案总览（建议完成全部题目后查看）
- 第 1 题：B
- 第 2 题：B
- 第 3 题：C
- 第 4 题：A
- 第 5 题：C
- 第 6 题：A
- 第 7 题：B
- 第 8 题：D
- 第 9 题：B
- 第 10 题：B
- 第 11 题：A
- 第 12 题：B
- 第 13 题：D
- 第 14 题：B
- 第 15 题：D
完成清单
复盘
- 哪道题最容易因访问顺序、标记时机或边分类判断失误？
- 我能否不背答案，重新画图或写出队列/栈变化过程？
- 如果改变起点或邻接顺序，哪些题的结论会变、哪些不变？
查看参考答案
- 访问顺序题最容易受邻接表顺序和“发现时标记/出队时标记”影响；边分类题必须结合 DFS 时间戳或颜色状态判断。
- 复盘时重新写出栈/队列的每一步：BFS 按层先进先出，DFS 深入当前分支后再回溯。
- 只改变邻接顺序时，具体访问序列、DFS 回溯顺序和树形可能改变，但在同一个起点下，BFS 层数（无权最短距离）与从该起点可达的顶点集合不变。改变起点时，BFS/DFS 的根、层数和树形都会重新计算；若图不连通，从新起点出发的可达集合也可能改变。图本身的连通关系与遍历复杂度
O(n+m)仍不变。