国家公务员录用考试《行测》历史真题（130题）

---

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

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

A.1→2→1→3→6→11→12

B.1→4→8→4→1→3→6→12

C.1→3→5→3→7→3→6→12

D.1→3→5→10→5→3→1→3→6→12

知识点：2025年国家公务员录用考试《行测》题（地市级）

参考答案：B

解析：

第一步：找出定义关键词。
“从初始节点出发，按照一定的顺序不断扩展到下一个节点，直到不能再扩展”、“此时返回上一个节点重新寻找一个新的节点继续扩展，直到找到目标节点，或者搜索完所有节点为止”。
第二步：逐一分析选项。
A项：1→2→1→3→6→11→12，图中显示，扩展到节点11时已无法继续扩展，且未找到目标节点，此时应返回到上一个节点6，而该项直接扩展到同级的节点12，不符合“此时返回上一个节点重新寻找一个新的节点继续扩展，如此搜索下去，直到找到目标节点，或者搜索完所有节点为止”，不符合定义，排除；
B项：1→4→8→4→1→3→6→12，图中显示，从初始节点1出发，扩展到下一个节点4，继续扩展到下一个节点8，此时已无法继续扩展，且未找到目标节点，应返回到上一个节点4，同理继续返回上一个节点1，扩展到下一个节点3，继续扩展到下一个节点6，再扩展到下一个节点12，此时已找到目标节点，搜索完成，符合“从初始节点出发，按照一定的顺序不断扩展到下一个节点，直到不能再扩展”、“此时返回上一个节点重新寻找一个新的节点继续扩展，直到找到目标节点，或者搜索完所有节点为止”，符合定义，当选；

C项：1→3→5→3→7→3→6→12，图中显示，扩展到节点5时直接返回到上一个节点3，而节点5含有节点9和节点10两个下级节点，属于扩展不完整，不符合“从初始节点出发，按照一定的顺序不断扩展到下一个节点，直到不能再扩展”，不符合定义，排除；
D项：1→3→5→10→5→3→1→3→6→12，图中显示，从节点10返回到节点5时又返回到节点3，而节点5还含有节点9这一下级节点，返回到节点5时需要继续扩展到节点9，因此扩展顺序有误，不符合“此时返回上一个节点重新寻找一个新的节点继续扩展，如此搜索下去，直到找到目标节点，或者搜索完所有节点为止”，不符合定义，排除。
故正确答案为B。