GESP 七级 · GESP 202509 C++ 七级 第 15 题

下列选项中，哪个不可能是下图的深度优先遍历序列（ ）。


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

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

【考点】深度优先遍历｜子树连续原则｜根节点优先

🎯 考纲定位：GESP 七级图论模块核心考点——深度优先遍历。命题人卡住的是"遍历顺序严格性"：学生常误以为只要包含所有节点就算合法，却忽略了父节点必须先于子节点被访问的硬性约束。本题特意把根节点放在序列中间（选项 B 的 1 在第 5 位），就是专测考生是否真正理解 DFS 的"根优先"性质。

🧠 解题思维：验证序列是否合法，需逐层检查父子顺序和子树完整性。第一节点必须为根 1；对任意节点，其所有子树节点必须在其之后、其兄弟节点之前连续出现。例如节点 5 的子树为{7,8,9}，必须作为一个整体紧跟在 5 之后。若某节点在序列中被打断（如 5 之后先出现 1 再出现 7），则非法。

🪤 陷阱拆解：错项 B 首节点为 5，却跳过根 1 直接访问子树——违反"根优先"铁律。更阴险的是，它把 5 的子树{7,8,9}完整放在后面，看似符合"子树连续"，实则因起始点错误直接判定非法。命题人利用"只要子树完整就合法"的假象，诱导粗心考生误选。对比其他选项：A、C、D 均以 1 开头，且各子树节点均在父节点后连续出现，因此合法。

🔄 反命题思维：若将树改为"1 不是根"（如 5 为独立根），则 B 可能成为合法序列。提醒：遇到"不可能"类题，先反向构造——假设它成立，看能否找到矛盾。