19283926 单定义-过程要件验证（深度优先搜索的扩展与回溯）

单定义-过程要件验证（深度优先搜索的扩展与回溯）

考点：定义判断 / 单定义-过程要件验证（深度优先搜索的扩展与回溯）

问法模型：给出’深度优先搜索’的过程定义并附节点树图，问哪条搜索路径符合定义 → 拆出’扩展到底、不能扩展才回溯上一节点、找到目标即停’三个要件，逐项沿路径核对每一步扩展与回溯是否合规

推理链

1. 第1步：从定义提取三要件：①’按照一定的顺序扩展到下一个节点……不断递归执行’即一路向深处扩展；②’直到某个节点不能再扩展……此时返回上一个节点重新寻找一个新的节点继续扩展’即只有不能再扩展时才回溯、且必须回到上一节点；③’直到找到目标节点，或者搜索完所有节点为止’即找到节点12即停
2. 第2步：结合附图确认父子结构：1的下级为2、3、4，3的下级为5、6、7，4的下级为8，5的下级为9、10，6的下级为11、12，目标节点12位于节点6之下
3. 第3步：验证B项路径1→4→8→4→1→3→6→12：8为叶节点’不能再扩展’且未达目标，返回上一节点4，4无新节点再返回1，随后依次扩展3、6直至12找到目标停止，每相邻两节点均有边相连，扩展到底、回溯落点均为上一节点，符合全部要件
4. 第4步：A项1→2→1→3→6→11后直接到12：节点11是叶节点已不能再扩展且未找到目标，应先返回上一节点6再由6扩展12，该项同级直接跳转、缺少回溯步骤，违反要件②，排除
5. 第5步：C项1→3→5后直接返回3：节点5还含有下级节点9、10，并不满足’不能再扩展’的回溯前提，属于扩展不完整，违反要件①，排除
6. 第6步：D项1→3→5→10→5后直接返回3：从10回溯到5时节点5尚有下级节点9未扩展，应先扩展9再回溯，回溯时机与落点错误，违反要件②，排除
7. 第7步：综上，只有B项完整满足’扩展到底—不能扩展才回溯上一节点—再找新节点扩展—找到目标12即停’的全部要求，当选

最快解法：⚡ 回溯落点检查法（排除法）：沿选项路径逐段检查，凡走到不能再扩展的节点，下一步必须回到树中的上一节点（父节点）——A在叶节点11处同级横跳到12、C在节点5未扩展完9和10就上跳3、D回到节点5后未扩展9就上跳3，均违反回溯规则，逐一排除后锁定B

易错点

• ⚠ 误把’按照一定的顺序’当成必须从左到右、必须遍历全部节点，见B路径未经过节点2、5、7就误排除B（定义允许既定顺序下先走4再走3，且’找到目标节点为止’即可停止）
• ⚠ A项中11→12在书写上相邻、且12确在6之下，容易忽略中间缺少’返回上一节点6’的回溯步骤
• ⚠ 忽略回溯的前提是’不能再扩展’，误认为C、D中随时返回上一节点也算正常回溯

母题抽象

🧩 当定义描述’扩展到底→不能扩展则返回上一节点→再找新节点扩展’这类递归回溯过程并要求选符合的路径时，先由图确认父子关系，再逐段核对选项每次折返是否发生在不能再扩展的节点、且落点是否恰为上一节点

同类特征：定义+树状节点图选路径、深度优先搜索、递归扩展到底、返回上一个节点、找到目标或搜索完所有节点为止、单定义要件比对

相关题

• 2274502（北京 2019，相关度1）
• 2377165（选调 2019，相关度1）
• 19889511（上海 2021，相关度1）
• 2188246（江西 2018，相关度1）

---

题干

深度优先搜索是指从初始节点出发，按照一定的顺序扩展到下一个节点，然后从下一个节点出发继续扩展到新的节点，不断递归执行这个过程，直到某个节点不能再扩展到下一个节点，此时返回上一个节点重新寻找一个新的节点继续扩展，如此搜索下去，直到找到目标节点，或者搜索完所有节点为止。

根据上述定义，如果以“1”为初始节点，“12”为目标节点，下列搜索路径符合深度优先搜索的是：

选项

• A.

  121361112

• B.

  148413612

  　✅
• C.

  135373612

• D.

  135105313612

官方解析

第一步：找出定义关键词。

“从初始节点出发，按照一定的顺序不断扩展到下一个节点，直到不能再扩展”、“此时返回上一个节点重新寻找一个新的节点继续扩展，直到找到目标节点，或者搜索完所有节点为止”。

第二步：逐一分析选项。

A项：121361112，图中显示，扩展到节点11时已无法继续扩展，且未找到目标节点，此时应返回到上一个节点6，而该项直接扩展到同级的节点12，不符合“此时返回上一个节点重新寻找一个新的节点继续扩展，如此搜索下去，直到找到目标节点，或者搜索完所有节点为止”，不符合定义，排除；

B项：148413612，图中显示，从初始节点1出发，扩展到下一个节点4，继续扩展到下一个节点8，此时已无法继续扩展，且未找到目标节点，应返回到上一个节点4，同理继续返回上一个节点1，扩展到下一个节点3，继续扩展到下一个节点6，再扩展到下一个节点12，此时已找到目标节点，搜索完成，符合“从初始节点出发，按照一定的顺序不断扩展到下一个节点，直到不能再扩展”、“此时返回上一个节点重新寻找一个新的节点继续扩展，直到找到目标节点，或者搜索完所有节点为止”，符合定义，当选；

C项：135373612，图中显示，扩展到节点5时直接返回到上一个节点3，而节点5含有节点9和节点10两个下级节点，属于扩展不完整，不符合“从初始节点出发，按照一定的顺序不断扩展到下一个节点，直到不能再扩展”，不符合定义，排除；

D项：135105313612，图中显示，从节点10返回到节点5时又返回到节点3，而节点5还含有节点9这一下级节点，返回到节点5时需要继续扩展到节点9，因此扩展顺序有误，不符合“此时返回上一个节点重新寻找一个新的节点继续扩展，如此搜索下去，直到找到目标节点，或者搜索完所有节点为止”，不符合定义，排除。

故正确答案为B。

给定材料

（无）