2022 年 CCF 非专业级软件能力认证（CSP-J/S 2022）第一轮认证于 2022 年 9 月 18 日举行。继上一篇单项选择题解析后，本文为您带来 第二部分：阅读程序题（共 3 大题，计 40 分） 的原题还原、程序主旨透视、算法模拟推演与全题目深度解析。

本次阅读程序题考查了 位运算与 Morton 码（Z 阶空间填充曲线）、经典的“高楼扔鸡蛋”动态规划与递归模型、二分求平方根与牛顿迭代法（巴比伦方法） 等经典算法与数论知识。

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

📍 第一题：位运算与 Morton Code（莫顿码 / Z 阶空间填充曲线）

💻 源码展示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

01 #include <iostream>
02
03 using namespace std;
04
05 int main()
06 {
07     unsigned short x, y;
08     cin >> x >> y;
09     x = (x | x << 2)& 0x33;
10     x = (x | x << 1)& 0x55;
11     y = (y | y << 2)& 0x33;
12     y = (y | y << 1)& 0x55;
13     unsigned short z = x | y << 1;
14     cout << z << endl;
15     return 0;
16 }

假设输入的 $x, y$ 均是不超过 15 的自然数，完成下面的判断题和单选题：

💡 程序主旨与算法原理

本程序是计算机图形学与空间索引中非常著名的 Morton 码（Morton Code / 莫顿码，又称 Z 阶空间填充曲线） 的位运算快速生成算法。

题设输入 $x, y \le 15$，它们的二进制表示最多占 4 位： 设 $x$ 的二进制为 $x_3 x_2 x_1 x_0$，$y$ 的二进制为 $y_3 y_2 y_1 y_0$。

1. 第 9 行 x = (x | x << 2) & 0x33：
   • 常数 0x33 的二进制为 0011 0011。
   • 此操作将原本连续的 4 位拆分成两组（每组 2 位），在中间插入 2 个 0，变为 00 x3 x2 00 x1 x0。
2. 第 10 行 x = (x | x << 1) & 0x55：
   • 常数 0x55 的二进制为 0101 0101。
   • 此操作进一步将相邻的位拆开，插入 1 个 0，最终使 $x$ 扩展为 8 位交错结构：0 x3 0 x2 0 x1 0 x0（即奇数位全为 0，偶数位存放 $x$ 的原二进制位）。
3. 第 11~12 行：对 $y$ 进行相同的位扩展，得到 $y =$ 0 y3 0 y2 0 y1 0 y0。
4. 第 13 行 unsigned short z = x | (y << 1)：
   • 将 $y$ 左移 1 位，得到 y3 0 y2 0 y1 0 y0 0。
   • 与 $x$ 按位或（|）合并后，$z$ 的二进制即为 $x$ 与 $y$ 的位交叉混合结果： \(z = (y_3 x_3 y_2 x_2 y_1 x_1 y_0 x_0)_2\)

❓ 判断题

1. 删去第 7 行与第 13 行的 unsigned，程序行为不变。（ ）

A. 正确
B. 错误
正确答案： A

深度解析：
unsigned short 的表示范围是 $0 \sim 65535$，short 的表示范围是 $-32768 \sim 32767$。
由于题干明确说明输入 $x, y \le 15$，位交叉后合成的最大值 $z$ 仅为 8 位整数（最大为 $(11111111)_2 = 255$），在 short 和 unsigned short 下均属于正整数且不会发生任何溢出，移位和按位运算的输出结果完全相同。因此程序行为不变，说法正确。

2. 将第 7 行与第 13 行的 short 均改为 char，程序行为不变。（ ）

A. 正确
B. 错误
正确答案： B

深度解析：

• 若改为 char，cin >> x >> y; 将不再把输入解析为整数，而是作为字符读入（例如输入数字 13 会把字符 '1' 读入给 x，字符 '3' 读入给 y）。
• 同时在 cout << z; 时，cout 会将 char 类型的 $z$ 作为 ASCII 字符打印输出，而不是打印整数数值。
  这使得程序行为发生了根本改变，故说法错误。

3. 程序总是输出一个整数 “0” 。（ ）

A. 正确
B. 错误
正确答案： B

深度解析：
根据位合并公式 $z = (y_3 x_3 y_2 x_2 y_1 x_1 y_0 x_0)_2$，只有当 $x = 0$ 且 $y = 0$ 时输出才为 0。只要输入的 $x$ 或 $y$ 中含有二进制位 1，输出就会是一个正整数。故说法错误。

4. 当输入为 2 2 时，输出为 10 。（ ）

A. 正确
B. 错误
正确答案： B

深度解析：

• $x = 2 = (0010)_2$
• $y = 2 = (0010)_2$
• 将二进制位交叉组合： $y$ 的各二进制位：$y_3=0, y_2=0, y_1=1, y_0=0$
  $x$ 的各二进制位：$x_3=0, x_2=0, x_1=1, x_0=0$
  交叉后得到：$z = (y_3 x_3 y_2 x_2 y_1 x_1 y_0 x_0)_2 = (00001100)_2 = 8 + 4 = \mathbf{12} \neq 10$。
  故说法错误。

5. 当输入为 2 2 时，输出为 59 。（ ）

A. 正确
B. 错误
正确答案： B

深度解析：
根据上一题解析，当输入为 2 2 时，实际输出结果为 12，并非 59。故说法错误。

❓ 单选题

6. 当输入为 13 8 时，输出为（ ）。

A. 0
B. 209
C. 197
D. 226
正确答案： B

深度解析：

1. 将输入转换为 4 位二进制表示：
   • $x = 13 = (1101)_2 \implies x_3=1, x_2=1, x_1=0, x_0=1$
   • $y = 8 = (1000)_2 \implies y_3=1, y_2=0, y_1=0, y_0=0$
2. 进行二进制位交叉合并： \(z = (y_3 x_3 y_2 x_2 y_1 x_1 y_0 x_0)_2 = (11010001)_2\)
3. 将二进制转为十进制： \(z = 1 \times 2^7 + 1 \times 2^6 + 0 \times 2^5 + 1 \times 2^4 + 0 \times 2^3 + 0 \times 2^2 + 0 \times 2^1 + 1 \times 2^0\) \(z = 128 + 64 + 16 + 1 = \mathbf{209}\)

对应 B 选项。

📍 第二题：高楼扔鸡蛋问题（记忆化递归与动态规划）

💻 源码展示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

01 #include <algorithm>
02 #include <iostream>
03 #include <limits>
04
05 using namespace std;
06
07 const int MAXN = 105;
08 const int MAXK = 105;
09
10 int h[MAXN][MAXK];
11
12 int f(int n, int m)
13 {
14     if (m == 1) return n;
15     if (n == 0) return 0;
16
17     int ret = numeric_limits<int>::max();
18     for (int i = 1; i <= n; i++)
19         ret = min(ret, max(f(n - i, m), f(i - 1, m - 1)) + 1);
20     return ret;
21 }
22
23 int g(int n, int m)
24 {
25     for (int i = 1; i <= n; i++)
26         h[i][1] = i;
27     for (int j = 1; j <= m; j++)
28         h[0][j] = 0;
29
30     for (int i = 1; i <= n; i++){
31         for (int j = 2; j <= m; j++){
32             h[i][j] = numeric_limits<int>::max();
33             for (int k = 1; k <= i; k++)
34                 h[i][j] = min(
35                     h[i][j],
36                     max(h[i - k][j], h[k - 1][j - 1]) + 1);
37         }
38     }
39
40     return h[n][m];
41 }
42
43 int main()
44 {
45     int n, m;
46     cin >> n >> m;
47     cout << f(n, m) << endl << g(n, m) << endl;
48     return 0;
49 }

假设输入的 $n$、$m$ 均是不超过 100 的正整数，完成下面的判断题和单选题：

💡 程序主旨与算法模型

本题是经典的 “鹰蛋问题 / 高楼扔鸡蛋（Egg Dropping Puzzle）”：

• 给定 $n$ 层楼和 $m$ 个鸡蛋，求在最坏情况下确定鸡蛋刚好碎裂临界楼层所需的最少测试次数。
• f(n, m) 是纯递归暴力解法：枚举在第 $i$ 层扔鸡蛋，如果碎了剩余 $m-1$ 个鸡蛋在下面的 $i-1$ 层测；如果不碎剩余 $m$ 个鸡蛋在上面的 $n-i$ 层测。取两者最坏情况 $\max + 1$，并在所有可能楼层中取 $\min$。
• g(n, m) 是标准的自底向上动态规划（DP）解法，h[i][j] 记录 $i$ 层楼 $j$ 个鸡蛋的状态值，避免了递归的大量重复计算。

❓ 判断题

1. 当输入为 7 3 时，第 19 行用来取最小值的 min 函数执行了 449 次。（ ）

A. 正确
B. 错误
正确答案： B

深度解析：
对于纯递归函数 f(n, m)：

• 当 $n=0$ 或 $m=1$ 时直接返回，不进入 for 循环。
• 当 $n \ge 1$ 且 $m > 1$ 时，第 18 行循环 $i$ 从 1 到 $n$，循环体内的 min 函数共执行 $n$ 次。
• 跟踪展开计算树：
  • f(7, 3) 执行 7 次，产生子问题：f(6,3), f(0,2)、f(5,3), f(1,2)、f(4,3), f(2,2)、f(3,3), f(3,2)、f(2,3), f(4,2)、f(1,3), f(5,2)、f(0,3), f(6,2)。
  • 继续递归展开所有分支并求和，min 函数实际累计执行次数为 448 次（并非 449 次）。故说法错误。

2. 输出的两行整数总是相同的。（ ）

A. 正确
B. 错误
正确答案： A

深度解析：
f(n, m) 与 g(n, m) 的状态转移方程完全一致（只是 f 是递归求解，g 是动态规划填表迭代求解），初始边界条件也完全相同。在没有死循环或越界的前提下，它们数学上计算的是完全相同的数学函数值，因此两行输出必定相同。故说法正确。

3. 当 $m$ 为 1 时，输出的第一行总为 $n$。（ ）

A. 正确
B. 错误
正确答案： A

深度解析：
根据第 14 行边界条件：if (m == 1) return n;。
物理意义上：当只有 1 个鸡蛋时，为了保证不漏掉临界层且鸡蛋碎了就无法继续测试，必须从第 1 层逐层向上线性尝试，最坏情况下必须测试 $n$ 次。因此第一行输出总为 $n$，说法正确。

❓ 单选题

4. 算法 $g(n, m)$ 最为准确的时间复杂度分析结果为（ ）。

A. $O(n^{3/2}m)$
B. $O(nm)$
C. $O(n^2 m)$
D. $O(nm^2)$
正确答案： C

深度解析：
观察 g(n, m) 中的三重嵌套循环：

• 外层循环：$i$ 从 1 到 $n$（执行 $n$ 次）；
• 中层循环：$j$ 从 2 到 $m$（执行 $m-1$ 次）；
• 内层循环：$k$ 从 1 到 $i$（平均执行 $\frac{n}{2}$ 次）； 总基本操作执行次数为： \(\sum_{i=1}^n \sum_{j=2}^m \sum_{k=1}^i 1 = (m - 1) \sum_{i=1}^n i = (m - 1) \frac{n(n+1)}{2} = O(n^2 m)\) 因此时间复杂度为 $O(n^2 m)$，对应 C 选项。

5. 当输入为 20 2 时，输出的第一行为（ ）。

A. 4
B. 5
C. 6
D. 20
正确答案： C

深度解析：
本题计算 2 个鸡蛋测 20 层楼的最少步数。
设测试次数为 $t$。在有 2 个鸡蛋的情况下，$t$ 次尝试最多可以覆盖的楼层数为等差数列求和： \(N(t) = t + (t - 1) + \dots + 1 = \frac{t(t + 1)}{2}\)

• 当 $t = 5$ 时：$N(5) = \frac{5 \times 6}{2} = 15 < 20$（步数不足以测完 20 层）；
• 当 $t = 6$ 时：$N(6) = \frac{6 \times 7}{2} = 21 \ge 20$（6 步足以测完 20 层）。 因此所需最少次数为 6，对应 C 选项。

6. （4分）当输入 100 100 时，输出的第一行为（ ）。

A. 6
B. 7
C. 8
D. 9
正确答案： B

深度解析：
当鸡蛋数 $m \ge \lceil \log_2(n + 1) \rceil$ 时，鸡蛋极其充足（甚至用不完），测试过程完全等价于标准的 二分查找。
对于 $n = 100$ 层楼：

• 6 次二分最多能区分 $2^6 - 1 = 63$ 层楼；
• 7 次二分最多能区分 $2^7 - 1 = 127$ 层楼。
  因为 $63 < 100 \le 127$，所以最少需要 7 次即可测出临界楼层。对应 B 选项。

📍 第三题：二分查找与牛顿迭代法求平方根

💻 源码展示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

01 #include <iostream>
02
03 using namespace std;
04
05 int n,k;
06
07 int solve1()
08 {
09     int l = 0, r = n;
10     while(l <= r){
11         int mid = (l + r) / 2;
12         if (mid * mid <= n) l = mid + 1;
13         else r = mid - 1;
14     }
15     return l - 1;
16 }
17
18 double solve2(double x)
19 {
20     if (x == 0) return x;
21     for (int i = 0; i < k; i++)
22         x = (x + n / x) / 2;
23     return x;
24 }
25
26 int main()
27 {
28     cin >> n >> k;
29     double ans = solve2(solve1());
30     cout << ans << ' ' << (ans * ans == n) << endl;
31     return 0;
32 }

假设 int 为 32 位有符号整数类型，输入的 $n$ 是不超过 47000 的自然数，$k$ 是不超过 int 表示范围的自然数，完成下面的判断题和单选题：

💡 程序主旨与数学原理

1. solve1() 函数：使用 二分查找法 计算 $\lfloor \sqrt{n} \rfloor$（即 $n$ 的整数算术平方根向下取整）。
2. solve2(x) 函数：使用著名的 牛顿迭代法（Newton’s Method / 巴比伦方法） 求解 $\sqrt{n}$：
   • 迭代公式为：$x_{i+1} = \frac{1}{2} \left( x_i + \frac{n}{x_i} \right)$。
   • 以 solve1() 的返回值作为迭代初始初值 $x_0$，共迭代 $k$ 轮。
3. main() 函数：输出近似平方根 ans，以及布尔表达式 (ans * ans == n) 的真假值（1 或 0）。

❓ 判断题

1. 该算法最准确的时间复杂度分析结果为 $O(\log n + k)$。（ ）

A. 正确
B. 错误
正确答案： A

深度解析：

• solve1() 在区间 $[0, n]$ 内进行二分查找，循环次数为 $O(\log n)$；
• solve2(x) 包含一个执行 $k$ 次的 for 循环，时间复杂度为 $O(k)$；
• 两者串行执行，总时间复杂度为 $O(\log n + k)$。故说法正确。

2. 当输入为 9801 1 时，输出的第一个数为 99。（ ）

A. 正确
B. 错误
正确答案： A

深度解析：
因为 $99^2 = 9801$：

• solve1() 精确计算出 $\sqrt{9801} = 99$。
• 将 $x_0 = 99$ 传入 solve2(99)，进行 $k=1$ 次迭代： \(x_1 = \frac{99 + 9801 / 99}{2} = \frac{99 + 99}{2} = 99\) 因此输出的第一个数恰好为 99。说法正确。

3. 对于任意输入的 $n$，随着所输入 $k$ 的增大，输出的第二个数值会变成 1。（ ）

A. 正确
B. 错误
正确答案： B

深度解析：

• 如果 $n$ 不是完全平方数（例如 $n = 2$ 或 $n = 3$），$\sqrt{n}$ 是一个无限不循环小数（无理数）。
• 计算机使用 double 双精度浮点数存储，只能保留有限位有效数字（约 15~17 位有效精度），必定存在浮点舍入误差。
• 无论迭代多少次，ans * ans == n 都无法做到精确的二进制严格相等，输出的第二个值恒为 0。故本题说法错误。

4. 该程序存在缺陷。当输入的 $n$ 过大时，第 12 行的乘法有可能溢出，因此应当将 mid 强制转换为 64 位整数再计算。（ ）

A. 正确
B. 错误
正确答案： B

深度解析：

• 题设明确给定前提：“输入的 $n$ 是不超过 47000 的自然数”。
• 32 位有符号整数 int 的最大表示范围为 $2^{31}-1 = 2,147,483,647$。
• 在二分查找初始阶段，$l = 0, r = n$：
  • 当 $n = 47000$ 时，$mid = \lfloor (0 + 47000) / 2 \rfloor = 23500$；
  • 此时计算 $mid \times mid = 23500 \times 23500 = 552,250,000$；
  • 由于 $552,250,000 > 47000$，条件 mid * mid <= n 不成立，程序会执行 r = mid - 1，将右边界缩小为 $23499$；
  • 在随后的二分迭代中，$mid$ 只会越来越小（均小于 $23500$）。
• 整个二分过程中，$mid$ 的最大可能取值仅为 $23500$，计算出的最大平方值为 $5.5225 \times 10^8$，远小于 32 位 int 的上限（约 $2.147 \times 10^9$），绝不会发生整型溢出。
• 出题人特意设定数据范围 $n \le 47000$，正是因为 $\sqrt{2^{31}-1} \approx 46340.95$；如果考生误以为 $mid$ 可以取到 $47000$（$47000^2 \approx 2.209 \times 10^9$ 确实超限）而忽视了二分首次迭代 $mid = n / 2 \le 23500$，就会掉入出题陷阱。
• 因此，在题目给定的输入数据约束下，程序不存在所述的溢出缺陷，不需要强制转换为 64 位整数。故说法错误。

❓ 单选题

5. 当输入为 2 1 时，输出的第一个数最接近（ ）。

A. 1
B. 1.414
C. 1.5
D. 2
正确答案： C

深度解析：

1. $n = 2, k = 1$。
2. solve1() 计算 $\lfloor \sqrt{2} \rfloor = 1$。
3. 进入 solve2(1.0) 执行 $k = 1$ 次迭代： \(x_1 = \frac{1 + 2 / 1}{2} = \frac{3}{2} = \mathbf{1.5}\) 故输出的第一个数为 1.5，对应 C 选项。

6. 当输入为 3 10 时，输出的第一个数最接近（ ）。

A. 1.7
B. 1.732
C. 1.75
D. 2
正确答案： B

深度解析：
牛顿迭代法求平方根具有 二阶平方收敛速度（每次迭代有效精度翻倍）。在迭代 10 次后，计算结果已经完全收敛至双精度浮点极限： \(\sqrt{3} \approx 1.7320508...\) 选项中最接近的值为 1.732，对应 B 选项。

7. 当输入为 256 11 时，输出的第一个数（ ）。

A. 等于 16
B. 接近但小于 16
C. 接近但大于 16
D. 前三种情况都有可能
正确答案： A

深度解析：

1. $n = 256$ 是完全平方数，solve1() 已经求出了精确平方根：$x_0 = \sqrt{256} = 16$。
2. 代入牛顿迭代式进行计算： \(x_1 = \frac{16 + 256 / 16}{2} = \frac{16 + 16}{2} = 16\)
3. 在之后的每一轮迭代中，$x$ 的值都恒等于 16.0，没有任何浮点误差累积。 因此输出的第一个数严格等于 16，对应 A 选项。

💡 备考总结

回顾 2022 年阅读程序大题，题目设计兼具算法广度与数学深度：

1. 重视位运算技巧：熟练掌握常用的掩码与移位操作（如 0x33, 0x55 配合交叉实现 Morton 码），能够看透其几何与数学本质。
2. 掌握经典动态规划模型：如高楼扔鸡蛋问题，理解最坏情况下最优策略的建模思维及状态转移方程的时间复杂度推导。
3. 理解数值计算与浮点特性：熟悉二分法和牛顿迭代法的收敛特点，注意整型溢出（int 范围）以及浮点数比较时的精度局限。

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

GESP 学习专题站：GESP WIKI

"luogu-"系列题目可在洛谷题库进行在线评测。

"bcqm-"系列题目可在编程启蒙题库进行在线评测。

欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答

欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总

欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助