Day8 CSP-J1 全真模拟①（重制版）·完善程序

共 2 个完整程序组、10 个空，每空 3 分，满分 30 分。每组均给出程序功能与变量含义。

第一组：统计无向图的连通块

---

程序功能

给定一个含 $n$ 个顶点、$m$ 条边的简单无向图，程序使用栈实现非递归深度优先遍历，并输出图的连通块数量。vis[v] 表示顶点 $v$ 是否已经被发现；每遇到一个尚未访问的起点 s，就开始遍历一个新的连通块。试补全程序。

#include <iostream>
#include <stack>
#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<bool> vis(n + 1, false);
    int components = 0;
    for (int s = 1; s <= n; ++s) {
        if (vis[s]) continue;
        ____①____;
        stack<int> st;
        st.push(____②____);
        vis[s] = true;
        while (!st.empty()) {
            int u = ____③____;
            st.pop();
            for (int v : g[u]) {
                if (____④____) {
                    vis[v] = true;
                    ____⑤____;
                }
            }
        }
    }
    cout << components;
    return 0;
}

第 1 题

①处应填（ {{ select(1) }} ）。

• components=0
• ++components
• --components
• components+=n

---

第 2 题

②处应填（ {{ select(2) }} ）。

• 1
• n
• u
• s

---

第 3 题

③处应填（ {{ select(3) }} ）。

• st.top()
• st.size()
• st.empty()
• s

---

第 4 题

④处应填（ {{ select(4) }} ）。

• v==s
• vis[v]
• !vis[v]
• g[v].empty()

---

第 5 题

⑤处应填（ {{ select(5) }} ）。

• st.pop()
• st.push(v)
• st.push(u)
• components++

---

第二组：一维 0/1 背包

---

程序功能

有 $n$ 件物品和容量为 $W$ 的背包，第 $i$ 件物品重量为 w[i]、价值为 v[i]，每件最多选择一次。dp[j] 表示已处理物品中，在总重量不超过 $j$ 时能取得的最大价值。程序输出容量为 $W$ 时的最大价值。试补全程序。

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

int main() {
    int n, W;
    cin >> n >> W;
    vector<int> w(n + 1), v(n + 1);
    for (int i = 1; i <= n; ++i) cin >> w[i] >> v[i];

    vector<int> dp(____①____, 0);
    for (int i = 1; i <= n; ++i) {
        for (int j = ____②____; ____③____; --j) {
            dp[j] = max(dp[j], ____④____);
        }
    }
    cout << ____⑤____;
    return 0;
}

第 6 题

①处应填（ {{ select(6) }} ）。

• n+1
• W
• W+1
• n*W

---

第 7 题

②处应填（ {{ select(7) }} ）。

• W
• 0
• w[i]
• n

---

第 8 题

③处应填（ {{ select(8) }} ）。

• j<=W
• j>0
• j>=0
• j>=w[i]

---

第 9 题

④处应填（ {{ select(9) }} ）。

• dp[j]+v[i]
• dp[j-w[i]]+v[i]
• dp[j-1]+w[i]
• v[j]

---

第 10 题

⑤处应填（ {{ select(10) }} ）。

• dp[W]
• dp[n]
• dp[0]
• v[n]

---