2021 CSP-J 第一轮（入门级）参考答案与逐题解析（43 题全）

答案经程序实测验证，以 CCF 官方公布为准。配套真题见《2021 CSP-J 第一轮（入门级）真题完整版（43 题）》。

一、答案速查表

一、单项选择题（1–15 题）

本段答案序列：D B A C D D C A B B B A C B B

二、阅读程序（16–33 题）

本段答案序列：B B B A B B B A A B B C A B B A C C

三、完善程序（34–43 题）

本段答案序列：D C C D B B D C B D

二、逐题解析

一、单项选择题

1.（答案 D，2.0 分） 考点：面向对象语言。C 语言是面向过程的，不属于 OOP 语言；C++/Python/Java 均支持面向对象。

2.（答案 B，2.0 分） 考点：计算机奖项。图灵奖是计算机领域最高奖。

3.（答案 A，2.0 分） 考点：数据存贮。计算机最终以二进制存贮数据。

4.（答案 C，2.0 分） 考点：找最大值的最少比较。N 个数找最大，最坏也只需 N-1 次比较（逐个比较）。

5.（答案 D，2.0 分） 考点：合法出栈序列。入栈 a,b,c,d,e。选项 D（c,d,a,e,b）非法：取出 c、d 后栈内剩 a、b（b 在顶），要取 a 须先弹出 b。

6.（答案 D，2.0 分） 考点：连通图变树。无向连通图有 n-1 条边时为树，需删 m-(n-1)=m-n+1 条。

7.（答案 C，2.0 分） 考点：二进制转十进制。101.11₂ = 4+1+0.5+0.25 = 5.75。

8.（答案 A，2.0 分） 考点：高度 5 的完全二叉树形态数。由完全二叉树的结构约束递推可得共 16 种。

9.（答案 B，2.0 分） 考点：后缀（逆波兰）表达式。a*(b+c)*d：先 b+c，再与 a 乘，再乘 d → abc+*d*。

10.（答案 B，2.0 分） 考点：不区分队伍的三人两组。6 人分成 3 个无序两人队：6!/(2³·3!) = 15。

11.（答案 B，2.0 分） 考点：哈夫曼编码本质。哈夫曼每次合并最小权值，是贪心策略。

12.（答案 A，2.0 分） 考点：由 1,1,2,2,3 组成不同三位数。枚举去重共 18 个。

13.（答案 C，2.0 分） 考点：递归求值。solve(7)=7·solve(5)=7·5·solve(3)=7·5·3·solve(2)=7·5·3·2=210。

14.（答案 B，2.0 分） 考点：DFS 遍历最后一个点。以 a 为起点对给定无向图做深度优先，b、c、d、e 中可能有 2 个成为最后访问点（依图结构）。

15.（答案 B，2.0 分） 考点：过河问题。最优：1、2 过(2)，1 回(1)，4、8 过(8)，2 回(2)，1、2 过(2)，共 15。

二、阅读程序

程序（1）功能：对输入每个 a[i] 输出 f(a[i])+g(a[i])，其中 f(x) 统计 x 二进制中 1 的个数（Brian Kernighan），g(x)=x & -x 取最低位 1 的值。

16.（答案 B，1.5 分） n 最大 1000，数组 a 大小 1000，下标 0..999，n=1001 会越界。结论：×。

17.（答案 B，1.5 分） a[i] 非正时 x &= x-1 对 0 不会死循环（循环条件 x 为 0 即停）。结论：×。

18.（答案 B，1.5 分） 输入 “5 2 11 9 16 10”：f/g 分别为 popcount 与 lowbit，逐项算得输出 “3 4 3 17 5” 成立。结论：√。

19.（答案 A，1.5 分） 输入 “1 511998”：popcount 与 lowbit 计算后输出并非 18。结论：×。

20.（答案 B，1.5 分） g 定义在 main 之后且未提前声明，C++ 无法编译通过。结论：×。

21.（答案 B，3.0 分） 输入 “2 -65536 2147483647”：注意负数补码，-65536 的 popcount 与 lowbit 计算得输出 “65532 33”。

程序（2）功能：Base64 解码。原题中 base[64] 应初始化为 Base64 字符表（本题代码省略了该初始化行，按原题 base 含 64 个 Base64 字符），解码后得到原始字节串。

22.（答案 B，1.5 分） decode 解码结果可能为任意字节（含非打印字符），“一定由字母数字和 + / = 构成”不成立。结论：×。

23.（答案 A，1.5 分） 不同输入可能解码到同一字节序列（Base64 填充/舍入），可能输出相同。结论：√。

24.（答案 A，1.5 分） 原题 base 含 64 个 Base64 字符，table[0] 未被覆盖仍为 0xff，int 转型为 -1，故第一行为 -1。结论：√。

25.（答案 B，3.0 分） decode 顺序扫描输入串，时间复杂度 O(n)。

26.（答案 B，3.0 分） 输入 “Y3Nx” 解码 Base64 得 “csq”。

27.（答案 C，3.5 分） 争议题（网传输入串有误，本站已修正为 “Y2NmIDIwMjE=”）。解码得 “ccf 2021”。详见文末避坑。

程序（3）功能：线性筛风格的预处理，计算 f[x]=x 的正因数个数、g[x]=x 的所有正因数之和。init 后可直接查表。

28.（答案 A，1.5 分） 若输入 x≠1，删去 f[1]=g[1]=1 不影响（1 的因数个数/和都是 1，x≥2 时不依赖它）。结论：√。

29.（答案 B，2.0 分） 第 25 行 f[i]/c[i*k] 中 c 为对应质因子指数，f 为除数函数，保证整除，题干说“可能无法整除”不成立。结论：×。

30.（答案 B，2.0 分） init 后 f 数组非单调递减（有起伏），g 单调递增。结论：×。

31.（答案 A，3.0 分） init 是线性筛，时间复杂度 O(n)。

32.（答案 C，3.0 分） 争议题。问 f[1..100] 中等于 2 的个数。f[x]=2 当且仅当 x 为质数；≤100 的质数共 25 个（f[1]=1 不计入）。题干范围易歧义，答案为 25。详见文末避坑。

33.（答案 C，4.0 分） 输入 “1000”：1000=2³·5³，因数个数 (3+1)(3+1)=16，因数和 (1+2+4+8)(1+5+25+125)=15·156=2340，故 “16 2340”。

三、完善程序

程序（1）功能：模拟 Josephus（0/1 交替报数，报 1 出圈）求最后剩下者编号。

34.（答案 D，3.0 分） ①循环继续条件：已出圈人数 c < n-1（剩 1 人即停）。

35.（答案 C，3.0 分） ②当报数为 1（即 p 为 1）时将该人标记离开：条件为 p。

36.（答案 C，3.0 分） ③标记离开后出圈人数 +1：c++。

37.（答案 D，3.0 分） ④无论是否离开，报数交替：p ^= 1。

38.（答案 B，3.0 分） ⑤移动到下一个人：i = (i+1)%n。

程序（2）功能：给定 n 个关键点，枚举横纵坐标不同的点对 (i,j)，若四点 (i.x,i.y)、(j.x,j.y)、(i.x,j.y)、(j.x,i.y) 都存在则计数一个轴平行矩形。

39.（答案 B，3.0 分） ①排序比较器：先比 x 再比 y：a.x!=b.x ? a.x<b.x : a.y<b.y。

40.（答案 D，3.0 分） ②去重：保留与已保留最后一个不同的点：t==0 || !equals(A[i],A[t-1])。

41.（答案 C，3.0 分） ③二分中点（下取整）：(a+b)>>1。

42.（答案 B，3.0 分） ④在有序数组中找 p，若 A[mid]<p 则向右：cmp(A[mid], p)。

43.（答案 D，3.0 分） ⑤枚举矩形：需两点横坐标不同且纵坐标不同：A[i].x<A[j].x && A[i].y<A[j].y。

三、卷子特点小结

• 单选题偏基础概念（OOP、奖项、进制、组合、递归、过河），难度平缓。
• 阅读程序三道分别是位运算(popcount+lowbit)、Base64 解码、线性筛求因数函数，信息量大。
• 完善程序为 Josephus 模拟与轴平行矩形计数，考察模拟与排序/二分查找。

四、争议与避坑（重点）

• 第 27 题（网传输入串有误，已修正）：网传版本 Base64 输入串有误（常漏写结尾 = 或字符错），导致解码结果偏差。本站已修正为 “Y2NmIDIwMjE=”，解码得到 “ccf 2021”，答案为 C。
• 第 32 题（题干范围易歧义）：问 f[1]~f[100] 中等于 2 的个数。f[x]=2 当且仅当 x 为质数（恰两个正因数），≤100 的质数共 25 个（注意 f[1]=1 不计入）。答案为 C（25），看清统计范围。
• 程序（2）base 初始化省略：本题代码省略了 base[64] 初始化为 Base64 字符表的一行，按原题 base 含 64 个 Base64 字符，table[0] 才会保持 0xff 使第 24 题第一行为 -1。

五、配套练习与来源

• 本站提供该年分三卷的 Hydro 客观题包，可在 OJ 导入后在线刷题、自动判分，巩固自测效果。
• 真题整理自网络流传版本，经多来源交叉核对；答案与解析以 CCF 官方公布为准。如有错漏欢迎在站内指正。