Day 14　图的存储、遍历与洪水填充

建议用时：24～30 分钟。请先打开今日知识卡完成复习，再独立提交本页答案。

今日学习资料

• 打开今日蓝白学习页
• 下载今日 PDF

复习目标：理解邻接矩阵和邻接表，分清 DFS 与 BFS，知道怎样把网格看成图，并能追踪按编号访问的 BFS 程序。

今日练习

1. 【CSP-J 2021·第 14 题｜原图关系重绘】无向图的边为 (a,b),(a,c),(b,d),(c,d),(c,e)。以 a 为起点进行深度优先遍历，b,c,d,e 中有可能成为最后一个被访问顶点的共有（　）个。

{{ select(1) }}

• 1
• 2
• 3
• 4

2. 【CSP-J 2022·第 10 题】以下关于数据结构的说法不恰当的是（　）。

{{ select(2) }}

• 图的深度优先遍历常使用栈
• 栈后进先出，队列先进先出
• 队列常用于广度优先搜索
• 栈与队列本质不同，无法用栈实现队列

3. 【大纲内巩固】无向图的邻接矩阵一定具有的性质是（　）。

{{ select(3) }}

• 所有元素都为 1
• 关于主对角线对称
• 每一行元素和都相等
• 主对角线元素都为 1

4. 在一个由 0 和 1 组成的网格中，从某个值为 1 的格子开始做四方向 Flood Fill，主要目的是（　）。

{{ select(4) }}

• 把所有格子按数值排序
• 访问与起点四方向连通的所有 1
• 用二分查找寻找起点
• 只访问起点所在的一行

5. DFS 和 BFS 的具体访问顺序都可能受到邻接点排列顺序的影响。（判断对错）

{{ select(5) }}

• 正确
• 错误

主题程序阅读

阅读下面的程序：

#include <iostream>
#include <queue>
using namespace std;

int g[6][6];
bool vis[6];

void addEdge(int u, int v) {
    g[u][v] = g[v][u] = 1;
}

int main() {
    addEdge(1, 2);
    addEdge(1, 3);
    addEdge(2, 4);
    addEdge(3, 4);
    addEdge(4, 5);

    queue<int> q;
    q.push(1);
    vis[1] = true;

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        cout << u << ' ';
        for (int v = 1; v <= 5; ++v) {
            if (g[u][v] && !vis[v]) {
                vis[v] = true;
                q.push(v);
            }
        }
    }
    return 0;
}

6. 程序输出（　）。

{{ select(6) }}

• 1 2 3 4 5
• 1 2 4 5 3
• 1 3 4 5 2
• 5 4 3 2 1

7. 在程序构造的图中，从顶点 1 到顶点 5 的最少边数是 3。（判断对错）

{{ select(7) }}

• 正确
• 错误

8. 若删除 addEdge(4, 5);，程序将不会输出顶点 5。（判断对错）

{{ select(8) }}

• 正确
• 错误