GESP 六级 · GESP 202503 C++ 六级 第 18 题

在树的深度优先搜索（DFS）中，使用队列作为辅助数据结构以实现“先进后出”的访问顺序。

DFS 使用栈（或递归），沿一条路径走到底再回溯，适合遍历所有可能状态。注意回溯时的状态恢复。

DFS 递归遍历时注意状态回溯（恢复现场）。图遍历需要visited数组避免重复访问和死循环。

【考点】DFS实现栈结构｜LIFO与FIFO区分｜图论遍历基础

看到"树的DFS"立刻锁定栈结构，因为DFS本质是深度优先，必须用后进先出的栈来保存回溯路径。题干却强行说"用队列实现先进后出"，这直接矛盾——队列是先进先出，栈才是先进后出。解题关键就是识别算法与数据结构的对应关系，而不是死记结论。

错误选项A的陷阱极深：它把"栈的LIFO特性"安在"队列"头上。命题人利用考生对"先进后出"一词的模糊理解——以为队列也能"后进先出"？不，队列是FIFO。如果你只背结论"DFS用栈"，却没理解数据结构与访问顺序的绑定关系，就会误选A。这道题专卡"遍历算法+数据结构+访问顺序"三重关系的认知，六级考生最容易栽在"队列也能FILO"这种伪命题上。

换种考法：若题干改为"树的BFS用队列实现先进先出"，答案就变A；换成"图的DFS用栈实现后进先出"，答案也是A。刷到遍历题先问"这算法对应什么结构"，再问"结构访问顺序是不是题干说的"。命题人最喜欢把正确特性拆成两个半句，让你觉得"对了一半"就掉坑里。记住：DFS=栈，BFS=队列，这是铁律，没有什么"队列也能实现先进后出"的例外。