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

1、广度优先搜索BFS依靠下面哪个容器实现？（） {{ select(1) }}

• stack栈
• queue队列
• vector动态数组
• string字符串

2、BFS搜索特点描述正确的是？（） {{ select(2) }}

• 能深则深，走不通就回退
• 逐层向外扩散，一层一层搜索
• 必须使用递归实现
• 搜索过的点可以反复入队

3、BFS中结构体node的作用是？（） {{ select(3) }}

• 只存地图障碍物数量
• 保存格子的行x、列y坐标
• 用来统计连通块面积
• 存储方向数组dx、dy

4、BFS入队的时候对vis标记数组操作正确的是？（） {{ select(4) }}

• 取出队首之后再标记vis=1
• 入队的同时立刻设置vis=1
• 全程不需要vis数组
• vis只标记终点位置

5、4方向数组dx[4]={1,0,-1,0},dy[4]={0,1,0,-1}代表的顺序是？（） {{ select(5) }}

• 上、右、下、左
• 下、右、上、左
• 下、左、上、右
• 上、左、下、右

6、BFS循环条件，继续搜索的条件是？（） {{ select(6) }}

• while(!q.empty())
• while(q.empty())
• while(q.size()==0)
• while(q.front()>0)

7、多组测试数据做BFS，不需要做下面哪一项？（） {{ select(7) }}

• 清空队列q
• vis数组全部重置为0
• 直接复用上次队列和vis
• 读取本组地图数据

8、迷宫寻宝，起点本身就是障碍物，应当如何处理？（） {{ select(8) }}

• 正常把起点入队再搜索
• 直接输出NO，不用执行BFS
• 修改起点为通路再入队
• 跳过起点直接搜索相邻点

9、求岛屿连通块面积，每遇到合法可走格子入队，需要？（） {{ select(9) }}

• ans计数器自增统计格子数量
• 判断是否等于宝藏数字2
• 直接return结束程序
• 不需要任何计数操作

10、BFS中q.pop()功能描述正确的是？（） {{ select(10) }}

• 获取队首元素坐标
• 删除队首元素，不返回数据
• 在队尾添加新元素
• 判断队列是否为空

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

11、BFS广度优先逐层搜索，起点不计入层数，第一步走到的点属于第一层。（） {{ select(11) }}

• 正确
• 错误

12、BFS可以递归实现，DFS必须使用队列实现。（） {{ select(12) }}

• 正确
• 错误

13、BFS如果等到取出队首才标记vis，会出现同一个点多次重复入队。（） {{ select(13) }}

• 正确
• 错误

14、统计整张地图连通块数量，需要双重循环遍历地图，遇到合法未访问点启动BFS。（） {{ select(14) }}

• 正确
• 错误

15、BFS判断新坐标nx,ny，只需要判断不越界就可以直接入队。（） {{ select(15) }}

• 正确
• 错误