一、单项选择题（每题2分，共20分）

1、深度优先搜索（DFS）的核心特点是？（） {{ select(1) }}

• 一层一层向外扩展访问
• 只能用于排序问题
• 必须使用队列实现
• 能深则深，走不通就回溯退回上一层

2、广度优先搜索BFS一般依靠队列实现，深度优先DFS主要依靠什么实现？（） {{ select(2) }}

• 栈/递归
• 数组
• 哈希表
• 结构体

3、迷宫统计路径数量，走完一条路径回溯时vis数组应当如何处理？（） {{ select(3) }}

• 保持vis=1不改变
• 直接清空整个地图数组
• 将vis标记重置为0，撤销访问标记
• 直接终止全部递归

4、在迷宫DFS中dx[]、dy数组的主要作用是？（） {{ select(4) }}

• 存储迷宫地图障碍物
• 标记格子是否访问过
• 统计连通块的总个数
• 保存上下左右方向的坐标偏移量

5、全排列算法中box数组的作用是？（） {{ select(5) }}

• 标记数字是否被使用
• 保存当前已经选择的数字
• 存放方向偏移量
• 统计一共多少种方案

6、全排列递归函数，x == n+1表示什么含义？（） {{ select(6) }}

• 递归发生错误直接退出
• 只选好了第一个数字
• n个数字全部选取完毕，输出一组排列
• 所有数字均不可选用

7、全排列中vis[i]==1代表？（） {{ select(7) }}

• 数字i还未被选用
• 到达迷宫边界
• 递归可以直接return
• 数字i已经被选用

8、想要得到降序优先输出的全排列，在调用dfs前需要执行哪一步？（） {{ select(8) }}

• 将数组进行降序排序
• 将数组升序排序
• 把vis数组全部置1
• 修改方向数组dx dy

9、n个数选k个做组合（不生成重复序列），循环i应当从哪里开始？（） {{ select(9) }}

• 每次循环固定从下标1开始
• 随机选取下标
• 从上一次选中位置的下一个下标开始
• 固定等于k值

10、迷宫深度搜索，下面哪一项不属于合法搜索判断条件？（） {{ select(10) }}

• 新坐标不能超出地图边界
• 当前格子不能是障碍物
• 该格子没有被访问过
• 只要坐标存在就无条件递归

二、判断题（每题2分，共10分）

11、DFS深度搜索可以解决连通块统计、路径计数、全排列、组合问题。（） {{ select(11) }}

• 正确
• 错误

12、统计连通块时，允许同一个格子被DFS多次重复访问。（） {{ select(12) }}

• 正确
• 错误

13、全排列回溯过程，必须恢复vis标记，否则只能输出第一组方案。（） {{ select(13) }}

• 正确
• 错误

14、组合问题n选k，如果循环i允许回头选前面下标，会产生重复的组合方案。（） {{ select(14) }}

• 正确
• 错误

15、DFS递归如果没有合理终止条件，会造成栈溢出。（） {{ select(15) }}

• 正确
• 错误