一、最终答案速查
单项选择题
题号 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 答案 B D C C B D D C B A A D C A B
阅读程序
程序 判断题 单选题 程序（1） 16. √ 17. × 18. √ 19. A 20. C 21. C 程序（2） 22. √ 23. × 24. × 25. B 26. A 27. C 程序（3） 28. × 29. √ 30. √ 31. B 32. D 33. C
完善程序
程序 ① ② ③ ④ ⑤ 进制减半 D B D B C 平衡分割 B D C A D
二、单项选择题超级详细解析
第 1 题：整数类型与精度
答案：B，long long。
题目中的数应理解为 1018+110^{18}+11018+1。
C++ 中常见类型的情况如下：
* int 通常是 32 位，最大值约为 2.1×1092.1\times10^92.1×109，远远不够。
* float 虽然表示范围较大，但有效数字通常只有约 7 位，不能精确保存这么大的整数。
* double 有约 15～16 位十进制有效数字，而 1018+110^{18}+11018+1 有 19 位，也无法区分 101810^{18}1018 和 1018+110^{18}+11018+1。
* long long 通常是 64 位有符号整数，最大值为 263−1=92233720368547758072^{63}-1=9223372036854775807263−1=9223372036854775807，大于 1018+110^{18}+11018+1，并且整数范围内可以精确存储。
所以选择 B。
第 2 题：十六进制转八进制
答案：D，1365。
先把十六进制数 2F5 转成十进制：
2F516=2×162+15×16+5=512+240+5=7572F5_{16}=2\times16^2+15\times16+5=512+240+5=7572F516 =2×162+15×16+5=512+240+5=757。
再把 757 不断除以 8：
* 757÷8=94⋯5757\div8=94\cdots5757÷8=94⋯5
* 94÷8=11⋯694\div8=11\cdots694÷8=11⋯6
* 11÷8=1⋯311\div8=1\cdots311÷8=1⋯3
* 1÷8=0⋯11\div8=0\cdots11÷8=0⋯1
余数从下往上读，得到 1365，所以选择 D。
第 3 题：整除、取模和运算顺序
答案：C，7。
代码为：
整数除法中，7 / 3 的结果是 2；7 % 3 的结果是 1。
乘除取模优先级相同，从左向右计算：
7/3×3+7%3=2×3+1=77/3\times3+7\%3=2\times3+1=77/3×3+7%3=2×3+1=7。
所以选择 C。
第 4 题：栈的出栈序列
答案：C，3，1，2，4 不可能出现。
栈的特点是“后进先出”。要先弹出 3，就必须先把 1、2、3 依次压入栈。此时栈从底到顶是：
弹出 3 后，栈顶是 2。下一项要求弹出 1，但 1 被 2 压在下面，不先弹出 2 就不能弹出 1。因此序列 3，1，2，4 不可能出现。
其他三个序列都可以通过适时入栈、出栈得到。
第 5 题：完全二叉树的叶子数量
答案：B，50。
在按照从 1 开始编号的完全二叉树中：
* 编号不超过 ⌊n/2⌋\lfloor n/2\rfloor⌊n/2⌋ 的结点至少有一个孩子；
* 编号从 ⌊n/2⌋+1\lfloor n/2\rfloor+1⌊n/2⌋+1 到 nnn 的结点都是叶子。
当 n=100n=100n=100 时，叶子编号为 51～100，共：
100−50=50100-50=50100−50=50 个。
所以选择 B。
第 6 题：3 或 5 的倍数之和
答案：D，2418。
1～100 中 3 的倍数有 33 个：
3+6+⋯+99=3(1+2+⋯+33)=3×33×342=16833+6+\cdots+99=3(1+2+\cdots+33)=3\times\frac{33\times34}{2}=16833+6+⋯+99=3(1+2+⋯+33)=3×233×34 =1683。
5 的倍数有 20 个：
5+10+⋯+100=5(1+2+⋯+20)=5×20×212=10505+10+\cdots+100=5(1+2+\cdots+20)=5\times\frac{20\times21}{2}=10505+10+⋯+100=5(1+2+⋯+20)=5×220×21 =1050。
15 的倍数既是 3 的倍数又是 5 的倍数，被重复计算了一次，需要减去：
15+30+⋯+90=15(1+2+⋯+6)=15×21=31515+30+\cdots+90=15(1+2+\cdots+6)=15\times21=31515+30+⋯+90=15(1+2+⋯+6)=15×21=315。
最终：
1683+1050−315=24181683+1050-315=24181683+1050−315=2418。
所以选择 D。
第 7 题：上楼梯动态规划
答案：D，81。
设 fif_ifi 表示走到第 iii 级台阶的方法数。最后一步可能走 1、2 或 3 级，因此：
fi=fi−1+fi−2+fi−3f_i=f_{i-1}+f_{i-2}+f_{i-3}fi =fi−1 +fi−2 +fi−3 。
地面视为第 0 级，什么也不走是一种方案，所以 f0=1f_0=1f0 =1。依次计算：
台阶 0 1 2 3 4 5 6 7 8 方法数 1 1 2 4 7 13 24 44 81
所以走到第 8 级共有 81 种走法，选择 D。
第 8 题：BFS 入队顺序
答案：C，14 个。
BFS 的关键是：一个格子第一次被发现时就立刻标记并入队。本题严格按照“上、下、左、右”的顺序扩展。
从 S 开始，到 E 第一次入队为止，入队顺序如下：
入队编号 坐标 说明 1 (0,0) S 2 (1,0) 从 S 向下 3 (0,1) 从 S 向右 4 (2,0) 从 (1,0) 向下 5 (1,1) 从 (1,0) 向右 6 (0,2) 从 (0,1) 向右 7 (2,1) 从 (2,0) 向右 8 (1,2) 从 (1,1) 向右 9 (2,2) 从 (2,1) 向右 10 (3,2) 从 (2,2) 向下 11 (4,2) 从 (3,2) 向下 12 (3,3) 从 (3,2) 向右 13 (4,1) 从 (4,2) 向左 14 (3,4) E，从 (3,3) 向右
E 第一次入队时，已经入队的格子包括 S 和 E，共 14 个，所以选择 C。
第 9 题：最大公约数计数
答案：B，6 个。
因为 gcd(n,60)=6\gcd(n,60)=6gcd(n,60)=6，所以 nnn 一定能写成 n=6kn=6kn=6k。
又因为 60=6×1060=6\times1060=6×10，于是：
gcd(6k,60)=6gcd(k,10)=6\gcd(6k,60)=6\gcd(k,10)=6gcd(6k,60)=6gcd(k,10)=6。
因此必须满足 gcd(k,10)=1\gcd(k,10)=1gcd(k,10)=1，也就是 kkk 不能含有因数 2 或 5。
由 1≤n≤1001\le n\le1001≤n≤100 得到 1≤k≤161\le k\le161≤k≤16。其中与 10 互质的数为：
共 6 个，对应的 nnn 为：
所以选择 B。
第 10 题：最少硬币数量
答案：A，3 枚。
9 元可以表示为：
9=4+4+19=4+4+19=4+4+1。
所以 3 枚硬币可以完成。两枚硬币的和只可能是 2、5、7、8、10、12，不可能等于 9。因此最少是 3 枚，选择 A。
第 11 题：数组与指针
答案：A，输出 14,13。
初始数组：
p = a + 2，所以 p 指向 a[2]。
第一条赋值：
* p - 1 指向 a[1]；
* p[0] 是 a[2]，值为 5；
* p[2] 是 a[4]，值为 9。
因此 a[1] = 5 + 9 = 14。
第二条赋值：
* p[1] 是 a[3]；
* *(a + 1) 是刚刚修改后的 a[1]，值为 14；
* a[0] 为 1。
因此 a[3] = 14 - 1 = 13，最终输出 14,13，选择 A。
第 12 题：二分查找最坏比较次数
答案：D，10 次。
每比较一次，待查区间大约缩小一半。
因为：
* 29=512<10002^9=512<100029=512<1000；
* 210=1024≥10002^{10}=1024\ge1000210=1024≥1000。
所以最坏情况下需要 10 次与数组元素比较，选择 D。
第 13 题：由前缀和还原原数组
答案：C，58。
前缀和满足：
si=3i2+is_i=3i^2+isi =3i2+i。
根据前缀和定义：
a10=s10−s9a_{10}=s_{10}-s_9a10 =s10 −s9 。
分别计算：
s10=3×102+10=310s_{10}=3\times10^2+10=310s10 =3×102+10=310；
s9=3×92+9=252s_9=3\times9^2+9=252s9 =3×92+9=252。
所以：
a10=310−252=58a_{10}=310-252=58a10 =310−252=58。
选择 C。
第 14 题：中位数使距离和最小
答案：A，37。
在数轴上，使到所有点的距离之和最小的位置是这些点的中位数。
7 个点已经有序：
中间的第 4 个数是 7，所以取 P=7P=7P=7。
距离和为：
6+4+3+0+3+8+13=376+4+3+0+3+8+13=376+4+3+0+3+8+13=37。
所以选择 A。
第 15 题：握手定理
答案：B，18 条边。
无向图中所有顶点的度数之和等于边数的 2 倍。
度数总和为：
4×3+6×4=12+24=364\times3+6\times4=12+24=364×3+6×4=12+24=36。
所以边数为：
36÷2=1836\div2=1836÷2=18。
选择 B。
三、阅读程序（1）逐行注释与解析
逐行注释代码
程序整体作用
每执行一次循环，就删掉 nnn 的一个二进制位。因此：
* 循环次数等于 nnn 的二进制位数；
* x 等于“二进制位数 + 1”；
* y 等于“二进制中 1 的数量 + 1”。
当输入为 0 时，循环一次也不执行，直接输出 1 1。
第 16 题
答案：√。
输入 3，二进制为 11：
循环 n 最低位 x y n 除以 2 后 初始 3 — 1 1 — 第 1 次 3 1 2 2 1 第 2 次 1 1 3 3 0
最终输出 3 3，所以判断正确。
第 17 题
答案：×。
删除 else 分支中的 ++x; 后：
* 遇到二进制位 0，x 增加；
* 遇到二进制位 1，y 增加。
此时 x 和 y 分别统计 0 和 1 的数量，再各自加上初值 1，它们并不一定相等。
例如输入 7，二进制是 111。删除该语句后，x 始终为 1，而 y 变成 4，显然不相等。
第 18 题
答案：√。
原程序中，处理每一个二进制位时 x 都会增加；只有二进制位为 1 时 y 才增加。
二进制位 1 的数量不可能超过总位数，因此 x 一定不小于 y。
第 19 题
答案：A，陷入死循环。
如果条件改成 while (n >= 0)，当 n 变成 0 后：
* 0 >= 0 成立，继续循环；
* 0 % 2 == 0，x 不断增加；
* 0 / 2 仍然是 0。
所以 n 永远不会变成负数，循环无法结束。
第 20 题
答案：C，输出 4 3。
6 的二进制是 110，一共有 3 位，其中有 2 个 1。
所以：
* x = 1 + 3 = 4；
* y = 1 + 2 = 3。
输出 4 3。
第 21 题
答案：C，31 次。
第二个输出数为 2，意味着：
1+二进制中 1 的数量=21+\text{二进制中 1 的数量}=21+二进制中 1 的数量=2。
所以输入数的二进制中恰好只有一个 1，也就是输入必须是 2 的幂：
20,21,22,…,2302^0,2^1,2^2,\ldots,2^{30}20,21,22,…,230。
题目范围是 0 到 231−12^{31}-1231−1，其中共有 31 个这样的数，所以选择 C。
四、阅读程序（2）逐行注释与解析
逐行注释代码
程序整体作用与关键陷阱
这是一段高精度加法程序。数组使用“低位在前”的方式保存数字，例如 123 保存为：
程序最大的陷阱是：它固定从 max(a_len,b_len) 输出到 0，因此总会输出“较长输入的位数 + 1”个位置。没有产生最高位进位时，最前面会多输出一个 0。
第 22 题
答案：√。
123 + 456 = 579。两个输入都是 3 位，程序输出下标 3、2、1、0，共 4 个位置。
因为没有千位进位，所以 c[3]=0，最终输出：
题目说法正确。
第 23 题
答案：×。
即使两个输入都没有前导零，只要它们相加后没有产生新的最高位进位，程序仍会把额外的 c[max(a_len,b_len)] 输出出来。
例如 123 + 456 输出 0579，出现了前导零。因此说法错误。
第 24 题
答案：×。
改成 c[i] = a[i] + b[i]; 后，程序不再把低位进位加到当前位。但是“结果一定比原来小”并不成立，因为如果原本没有任何进位，修改前后结果完全相同。
例如 12 + 34 每一位相加都不超过 9，删除 carry[i] 不会改变结果。因此“必定更小”是错误的。
第 25 题
答案：B，013023。
12345+678=1302312345+678=1302312345+678=13023。
最长输入有 5 位，程序固定输出 6 个位置。最高的第 6 位为 0，因此输出：
选择 B。
第 26 题
答案：A，01010。
把判断条件改成 c[i] > 10 后，恰好等于 10 时不会进位，也不会减去 10。
输入 95 15：
* 个位：5+5=105+5=105+5=10，条件 10 > 10 为假，所以 c[0]=10；
* 十位：9+1=109+1=109+1=10，仍不进位，所以 c[1]=10；
* 百位：c[2]=0。
cout 输出一个值为 10 的整数时会打印两个字符 10。从高位到低位连接起来就是：
所以选择 A。
第 27 题
答案：C。
题目中的“和小于 10n10^n10n”说明两个 nnn 位数相加后没有产生第 n+1n+1n+1 位，也就是额外最高位 c[n] 为 0。
程序仍然会从下标 nnn 输出到 0，共输出 n+1n+1n+1 个字符。因此字符串长度一定为 n+1n+1n+1，且第一个字符是 0，选择 C。
五、阅读程序（3）逐行注释与解析
逐行注释代码
程序整体作用
程序构造一棵“质数前缀树”：
1. 当前数字 x 必须是质数，否则立即剪枝；
2. 如果 x < n，就在末尾追加一位数字，继续搜索；
3. 如果 x >= n，输出 x，并停止向下扩展。
因此，每个输出数本身是质数，而且从右向左不断删除末位后，得到的每一级前缀也都是质数。
第 28 题
答案：×。
输入 10 时，一位质数 2、3、5、7 都小于 10，需要继续追加一位。能够输出的两位质数为：
共 9 行，不是 10 行，所以说法错误。
第 29 题
答案：√。
如果 n≤5n\le5n≤5，主函数执行到 search_result(5) 时：
* 5 是质数；
* 5≥n5\ge n5≥n；
* 因此程序直接输出 5。
所以输出中一定包含 5。
第 30 题
答案：√。
当 n>10n>10n>10 时，继续递归的数字最终会成为多位数。一个多位质数的个位不可能是：
因此真正有可能产生质数的末位只需要考虑 1、3、7、9。修改后的循环尝试 1、3、5、7、9，已经包含全部可能的奇数末位；末位 5 的多位数会被 check_prime 自动排除。
所以删掉偶数和 0 的尝试只减少无效搜索，不会改变输出结果。
第 31 题
答案：B，第 3 行是 29。
输入 24 时，程序按深度优先顺序搜索。
首先从 2 开始：
* 23 是质数，但 23<2423<2423<24，所以不会直接输出 23，而是继续在末尾追加数字；
* 233 是质数且不小于 24，输出第 1 行；
* 239 是质数且不小于 24，输出第 2 行；
* 之后轮到 29。29 是质数且不小于 24，输出第 3 行。
前三行是：
所以选择 B。
第 32 题
答案：D。
* A 错误：输出不一定递增。例如输入 24 时先输出 233、239，之后才输出 29。
* B 错误：随着 nnn 增大，原来直接输出的一个质数节点可能继续展开成多个质数孩子，输出行数可能增加。
* C 错误：个位还可能是 1 或 9；输入较小时还可能直接输出一位质数 2 或 5。
* D 正确：大于等于 10 的输出数一定是通过某个父节点追加一位得到的，而程序只有在父节点为质数且小于 nnn 时才会继续递归。因此删掉输出数的末位后，得到的父节点一定是质数。
第 33 题
答案：C，14 行。
输入 200 时，输出结果依次为：
共 14 行，所以选择 C。
六、完善程序（1）进制减半
核心原理
输入数原本使用 mnmnmn 进制，其中这里的 mnmnmn 表示 m×nm\times nm×n。程序把答案数组 b 当作 nnn 进制数，并使用低位在前的方式保存。
每读入一个原进制数位 x，相当于：
Anew=Aold×(mn)+xA_{new}=A_{old}\times(mn)+xAnew =Aold ×(mn)+x。
因为目标是 nnn 进制，所以乘以 nnn 相当于整体左移一位；剩下还需要把每一位乘以 mmm。这正是①使用 b[j - 1] * m 的原因。
补全并逐行注释后的代码
各空详细解析
①：D，B[J - 1] * M
旧数乘以 mn=m×nmn=m\times nmn=m×n。在 nnn 进制中，乘以 nnn 就是把所有数位向高位移动一格，因此新位置 b[j] 来自旧位置 b[j-1]；同时还要乘以 mmm。
所以填写：
②：B，X
完成旧数乘以原进制后，还要加上新读入的最低位 x，因此直接令：
③：D，B[J] / N
在 nnn 进制中，如果当前位达到或超过 nnn，整除 nnn 得到向高位传递的进位。
④：B，B[J] % N
当前位最终只能保留除以 nnn 的余数，范围必定在 0 到 n−1n-1n−1 之间。
⑤：C，LEN > 1 && B[LEN - 1] == 0
需要删除最高位多余的 0，但表示数值 0 时必须至少输出一位，所以条件必须是 len > 1，不能把长度减到 0。
七、完善程序（2）平衡分割
题意整理
题目原文中“第 pi+1p_i+1pi +1 个数到第 pi+1p_i+1pi +1 个数”应理解为“第 pi+1p_i+1pi +1 个数到第 pi+1p_{i+1}pi+1 个数”。
程序要枚举字符串的所有连续分段方法。每一段计算平均值，最终让所有分段平均值中的最大值与最小值之差尽可能小。
split(l,cnt,mnb,mxb) 的含义是：
* l：下一段从第 l 个元素开始；
* cnt：目前已经使用的切分位置数量；
* mnb：已确定各段平均值的最小值；
* mxb：已确定各段平均值的最大值。
补全并逐行注释后的代码
各空详细解析
①：B
对于字符 0～9：
对于字符 A～F：
选项 B：
当 c >= 'A' 时，展开为 c - ('A' - 10)，也就是 c - 'A' + 10。
②：D
当前段必须从 l 开始，右端点可以是 l、l+1、……、n，因此循环为：
这样才能枚举所有可能的连续段。
③：C
区间 a[l..r] 的长度是 r-l+1，平均值是：
乘以 1.0 是为了进行浮点除法，避免整数除法丢失小数部分。
④：A
当前段选择为 a[l..r] 后：
* 下一段从 r+1 开始；
* 只有当 r<n 时，r 才是真正的切分位置，所以 cnt 增加 r<n；
* 新的最小平均值是 min(mnb,nwb)；
* 新的最大平均值是 max(mxb,nwb)。
⑤：D
数组从 1 开始使用，所以初始位置是 1；还没有切分，所以 cnt=0。
为了让第一段平均值能够正确更新最小值和最大值：
* mnb 初始化为极大值 1e100；
* mxb 初始化为极小值 -1e100。
因此调用为：
