GESP 六级 · GESP 六级样题（C++ 组） 第 25 题

深度优先遍历一般需要借助数据结构栈来实现，广度优先遍历一般需要借助数据结构队列来实现。

这题考图遍历算法与栈、队列的对应关系。拿到题先想：DFS是深进浅出、BFS是分层扩展，再看数据结构特性（栈后进先出、队列先进先出），就能直接锁定答案。

很多考生容易把‘递归’和‘显式栈’混为一谈，觉得DFS只要写递归就行，不用栈，从而对题干‘借助栈实现’产生怀疑。还有人会死记硬背‘DFS用栈，BFS用队列’，却忘了递归DFS其实依赖系统栈，命题人特意去掉‘非递归’等限定词，就是挖这个坑。另外，部分同学会把BFS的‘分层’误认为是‘深度优先’，导致判断失误。

【考点】深度优先遍历｜栈｜广度优先遍历｜队列

GESP六级《图论》模块的基础题，卡住不少同学的是‘遍历算法与数据结构对应关系’的模糊认知。

遍历算法的本质是‘访问顺序+状态保存’：深度优先（DFS）沿着一条路径一直走到底，遇到死胡同才回溯，这种‘深进浅出’的行为天然对应栈的‘后进先出’特性；广度优先（BFS）则是从起点一层层向外扩展，先访问离起点近的，再访问远的，这种‘分层’行为必须用队列的‘先进先出’来保证顺序。

命题人特意做了极简表述——去掉‘迭代实现’等限定词，就是要考你是否建立了算法与数据结构的底层对应关系，而非死记硬背。陷阱在于：很多同学会把‘递归’和‘显式栈’混为一谈，觉得DFS只要写递归就行，不用栈，从而对题干‘借助栈实现’产生怀疑。还有人会死记硬背‘DFS用栈，BFS用队列’，却忘了递归DFS其实依赖系统栈，命题人就是想挖这个坑。另外，部分同学会把BFS的‘分层’误认为是‘深度优先’，导致判断失误。

若改为‘非递归DFS用栈，递归DFS用系统栈’，则答案变为‘部分正确’；或问‘BFS队列是否可为栈’，答案立刻反转。这说明题干表述的严谨性正是考点所在。

【考频趋势】栈在题库中已考89题，其中GESP六级占了37题，说明这是六级高频基础点；队列考了46题，GESP六级更是占了31题，几乎覆盖了该级别的一半队列题。二叉树遍历在六级中高达100题，但本题属于更底层的‘遍历与数据结构对应’概念，是后续所有树、图遍历题的基石。

【预测】未来六级仍会高频出现‘算法与数据结构对应’的判断题，命题人可能会把‘栈’‘队列’换成‘堆’‘链表’等，或者在题干中加入‘非递归’‘显式’等限定词来增加干扰。只要记住‘DFS=栈，BFS=队列’这个铁律，并注意题干表述的严谨性，这类题基本不会丢分。