该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

2025年 CSP-S 第一轮模拟练习试题

一、 单项选择题（共 15 题，每题 2 分，共计 30 分；每题有且仅有一个正确选项）

1. [2 分] 将 4 个相同的红球和 6 个相同的蓝球排成一排，要求任意两个红球都不相邻，有多少种不同的排列方法？ （ {{ select(1) }} ）

• 21
• 35
• 42
• 70

2. [2 分] 在 KMP 算法中，对于模式串 $P = \text{ababaca}$，其 next 数组（next[i] 定义为模式串 $P[0..i]$ 最长公共前后缀的长度，且数组下标从 0 开始）的值是什么？ （ {{ select(2) }} ）

• $\{0, 0, 1, 2, 3, 0, 1\}$
• $\{0, 1, 2, 3, 4, 0, 1\}$
• $\{0, 0, 1, 2, 3, 1, 1\}$
• $\{0, 0, 1, 2, 3, 0, 0\}$

3. [2 分] 对一个大小为 16（下标 $0 \sim 15$）的数组构建满线段树。查询区间 $[2, 13]$ 时，最少需要访问多少个树结点（包括路径上的父结点和完全包含在查询区间内的结点）？ （ {{ select(3) }} ）

• 7
• 8
• 9
• 10

4. [2 分] 将字符串 apple, apply, app, ape, bat, bag 插入一个空的 Trie 树（前缀树）中。构建完成的 Trie 树（包括根节点）共有多少个结点？ （ {{ select(4) }} ）

• 10
• 11
• 12
• 13

5. [2 分] 对于一个包含 $n$ 个结点和 $m$ 条边的有向无环图（DAG），如果它是连通的，且存在唯一的拓扑排序，那么它必须满足什么条件？ （ {{ select(5) }} ）

• 图中每个顶点的入度都必须大于 0
• 图中必须存在一条包含所有 $n$ 个顶点的有向路径（哈密顿路径）
• 图必须是一棵有向树
• 边数 $m$ 必须等于 $n(n-1)/2$

6. [2 分] 在一个大小为 11 的哈希表中，使用闭散列法的二次探查法（$H_i = (H(\text{key}) + i^2) \bmod 11$）来解决冲突。哈希函数为 $H(\text{key}) = \text{key} \bmod 11$。依次插入关键字 23, 34, 45, 12, 56。插入 56 后，它最终被放置在哪个索引位置？ （ {{ select(6) }} ）

• 4
• 6
• 8
• 10

7. [2 分] 一个包含 6 个顶点的完全图（顶点的编号为 1 到 6），任意两点之间的边权等于两顶点编号的乘积。该图的最小生成树总权重是多少？ （ {{ select(7) }} ）

• 15
• 20
• 21
• 25

8. [2 分] 如果一棵二叉树的中序遍历序列是 D B E A F C，后序遍历序列是 D E B F C A，那么该树的前序遍历是什么？ （ {{ select(8) }} ）

• A B D E C F
• A B E D C F
• A C F B D E
• A D B E F C

9. [2 分] 一个 $0-1$ 背包问题，背包容量为 15。现有 5 个物品，其重量和价值分别为 3, 4, 5, 6, 7 和 8, 10, 12, 15, 18。装入背包的物品能获得的最大总价值是多少？ （ {{ select(9) }} ）

• 35
• 37
• 38
• 40

10. [2 分] 在一棵以结点 1 为根的树中，已知结点 12 和结点 18 的最近公共祖先（LCA）是结点 4。那么下列哪个结点的 LCA 组合是不可能出现的？ （ {{ select(10) }} ）

• $LCA(12, 4) = 4$
• $LCA(18, 4) = 4$
• $LCA(12, 18, 4) = 4$
• $LCA(12, 1) = 4$

11. [2 分] 递归关系式 $T(n) = 3T(n/3) + O(n \log n)$ 描述了某个分治算法的时间复杂度。请问该算法的时间复杂度是多少？ （ {{ select(11) }} ）

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

12. [2 分] 在一个初始为空的最大堆（max-heap）中，依次插入元素 10, 25, 15, 30, 20, 5。然后连续执行两次“删除最大值”（delete-max）操作。请问此时堆顶元素是什么？ （ {{ select(12) }} ）

• 10
• 15
• 20
• 25

13. [2 分] 1 到 1000 之间，不能被 3, 5, 7 中任意一个数整除的整数有多少个？ （ {{ select(13) }} ）

• 456
• 457
• 458
• 459

14. [2 分] 在使用分治法求解最大子段和问题时，时间复杂度为 $O(n \log n)$，而使用动态规划（Kadane 算法）时间复杂度为 $O(n)$。造成这种差异的根本原因是？ （ {{ select(14) }} ）

• 分治法需要额外的递归调用栈空间
• 分治法在合并左右子区间时，需要 $O(n)$ 的时间计算跨越中点的最大子段和，存在重复计算；而动态规划通过状态转移避免了这种重复计算
• 动态规划使用了更少的数据存储空间
• 分治法无法处理包含负数的数组

15. [2 分] 有 4 个独立任务 $T_1, T_2, T_3, T_4$，处理时间分别为 2, 3, 4, 5，截止时刻分别为 3, 5, 6, 8。如果任务超时，惩罚为其处理时间。为了最小化总惩罚，应该采用哪种贪心策略？ （ {{ select(15) }} ）

• 优先执行处理时间最短的任务
• 优先执行截止时间最早的任务，若冲突则替换掉已选任务中处理时间最长的任务
• 优先执行处理时间最长的任务
• 优先执行截止时间最晚的任务

---

二、 阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填 A，错误填 B；除特殊说明外，判断题 1.5 分，选择题 3 分，共计 40 分）

（1）

#include <algorithm>
#include <cstdio>
#include <cstring>
bool flag[27];
int n;
int p[27];
int ans = 0;
void dfs(int k) {
    if (k == n + 1) {
        ++ans;
        return;
    }
    for (int i = 1; i <= n; ++i) {
        if (flag[i]) continue;
        if (k > 1 && i == p[k - 1] + 1) continue;
        p[k] = i;
        flag[i] = true;
        dfs(k + 1);
        flag[i] = false;
    }
    return;
}
int main() {
    scanf("%d", &n);
    dfs(1);
    printf("%d\n", ans);
    return 0;
}

判断题

16. [1 分] 当输入的 $n=3$ 的时候，程序输出的答案为 3。 （ {{ select(16) }} ）

• 正确
• 错误

17. [1.5 分] 在 dfs 函数运行过程中，$k$ 的取值会满足 $1 \le k \le n+1$。 （ {{ select(17) }} ）

• 正确
• 错误

18. [1.5 分] 删除第 19 行的 flag[i]=false;，对答案不会产生影响。 （ {{ select(18) }} ）

• 正确
• 错误

单选题

19. [3 分] 当输入的 $n=4$ 的时候，程序输出的答案为（ {{ select(19) }} ）。

• 11
• 12
• 24
• 9

20. [3 分] 如果因为某些问题，导致程序运行第 25 行的 dfs 函数之前，数组 p 的初值并不全为 0，则对程序的影响是（ {{ select(20) }} ）。

• 输出的答案比原答案要小
• 无法确定输出的答案
• 程序可能陷入死循环
• 没有影响

21. [3 分] 假如删去第 14 行的 if(flag[i]) continue;，输入 3，得到的输出答案是（ {{ select(21) }} ）。

• 27
• 3
• 16
• 12

（2）

#include <algorithm>
#include <cstdio>
#include <cstring>
#define ll long long
int cnt_broken = 0;
int cnt_check = 0;
int n, k;
inline bool check(int h) {
    printf("now check:%d\n", h);
    ++cnt_check;
    if (cnt_broken == 2) {
        printf("You have no egg!\n");
        return false;
    }
    if (h >= k) {
        ++cnt_broken;
        return true;
    } else {
        return false;
    }
}
inline bool assert_ans(int h) {
    if (h == k) {
        printf("You are Right using %d checks\n", cnt_check);
        return true;
    } else {
        printf("Wrong answer!\n");
        return false;
    }
}
inline void guess1(int n) {
    for (int i = 1; i <= n; ++i) {
        if (check(i)) {
            assert_ans(i);
            return;
        }
    }
}
inline void guess2(int n) {
    int w = 0;
    for (w = 1; w * (w + 1) / 2 < n; ++w)
        ;
    for (int ti = w, nh = w; --ti, nh += ti, nh = std::min(nh, n)) {
        if (check(nh)) {
            for (int j = nh - ti + 1; j < nh; ++j) {
                if (check(j)) {
                    assert_ans(j);
                    return;
                }
            }
            assert_ans(nh);
            return;
        }
    }
}
int main() {
    scanf("%d%d", &n, &k);
    int t;
    scanf("%d", &t);
    if (t == 1) {
        guess1(n);
    } else {
        guess2(n);
    }
    return 0;
}

注意：下述的"猜测数"为调用 check 函数的次数（即 cnt_check 的值）；"猜测正确"的含义为 assert_ans 函数 return true 的情况；所有输入保证 $1 \le k \le n$。

判断题

22. [1.5 分] 当输入为 "6 5 1" 时，猜测次数为 5；当输入为 "6 5 2" 时，猜测次数为 3。 （ {{ select(22) }} ）

• 正确
• 错误

23. [1.5 分] 不管输入的 $n$ 和 $k$ 具体为多少，$t=2$ 时的猜测数总是小于等于 $t=1$ 时的猜测数。 （ {{ select(23) }} ）

• 正确
• 错误

24. [1.5 分] 不管 $t=1$ 或 $t=2$，程序都一定会猜到正确结果。 （ {{ select(24) }} ）

• 正确
• 错误

单选题

25. [3 分] 函数 guess1 在运行过程中，cnt_broken 的值最多为（ {{ select(25) }} ）。

• 0
• 1
• 2
• $n$

26. [3 分] 函数 guess2 在运行过程中，最多使用的猜测次数的量级为（ {{ select(26) }} ）。

• $O(n)$
• $O(n^2)$
• $O(\sqrt{n})$
• $O(\log n)$

27. [3 分] 当输入的 $n=100$ 的时候，代码中 $t=1$ 和 $t=2$ 分别需要的猜测次数最多分别为（ {{ select(27) }} ）。

• 100, 14
• 100, 13
• 99, 14
• 99, 13

（3）

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#define ll long long
int n, m;
std::vector<int> k, p;
inline int mpow(int x, int k) {
    int ans = 1;
    for (; k; k >>= 1, x = x * x) {
        if (k & 1)
            ans = ans * x;
    }
    return ans;
}
std::vector<int> ans1, ans2;
int cnt1, cnt2;
inline void dfs(std::vector<int>& ans, int& cnt, int l, int r, int v) {
    if (l > r) {
        ++cnt;
        ans.push_back(v);
        return;
    }
    for (int i = 1; i <= m; ++i) {
        dfs(ans, cnt, l + 1, r, v + k[l] * mpow(i, p[l]));
    }
    return;
}
std::vector<int> cntans1;
int main() {
    scanf("%d%d", &n, &m);
    k.resize(n + 1);
    p.resize(n + 1);
    for (int i = 1; i <= n; ++i) {
        scanf("%d%d", &k[i], &p[i]);
    }
    dfs(ans1, cnt1, 1, n >> 1, 0);
    dfs(ans2, cnt2, (n >> 1) + 1, n, 0);
    std::sort(ans1.begin(), ans1.end());
    int newcnt1 = 1;
    cntans1.push_back(1);
    for (int i = 1; i < cnt1; ++i) {
        if (ans1[i] == ans1[newcnt1 - 1]) {
            ++cntans1[newcnt1 - 1];
        } else {
            ans1[newcnt1++] = ans1[i];
            cntans1.push_back(1);
        }
    }
    cnt1 = newcnt1;
    std::sort(ans2.begin(), ans2.end());
    int las = 0;
    ll ans = 0;
    for (int i = cnt2 - 1; i >= 0; --i) {
        for (; las < cnt1 && ans1[las] + ans2[i] < 0; ++las)
            ;
        if (las < cnt1 && ans1[las] + ans2[i] == 0)
            ans += cntans1[las];
    }
    printf("%lld\n", ans);
    return 0;
}

判断题

28. [1.5 分] 删除第 51 行的 std::sort(ans2.begin(), ans2.end()); 后，代码输出的结果不会受到影响。 （ {{ select(28) }} ）

• 正确
• 错误

29. [1.5 分] 假设计算过程中不发生溢出，函数 mpow(x, k) 的功能是求出 $x^k$ 的取值。 （ {{ select(29) }} ）

• 正确
• 错误

30. [1.5 分] 代码中第 39 行到第 50 行的目的是为了将 ans1 数组进行"去重"并统计频次的操作。 （ {{ select(30) }} ）

• 正确
• 错误

单选题

31. [3 分] 当输入为 3 15 1 2 -1 2 1 2 时，输出结果为（ {{ select(31) }} ）。

• 4
• 8
• 0
• 10

32. [3 分] 记程序结束前 $p$ 数组元素的最大值为 $P$，则该代码的时间复杂度是（ {{ select(32) }} ）。

• $O(n)$
• $O(m^n \log m^n)$
• $O(m^{n/2} \log m^{n/2})$
• $O(m^{n/2}(\log m^{n/2} + \log P))$

33. [3 分] 本题所求出的是（ {{ select(33) }} ）。

• 满足 $a, b, c \in [1, m]$ 的整数方程 $a^3 + b^3 = c^3$ 的解的数量
• 满足 $a, b, c \in [1, m]$ 的整数方程 $a^2 + b^2 = c^2$ 的解的数量
• 满足 $x_i \in [0, m]$ 的整数方程 $\sum_{i=1}^{n} k_i \cdot x_i^{p_i} = 0$ 的解的数量
• 满足 $x_i \in [1, m]$ 的整数方程 $\sum_{i=1}^{n} k_i \cdot x_i^{p_i} = 0$ 的解的数量

---

三、完善程序（单选题，每小题 3 分，共计 30 分）

（1）（特殊最短路）

给定一个含 $N$ 个点、$M$ 条边的带权无向图，边权非负。起点为 $S$，终点为 $T$。对于一条 $S$ 到 $T$ 的路径，可以在整条路径中，至多选择一条边作为"免费边"：当第一次经过这条被选中的边时，费用视为 0；如果之后再次经过该边，则仍按其原始权重计费。点和边均允许重复经过。求从 $S$ 到 $T$ 的最小总费用。

#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
 
const long long INF = 1e18;
 
struct Edge {
    int to;
    int weight;
};
 
struct State {
    long long dist;
    int u;
    int used_freebie; // 0 for not used, 1 for used
    bool operator>(const State &other) const {
        return dist > other.dist;
    }
};
 
int main() {
    int n, m, s, t;
    cin >> n >> m >> s >> t;
 
    vector<vector<Edge>> adj(n + 1);
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
 
    vector<vector<long long>> d(n + 1, vector<long long>(2, INF));
    priority_queue<State, vector<State>, greater<State>> pq;
 
    d[s][0] = 0;
    pq.push({0, s, __①__});
 
    while (!pq.empty()) {
        State current = pq.top();
        pq.pop();
 
        long long dist = current.dist;
        int u = current.u;
        int used = current.used_freebie;
        
        if (dist > __②__) {
            continue;
        }
 
        for (const auto &edge : adj[u]) {
            int v = edge.to;
            int w = edge.weight;
 
            if (d[u][used] + w < __③__) {
                __③__ = d[u][used] + w;
                pq.push({__③__, v, used});
            }
 
            if (used == 0) {
                if (__④__ < d[v][1]) {
                    d[v][1] = d[u][used];
                    pq.push({d[v][1], v, 1});
                }
            }
        }
    }
 
    cout << __⑤__ << endl;
    return 0;
}

34. [3 分] ① 处应填（ {{ select(34) }} ）

• 0
• 1
• -1
• false

35. [3 分] ② 处应填（ {{ select(35) }} ）

• d[u][!used]
• d[u][used]
• d[t][used]
• INF

36. [3 分] ③ 处应填（ {{ select(36) }} ）

• d[v][1]
• d[v][used]
• d[u][used]
• d[v][0]

37. [3 分] ④ 处应填（ {{ select(37) }} ）

• d[v][0]
• d[v][1]
• d[u][0]
• d[u][1]

38. [3 分] ⑤ 处应填（ {{ select(38) }} ）

• d[t][1]
• d[t][0]
• min(d[t][0], d[t][1])
• d[t][0] + d[t][1]

（2）（组合测试）

工厂打算通过客户反馈来间接测试生产线，从而找到存在缺陷的生产线。工厂有 $n$ 条生产线（编号 $0 \sim n-1$），已知其中恰有一条生产线存在缺陷。每一轮测试为，从若干生产线的产品取样混合成一个批次发给客户。若该批次中包含缺陷生产线的产品，客户将要求退货（结果记为 1），否则正常收货（记为 0）。受售后压力限制，在所有发货批次中，最多只能有 $k$ 次退货（即结果为 1 的次数 $\le k$）。工厂的目标是，设计最少的间接测试轮数 $w$（发货总批次），保证根据客户收货或退货的反馈结果，唯一确定存在缺陷的生产线。

#include <algorithm>
#include <cstddef>
#include <iostream>
#include <vector>
using namespace std;
 
long long comb(int w, int i) {
    if (i < 0 || i > w) {
        return 0;
    }
    long long res = 1;
    for (int t = 1; t <= i; ++t) {
        res = res * (w - t + 1) / t;
    }
    return res;
}
 
// 计算长度为 w、1 的个数 ≤ k 的码字总数
long long count_patterns(int w, int k) {
    long long total = 0;
    for (int t = 0; t <= min(w, k); ++t) {
        total += comb(w, t);
    }
    return total;
}
 
// 抽象测试接口
int test_subset(const vector<vector<int>> &plan);
 
int solve(int n, int k) {
    // === 第 1 步：求最小 w ===
    int w = 1;
    while (__①__) {
        ++w;
    }
    cout << w << endl;
 
    // === 第 2 步：生成测试方案 ===
    vector<vector<int>> code(n, vector<int>(w, 0));
    int idx = 0;
    for (int ones = 0; ones <= k && idx < n; ++ones) {
        vector<int> bits(w, 0);
        fill(bits.begin(), bits.begin() + ones, 1);
        do {
            for (int b = 0; b < w; ++b) {
                code[idx][b] = bits[b];
            }
            ++idx;
            if (idx >= n) {
                break;
            }
        } while (__②__);
    }
 
    vector<vector<int>> plan(w);
    for (int i = 0; i < w; ++i) {
        for (int j = 0; j < n; ++j) {
            if (__③__) {
                plan[i].push_back(j);
            }
        }
    }
 
    // === 第 3 步：调用测试接口 ===
    int signature = test_subset(plan);
 
    // === 第 4 步：结果解码 ===
    vector<int> sig_bits(w, 0);
    for (int i = 0; i < w; ++i) {
        if (__④__) {
            sig_bits[i] = 1;
        }
    }
 
    for (int j = 0; j < n; ++j) {
        if (__⑤__) return j;
    }
}
 
int main() {
    int n, k;
    cin >> n >> k;
    int ans = solve(n, k);
    cout << ans << endl;
    return 0;
}

39. [3 分] ① 处应填（ {{ select(39) }} ）

• (1 << w) < n
• count_patterns(w, k) < n
• count_patterns(k, w) < n
• comb(w, k) < n

40. [3 分] ② 处应填（ {{ select(40) }} ）

• next_permutation(bits.begin(), bits.end())
• prev_permutation(bits.begin(), bits.end())
• next_permutation(bits.begin(), bits.begin()+ones)
• prev_permutation(bits.begin(), bits.begin()+ones)

41. [3 分] ③ 处应填（ {{ select(41) }} ）

• (j >> i) & 1
• (i >> j) & 1
• code[i][j] == 1
• code[j][i] == 1

42. [3 分] ④ 处应填（ {{ select(42) }} ）

• (signature >> i) & 1
• (signature >> i) ^ 1
• signature | (1 << i)
• (signature >> i) | 1

43. [3 分] ⑤ 处应填（ {{ select(43) }} ）

• is_permutation(code[j].begin(), code[j].end(), sig_bits.begin())
• code[j] == sig_bits
• plan[j] == sig_bits
• code[j][i] == sig_bits[i]