参考答案及解析仅供参考，不代表官方标准答案
单项选择题
1. 下列 C++ 数据类型中，能够精确存储 这个整数的是（ ）
A. float
B. long long
C. double
D. int
参考答案：B
解析：int 通常为 32 位，最大约 ，不够；float 和 double 是浮点数，不能精确表示题目中的数字
2. 十六进制数 2F5 转换为八进制数是（ ）
A. 1364
B. 1635
C. 1405
D. 1365
参考答案：D
解析：。再转八进制： 余 5， 余 6， 余 3， 余 1，倒序得 。
3. 执行下列 C++ 代码，输出是（ ）
int a = 7, b = 3;
std::cout << a / b * b + a % b;A. 9
B. 10
C. 7
D. 6
参考答案：C
解析：整数除法 a/b = 2，2*b = 6，% 优先级高于+，先算a%b = 1，所以 6+1=7。
4. 初始时栈为空，将 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
解析：要首先出栈 3，则 1、2、3 必须已入栈，此时栈内从底到顶为 1、2、3，栈顶为 3。出栈 3 后栈顶为 2，不可能先出 1，因此 C 不可能。
5. 一棵有 100 个结点的完全二叉树，其中叶子结点个数是（ ）
A. 49
B. 50
C. 64
D. 51
参考答案：B
解析：完全二叉树中，叶子结点数 。，叶子数为 50。
6. 执行下列代码后 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
解析：3 的倍数和：；5 的倍数和：；15 的倍数和：。总和 。
7. 上楼梯每步可上 1 级、2 级或 3 级，从地面（可视为第 0 级）走到第 8 级台阶共有多少种不同走法（ ）
A. 44
B. 121
C. 149
D. 81
参考答案：D
解析：设 为走到第 级的走法数，，，，。依次计算：，，，，，。
8. 下图为 网格，行号、列号均从 0 开始，# 为障碍，. 为可通行格：
从 S 出发做广度优先搜索（BFS）：初始时把 S 入队；每次取出队首格子，按“上、下、左、右”（上＝行号减 1，下＝行号加 1，左＝列号减 1，右＝列号加 1）的顺序遍历它的四个相邻格子，越界、障碍或已访问的格子跳过，其余格子标记为已访问并入队。当 E 第一次入队时，已经入队过的格子（含 S 和 E）共有多少个（ ）
A. 15
B. 12
C. 14
D. 13
参考答案：C
解析：按 BFS 顺序模拟入队：
S(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) → E(3,4)。E 入队时共入队 14 个格子。
9. 满足 且 的正整数 n 共有多少个（ ）
A. 8
B. 6
C. 4
D. 5
参考答案：B
解析：，，所以 ，且 与 互质。 得 。 中与 10 互质的有 ，共 6 个。
10. 某国硬币面值为 1 元、4 元、6 元且数量不限，凑出 9 元最少需要多少枚（ ）
A. 3
B. 4
C. 5
D. 2
参考答案：A
解析：，共 3 枚，最少。
11. 执行下列代码，输出是（ ）
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
解析：p = a + 2 指向 a[2]。p[0]=5，p[2]=a[4]=9，所以 a[1] = 5+9 = 14。*(a+1)=a[1]=14，a[0]=1，所以 p[1]=a[3]=13。输出 14,13。
12. 在含 1000 个互不相同元素的升序数组中，用二分法查找给定值（返回元素位置或报告不存在），最坏情况下需要与数组元素比较多次？（ ）
A. 500
B. 9
C. 11
D. 10
参考答案：D
解析：二分查找最坏比较次数为 。，所以最多比较 10 次。
13. 数组 a[1..n] 的前缀和数组 s（即 ）满足 。则 a[10] 的值是（ ）
A. 252
B. 310
C. 58
D. 61
参考答案：C
解析：。
14. 数轴上有 7 个点，坐标分别为 1、3、4、7、10、15、20。在数轴上选取一个整数坐标点 P，使 P 到这 7 个点的距离之和最小，这个最小距离和是（ ）
A. 37
B. 42
C. 40
D. 38
参考答案：A
解析：中位数第 4 个为 7，取 。距离和 。
15. 一个无向图有 10 个顶点，其中 4 个顶点的度为 3，其余顶点的度均为 4，则该图的边数是（ ）
A. 36
B. 18
C. 17
D. 20
参考答案：B
解析：总度数为 ，无向图边数 。
阅读程序
（1）
01 #include <iostream>
02 using namespace std;
03int 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 }16. 当输入为 3 时，程序输出为 3 3。（ ）
参考答案：√
解析：，循环 2 次，每次 ++x，共加 2，x=3；奇数两次，++y 两次，y=3。输出 3 3。
17. 将第 11 行的 ++x; 删除后，程序输出的两个数一定相等。（ ）
参考答案：×
解析：删除后奇数分支不再增加 x，x 只与偶数次数有关，y 与奇数次数有关，二者不一定相等。例如输入 3，输出 1 3。
18. 假设输入为非负整数，则程序输出的第一个数一定不小于第二个数。（ ）
参考答案：√
解析：x = 1 + 二进制位数，y = 1 + 二进制中 1 的个数。位数 ≥ 1 的个数，所以 x ≥ y。
19. 将第 7 行的 while (n > 0) 改为 while (n >= 0) 后，程序可能出现的问题是（ ）。
A. 陷入死循环
B. 输出结果比原来大
C. 输出结果比原来小
D. 输出结果不受影响
参考答案：A
解析：当 n 变为 0 后，0 >= 0 仍成立，n = n/2 始终为 0，循环无法结束。
20. 当输入为 6 时，输出为（ ）。
A. 3 3
B. 4 2
C. 4 3
D. 5 2
参考答案：C
解析：，位数 3，1 的个数 2。x=1+3=4，y=1+2=3，输出 4 3。
21. 若输入 n 依次取遍 0,1,2,..., 中的所有整数，则程序输出的第二个数恰好为 2 的次数为（ ）。
A. 16
B. 30
C. 31
D. 32
参考答案：C
解析：y = 1 + popcount(n)（n>0 时）。y=2 要求 popcount(n)=1，即 n 是 2 的幂。 共 31 个。
（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;
08int 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 }22. 当输入为 123456 时，程序输出为 0579。（ ）
参考答案：√
解析：，程序固定输出 位，即 0579。
23. 假设输入的两个数均不含前导零，则程序输出的结果也一定不会含有前导零。（ ）
参考答案：×
解析：程序固定输出 max_len+1 位，可能输出前导零。例如 1 和 2 输出 03。
24. 将第 21 行改为 c[i] = a[i] + b[i]; 后，程序输出的结果一定比原来的结果小。（ ）
参考答案：×
解析：忽略进位后，若无进位，结果相同；有进位时才会变小，因此不是“一定”变小。
25. 当输入为 12345678 时，输出为（ ）。
A. 012923
B. 013023
C. 13023
D. 130230
参考答案：B
解析：，输出 6 位即 013023。
26. 将第 22 行的 if (c[i] >= 10) 改为 if (c[i] > 10) 后，当输入为 9515 时，输出为（ ）。
A. 01010
B. 110
C. 140
D. 1410
参考答案：A
解析：。按修改后的条件，10 不满足 >10，所以不进位，输出 01010。
27. 假设输入的两个数均为 n 位正整数（不含前导零），且它们的和小于 ，则程序输出的字符串一定满足（ ）。
A. 第一个字符一定不为 0
B. 长度一定为 n
C. 长度一定为 ，且第一个字符为 0
D. 长度可能为
参考答案：C
解析：两个 n 位数相加，和小于 ，说明最高位无进位。程序输出 max_len+1 = n+1 位，最高位为 0。
（3）
01 #include <iostream>
02 using namespace std;
03bool 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;
11void 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 }
21int main(){
22 cin >> n;
23 for (int i = 1; i <= 9; i++) search_result(i);
24 return 0;
25 }28. 当输入为 10 时，程序的输出共有 10 行。（ ）
参考答案：×
解析：该程序会递归构造所有“右截断质数”，即一个数本身是质数，并且从最高位开始的所有前缀也都是质数。当输入 n = 10 时，一位质数 2、3、5、7 都小于 10，因此不会直接输出，而是继续向后扩展。扩展后满足条件且数值 ≥ 10 的数有：23, 29, 31, 37, 53, 59, 71, 73, 79。共 9 个。
29. 若输入的 n 不大于 5，则程序的输出中一定包含 5。（ ）
参考答案：√
解析：起始数字 5 是质数，且 ，所以会直接输出 5。
30. 若输入的 n 大于 10，将第 17 行的 for (int i = 0; i <= 9; i++) 改为 for (int i = 1; i <= 9; i += 2) 后，程序的输出结果一定不变。（ ）
参考答案：√
解析：多位数质数的末位只能是 1、3、7、9，添加偶数或 5 后一定不是质数，因此跳过这些分支不会影响输出。
31. 当输入为 24 时，程序输出的第 3 行为（ ）。
A. 23
B. 29
C. 31
D. 239
参考答案：B
解析：输出顺序为 233, 239, 29, 31, 37, 53, 59, 71, 73, 79，第 3 行为 29。
32. 下列关于该程序输出的说法中，正确的是（ ）。
A. 输出的数一定按照从小到大的顺序排列
B. 随着输入 n 的增大，输出的行数一定不会增加
C. 输出的数的个位数字只可能是 3 或 7
D. 输出的每个大于等于 10 的数，十进制下删去它的末位数字后得到的数一定是质数
参考答案：D
解析：程序递归构造时要求每个前缀都是质数，所以输出的多位数去掉末位后仍是质数。A、B、C 均错误。
33. 当输入为 200 时，程序输出的行数为（ ）。
A. 12
B. 13
C. 14
D. 15
参考答案：C
解析：首次达到 的右截断质数即所有 3 位右截断质数，共有 14 个：233, 239, 293, 311, 313, 317, 373, 379, 593, 599, 719, 733, 739, 797。
完善程序
（1）（进制减半）
给定 n, m，再给定一个 mn 进制下的数 A，其各个数位上的数按照从高位到低位的顺序给出，请你将其转化为 n 进制，并同样按照从高位到低位的顺序输出。
输入的第一行依次为 n、m 和 A 的位数 d，接下来 d 个数 , , · · · , 从高位到低位描述各个数位上的数。
数据满足 2 ≤ n, m ≤ 10，1 ≤ d ≤ 18，0 ≤ A < ，对于所有 1 ≤ i ≤ d，0 ≤ < mn。
以下程序按“逐位除以 n”的方法完成进制转换。请补全程序。
01 #include <iostream>
02
03 constexpr int N = 100005;
04 long long b[N];
05
06int 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 }34. ① 处应填（ ）
A. b[j] * n
B. b[j] * m
C. b[j - 1] * n
D. b[j - 1] * m
参考答案：D
解析：将当前 n 进制数乘以 并左移一位（相当于乘以 ），所以 b[j] = b[j-1] * m。
35. ② 处应填（ ）
A. x * n
B. x
C. 0
D. m
参考答案：B
解析：最低位加上新的数位 x。
36. ③ 处应填（ ）
A. b[j] / m
B. b[j] % n
C. b[j] % m
D. b[j] / n
参考答案：D
解析：进位为 b[j] / n。
37. ④ 处应填（ ）
A. b[j] / m
B. b[j] % n
C. b[j] % m
D. b[j] / n
参考答案：B
解析：本位保留 b[j] % n。
38. ⑤ 处应填（ ）
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
解析：去除高位前导零，至少保留一位，所以条件为 len > 1 && b[len - 1] == 0。
（2）（平衡分割）
给定一个长度为 n 的字符串，其中每个字符都是一个十六进制数位。例如，字符串 016A 表示十进制下的四个数 0、1、6、10。
现在请选择 k 个（k 是你选定的数）切分位置 , , . . . , ，其中 1 ≤ k < n，且 1 ≤ < < · · · < < n。再令 = 0， = n。
对于每个 0 ≤ i ≤ k，计算第 + 1 个数到第 个数的平均值，记作 。你的目标是使 , , . . . , 中最大值与最小值之差尽可能小，并输出这个最小值。
其中 2 ≤ n ≤ 20。输入字符串中的字符只可能是 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
14int value(char c){ return __①__; }
15
16void 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
30int 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 }39. ① 处应填（ ）
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
解析：'0'~'9' 减 '0'，'A'~'F' 减 'A' - 10。
40. ② 处应填（ ）
A. int r = l + 1; r <= n; ++r
B. int r = 1; r < n; ++r
C. int r = 1; r <= n; r += 2
D. int r = l; r <= n; ++r
参考答案：D
解析：当前段从 l 开始，枚举结束位置 r，所以 r = l 到 n。
41. ③ 处应填（ ）
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
解析：段 [l, r] 的平均值为 sum * 1.0 / (r - l + 1)。
42. ④ 处应填（ ）
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
解析：下一段从 r+1 开始；cnt 是切分位置数，只有 r<n 时才算一次切分，所以加 (r<n)；mnb、mxb 分别维护最小、最大平均值，所以用 min(mnb,nwb)、max(mxb,nwb)。
43. ⑤ 处应填（ ）
A. 0, 0, 1e100, -1e100
B. 0, 0, -1e100, 1e100
C. 1, 0, -1e100, 1e100
D. 1, 0, 1e100, -1e100
参考答案：D
解析：从位置 1 开始，已分段数 0；最小值初始化为很大的数 1e100，最大值初始化为很小的数 -1e100。
