2026年CSP-J初赛：参考答案与解析

答案速查表

单项选择题表

答题编号	原卷题号	答案
1	第 1 题	B
2	第 2 题	D
3	第 3 题	C
4	第 4 题
5	第 5 题	B
6	第 6 题	D
7	第 7 题
8	第 8 题	C
9	第 9 题	B
10	第 10 题	A
11	第 11 题
12	第 12 题	D
13	第 13 题	C
14	第 14 题	A
15	第 15 题	B

阅读程序题表

答题编号	原卷题号	答案
16	第 1 组第 1 小题	A（正确）
17	第 1 组第 2 小题	B（错误）
18	第 1 组第 3 小题	A（正确）
19	第 1 组第 4 小题	A
20	第 1 组第 5 小题	C
21	第 1 组第 6 小题
22	第 2 组第 1 小题	A（正确）
23	第 2 组第 2 小题	B（错误）
24	第 2 组第 3 小题
25	第 2 组第 4 小题	B
26	第 2 组第 5 小题	A
27	第 2 组第 6 小题	C
28	第 3 组第 1 小题	B（错误）
29	第 3 组第 2 小题	A（正确）
30	第 3 组第 3 小题
31	第 3 组第 4 小题	B
32	第 3 组第 5 小题	D
33	第 3 组第 6 小题	C

完成程序题表

答题编号	原卷题号	答案
34	第 1 组第 1 小题	D
35	第 1 组第 2 小题	B
36	第 1 组第 3 小题	D
37	第 1 组第 4 小题	B
38	第 1 组第 5 小题	C
39	第 2 组第 1 小题	B
40	第 2 组第 2 小题	D
41	第 2 组第 3 小题	C
42	第 2 组第 4 小题	A
43	第 2 组第 5 小题	D

配分说明

本题采用教师指定的 30／40／30 自定义配分，阅读判断题每题 1.5 分；其余分数按各部分选择题数量均分。源资料中的旧分值另行保留在转换记录中，正式计分以本题题面为准。

• 答题编号 16：原文标注 1 分，本题计 1.5 分。

一、单项选择题

第 1 题（2 分）

下列 C++ 数据类型中，能够精确存储 $10^{18}+1$ 这个整数的是（ ）。

• A. float
• B. long long
• C. double
• D. int

答案：B

解析：

正确答案： B

考查知识点： 变量定义

解题分析：

在通常竞赛环境中，long long 为 64 位有符号整数类型，其最大值为 $2^{63}-1=9223372036854775807$，大于 $10^{18}+1$，且范围内的整数都能精确保存。常用的 32 位 int 超出范围；float 和 double 虽可表示这一数量级，但有效二进制位数不足，不能精确保存该整数。

选项分析：

• A：常用单精度浮点数的有效位数不足。
• B：64 位有符号整数能够精确存储该数。
• C：常用双精度浮点数只有 53 位二进制有效精度，不能精确表示这个奇数。
• D：常用 32 位整数的取值范围不足。

第 2 题（2 分）

十六进制数 2F5 转换为八进制数是（ ）。

• A. 1364
• B. 1635
• C. 1405
• D. 1365

答案：D

解析：

正确答案： D

考查知识点： 进制转换

解题分析：

先转为十进制：$2\times16^2+15\times16+5=757$。又有 $757=1\times8^3+3\times8^2+6\times8+5$，故八进制表示为 1365。

选项分析：

• D：与上述计算结果一致。
• A、B、C：与上述计算结果不符。

第 3 题（2 分）

执行下列 C++ 代码，输出是（ ）。

int a = 7, b = 3;
std::cout << a / b * b + a % b;

• A.

  9
  

• B.

  10
  

• C.

  7
  

• D.

  6
  

答案：C

解析：

正确答案： C

考查知识点： 算术运算符

解题分析：

整数除法 7 / 3 得到 2，取余 7 % 3 得到 1。乘除取余优先于加法，乘除按从左到右计算，因此表达式值为 $2\times3+1=7$。

选项分析：

• C：与上述计算结果一致。
• A、B、D：与上述计算结果不符。

第 4 题（2 分）

初始时栈为空，将 1、2、3、4 依次入栈，入栈过程中允许随时出栈。下列出栈序列中不可能出现的是（ ）。

• A. 2，4，3，1
• B. 1，2，3，4
• C. 3，1，2，4
• D. 1，4，3，2

答案：C

解析：

正确答案： C

考查知识点： 栈

解题分析：

栈遵循后进先出。若第一个弹出 3，则 1、2、3 已按顺序入栈；弹出 3 后，2 仍压在 1 上方，不可能跳过 2 先弹出 1，因此序列 C 不可能。

选项分析：

• A：压入 1、2 后弹出 2，再压入 3、4，依次弹出 4、3、1，可以实现。
• B：每压入一个数就立刻弹出，可以实现。
• C：弹出 3 后不能越过 2 弹出 1，因此本题选 C。
• D：压入并弹出 1，再压入 2、3、4，依次弹出 4、3、2，可以实现。

第 5 题（2 分）

一棵有 100 个结点的完全二叉树，其叶子结点个数是（ ）。

• A. 49
• B. 50
• C. 64
• D. 51

答案：B

解析：

正确答案： B

考查知识点： 二叉树

解题分析：

按从上到下、从左到右的顺序将结点编号为 1 至 100。结点 $i$ 有左孩子的条件是 $2i\le100$，因此 1 至 50 号为非叶子，51 至 100 号为叶子，共 50 个。

选项分析：

• B：与上述计算结果一致。
• A、C、D：与上述计算结果不符。

第 6 题（2 分）

执行下列代码后 s 的值是（ ）。

int s = 0;
for (int i = 1; i <= 100; i++)
    if (i % 3 == 0 || i % 5 == 0)
        s += i;

• A. 3048
• B. 2733
• C. 2318
• D. 2418

答案：D

解析：

正确答案： D

考查知识点： 循环结构

解题分析：

统计 1 至 100 内是 3 或 5 的倍数的整数之和。3 的倍数之和为 $3(1+\cdots+33)=1683$；5 的倍数之和为 $5(1+\cdots+20)=1050$。15 的倍数被重复统计一次，其和为 $15(1+\cdots+6)=315$，所以结果为 $1683+1050-315=2418$。逻辑或不会使同一整数在一次循环中累加两遍。

选项分析：

• D：与上述计算结果一致。
• A、B、C：与上述计算结果不符。

第 7 题（2 分）

上楼梯每步可上 1 级、2 级或 3 级，从地面（可视为第 0 级）走到第 8 级台阶共有多少种不同走法（ ）。

• A. 44
• B. 121
• C. 149
• D. 81

答案：D

解析：

正确答案： D

考查知识点： 递推

解题分析：

设 $f(k)$ 为走到第 $k$ 级的方案数。按最后一步跨 1、2、3 级分类，有 $f(k)=f(k-1)+f(k-2)+f(k-3)$，越界项按 0 处理。由 $f(0)=1$，依次得到 $f(1),\ldots,f(8)$ 为 1、2、4、7、13、24、44、81，所以答案是 81。

选项分析：

• D：与上述计算结果一致。
• A、B、C：与上述计算结果不符。

第 8 题（2 分）

下图为 $5\times5$ 网格，行号、列号均从 0 开始，# 为障碍，. 为可通行格：

S . . # .
. . . # .
. . . # .
# # . . E
. . . # .

从 S 出发做广度优先搜索（BFS）：初始时把 S 入队；每次取出队首格子，按“上、下、左、右”（上＝行号减 1，下＝行号加 1，左＝列号减 1，右＝列号加 1）的顺序遍历它的四个相邻格子，越界、障碍或已访问的格子跳过，其余格子标记为已访问并入队。当 E 第一次入队时，已经入队过的格子（含 S 和 E）共有多少个（ ）。

• A. 15
• B. 12
• C. 14
• D. 13

答案：C

解析：

正确答案： C

考查知识点： 广度优先搜索

解题分析：

按照指定的方向顺序，首次入队的格子依次为：

(0,0), (1,0), (0,1), (2,0), (1,1), (0,2), (2,1),
(1,2), (2,2), (3,2), (4,2), (3,3), (4,1), (3,4)

第 14 个格子是 E，故已有 14 个不同格子入队。注意题目统计“已经入队过”，不是统计此时仍留在队列中的格子。

选项分析：

• C：与上述计算结果一致。
• A、B、D：与上述计算结果不符。

第 9 题（2 分）

满足 $1\le n\le100$ 且 $\gcd(n,60)=6$ 的正整数 $n$ 共有多少个（ ）。

• A. 8
• B. 6
• C. 4
• D. 5

答案：B

解析：

正确答案： B

考查知识点： 最大公约数

解题分析：

令 $n=6k$，则 $1\le k\le16$，且 $\gcd(6k,60)=6\gcd(k,10)$。所以 $k$ 必须与 10 互质，可取 1、3、7、9、11、13，对应 $n$ 为 6、18、42、54、66、78，共 6 个。

选项分析：

• B：与上述计算结果一致。
• A、C、D：与上述计算结果不符。

第 10 题（2 分）

某国硬币面值为 1 元、4 元、6 元且数量不限，凑出 9 元最少需要多少枚（ ）。

• A. 3
• B. 4
• C. 5
• D. 2

答案：A

解析：

正确答案： A

考查知识点： 枚举

解题分析：

用 $4+4+1=9$ 可以用 3 枚凑出。1 枚显然不行；2 枚可能的金额只有 2、5、7、8、10、12，均不是 9，所以最少为 3 枚。

选项分析：

• A：3 枚可行，且 1、2 枚均不可行。
• B、C：都不是最少枚数。
• D：两枚硬币无法凑出 9 元。

第 11 题（2 分）

执行下列代码，输出是（ ）。

int a[5] = {1, 3, 5, 7, 9};
int *p = a + 2;
*(p - 1) = p[0] + p[2];
p[1] = *(a + 1) - a[0];
cout << a[1] << "," << a[3];

• A.

  14,13
  

• B.

  8,13
  

• C.

  14,7
  

• D.

  14,2
  

答案：A

解析：

正确答案： A

考查知识点： 指针

解题分析：

p 指向 a[2]，因此 *(p-1) 是 a[1]，p[0] 是 a[2]，p[2] 是 a[4]。第一条赋值令 a[1]=5+9=14；随后 p[1] 即 a[3]，被赋为更新后的 a[1]-a[0]=14-1=13。输出为：

14,13

选项分析：

• A：与上述计算结果一致。
• B、C、D：与上述计算结果不符。

第 12 题（2 分）

在含 1000 个互不相同元素的升序数组中，用二分法查找给定值（返回元素位置或报告不存在），最坏情况下需要与数组元素比较多少次（ ）。

• A. 500
• B. 9
• C. 11
• D. 10

答案：D

解析：

正确答案： D

考查知识点： 二分查找

解题分析：

按二分查找中“与一个中间元素比较一次”的通常计数方式，最坏比较次数为 $\lfloor\log_2 1000\rfloor+1=10$。剩余候选区间的最大长度可依次为 1000、500、250、125、62、31、15、7、3、1，最多需要比较 10 个中间元素。

选项分析：

• D：与上述计算结果一致。
• A、B、C：与上述计算结果不符。

第 13 题（2 分）

数组 a[1..n] 的前缀和数组 s（即 $s[i]=a[1]+a[2]+\cdots+a[i]$）满足 $s[i]=3i^2+i$。则 a[10] 的值是（ ）。

• A. 252
• B. 310
• C. 58
• D. 61

答案：C

解析：

正确答案： C

考查知识点： 前缀和

解题分析：

由前缀和定义，$a[10]=s[10]-s[9]$。其中 $s[10]=3\times10^2+10=310$，$s[9]=3\times9^2+9=252$，所以 $a[10]=310-252=58$。

选项分析：

• C：与上述计算结果一致。
• A、B、D：与上述计算结果不符。

第 14 题（2 分）

数轴上有 7 个点，坐标分别为 1、3、4、7、10、15、20。在数轴上选取一个整数坐标点 P，使 P 到这 7 个点的距离之和最小，这个最小距离和是（ ）。

• A. 37
• B. 42
• C. 40
• D. 38

答案：A

解析：

正确答案： A

考查知识点： 基础数学知识

解题分析：

到一组数的绝对距离和在中位数处取得最小值，因此取 $P=7$。距离和为 $6+4+3+0+3+8+13=37$。也可以将最左与最右的点两两配对：每对的距离和下界分别为 19、12、6，取 7 时同时达到这些下界。

选项分析：

• A：与上述计算结果一致。
• B、C、D：与上述计算结果不符。

第 15 题（2 分）

一个无向图有 10 个顶点，其中 4 个顶点的度为 3，其余顶点的度均为 4，则该图的边数是（ ）。

• A. 36
• B. 18
• C. 17
• D. 20

答案：B

解析：

正确答案： B

考查知识点： 图的概念

解题分析：

无向图所有顶点的度数之和等于边数的 2 倍。总度数为 $4\times3+6\times4=36$，因此边数为 $36/2=18$。

选项分析：

• B：与上述计算结果一致。
• A、C、D：与上述计算结果不符。

二、阅读程序

第 1 组

（1）阅读以下程序

01  #include <iostream>
02  using namespace std;
03  int main() {
04      int n;
05      cin >> n;
06      int x = 1, y = 1;
07      while (n > 0) {
08          if (n % 2 == 0) {
09              ++x;
10          } else {
11              ++x;
12              ++y;
13          }
14          n = n / 2;
15      }
16      cout << x << ' ' << y << endl;
17      return 0;
18  }

以下问题均假定输入的 $n$ 为不超过 $2^{31}-1$ 的非负整数。

识别校注：第 12 行原文被手写笔迹遮挡，本版暂按“++y;”复原，需对照清晰原卷确认。

第 1 小题（1.5 分）

当输入为 3 时，程序输出为 3 3。（ ）

• A. 正确
• B. 错误

答案：A（正确）

解析：

判断结果： 正确

考查知识点： 进制转换

判断依据：

循环中 n 依次为 3、1，都进入奇数分支，各令 x、y 加 1。两者初值均为 1，最终都为 3。

第 2 小题（1.5 分）

将第 11 行的 ++x; 删除后，程序输出的两个数一定相等。（ ）

• A. 正确
• B. 错误

答案：B（错误）

解析：

判断结果： 错误

考查知识点： 进制转换

判断依据：

删除该行后，偶数分支只增加 x，奇数分支只增加 y。例如输入 1 时，仅执行一次奇数分支，输出 1 2，两数不相等。

正确说法：

修改后，x 等于 1 加上循环中出现偶数的次数，y 等于 1 加上循环中出现奇数的次数；这两个次数不一定相等。

第 3 小题（1.5 分）

假设输入为非负整数，则程序输出的第一个数一定不小于第二个数。（ ）

• A. 正确
• B. 错误

答案：A（正确）

解析：

判断结果： 正确

考查知识点： 进制转换

判断依据：

每轮循环都会使 x 增加 1，只有奇数分支才使 y 增加 1，且二者初值相同。因此总有 x>=y。输入 0 时循环不执行，两者均为 1，同样成立。

第 4 小题（2.944445 分）

将第 7 行的 while (n > 0) 改为 while (n >= 0) 后，程序可能出现的问题是（ ）。

• A. 陷入死循环
• B. 输出结果比原来大
• C. 输出结果比原来小
• D. 输出结果不受影响

答案：A

解析：

正确答案： A

考查知识点： 循环结构

解题分析：

当 n 经过整数除以 2 变成 0 后，0>=0 仍成立，而且 0/2 仍为 0，所以循环条件始终不能变为假，程序无法按原逻辑退出循环输出结果。

选项分析：

• A：n 为 0 后不再变化，循环不能正常结束。
• B、C、D：程序不能正常走到原来的输出语句，不能据此比较一个正常的最终输出。

第 5 小题（2.944445 分）

当输入为 6 时，输出为（ ）。

• A.

  3 3
  

• B.

  4 2
  

• C.

  4 3
  

• D.

  5 2
  

答案：C

解析：

正确答案： C

考查知识点： 进制转换

解题分析：

n 在三轮循环中依次为 6、3、1。x 每轮增加 1，从 1 变为 4；y 只在 3、1 两轮增加，从 1 变为 3。最终输出 4 3。

选项分析：

• C：与上述计算结果一致。
• A、B、D：与上述计算结果不符。

第 6 小题（2.944445 分）

若输入 $n$ 依次取遍 $0,1,2,\ldots,2^{31}-1$ 中的所有整数，则程序输出的第二个数恰好为 2 的次数为（ ）。

• A. 16
• B. 30
• C. 31
• D. 32

答案：C

解析：

正确答案： C

考查知识点： 进制转换

解题分析：

循环用除以 2 逐个移去二进制最低位，n%2 为 1 时令 y 加 1。因 y 初值是 1，最终为 2 等价于原数二进制恰有一个 1，即 $n=2^k$。范围内 $k$ 可为 0 至 30，共 31 个；输入 0 时 y=1，不计入。

选项分析：

• C：与上述计算结果一致。
• A、B、D：与上述计算结果不符。

第 2 组

（2）阅读以下程序

01  #include <algorithm>
02  #include <iostream>
03  #include <string>
04  using namespace std;
05  int a[100007], b[100007], c[100007], carry[100007];
06  string input_str;
07  int a_len, b_len;
08  int main() {
09      cin >> input_str;
10      a_len = input_str.size();
11      for (int i = 0; i < a_len; i++) {
12          a[i] = input_str[a_len - i - 1] - '0';
13      }
14      cin >> input_str;
15      b_len = input_str.size();
16      for (int i = 0; i < b_len; i++) {
17          b[i] = input_str[b_len - i - 1] - '0';
18      }
19      carry[0] = 0;
20      for (int i = 0; i < max(a_len, b_len) + 1; i++) {
21          c[i] = a[i] + b[i] + carry[i];
22          if (c[i] >= 10) {
23              carry[i + 1] = 1;
24              c[i] -= 10;
25          } else {
26              carry[i + 1] = 0;
27          }
28      }
29      for (int i = max(a_len, b_len); i >= 0; i--) {
30          cout << c[i];
31      }
32      cout << endl;
33      return 0;
34  }

本题输入的两个数均为非负整数，位数不超过 100000，可能包含前导零。

第 1 小题（1.5 分）

当输入为 123 456 时，程序输出为 0579。（ ）

• A. 正确
• B. 错误

答案：A（正确）

解析：

判断结果： 正确

考查知识点： 高精度

判断依据：

各位相加得到 579。程序从下标 max(a_len,b_len)=3 一直输出到 0，共输出 4 个位置；最高位置 c[3] 是 0，所以输出 0579。

第 2 小题（1.5 分）

假设输入的两个数均不含前导零，则程序输出的结果也一定不会含有前导零。（ ）

• A. 正确
• B. 错误

答案：B（错误）

解析：

判断结果： 错误

考查知识点： 高精度

判断依据：

程序固定输出 max(a_len,b_len)+1 个位置，不会跳过最高位的 0。反例是输入 123 456，输出 0579，输入无前导零但输出有前导零。

正确说法：

输入没有前导零，并不能保证输出没有前导零；只有加法产生最高位进位时，输出的首位才不是 0。

第 3 小题（1.5 分）

将第 21 行改为 c[i]=a[i]+b[i]; 后，程序输出的结果一定比原来的结果小。（ ）

• A. 正确
• B. 错误

答案：B（错误）

解析：

判断结果： 错误

考查知识点： 高精度

判断依据：

修改后不再把低位的进位加到当前位。但若整个加法没有进位，结果就不会改变。例如输入 1 2 时，原程序和修改后的程序都输出 03，故“一定更小”不成立。

正确说法：

忽略进位可能使结果变小，但没有进位时，结果与原程序相同。

第 4 小题（2.944445 分）

当输入为 12345 678 时，输出为（ ）。

• A.

  012923
  

• B.

  013023
  

• C.

  13023
  

• D.

  130230
  

答案：B

解析：

正确答案： B

考查知识点： 高精度

解题分析：

$12345+678=13023$。较长的输入有 5 位，输出循环却从下标 5 到 0 输出 6 个位置，最高位为 0，所以输出：

013023

选项分析：

• B：与上述计算结果一致。
• A、C、D：与上述计算结果不符。

第 5 小题（2.944444 分）

将第 22 行的 if (c[i]>=10) 改为 if (c[i]>10) 后，当输入为 95 15 时，输出为（ ）。

• A.

  01010
  

• B.

  110
  

• C.

  140
  

• D.

  1410
  

答案：A

解析：

正确答案： A

考查知识点： 高精度

解题分析：

个位相加得到 10，因为不满足 >10，所以 c[0] 保留为 10，且没有向十位进位。十位相加也得到 $9+1=10$，同样保留为 10；c[2]=0。输出循环连续输出 c[2]、c[1]、c[0]，即拼接 0、10、10，得到：

01010

选项分析：

• A：与上述计算结果一致。
• B、C、D：与上述计算结果不符。

第 6 小题（2.944444 分）

假设输入的两个数均为 $n$ 位正整数（不含前导零），且它们的和小于 $10^n$，则程序输出的字符串一定满足（ ）。

• A. 第一个字符一定不为 '0'
• B. 长度一定为 $n$
• C. 长度一定为 $n+1$，且第一个字符为 '0'
• D. 长度可能为 $n+2$

答案：C

解析：

正确答案： C

考查知识点： 高精度

解题分析：

两数长度都是 $n$，输出下标固定为 $n,n-1,\ldots,0$，共 $n+1$ 个位置。原程序正确处理进位，各位置均为一个十进制数字；由于和小于 $10^n$，下标 $n$ 处必为 0，因此首字符是 0。

选项分析：

• A：最高位没有进位，首字符恰好为 0。
• B：实际多输出了最高的一个位置，长度是 $n+1$。
• C：长度和首字符均符合上述分析。
• D：正常进位后每个位置只输出一位，长度不会达到 $n+2$。

第 3 组

（3）阅读以下程序

01  #include <iostream>
02  using namespace std;
03  bool check_prime(int x) {
04      if (x <= 1) return false;
05      for (int i = 2; i * i <= x; i++) {
06          if (x % i == 0) return false;
07      }
08      return true;
09  }
10  int n;
11  void search_result(int x) {
12      if (!check_prime(x)) return;
13      if (x >= n) {
14          cout << x << endl;
15          return;
16      }
17      for (int i = 0; i <= 9; i++) {
18          search_result(x * 10 + i);
19      }
20  }
21  int main() {
22      cin >> n;
23      for (int i = 1; i <= 9; i++) search_result(i);
24      return 0;
25  }

第 1 小题（1.5 分）

当输入为 10 时，程序的输出共有 10 行。（ ）

• A. 正确
• B. 错误

答案：B（错误）

解析：

判断结果： 错误

考查知识点： 深度优先搜索、素数

判断依据：

一位数中只有 2、3、5、7 能继续搜索。将它们作为十位得到的两位质数为 23、29、31、37、53、59、71、73、79，共 9 个。它们都不小于 10，因此输出后立刻返回，不再搜索更长的数。

正确说法：

输入 10 时，程序输出 9 行。

第 2 小题（1.5 分）

若输入的 $n$ 不大于 5，则程序的输出中一定包含 5。（ ）

• A. 正确
• B. 错误

答案：A（正确）

解析：

判断结果： 正确

考查知识点： 深度优先搜索、素数

判断依据：

主函数必定调用 search_result(5)。5 是质数，且当 $n\le5$ 时满足 5>=n，所以该调用一定输出 5。

第 3 小题（1.5 分）

若输入的 $n$ 大于 10，将第 17 行的 for (int i=0;i<=9;i++) 改为 for (int i=1;i<=9;i+=2) 后，程序的输出结果一定不变。（ ）

• A. 正确
• B. 错误

答案：A（正确）

解析：

判断结果： 正确

考查知识点： 深度优先搜索、素数

判断依据：

递归扩展只发生在 x 已被确认是质数之后，故 $x\ge2$。末尾添加 0、2、4、6、8 后得到的是至少为 20 的偶数，不可能是质数，原程序对这些分支也会立刻返回。删除这些分支不影响输出；保留的奇数末位仍按原来的顺序访问。

第 4 小题（2.944444 分）

当输入为 24 时，程序输出的第 3 行为（ ）。

• A.

  23
  

• B.

  29
  

• C.

  31
  

• D.

  239
  

答案：B

解析：

正确答案： B

考查知识点： 深度优先搜索、素数

解题分析：

搜索先从 2 开始。23 是质数但小于 24，所以继续扩展，依次输出 233、239；返回后再尝试 24、25、26、27、28、29，其中只有 29 是质数，且已达到 24，于是第 3 行输出 29。

选项分析：

• A：23 小于 24，只用于继续搜索，不会直接输出。
• B：29 是第 3 行输出。
• C：31 会在处理完 2 开头的分支之后输出，不是第 3 行。
• D：239 是第 2 行输出。

第 5 小题（2.944444 分）

下列关于该程序输出的说法中，正确的是（ ）。

• A. 输出的数一定按照从小到大的顺序排列
• B. 随着输入 $n$ 的增大，输出的行数一定不会增加
• C. 输出的数的个位数字只能是 3 或 7
• D. 输出的每个大于等于 10 的数，十进制下删去它的末位数字后得到的数一定是质数

答案：D

解析：

正确答案： D

考查知识点： 深度优先搜索、素数

解题分析：

每个两位及以上的候选数都是由某个已经通过质数检查的 x 扩展成 x*10+i 而来。删去新数末位得到的正是父结点 x，因此必为质数。

选项分析：

• A：输入 24 时开头输出 233、239、29，并非从小到大。
• B：输入 2 时输出 2、3、5、7，共 4 行；输入 10 时有 9 行，行数会增加。
• C：例如输入 10 时会输出 29、31，末位并非只可能为 3 或 7。
• D：每个新数的父结点都必须先通过质数检查，故该项正确。

第 6 小题（2.944444 分）

当输入为 200 时，程序输出的行数为（ ）。

• A. 12
• B. 13
• C. 14
• D. 15

答案：C

解析：

正确答案： C

考查知识点： 深度优先搜索、素数

解题分析：

一位和两位的质数前缀都小于 200，会继续扩展。从这些前缀能得到的三位质数依次为：

233, 239, 293, 311, 313, 317, 373,
379, 593, 599, 719, 733, 739, 797

这些数都不小于 200，输出后立即返回，不再生成四位数；其余分支在质数检查处返回。因此共输出 14 行。

选项分析：

• C：与上述计算结果一致。
• A、B、D：与上述计算结果不符。

三、完善程序

第 1 组

（1）进制减半

给定 $n,m$，再给定一个 $nm$ 进制下的数 $A$，其各个数位上的数按照从高位到低位的顺序给出，请你将其转化为 $n$ 进制，并同样按照从高位到低位的顺序输出。

输入的第一行依次为 $n,m$ 和 $A$ 的位数 $d$，接下来 $d$ 个数 $a_d,a_{d-1},\ldots,a_1$ 从高位到低位描述各个数位上的数。

数据满足 $2\le n,m\le10$，$1\le d\le18$，$0\le A<2^{63}$，对于所有 $1\le i\le d$，$0\le a_i<mn$。以下程序按“逐位除以 $n$”的方法完成进制转换。请补全程序。

01  #include <iostream>
02  
03  constexpr int N = 100005;
04  long long b[N];
05  
06  int main() {
07      long long n, m, d;
08      std::cin >> n >> m >> d;
09      int len = 1;
10      for (int i = 0; i < d; i++) {
11          long long x;
12          std::cin >> x;
13          for (int j = len; j >= 1; j--)
14              b[j] = ___①___;
15          b[0] = ___②___;
16          len++;
17          for (int j = 0; j < len; j++)
18              if (b[j] >= n) {
19                  b[j + 1] += ___③___;
20                  b[j] = ___④___;
21                  if (j + 1 == len) len++;
22              }
23      }
24      while (___⑤___) len--;
25      for (int i = len - 1; i >= 0; i--)
26          std::cout << b[i] << ' ';
27      return 0;
28  }

第 1 小题（3 分）

①处应填（ ）。

• A. b[j] * n
• B. b[j] * m
• C. b[j - 1] * n
• D. b[j - 1] * m

答案：D

解析：

正确答案： D

考查知识点： 进制转换

解题分析：

数组 b 按从低位到高位保存当前值的 $n$ 进制数位。读入下一位 x 时，原值应先乘原进制基数 $mn$，再加 x。把 b[j-1] 移到 b[j] 相当于乘 $n$，还需将其乘 $m$，因此填 b[j-1]*m。从高位向低位赋值可避免覆盖尚未使用的旧数位。

选项分析：

• A、B：使用 b[j] 没有完成向高位移动。
• C：移动一位已乘 $n$，再乘 $n$ 会变成乘 $n^2$，不能处理一般的 $m$。
• D：移动一位并乘 $m$，整体恰好乘 $mn$。

第 2 小题（3 分）

②处应填（ ）。

• A. x * n
• B. x
• C. 0
• D. m

答案：B

解析：

正确答案： B

考查知识点： 进制转换

解题分析：

高位移动并乘 $m$ 后，已完成原值乘 $mn$。下一步应加上新读入的数位 x，因此将最低位置 b[0] 设为 x。即使 x>=n，后续进位循环也会将它正规化。

选项分析：

• A：将新数位额外乘了 $n$，不符合加上 x 的要求。
• B：正确加入新读入的数位。
• C：遗漏了新数位。
• D：把固定基数因子当成输入数位。

第 3 小题（3 分）

③处应填（ ）。

• A. b[j] / m
• B. b[j] % n
• C. b[j] % m
• D. b[j] / n

答案：D

解析：

正确答案： D

考查知识点： 进制转换

解题分析：

目标是 $n$ 进制，当前数位每满 $n$ 就要向高一位进 1。因此 b[j] 应向 b[j+1] 贡献的进位量是整数商 b[j]/n。必须使用 +=，因为高位可能已有值。

选项分析：

• A：进位基数应为 $n$，而非 $m$。
• B：余数应留在当前位，不是进位量。
• C：使用了错误基数，并且计算的是余数。
• D：商正是应加入高一位的进位量。

第 4 小题（3 分）

④处应填（ ）。

• A. b[j] / m
• B. b[j] % n
• C. b[j] % m
• D. b[j] / n

答案：B

解析：

正确答案： B

考查知识点： 进制转换

解题分析：

向高位加入 b[j]/n 后，当前位应保留除以 $n$ 的余数，也就是 b[j]%n，保证该数位位于 0 至 $n-1$。

选项分析：

• A：既使用了错误基数，也没有保留余数。
• B：保留目标进制下的合法数位。
• C：余数的基数应为 $n$，而非 $m$。
• D：商应进到高位，不应留在当前位。

第 5 小题（3 分）

⑤处应填（ ）。

• A. len > 0 && b[len - 1] == 0
• B. len > 0 && b[0] == 0
• C. len > 1 && b[len - 1] == 0
• D. len > 1 && b[0] == 0

答案：C

解析：

正确答案： C

考查知识点： 进制转换

解题分析：

输出前需要删除最高位多余的 0。最高有效位置是 b[len-1]，故应检查它是否为 0；同时 $A$ 可以为 0，此时必须至少保留一位以输出 0，所以长度条件为 len>1。

选项分析：

• A：当整个数为 0 时会删到长度为 0，导致不输出任何数位。
• B：检查的是最低位，且可能删光全部数位。
• C：正确删除最高位的多余 0，并保留至少一位。
• D：误检查最低位，会破坏末位为 0 的非零数。

第 2 组

（2）平衡分割

给定一个长度为 $n$ 的字符串，其中每个字符都是一个十六进制数位。例如，字符串 016A 表示十进制下的四个数 0, 1, 6, 10。

现在请选择 $k$ 个（$k$ 是你选定的数）切分位置 $p_1,p_2,\ldots,p_k$，其中 $1\le k<n$，且 $1\le p_1<p_2<\cdots<p_k<n$。再令 $p_0=0$，$p_{k+1}=n$。

对于每个 $0\le i\le k$，计算第 $p_i+1$ 个数到第 $p_{i+1}$ 个数的平均值，记作 $b_i$。你的目标是使 $b_0,b_1,\ldots,b_k$ 中最大值与最小值之差尽可能小，并输出这个最小值。

其中 $2\le n\le20$。输入字符串中的字符只可能是 0～9 或 A～F。本题假定字符采用 ASCII 编码。输出答案时保留小数点后 6 位。

以下程序通过递归枚举所有可能的连续分段方案。请补全程序。

01  #include <algorithm>
02  #include <iomanip>
03  #include <iostream>
04  
05  using namespace std;
06  
07  constexpr int N = 25;
08  
09  int n, a[N];
10  char s[N];
11  
12  double ans = 1e100;
13  
14  int value(char c) { return ___①___; }
15  
16  void split(int l, int cnt, double mnb, double mxb) {
17      if (l > n) {
18          if (cnt == 0) return;
19          ans = min(ans, mxb - mnb);
20          return;
21      }
22      int sum = 0;
23      for (___②___) {
24          sum += a[r];
25          double nwb = ___③___;
26          split(___④___);
27      }
28  }
29  
30  int main() {
31      cin >> n >> s + 1;
32      for (int i = 1; i <= n; ++i)
33          a[i] = value(s[i]);
34      split(___⑤___);
35      cout << fixed << setprecision(6) << ans;
36      return 0;
37  }

第 1 小题（3 分）

①处应填（ ）。

• A. c - (c < '9' ? '0' : 'A' - 10)
• B. c - (c < 'A' ? '0' : 'A' - 10)
• C. c - (c < 'A' ? 'A' - 10 : '0')
• D. c - (c < 'A' ? '0' : 'A' + 10)

答案：B

解析：

正确答案： B

考查知识点： 字符

解题分析：

ASCII 编码中数字字符 0～9 都小于 A。数字字符的值为 c-'0'，字母 A～F 的值为 c-'A'+10，后者等价于 c-('A'-10)，因此选 B。

选项分析：

• A：字符 9 不满足 c<'9'，会误用字母的换算方法。
• B：正确区分数字与字母并转换到 0～15。
• C：数字和字母对应的两种减数颠倒了。
• D：字母分支变为 c-'A'-10，与应有的加 10 相反。

第 2 小题（3 分）

②处应填（ ）。

• A. int r = l + 1; r <= n; ++r
• B. int r = l; r < n; ++r
• C. int r = l; r <= n; r += 2
• D. int r = l; r <= n; ++r

答案：D

解析：

正确答案： D

考查知识点： 深度优先搜索

解题分析：

l 是当前段的左端点，右端点 r 应枚举从 l 到 n 的每一个位置。这样既包含单个元素组成的段，也包含延伸到末尾的段；循环每次累加 a[r]，得到区间 [l,r] 的和。

选项分析：

• A：漏掉长度为 1 的段，并且没有把 a[l] 累加到 sum。
• B：漏掉 r=n，无法形成覆盖末尾的完整方案。
• C：跳过部分右端点，同时遗漏相应元素的累加。
• D：覆盖所有合法右端点，且正确维护区间和。

第 3 小题（3 分）

③处应填（ ）。

• A. sum / (r - l + 1) * 1.0
• B. sum * 1.0 / (r - l) + 1
• C. sum * 1.0 / (r - l + 1)
• D. (sum - a[r]) * 1.0 / (r - l + 1)

答案：C

解析：

正确答案： C

考查知识点： 算术运算符

解题分析：

区间 [l,r] 有 r-l+1 个元素，平均值应为区间和除以这个长度。sum 与长度都是整数，必须在除法之前将参与运算的值转为浮点数，所以写作 sum*1.0/(r-l+1)。

选项分析：

• A：先做整数除法，小数部分会丢失，之后再乘 1.0 无法恢复。
• B：分母不是区间长度，而且 r=l 时分母为 0。
• C：正确进行浮点除法。
• D：从和中错误地减去了最后一个元素。

第 4 小题（3 分）

④处应填（ ）。

• A. r + 1, cnt + (r < n), min(mnb, nwb), max(mxb, nwb)
• B. r + 1, cnt + (r <= n), min(mnb, nwb), max(mxb, nwb)
• C. r + 1, cnt + (r < n), max(mnb, nwb), min(mxb, nwb)
• D. r + 1, cnt + (r <= n), max(mnb, nwb), min(mxb, nwb)

答案：A

解析：

正确答案： A

考查知识点： 深度优先搜索

解题分析：

确定当前段 [l,r] 后，下一段从 r+1 开始。cnt 统计真正的切分位置数，只有 r<n 时，当前段后面还有元素，需要增加一次切分；r=n 是整串末尾，不应计为切分。新的最小平均值取 min(mnb,nwb)，最大平均值取 max(mxb,nwb)。

选项分析：

• A：下一起点、切分计数和最大最小值更新都正确。
• B：把整串末尾也计作切分，导致不切分的单段方案被错误接受。
• C：把最小值和最大值的更新方向颠倒了。
• D：同时存在计数错误和最大最小值更新错误。

第 5 小题（3 分）

⑤处应填（ ）。

• A. 0, 0, 1e100, -1e100
• B. 0, 0, -1e100, 1e100
• C. 1, 0, -1e100, 1e100
• D. 1, 0, 1e100, -1e100

答案：D

解析：

正确答案： D

考查知识点： 深度优先搜索

解题分析：

字符串和数组从下标 1 开始存放，因此初始左端点为 1，初始切分次数为 0。尚未选择任何段时，最小平均值置为很大的正数 1e100，最大平均值置为很小的负数 -1e100；处理第一段时便能用 min 和 max 正确替换它们。

选项分析：

• A：初始左端点错误，会把下标 0 也算入。
• B：左端点错误，且最大最小值初值颠倒。
• C：最大最小值初值颠倒，无法按后续更新得到真实极值。
• D：四个初始参数均正确。

资料说明与待核验项

• 2.组合题/1：共享题干含需核验的原始识别校注，已原样保留；请对照清晰原卷确认被遮挡代码。