Day6 课后 A4-A6 BFS 与 DP（重制版·20题）

包含基础辨析、完整 BFS 程序阅读、线性 DP 程序阅读和 0/1 背包程序阅读。

所有程序均使用数组或 STL 容器，不涉及指针。

一、基础辨析

---

第 1 题

在一般图的 BFS 中，通常应在什么时候把顶点标记为已访问（ {{ select(1) }} ）。

• 从队列中弹出时
• 第一次加入队列时
• 扫描完它的所有邻边后
• 整个 BFS 结束后

---

第 2 题

使用邻接表对一个含 $n$ 个顶点、$m$ 条边的无向图执行一次完整 BFS，时间复杂度是（ {{ select(2) }} ）。

• $O(1)$
• $O(n)$
• $O(n+m)$
• $O(n^2)$

---

第 3 题

使用邻接矩阵执行一次完整 BFS，即使图很稀疏，最坏时间复杂度仍是（ {{ select(3) }} ）。

• $O(\log n)$
• $O(n)$
• $O(n+m)$
• $O(n^2)$

---

第 4 题

阅读动态规划程序时，首先明确 dp[i] 的含义，主要是为了（ {{ select(4) }} ）。

• 判断状态、转移、初值和答案位置是否一致
• 保证数组下标一定从 1 开始
• 把所有循环改成倒序
• 避免使用任何额外空间

---

第 5 题

一维 0/1 背包中，容量通常从大到小枚举，主要是为了（ {{ select(5) }} ）。

• 让物品按价值排序
• 使背包必须恰好装满
• 防止同一件物品在本轮被重复使用
• 把复杂度降为 $O(n)$

---

第 6 题

在同一个无权图中，仅改变邻接表中邻居的排列顺序，最可能出现的情况是（ {{ select(6) }} ）。

• 各点最短距离一定改变
• BFS 树可能改变，但各点最短距离不变
• BFS 不再需要队列
• 时间复杂度变成指数级

---

二、完整程序组一：BFS 最短距离与最短路条数

---

程序功能

程序读入一个简单无向图，从顶点 1 开始 BFS。dist[v] 表示从 1 到 $v$ 的最少边数，ways[v] 表示达到该最短距离的不同路径条数。输入保证顶点编号为 $1\sim n$。

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

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> g(n + 1);
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    vector<int> dist(n + 1, -1);
    vector<int> ways(n + 1, 0);
    queue<int> q;
    dist[1] = 0;
    ways[1] = 1;
    q.push(1);

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : g[u]) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                ways[v] = ways[u];
                q.push(v);
            } else if (dist[v] == dist[u] + 1) {
                ways[v] += ways[u];
            }
        }
    }

    cout << dist[5] << " " << ways[5] << " "
         << dist[6] << " " << ways[6];
    return 0;
}

第 7 题

输入如下：

6 6
1 2
1 3
2 4
3 4
4 5
3 6

程序输出（ {{ select(7) }} ）。

• 2 1 3 2
• 3 1 2 2
• 2 2 2 1
• 3 2 2 1

---

第 8 题

程序使用 dist[v] == -1 判断（ {{ select(8) }} ）。

• 顶点 $v$ 是否尚未被发现
• 顶点 $v$ 是否没有邻边
• 顶点 $v$ 是否为起点
• 从 1 到 $v$ 是否存在两条路径

---

第 9 题

若删去 dist[v] == -1 的限制，使每次扫描到邻居都重新入队，最直接的问题是（ {{ select(9) }} ）。

• 所有距离都会变为 0
• 同一顶点可能反复入队，甚至无法结束
• 图会自动变成有向图
• 空间复杂度一定变为 $O(1)$

---

第 10 题

使用邻接表时，这段 BFS 的时间复杂度是（ {{ select(10) }} ）。

• $O(1)$
• $O(n)$
• $O(n+m)$
• $O(n^2)$

---

第 11 题

变量 ways[v] 的准确含义是（ {{ select(11) }} ）。

• 从顶点 1 到 $v$ 的最短路径条数
• 从顶点 1 到 $v$ 的所有不重复路径条数
• 顶点 $v$ 的度数
• 顶点 $v$ 被加入队列的次数

---

第 12 题

对给定样例，若删除 else if 分支，输出中的 ways[5] 将变为（ {{ select(12) }} ）。

• $0$
• $2$
• $3$
• $1$

---

三、完整程序组二：最大不相邻元素和

---

程序功能

给定 $n$ 个正整数，从中选择若干个数，要求不能同时选择相邻位置的两个数，并使所选数字之和最大。dp[i] 表示只考虑前 $i$ 个数时能够得到的最大和。输入保证 $n\ge1$。

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

int main() {
    int n;
    cin >> n;
    vector<int> a(n + 1), dp(n + 1, 0);
    for (int i = 1; i <= n; ++i) cin >> a[i];

    dp[1] = a[1];
    for (int i = 2; i <= n; ++i)
        dp[i] = max(dp[i - 1], dp[i - 2] + a[i]);

    cout << dp[n];
    return 0;
}

第 13 题

输入 5 3 2 7 10 12 时，程序输出（ {{ select(13) }} ）。

• $15$
• $17$
• $22$
• $24$

---

第 14 题

状态 dp[i] 表示（ {{ select(14) }} ）。

• 必须选择第 $i$ 个数时的最大和
• 只考虑前 $i$ 个数且不选相邻位置时的最大和
• 前 $i$ 个数的普通前缀和
• 恰好选择 $i$ 个数时的最大和

---

第 15 题

转移中 dp[i-2]+a[i] 对应的决策是（ {{ select(15) }} ）。

• 不选择第 $i$ 个数
• 同时选择第 $i-1$ 和第 $i$ 个数
• 删除前两个数
• 选择第 $i$ 个数，因此不能选择第 $i-1$ 个数

---

第 16 题

程序关于 $n$ 的时间复杂度是（ {{ select(16) }} ）。

• $O(n)$
• $O(\log n)$
• $O(n^2)$
• $O(2^n)$

---

四、完整程序组三：一维 0/1 背包

---

程序功能

有 $n$ 件物品和容量为 $W$ 的背包，每件物品有重量 $w$ 和价值 $v$，每件最多选择一次。dp[j] 表示已处理物品中，在总重量不超过 $j$ 时能获得的最大价值。

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

int main() {
    int n, W;
    cin >> n >> W;
    vector<int> dp(W + 1, 0);
    for (int i = 1; i <= n; ++i) {
        int w, v;
        cin >> w >> v;
        for (int j = W; j >= w; --j)
            dp[j] = max(dp[j], dp[j - w] + v);
    }
    cout << dp[W];
    return 0;
}

第 17 题

输入 4 7 2 3 3 4 4 5 5 8 时，程序输出（ {{ select(17) }} ）。

• $9$
• $11$
• $12$
• $14$

---

第 18 题

若容量循环误写成 for(int j=w;j<=W;++j)，程序可能出现（ {{ select(18) }} ）。

• 每件物品仍恰好使用一次
• 所有物品都无法选择
• 程序一定越界
• 同一件物品在一轮中被重复使用

---

第 19 题

dp[j] 的准确含义是（ {{ select(19) }} ）。

• 总重量恰好等于 $j$ 时的物品数量
• 处理第 $j$ 件物品后的总重量
• 容量不超过 $j$ 时能够得到的最大价值
• 价值不超过 $j$ 时的最小重量

---

第 20 题

该程序的时间复杂度是（ {{ select(20) }} ）。

• $O(nW)$
• $O(n+m)$
• $O(W\log n)$
• $O(2^n)$

---