【CSP-S 第一轮】2026非专业软件能力认证原卷和答案
本帖最后由 高山 于 2026-9-20 22:00 编辑【CSP-S第一轮】2026年卷
原卷和答案
序言
本系列旨在帮助鱼油复习和了解CSP-S 第一轮试卷的内容，并协助鱼油开展对第二轮的练习。针对第一轮，现已完成考试，本系列将逐步解析试卷。针对第二轮，我们将逐步讲解洛谷往年真题，鱼油们可以对此开展学习。
对于本系列的所有内容，您可以打开淘专辑进行学习，快速查找您所需要的内容。为了鼓励鱼油们参与题目的思考，您回复本帖，解锁答案时，将获取回帖奖励。同时，针对于较优质的思考，我们还会同时进行评分奖励。本帖旨在帮您回顾原卷和答案。如您需要详细的解析，请关注本淘专辑系列，我们将通过详细的动画为您逐题讲解。您可通过「目录」选择试卷和答案部分进行核对。为了方面您记忆，我们已将答案融入试卷中。
如您习惯直接展示全文，可点击下方【查看全文】按钮直接阅读帖子，无需根据题型选择。
（感谢洛谷提供试卷和答案，题目版权属于CCF，本次提供的内容可能与原卷有所不同，后期逐题解析可能与洛谷答案或CCF标准答案有所不同，这里仅供帮助鱼油快速核对试卷和答题内容）
（题目来源于洛谷chen_zhe，本帖进行了排版）
一、单项选择题
共 15 题，每题 2 分，共计 30 分；每题有且仅有一个正确选项。
题号答案题号答案题号答案
1D6C11C
2D7A12C
3C8B13B
4D9A14C
5A10D15B
1. 执行下列代码后，cnt 的值是（ D ）。
int x = 2026, cnt = 0;
while (x) {
x &= x - 1;
cnt++;
}A. 6 B. 7 C. 11 D. 8
2. 用权值 {1, 2, 3, 4, 5, 6, 7, 8} 构造哈夫曼树，其带权路径长度是（ D ）。
A. 108 B. 96 C. 99 D. 102
3. 把 1 到 1000 的所有整数按十进制写出，数字“1”总共出现了多少次（ C ）。
A. 300 B. 271 C. 301 D. 320
4. 将 5 封信随机装入 5 个写好地址的信封（每封一个），恰好有 2 封装对的方案数是（ D ）。
A. 44 B. 24 C. 10 D. 20
5. 3^2026 mod 100 的值是（ A ）。
A. 29 B. 9 C. 43 D. 81
6. 有 5 堆石子排成一行，重量依次为 4、1、3、2、5。每次只能把相邻的两堆合并成一堆，代价为这两堆重量之和。将所有石子合并成一堆的最小总代价是（ C ）。
A. 36 B. 35 C. 34 D. 33
7. 树状数组维护长度 n=16 的序列，查询前缀和 sum(11) 与单点修改 add(3, x) 分别需要访问树状数组中多少个下标（ A ）。
A. 3 和 4 B. 4 和 4 C. 3 和 5 D. 4 和 3
8. 有向无环图 G 顶点集为 {1,2,3,4}，边集为 {(1,2),(1,3)}，顶点 4 与任何顶点均不相邻。该图不同的拓扑序共有多少种（ B ）。
A. 12 B. 8 C. 4 D. 6
9. 某分治算法满足 T(n)=T(n/3)+T(2n/3)+Θ(n)，T(1)=O(1)，则 T(n) 是（ A ）。
A. Θ(nlogn) B. Θ(n^2) C. Θ(n^1.5) D. Θ(n)
10. 无根树含 9 个结点（编号为 1—9），边集为 {(1,2),(1,3),(2,4),(2,5),(3,6),(6,7),(7,8),(5,9)}。该树的直径（以边数计）与重心分别是（ D ）。
A. 直径 6，重心为结点 3
B. 直径 7，重心为结点 2
C. 直径 8，重心为结点 1
D. 直径 7，重心为结点 1
11. 一张有向图缩点后得到的有向无环图含 6 个顶点，其中入度为 0 的顶点有 3 个，出度为 0 的顶点有 4 个。为使原图变成强连通图，至少需要添加多少条有向边（ C ）。
A. 7 B. 6 C. 4 D. 3
12. 含 6 个结点的不同形态的二叉树共有多少棵（结点不带标号，区分左右子树）（ C ）。
A. 42 B. 429 C. 132 D. 720
13. 字符串 S = "ababaabab"，其所有既是真前缀又是真后缀的子串（非空）的长度之和是（ B ）。
A. 4 B. 6 C. 7 D. 5
14. 用归并排序统计逆序对，合并部分的核心代码为：
// 分并 a 与 a，同时累加逆序对
if (a <= a) {
tmp = a; // 取左半段元素
} else {
tmp = a; // 取右半段元素
ans += mid - i + 1;
}
若把判断条件中的 a <= a 改成 a < a，则 ans 统计出的结果（ C ）。
A. 完全不变
B. 变为原来的两倍
C. 变为满足 i<j 且 a≥a 的数对个数
D. 变为原来的一半
15. 执行 power(2, 100, 1000) 调用下列函数，返回值是（ B ）。
long long power(long long a, long long b, long long p) {
long long r = 1 % p;
while (b) {
if (b & 1)
r = r * a % p;
a = a * a % p;
b >>= 1;
}
return r;
}
A. 576 B. 376 C. 976 D. 176
二、阅读程序
答案汇总
题号答案题号答案题号答案
16√22√28√
17√23√29×
18×24×30×
19C25B31A
20B26B32C
21C27D33C
（1）
#include <iostream>
#include <string>
using namespace std;
int a;
string s;
int gen = {1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1};
int main() {
cin >> s;
for (int i = 0; i < 32; ++i) {
a = s - '0';
}
for (int i = 32; i < 44; ++i) {
a = 0;
}
for (int i = 0; i < 32; ++i) {
if (a == 0) continue;
for (int j = 0; j < 13; ++j) {
a ^= gen;
}
}
for (int i = 32; i < 44; ++i) {
cout << a;
}
cout << endl;
return 0;
}
说明：输入保证为一个长度恰为 32 的 '0' / '1' 字符串。
判断题
（1 分）当输入为 32 个 '0' 时，程序输出 12 个 0。（ √ ）
程序运行结束后，数组 a 中下标从 0 到 31 的元素一定全部为 0。（ √ ）
若将第 12—14 行（为 a 到 a 补 0 的循环）删除，会改变程序输出的结果。（ × ）
单选题
19. 关于第 6 行定义的数组 gen，下列说法正确的是（ C ）。
A. gen 共有 12 个元素，表示一个 12 位的除数
B. gen 共有 13 个元素，表示一个 13 位的被除数
C. gen 共有 13 个元素，其中 gen 是除数的最高位
D. gen 共有 13 个元素，其中 gen 是除数的最高位
20. 该程序实现的功能，最准确的说法是（ B ）。
A. 将输入的 32 位串看成二进制数 M，输出 M 与 13 位二进制数 1100000001111 按位异或的结果
B. 将输入串视为 32 位二进制数 M，在其后补 12 个 0（即计算 M×2^12），再对它做模 2 除法求余数，并输出 12 位余数
C. 对输入的 32 位串逐位取反并输出结果
D. 统计输入串中 1 的个数，并把该个数用 12 位二进制表示后输出
21. 若把第 16 行 if (a == 0) continue; 删除，说法正确的是（ C ）。
A. 程序输出的结果不会改变
B. 可能造成程序运行错误
C. 程序能够正常输出一个 12 位 '0' / '1' 串，但是输出结果与输入的 s 无关
D. 程序运行结束后，a 的值一定为 0
（2）
#include <iostream>
using namespace std;
int n, m, a, L, R, lg, i, j, t, dp, pw;
int gcd(int x, int y) {
if (y == 0) return x;
return gcd(y, x % y);
}
int main() {
cin >> n >> m;
for (i = 1; i <= n; i++) cin >> a;
t = 0;
pw = 1;
for (i = 1; i <= 24; i++) pw = pw * 2;
for (i = 1; i <= 100000; i++)
if (pw >= i) lg = t;
else { t++; lg = t; }
for (i = 1; i <= n; i++) {
dp = a;
}
for (j = 1; j <= lg; j++) {
for (i = 1; i + pw - 1 <= n; i++) {
dp = gcd(dp, dp]);
}
}
for (i = 1; i <= m; i++) {
cin >> L >> R;
cout << gcd(dp], dp] + 1]]) << endl;
}
return 0;
}
说明：保证 1≤n≤100000，每次查询满足 1≤L≤R≤n，且数组 a 的元素均为正整数。
判断题
当 n=5，a={4,2,6,3,3}，且仅有一次查询 L=2,R=5 时，输出为 1。（ √ ）
当某次查询的区间长度为 1（即 L=R）时，该次查询的输出一定等于 a。（ √ ）
任意一次查询的输出结果一定不小于该查询区间内的最小值。（ × ）
单选题
25. 对于 j≥1，数组 dp 保存的是（ B ）。
A. 从 a 开始连续 j 个数的最大公约数
B. 从 a 开始连续 2^j 个数的最大公约数
C. a 与 a 的最大公约数
D. 从 a 到 a 的最大公约数
26. 若把一次求最大公约数的运算视为 O(1)，则第 17—22 行建表过程的时间复杂度为（ B ）。
A. Θ(n) B. Θ(nlogn) C. Θ(n^2) D. Θ(mn)
27. 设 x 为一次查询的区间长度（即 x=R−L+1），则使得 lg = 5 的 x 的取值范围是（ D ）。
A. B. C. D.
（3）
#include <iostream>
using namespace std;
int n, fa, f, ans;
int main() {
cin >> n;
for (int i = 2; i <= n; ++i) {
cin >> fa;
}
for (int i = n; i >= 2; --i) {
if (f] + f + 1 > ans) {
ans = f] + f + 1;
}
if (f + 1 > f]) {
f] = f + 1;
}
}
cout << ans << endl;
return 0;
}
说明：输入第一行为结点个数 n，第二行为 n−1 个整数，依次表示结点 2—n 的父结点编号，满足 2≤n≤10000 且 1≤fa<i，根结点为 1。
判断题
当 n=5，fa∼fa={1,2,3,4} 时，程序输出 4。（ √ ）
程序输出前，f 的值一定等于 ans 的值。（ × ）
将第 10—12 行与第 13—15 行两个 if 语句的顺序交换后，程序输出结果不受影响。（ × ）
单选题
31. 程序输出的 ans 表示的是（ A ）。
A. 树中距离最远的两个结点之间路径所经过的边数
B. 根结点 1 到最远叶子结点之间路径所经过的边数
C. 树中叶子结点的个数
D. 所有结点的父结点编号之和
32. 当 n=7，fa∼fa={1,1,2,2,3,3} 时，输出为（ C ）。
A. 2 B. 3 C. 4 D. 5
33. 当 n=10，满足输出为 9 的合法输入种类数为（ C ）。
A. 0 B. 9 C. 256 D. 512
三、完善程序
（单选题，每小题 3 分，共计 30 分）
答案汇总
（1）34-38
题号3435363738
答案CDBAC
（2）39-43
题号3940414243
答案CBDAA
（1）平衡路线
给定一张有 n 个顶点、m 条边的无向图，每条边带有符号 '+' 或 '-'。对于一条从顶点 s 到顶点 t 的路线，允许重复经过顶点和边。定义一条路线的权值如下：记 n+ 为经过的 '+' 边数，n- 为经过的 '-' 边数，则该路线的权值为 |n+ - n-|。
请计算从 s 到 t 的路线的最小权值。若不存在从 s 到 t 的路线，则输出 −1。
输入第一行为四个整数 n,m,s,t。接下来 m 行，每行给出两个整数 a,b 和一个字符 '+' 或 '-'，描述一条连接 a 与 b 的无向边及其符号。
数据满足 2≤n≤2×10^5，1≤m≤4×10^5，1≤s,t≤n 且 s 不等于 t，1≤a,b≤n，可能出现重边。
以下程序通过 BFS 求出最小权值。请补全程序。
#include <iostream>
constexpr int N = 200005;
constexpr int M = 400005;
int n, m, s, t;
int h, e, ne, w, idx;
int q, d, c;
void add(int a, int b, int z) {
e = b;
w = z;
ne = h;
h = idx++;
}
int main() {
std::cin >> n >> m >> s >> t;
for (int i = 1; i <= n; i++)
h = d = c = -1;
for (int i = 0; i < m; i++) {
int a, b;
char op;
std::cin >> a >> b >> op;
int z = /* ① */;
add(a, b, z);
add(b, a, z);
}
int hh = 0, tt = 0;
int p = 0, ng = 0, ok = 1;
q = s;
d = c = 0;
while (/* ② */) {
int x = q;
for (int i = h; i != -1; i = ne) {
int y = e;
if (w > 0) p = 1;
if (w < 0) ng = 1;
if (d == -1) {
d = /* ③ */;
c = c ^ 1;
q = y;
} else if (/* ④ */)
ok = 0;
}
}
if (d == -1) {
std::cout << -1;
return 0;
}
if (!p || !ng) {
std::cout << d;
return 0;
}
if (/* ⑤ */) std::cout << 0;
else std::cout << 1;
return 0;
}
34. ①处应填（ C ）。
A. op == '+' ? 0 : 1
B. op == '+'
C. op == '+' ? 1 : -1
D. op == '-' ? 1 : 0
35. ②处应填（ D ）。
A. hh < n B. tt < n C. hh <= tt D. hh < tt
36. ③处应填（ B ）。
A. d + 1 B. d + 1 C. d D. d - 1
37. ④处应填（ A ）。
A. c == c
B. w == 1
C. c != c
D. d + 1 != d
38. ⑤处应填（ C ）。
A. ok && c == c
B. ok && c != c
C. !ok || c == c
D. !ok && c != c
（2）标准答案
给定 n 名学生参加一场考试，考试共有 m 道选择题，每道题只有 A、B 两个选项。
第 i 名学生的作答为一个长度为 m 的字符串。若最终公布的标准答案与该学生在某道题上的作答相同，则该学生在这道题上得 1 分，否则不得分。记第 i 名学生最终得到的总分为 r。
每名学生还有一个预期得分 x。现在需要构造一份标准答案，使 sum(i=1 到 n) |r - x| 尽可能大。
数据满足 1≤n≤18，1≤m≤300，0≤x≤m。
提示：可以换一个角度处理 sum(i=1 到 n) |r - x|，把它写成更易优化的形式；对正整数 x，__builtin_ctzll(x) 返回 x 的二进制表示末尾连续 0 的个数；__builtin_popcountll(x) 返回 x 的二进制表示中 1 的个数。
以下程序构造出一组满足要求的标准答案。请补全程序。
#include <cstdlib>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int main() {
int n, m;
cin >> n >> m;
vector<ll> x(n), c(n);
for (int i = 0; i < n; i++) {
cin >> x;
c = /* ① */;
}
vector<string> a(n);
for (int i = 0; i < n; i++)
cin >> a;
vector<int> s(n, -1);
vector<ll> q(m, 0);
ll C = 0, S = 0;
for (int i = 0; i < n; i++) {
C -= c;
for (int j = 0; j < m; j++) {
if (a == 'A') q--;
else q++;
}
}
for (int j = 0; j < m; j++) S += abs(q);
ll ans = C + S;
ull best = 0, lst = 0;
for (ull mask = 1; mask < (1ULL << n); mask++) {
ull g = /* ② */;
ull d = g ^ lst;
int k = /* ③ */;
C -= /* ④ */;
for (int j = 0; j < m; j++) {
ll old = q;
int v = (a == 'A' ? 1 : -1);
q -= 2ll * s * v;
S += abs(q) - abs(old);
}
s = -s;
if (C + S > ans) {
ans = C + S;
best = g;
}
lst = g;
}
for (int i = 0; i < n; i++) {
if ((best >> i) & 1) s = 1;
else s = -1;
}
string res(m, 'A');
for (int j = 0; j < m; j++) {
ll v = 0;
for (int i = 0; i < n; i++) {
if (a == 'A') v += s;
else v -= s;
}
if (/* ⑤ */) res = 'A';
else res = 'B';
}
cout << res << endl;
return 0;
}
39. ①处应填（ C ）。
A. 2 * x - m
B. -m + 2 * x + 1
C. m - 2 * x
D. m + 2 * x
40. ②处应填（ B ）。
A. mask | (mask >> 1)
B. mask ^ (mask >> 1)
C. mask & (mask >> 1)
D. mask ^ ((mask >> 1) + 1)
41. ③处应填（ D ）。
A. __builtin_ctzll(d) + 1
B. __builtin_popcountll(d)
C. __builtin_ctzll(g)
D. __builtin_ctzll(d)
42. ④处应填（ A ）。
A. 2ll * s * c
B. s * c
C. 2ll * (s - c)
D. 2ll * c
43. ⑤处应填（ A ）。
A. v >= (n & 1)
B. v > (n & 1)
C. v + (n & 1) >= 0
D. v * (n & 1) >= 0
在后续的系列中，我们将继续对CSP - J/S 第一轮的题目进行讲解，并为大家准备第二轮的复赛。
如您喜欢，请不要忘记「评分」和「评论」哟~感谢你对鱼C的支持！
在本帖下方发布你的题解或看法，我们将给予除回帖奖励外的额外「荣誉」、「贡献」、「鱼币」哦！
static/image/hrline/line1.png
请不要大范围刷帖或违反《鱼C论坛规则》。请注意，出于鱼C论坛对于评分工具的限制，每日发出的评分有限，因此对您的优质评论不保证及时评分如未收到，请等待一些时间。在本专辑中，标注为【第二轮】的帖子，均在第一轮正式发布成绩、各省划定分数线、CCF公布认证等级后，进行关闭。部分除外。工作人员将根据参与度等情况，对本次回帖奖励的鱼币数、总数和总量进行调整。数量有限，先到先得。对于回帖中奖概率，请以论坛帖子功能上公示的为主，工作人员会进行调整。帖子变更后，工作人员如有说明，将通过【补充】功能进行设置。
@zhangjinxuan 厉害呀！赞一个！ {:7_146:}支持支持！ {:5_108:} {:5_106:} {:13_439:} 本帖最后由 zhangjinxuan 于 2026-9-20 21:23 编辑
完善程序最后一题不是给人类做的，直接在这个题错 3 个的情况下获得总分 $3^4$ 分{:10_282:} zhangjinxuan 发表于 2026-9-20 21:20
完善程序最后一题不是给人类做的，直接在这个题错 3 个的情况下获得总分 $3^4$ 分
CCF是这样的，请问这位先生知道另外10分去哪里了嘛{:10_325:} 本帖最后由 zhangjinxuan 于 2026-9-20 22:03 编辑
高山 发表于 2026-9-20 21:37
CCF是这样的，请问这位先生知道另外10分去哪里了嘛
去了 $3^{2026}$ 和 $2^{100}$、$\log x=5$ 和直径为 $9$ 的 $10$ 个点树的数量，不是人类了{:10_282:} {:7_146:}
页:
[1]