CSP-S 提高级 · CSP 2020 提高级第一轮第 9 题

选择题 · 答案 C · 考点：队列(queue)、BFS(广度优先搜索)

题目

广度优先搜索时，一定需要用到的数据结构是( )

答案：C

这题考的是图遍历核心数据结构。拿到题先想BFS的‘层次’特性：必须按访问顺序依次扩展，所以得用FIFO的队列存待访问点，选C。

容易把BFS和DFS搞混，误选栈；或者觉得二叉树是BFS遍历对象，误选二叉树；还有人把哈希表当‘访问标记’就以为它也是BFS必需，其实哈希表只是辅助，BFS真正离不开的是队列。

这题考查广度优先搜索（BFS）的核心数据结构。BFS按层次遍历图：从起点开始，先访问距离起点最近的所有点（第1层），再访问次近的（第2层），依此类推。要实现这种“先访问的先扩展”的规律，必须用遵循先进先出（FIFO）原则的队列来存储待访问的顶点。

命题人喜欢把BFS和DFS的核心结构放在一起考，让你区分FIFO和LIFO；还会用“二叉树”这种BFS的常见对象来干扰，让你误以为二叉树是BFS必需的数据结构；偶尔也拿哈希表做“访问标记”来混淆，其实哈希表只是辅助，BFS真正离不开的是队列。

第 22 题· NOIP 2010 普及组初赛试题 · 答案 49看解析 →
第 2 题· NOIP 2012 普及组初赛试题 · 答案 B看解析 →
第 28 题· NOIP 2012 提高组初赛试题 · 答案 return(k%c)+1s[n]=q[tail]q[head]q[tail]next(head)看解析 →
第 28 题· NOIP 2016 提高组初赛试题 · 答案 dist[1]=0dist[x]+weight[j]<dist[point[j]]weight[j]+dist[x]<dist[point[j]]dist[point[j]]>weight[j]+dist[x]dist[point[j]]>dist[x]+weight[j]visit[x]=0weight[j]+dist[x]==dist[point[j]]dist[x]+weight[j]==dist[point[j]]visit[point[j]]=1看解析 →
第 19 题· CSP 2021 提高级第一轮 · 答案 DAC看解析 →

在 OI伴学里做这道题

登录后可计时作答、查看完整六段式解析，并按你的错题自动生成同类练习。