该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

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

• float
• long long
• double
• int

2. 十六进制数 2F5 转换为八进制数是（ ）。 {{ select(2) }}

• 1364
• 1635
• 1405
• 1365

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

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

{{ select(3) }}

• 9
• 10
• 7
• 6

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

• 2, 4, 3, 1
• 1, 2, 3, 4
• 3, 1, 2, 4
• 1, 4, 3, 2

5. 一棵有100个结点的完全二叉树，其叶子结点个数是（ ）。 {{ select(5) }}

• 49
• 50
• 64
• 51

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

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

{{ select(6) }}

• 3048
• 2733
• 2318
• 2418

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

• 44
• 121
• 149
• 81

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

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

• 15
• 12
• 14
• 13

9. 满足 $1 \le n \le 100$ 且 $\text{gcd}(n, 60) = 6$ 的正整数 n 共有多少个（ ）。 {{ select(9) }}

• 8
• 6
• 4
• 5

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

• 3
• 4
• 5
• 2

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

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

{{ select(11) }}

• 14, 13
• 8, 13
• 14, 7
• 14, 2

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

• 500
• 9
• 11
• 10

13. 数组 a[1..n] 的前缀和数组 s（即 $s[i] = a[1] + a[2] + \dots + a[i]$）满足 $s[i] = 3i^2 + i$，则 a[10] 的值是（ ）。 {{ select(13) }}

• 252
• 310
• 58
• 61

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

• 37
• 42
• 40
• 38

15. 一个无向图有10个顶点，其中4个顶点的度为3，其余顶点的度均为4，则该图的边数是（ ）。 {{ select(15) }}

• 36
• 18
• 17
• 20

二、阅读程序

(1)

1  #include <iostream>
2  using namespace std;
3  int main() {
4      int n;
5      cin >> n;
6      int x = 1, y = 1;
7      while (n > 0) {
8          if (n % 2 == 0) {
9              ++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$ 的非负整数。

16. (1分) 当输入为3时，程序输出为3 3。（ ） {{ select(16) }}

• √
• ×

17. 将第11行的 ++x; 删除后，程序输出的两个数一定相等。（ ） {{ select(17) }}

• √
• ×

18. 假设输入为非负整数，则程序输出的第一个数一定不小于第二个数。（ ） {{ select(18) }}

• √
• ×

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

• 陷入死循环
• 输出结果比原来大
• 输出结果比原来小
• 输出结果不受影响

20. 当输入为6时，输出为（ ）。 {{ select(20) }}

• 3 3
• 4 2
• 4 3
• 5 2

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

• 16
• 30
• 31
• 32

(2)

1  #include <algorithm>
2  #include <iostream>
3  #include <string>
4  using namespace std;
5  int a[100007], b[100007], c[100007], carry[100007];
6  string input_str;
7  int a_len, b_len;
8  int main() {
9      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，可能包含前导零。

22. 当输入为 123 456 时，程序输出为 0579。（ ） {{ select(22) }}

• √
• ×

23. 假设输入的两个数均不含前导零，则程序输出的结果也一定不含前导零。（ ） {{ select(23) }}

• √
• ×

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

• √
• ×

25. 当输入为 12345 678 时，输出为（ ）。 {{ select(25) }}

• 012923
• 013023
• 13023
• 130230

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

• 01010
• 110
• 140
• 1410

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

• 第一个字符一定不为 '0'
• 长度一定为 n
• 长度一定为 n+1，且第一个字符为 '0'
• 长度可能为 n+2

(3)

1  #include <iostream>
2  using namespace std;
3  bool check_prime(int x) {
4      if (x <= 1) return false;
5      for (int i = 2; i * i <= x; i++) {
6          if (x % i == 0) return false;
7      }
8      return true;
9  }
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++) 
24         search_result( i);
25     
26     return 0;
27 }

28. 当输入为 10 时，程序的输出共有 10 行。（ ） {{ select(28) }}

• √
• ×

29. 若输入的 n 大于 5，则程序的输出中一定包含 5。（ ） {{ select(29) }}

• √
• ×

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

• √
• ×

31. 当输入为 24 时，程序输出的第 3 行为（ ）。 {{ select(31) }}

• 23
• 29
• 31
• 239

32. 下列关于该程序输出的说法中，正确的是（ ）。 {{ select(32) }}

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

33. 当输入为 200 时，程序输出的行数为（ ）。 {{ select(33) }}

• 12
• 13
• 14
• 15

三、完整程序

(1) (进制减半)

给定 n, m，再给定一个 m 进制下的数 A，其各个数位上的数按照从高位到低位的顺序给出，请你将其转化为 n 进制，并同样按照从高位到低位的顺序输出。 输入的第一行依次为 n, m 和 A 的位数 d，接下来 d 个数 $a_0, a_1, \dots, a_{d-1}$，从高位到低位描述各个数位上的数。 数据满足 $2 \le n, m \le 10, 1 \le d \le 18, 0 \le A < 2^{63}$，对于所有 $1 \le i \le d, 0 \le a_i < m$。 以下程序按“逐位除以 n”的方法完成进制转换，请补全程序。

1  #include <iostream>
2  constexpr int N = 100005;
3  long long b[N];
4  int main()
5  {
6      int n, m, d;
7      cin >> n >> m >> d;
8      for(int i = 1; i <= d; i++)
9          cin >> b[i];
10     int len = d;
11     for(int j = 1; j <= d; j++)
12     {
13         b[j] = __①__;
14         for(int j = 0; j < len; j++)
15         {
16             b[j+1] += __②__;
17             b[j] = __③__;
18         }
19         while (__④__)
20             len--;
21     }
22     for(int i = len - 1; i >= 0; i--)
23         cout << b[i];
24     cout << endl;
25     return 0;
26 }

34. ①处应填（ ） {{ select(34) }}

• b[i] * n
• b[i] * m
• b[i-1] * n
• b[i-1] * m

35. ②处应填（ ） {{ select(35) }}

• x * n
• x
• 0
• m

36. ③处应填（ ） {{ select(36) }}

• b[j] / m
• b[j] % n
• b[j] % m
• b[j] / n

37. ④处应填（ ） {{ select(37) }}

• b[j] / m
• b[j] % n
• b[j] % m
• b[j] / n

38. ⑤处应填（ ） {{ select(38) }}

• len > 0 && b[len - 1] == 0
• len > 0 && b[0] == 0
• len > 1 && b[len - 1] == 0
• len > 1 && b[0] == 0

（2）平衡分割

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

现在请选择 $k$ 个（$k$ 是你选定的数）切分位置 $p_1, p_2, \dots, p_k$，其中 $1 \le k < n$，且 $1 \le p_1 < p_2 < \dots < 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, \dots, b_k$ 中最大值与最小值之差尽可能小，并输出这个最小值。

其中 $2 \le n \le 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  
  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  }

39. ①处应填（ ）。 {{ select(39) }}

• c - (c < '9' ? '0' : 'A' - 10)
• c - (c < 'A' ? '0' : 'A' - 10)
• c - (c < 'A' ? 'A' - 10 : '0')
• c - (c < 'A' ? '0' : 'A' + 10)

40. ②处应填（ ）。 {{ select(40) }}

• int r = l + 1; r <= n; ++r
• int r = l; r < n; ++r
• int r = l; r <= n; r += 2
• int r = l; r <= n; ++r

41. ③处应填（ ）。 {{ select(41) }}

• sum / (r - l + 1) * 1.0
• sum * 1.0 / (r - l) + 1
• sum * 1.0 / (r - l + 1)
• (sum - a[r]) * 1.0 / (r - l + 1)

42. ④处应填（ ）。 {{ select(42) }}

• r + 1, cnt + (r < n), min(mnb, nwb), max(mxb, nwb)
• r + 1, cnt + (r <= n), min(mnb, nwb), max(mxb, nwb)
• r + 1, cnt + (r < n), max(mnb, nwb), min(mxb, nwb)
• r + 1, cnt + (r <= n), max(mnb, nwb), min(mxb, nwb)

43. ⑤处应填（ ）。 {{ select(43) }}

• 0, 0, 1e100, -1e100
• 0, 0, -1e100, 1e100
• 1, 0, -1e100, 1e100
• 1, 0, 1e100, -1e100