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

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

一、答案速查表

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

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

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

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

三、完善程序（35–44 题）

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

二、逐题解析

一、单项选择题

1.（答案 A，2.0 分） 考点：C++ 面向对象特性。printf 属于 C 标准库函数，不触及类、对象、继承、多态等 OOP 概念；B/C/D 都直接用到类或继承。陷阱：把“调用函数”当成面向对象。

2.（答案 C，2.0 分） 考点：栈的合法出栈序列。元素按 6、5、4、3、2、1 入栈。选项 C（3 4 6 5 2 1）非法：取出 3、4 后栈内剩余 6、5（5 在顶），要取 6 必须先弹出 5。

3.（答案 D，2.0 分） 考点：指针赋值语义。p = q; 仅改变指针 p 的指向，使其指向 y，x 与 y 的值均不变。陷阱：误以为会修改 x 或 y。

4.（答案 C，2.0 分） 考点：数组与链表。数组容量静态固定、链表可动态增减；数组同样可以排序。

5.（答案 B，2.0 分） 考点：栈/队列混合作业的最大栈深。依题意还原 e1~e6 的进栈/出栈与入队/出队序列，求过程中栈 S 出现过的最大元素个数，至少需 3。

6.（答案 B，2.0 分） 考点：前缀（波兰）表达式。a+(b-c)*d：先 b-c，再乘 d，最后加 a → +a*-bcd。

7.（答案 B，2.0 分） 考点：哈夫曼编码长度。按权值 10/15/30/16/29 反复合并最小两堆，d 处在深度 2。陷阱：先合并最小权值，不是按字母顺序。

8.（答案 C，2.0 分） 考点：完全二叉树数组下标（根在 1）。第 9 号结点父为 4，左兄弟为 8，右子为 2*9+1=19。陷阱：兄弟是 8 而非 10。

9.（答案 B，2.0 分） 考点：有向连通图的邻接矩阵。至少要有 n-1 条有向边构成一棵生成树，故至少 n-1 个非零元。

10.（答案 D，2.0 分） 考点：栈与队列。两个栈可模拟队列（经典做法），D 说“无法用栈实现队列”错误。

11.（答案 D，2.0 分） 考点：双向循环链表在 p 后插 s。须先接好 s 的前/后指针，再改 p->next，且 p->next->prev = s 必须在 p->next = s 之前执行。

12.（答案 B，2.0 分） 考点：排序稳定性。简单选择排序是不稳定的（相同元素可能被交换）；冒泡、插入、归并均稳定。

13.（答案 C，2.0 分） 考点：八进制转十进制。32.1₈ = 3×8 + 2 + ¹⁄₈ = 26.125。

14.（答案 B，2.0 分） 考点：子串计数（争议题）。“abcab” 的互不相同非空子串共 12 个；若把空串也算作子串则为 13。官方答案取 13（含空串），争议详见文末避坑。

15.（答案 B，2.0 分） 考点：递归的定义。递归是函数通过调用自身来解决问题的技术。

二、阅读程序

程序（1）功能：把两个 ≤15 的自然数 x、y 的低 4 位各自“拆成 4 个比特”后交错合并——x 的位落入结果的偶数位、y 的位落入奇数位（等价于两位十六进制位的按位重排）。

16.（答案 A，1.5 分） x、y≤15 时所有中间结果都被 &0x33、&0x55 掩码限制在低 4 位内，有无 unsigned 在该范围内行为一致。结论：√。

17.（答案 B，1.5 分） 把 short 改为 char：char 通常为有符号，移位与按位运算会发生符号扩展，结果改变。结论：×。

18.（答案 B，1.5 分） 程序输出随输入变化，并非恒为 0。结论：×。

19.（答案 B，1.5 分） 输入 “2 2” 实际输出 30（x=y=2，经掩码后 z=2|(2<<1)=30），并非 10。结论：×。

20.（答案 B，1.5 分） 同上，输入 “2 2” 输出 30 而非 59。结论：×。

21.（答案 B，3.0 分） 输入 “13 8” 按位重排后 z = 209。

程序（2）功能：用递归 f 与递推 g 计算“将 n 拆成 m 段时的最坏最少步数”（鸡蛋/决策类 DP 的两种实现）。两函数计算的是同一数值。

22.（答案 B，1.5 分） 输入 “7 3” 时第 19 行 min 的实际执行次数并非 449（可程序验证），题干表述不成立。结论：×。

23.（答案 A，1.5 分） f 与 g 是同一问题的递归/递推两种写法，输出两行恒相等。结论：√。

24.（答案 A，1.5 分） m=1 时退化为线性扫描，第一行恒输出 n。结论：√。

25.（答案 C，3.0 分） g 含 i、j、k 三层循环，时间复杂度为 O(n²·m)。

26.（答案 C，3.0 分） 输入 “20 2” 计算得第一行为 6。

27.（答案 B，3.0 分） 输入 “100 100” 计算得第一行为 7。

程序（3）功能：solve1 用二分求 ⌊√n⌋；solve2 用牛顿迭代对 √n 做 k 次逼近。最终输出 ⌊√n⌋ 与 √n 的近似值 两个数。

28.（答案 A，1.5 分） 二分 O(log n)，牛顿迭代 O(k)，整体 O(log n + k)。结论：√。

29.（答案 A，1.5 分） 9801 = 99²，solve1 返回 99。结论：√。

30.（答案 B，1.5 分） 牛顿法对整数平方根会收敛到 ⌊√n⌋，不会趋于 1。结论：×。

31.（答案 B，1.5 分） 争议题。题称 n 过大时 mid*mid 可能溢出需转 64 位；但 n≤47000，mid≤47000，mid²≈2.21×10⁹ 已超 int 上限 2³¹−1≈2.15×10⁹，理论上确有溢出风险。官方却判为 ×，属争议点，详见文末避坑。

32.（答案 C，3.0 分） 输入 “2 1”：第一个数 ⌊√2⌋=1；第二个数经 1 次牛顿迭代 (1+²⁄₁)/2=1.5。题面虽写“第一个数”，答案对应第二个数的近似值 1.5（易混点）。

33.（答案 B，3.0 分） 输入 “3 10”：第一个数 ⌊√3⌋=1；第二个数经 10 次牛顿迭代收敛到 √3≈1.732。同理注意区分两数。

34.（答案 A，4.0 分） 输入 “256 11”：第一个数 ⌊√256⌋=16，且 256 为完全平方数，牛顿迭代后第二数也为 16，故“等于 16”。

三、完善程序

35.（答案 A，3.0 分） ①判断 i 是否为 n 的因数：n % i == 0。

36.（答案 B，3.0 分） ②正序输出已收集的小因数本身 fac[k]。

37.（答案 C，3.0 分） ③循环结束后 i=⌈√n⌉，用 i*i==n 判断 n 是否为完全平方数。

38.（答案 D，3.0 分） ④若是完全平方数，单独输出中间因数 i。

39.（答案 A，3.0 分） ⑤逆序输出大因数 n/fac[k]。

程序（2）功能：BFS 洪水填充（flood fill）。从起点出发，把颜色相同且四连通可达的像素替换为新颜色。

40.（答案 A，3.0 分） ①is_valid 需保证目标像素仍是原颜色（未被填）：image[r][c] == prev_color。

41.（答案 B，3.0 分） ②把起点自身标记为已填充：image[cur.r][cur.c] = new_color。

42.（答案 C，3.0 分） ③四个方向还差“向下”，即 Point(cur.r+1, cur.c)。

43.（答案 D，3.0 分） ④把新访问到的像素 p 染成新颜色：image[p.r][p.c] = new_color。

44.（答案 A，3.0 分） ⑤把 p 入队继续扩散：queue.push(p)。

三、卷子特点小结

• 单选题覆盖 C++ 基础、数据结构、算法复杂度、数学（进制/哈夫曼/图），注重概念辨析。
• 阅读程序三道分别是位运算重排、扔鸡蛋 DP、二分+牛顿开方，计算量偏大，需动手验算。
• 完善程序为“枚举因数”与“BFS 洪水填充”，考察基础模拟与图遍历。

四、争议与避坑（重点）

• 第 14 题（子串是否含空串）：按非空子串计数“abcab”应为 12；若把空串计入则为 13。官方答案为 B（13，含空串），自测时注意题目对“子串”的定义。
• 第 31 题（溢出边界）：题中称 mid*mid 可能溢出需转 64 位。但 n≤47000 时 mid²≈2.21×10⁹ 已超 int 上限 ≈2.15×10⁹，理论上确有溢出风险；官方却判为 B（×），属争议题，请勿凭直觉改答案。
• 第 32、33 题（第一个数 vs 第二个数）：程序输出两个数——第一个是 ⌊√n⌋，第二个是牛顿近似。题面写“第一个数”，但答案对应的是第二个数的近似值（32 题 1.5、33 题 1.732）。自测时务必区分两数，避免混淆。

五、配套练习与来源

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