朝外信奥1队 2026-05-31 小测试（CSP-S 2024 第 4 套）

答案版（绿色为正确答案，附简要解析）
题型：单选 15 + 阅读程序 12 + 完善程序 5
题量：32 题
用途：课堂讲评 / LearnDash 嵌入
一、单项选择题（共 15 题）
每题只有一个正确选项，绿色为正确答案。
1. 运行如下代码的输出结果是（ ）
第 1 题代码
C++
1 char c = '0' + ' ';
2 cout << c << endl;
A. 0
B. P
C. 48
D. 80
答案：B。'0' 的 ASCII 为 48，空格 ' ' 为 32，相加得 80，char 按 ASCII 输出字符 'P'。
2. 以下代码段的功能是（ ）
第 2 题代码
C++
1 #include <iostream>
2 using namespace std;
3 int Lowbit(int x) {
4 return (x & -x);
5 }
6 int main() {
7 int n, res = 0;
8 cin >> n;
9 while (n) {
10 n -= Lowbit(n);
11 res++;
12 }
13 cout << res;
14 return 0;
15 }
A. 求该数转为二进制后各位上 1 的总数
B. 求该数转为二进制的反码
C. 求该数转为二进制的补码
D. 求该数转为二进制的原码
答案：A。Lowbit(x) 返回 x 的二进制表示中最低位的 1 所对应的值。循环中执行 n -= Lowbit(n)，每次都会恰好消去二进制里的一个 1，因此循环次数正好等于该数二进制中 1 的个数（popcount）。
3. 前缀表达式 - * + 1 34 5 / 56 7 的后缀表达式为（ ）。
A. 1 + 34 * 5 - 56 / 7
B. - * + 1 34 5 / 56 7
C. 1 34 + 5 * 56 7 / -
D. 1 345 * + 567 / -
答案：C。前缀结构为 -( *(+(1,34),5), /(56,7) )，转后缀即 1 34 + 5 * 56 7 / -。
4. 对于序列 7, 4, 1, 9, 3, 6, 8, 5，其中有（ ）个逆序对。
A. 10
B. 11
C. 12
D. 13
答案：D。逐对统计可得该序列共有 13 个逆序对。
5. 以下哪个操作不属于 STL 中双端队列 deque 的操作函数？（ ）
A. front
B. back
C. top
D. erase
答案：C。deque 没有 top()；top() 属于 stack / priority_queue。
6. 下列问题或算法的典型解法中，通常不以贪心思想作为核心的是（ ）。
A. 用 Kahn 算法求拓扑序
B. 用 Kruskal 算法求最小生成树
C. 求部分背包问题的最优解
D. 用 KMP 算法进行字符串匹配
答案：D。KMP 基于失配（前缀函数）匹配，不属于贪心思想。
7. 农夫运狼、羊、白菜过河，船每次只能带一样，最少需要几次渡河（单程计）？（ ）
A. 5
B. 6
C. 7
D. 8
答案：C。具体过程为：1. 先把羊运到对岸；2. 农夫空船返回；3. 把狼运到对岸；4. 把羊再带回原岸；5. 把白菜运到对岸；6. 农夫空船返回；7. 最后把羊运到对岸。共 7 次，且全过程都不会出现“狼和羊单独在一起”或“羊和白菜单独在一起”的情况。
8. 5 x 5 棋盘从左下角到右上角（只能向右/向上、避开 x 格）共有（ ）条路径。
棋盘示意
grid
1 +---+---+---+---+---+
2 | | x | | | |
3 +---+---+---+---+---+
4 | | | | x | |
5 +---+---+---+---+---+
6 | | | | | |
7 +---+---+---+---+---+
8 | | | x | | |
9 +---+---+---+---+---+
10 | O | | | | |
11 +---+---+---+---+---+
A. 10
B. 11
C. 12
D. 13
答案：D。按路径数 DP 累加并避开 x 格：起点为 1，障碍格记为 x，每个普通格子的路径数等于左边格子与下边格子的路径数之和。自下而上得到各行路径数为 1 1 1 1 1、1 2 x 1 2、1 3 3 4 6、1 4 7 x 6、1 x 7 7 13，所以到达右上角共有 13 条路径。13 种走法如下（右=向右走一格，上=向上走一格）：
1. 右右右右上上上上
2. 右右右上右上上上
3. 右右右上上右上上
4. 右上上右右右上上
5. 右上上右上上右右
6. 右上上上右上右右
7. 上右上右右右上上
8. 上右上右上上右右
9. 上右上上右上右右
10. 上上右右右右上上
11. 上上右右上上右右
12. 上上右上右上右右
13. 上上上右右上右右
9. 关于图论，下面说法正确的是（ ）。
A. 欧拉通路有一个奇点
B. 欧拉回路有两个奇点
C. 对于无向图，若任意一对顶点都连通，则称为连通图
D. 不存在割点的无向图称为“2-边连通图”
答案：C。连通图的定义即任意一对顶点都连通；A、B 表述有误，D 应为“2-点连通图”。
10. 用 V = (p1, ..., p5) 表示无向图 5 个顶点的度数，下面哪组合理？（ ）
A. (5, 3, 3, 3, 1)
B. (2, 2, 2, 1, 1)
C. (3, 3, 3, 2, 2)
D. (1, 4, 3, 2, 5)
答案：B。度数之和必为偶数且每个度 ≤ n-1=4；只有 (2,2,2,1,1) 满足（和为 8）。
11. 下述选项哪个不属于与典型图论有关的算法？（ ）
A. 线段树
B. 次小生成树
C. 最小生成树
D. 单源最短路径
答案：A。线段树是区间数据结构，与典型图论算法无关。
12. 有如下递归代码，则 fun(30, 30) 的结果为（ ）。
第 12 题代码
C++
1 int fun(int a, int b) {
2 if (a == 1) return 1;
3 return 9 * fun(a - 1, b) % b;
4 }
A. 9
B. 18
C. 21
D. 27
答案：A。fun(a,b)=9^(a-1) mod b；9 的幂模 30 在 9 与 21 间循环，指数 29 为奇数，结果为 9。
13. 6 道选择题、4 道判断题，甲乙依次各抽 1 题，至少一人抽到选择题的概率是（ ）。
A. 4/15
B. 13/15
C. 4/5
D. 11/15
答案：B。P = 1 - 两人都抽判断题 = 1 - (4/10)(3/9) = 1 - 12/90 = 13/15。
14. 用 4 种颜色给图中 6 个点涂色，相邻端点颜色不同，不同涂色方法有（ ）种。（配图见原卷）
A. 288
B. 264
C. 240
D. 168
答案：B。按图的相邻约束计数，合法染色方案共 264 种。
15. 1800 的所有约数之和为（ ）。
A. 6043
B. 6044
C. 6045
D. 6046
答案：C。1800 = 2³·3²·5²，约数和 = (1+2+4+8)(1+3+9)(1+5+25) = 15·13·31 = 6045。
二、阅读程序题
（一）阅读下面的程序，回答 16~21 题
代码解析：这段程序主要考查 快速幂 + 模运算 + 按位数分段统计。其中 qpow 用二进制快速幂计算幂模，add 用一次减法完成取模，calc(n) 统计从 1 到 n 的十进制位数总和，因此整题本质是在把若干计数公式拼起来求值，时间复杂度是 O(log n)。
阅读程序（一）
C++
1 #include <bits/stdc++.h>
2 using namespace std;
3 const int mod = 1e4;
4 int n;
5 int ans;
6
7 inline int qpow(int a, int b) {
8 int res = 1;
9 for (; b; b >>= 1, a = 1LL * a * a % mod)
10 if (b & 1) res = 1LL * res * a % mod;
11 return res;
12 }
13
14 inline void add(int &x, const int &y) {
15 x += y;
16 if (x >= mod) x -= mod;
17 }
18
19 inline int calc(int n) {
20 int res = 0;
21 int c = 1, x = 1;
22 for (; x * 10 - 1 <= n; ++c, x *= 10)
23 add(res, 9LL * x * c % mod);
24 add(res, 1LL * c * (n - x + 1) % mod);
25 return res;
26 }
27
28 int main() {
29 cin >> n;
30 if (n == 1) return puts("4"), 0;
31 ans = n % mod;
32 add(ans, 1LL * qpow(2, n - 1) * n % mod);
33 add(ans, (calc(n) - 1 + mod) % mod);
34 add(ans, 1LL * qpow(2, n - 1) * calc(n) % mod);
35 add(ans, (qpow(2, n) - 1 + mod) % mod);
36 add(ans, 2 * (n - 1) % mod);
37 cout << ans << endl;
38 return 0;
39 }
16. 第 14 行的两个 & 符号作用一致。（ ）
A. true
B. false
答案：A。第 14 行 int &x 与 const int &y 两处 & 均表示引用，作用一致。
17. 第 16 行等价于把 x 对 mod 取模，只是更慢。（ ）
A. true
B. false
答案：A。相加前 x、y 均小于 mod，结果小于 2·mod，一次减法即可完成取模，效果与 %mod 相同。
18. 输入为 5 的时候，输出为 209。（ ）
A. true
B. false
答案：B。代入 n=5 实际计算，输出并非 209。
19. 输入每增加 1，输出都会扩大 2 倍以上。（ ）
A. true
B. false
答案：B。结果中含 n、calc(n) 等线性增长项，并非每次都扩大 2 倍以上。
20. 输入为 0 的时候，程序会（ ）。
A. 输出乱码
B. 死循环
C. 输出 0
D. 输出 -1
答案：B。n=0 时调用 qpow(2,-1)，b=-1 算术右移恒为 -1，for 循环条件永真，导致死循环。
21. 本程序的时间复杂度为（ ）。
A. O(log N)
B. O(log log N)
C. O(N)
D. O(log^2 N + log N)
答案：A。qpow 为 O(log N)，calc 为 O(log N)，整体 O(log N)。
（二）阅读下面的程序，回答 22~27 题
代码解析：这段程序主要考查 线性筛/最小质因子预处理 + 区间统计。数组 o[i] 记录每个数的最小质因子，筛完以后程序在区间 [l,r] 中枚举所有合数，并把 i / o[i] 累加到答案里，所以核心是“先筛出质数与最小质因子，再对区间内的合数做统一统计”。
阅读程序（二）
C++
1 #include <bits/stdc++.h>
2 using namespace std;
3 typedef long long i64;
4 const int NN = 1e7 + 5;
5 i64 ans, l, r;
6 bool s[NN];
7 int p[NN], o[NN], cnt;
8
9 inline void sss() {
10 o[1] = 1;
11 for (int i = 2; i <= r; ++i) {
12 if (!s[i]) o[p[++cnt] = i] = i;
13 for (int j = 1; j <= cnt && p[j] * i <= r; ++j) {
14 s[p[j] * i] = true;
15 o[p[j] * i] = p[j];
16 if (i % p[j] == 0) break;
17 }
18 }
19 }
20
21 inline void answer() {
22 sss();
23 for (int i = l; i <= r; ++i)
24 if (s[i]) ans += i / o[i];
25 cout << ans << endl;
26 }
27
28 int main() {
29 cin >> l >> r;
30 answer();
31 }
22. 本题使用了埃氏筛法。（ ）
A. true
B. false
答案：B。代码每个合数只被其最小质因子筛去（见第 16 行 break），是线性筛（欧拉筛），不是埃氏筛。
23. 如果输入数据 l > r，那么程序会报错或者发生死循环。（ ）
A. true
B. false
答案：B。l>r 时统计循环 i=l..r 不执行，直接输出 ans=0，不会报错或死循环。
24. 本程序可以处理的最大 r 是 10000000。（ ）
A. true
B. false
答案：B。r 接近 1e7 时 p[j] * i 用 int 运算会溢出，无法正确处理到 1e7，题述绝对说法不成立。
25. 在确保 l <= r 的前提下，l 的大小不影响程序的运行速度。（ ）
A. true
B. false
答案：B。统计循环 i=l..r 的次数随 l 变化，故 l 会影响运行速度，题述错误。
26. 当输入为 6 27 时，输出为（ ）。
A. 115
B. 116
C. 117
D. 118
答案：C。对 [6,27] 内每个合数 i 累加 i / o[i]（o[i] 为最小质因子），求和得 117。
27. 本程序的时间复杂度为（ ）。
A. O(log N)
B. O(N)
C. O(log log N)
D. O(N log log N)
答案：B。线性筛 O(r) 加统计 O(r-l)，整体为 O(N)。
三、完善程序（回答 28~32 题）
输入一系列短棍长度（≤64 根，长度≤50），求原始等长木棒的最小可能长度，使用搜索加剪枝。
代码解析：这道完善程序题的核心是 DFS + 回溯 + 剪枝。程序按从大到小的顺序尝试拼出每根原木棒，cab 表示当前这根木棒已经拼出的长度，last 控制下一段短棍的搜索起点，fail 用来跳过同长度的重复失败分支；其中“当前木棒一开始就失败”或“正好拼满仍失败”都会触发强剪枝，因此这是典型的木棒拼接搜索题。
完善程序（木棒）
C++
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 int a[100], v[100], n, len, cnt;
5 bool dfs(int stick, int cab, int last) {
6 if (stick > cnt) return true;
7 if (cab == len) return dfs(stick + 1, 0, 1);
8 int fail = 0;
9 for (28. __________) {
10 if (!v[i] && cab + a[i] <= len && fail != a[i]) {
11 v[i] = 1;
12 if (dfs(stick, cab + a[i], i + 1)) return true;
13 29. __________;
14 v[i] = 0;
15 if (30. __________ || 31. __________) return false;
16 }
17 }
18 return false;
19 }
20
21 int main() {
22 while (cin >> n && n) {
23 int sum = 0, val = 0;
24 for (int i = 1; i <= n; i++) {
25 scanf("%d", &a[i]);
26 sum += a[i];
27 val = max(val, a[i]);
28 }
29 sort(a + 1, a + n + 1);
30 reverse(a + 1, a + n + 1);
31 for (len = val; len <= sum; len++) {
32 if (sum % len) continue;
33 cnt = sum / len;
34 memset(v, 0, sizeof(v));
35 if (32. __________) break;
36 }
37 cout << len << endl;
38 }
39 return 0;
40 }
28. 28. 处应填（ ）。
A. int i = n; i >= last; i--
B. int i = last; i <= n; i++
C. int i = last + 1; i <= n; i++
D. int i = n; i >= last + 1; i--
答案：B。木棒按长度降序排序，从下标 last 开始枚举可避免重复排列。
29. 29. 处应填（ ）。
A. fail += a[i]
B. a[i] = fail
C. fail = cab + a[i]
D. fail = a[i]
答案：D。记录本次失败所用的棍长，后续相同长度的棍直接跳过（与第 10 行 fail != a[i] 配合剪枝）。
30. 30. 处应填（ ）。
A. cab == 0
B. cab == a[i]
C. a[last] == fail
D. last == 0
答案：A。若当前木棒第一根（cab==0）就尝试失败，说明整体无解，直接剪枝返回。
31. 31. 处应填（ ）。
A. cab + a[i] <= len
B. a[i] == fail
C. cab + a[i] == len
D. a[i] > cab / 2
答案：C。若放入这根棍恰好填满木棒却仍失败，则该方案无望，直接剪枝。
32. 32. 处应填（ ）。
A. dfs(0, 0, 1)
B. dfs(1, 0, 1)
C. dfs(0, 0, 0)
D. dfs(1, 1, 1)
答案：B。从第 1 根木棒、当前长度 0、起始下标 1 开始搜索。