一、单项选择题（共 15 题，每题 2 分，共计 30 分；每题有且仅有一个正确选项）

1. 1983 年，我国第一台亿次超级计算机研发成功，成为继美国、日本之后，第三个能独立设计和制造巨型计算机的国家。该计算机的型号是（ ）。 {{ select(1) }}

• A. 天河一号
• B. 银河一号
• C. 神威·太湖之光
• D. 曙光星云

2. 传输控制协议（TCP）是一种面向连接的、可靠的、基于字节流的传输层通信协议。TCP 使用确认应答（ACK）机制来确保数据的可靠传输。每当发送方发送一个数据包时，接收方都会返回一个确认应答。TCP 建立连接的过程叫作握手。客户端和服务器之间完成连接建立需要通过（ ）次握手，才能确保建立 TCP 连接。 {{ select(2) }}

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

3. 计算机高级语言需要通过“翻译程序”翻译成机器语言形式的目标程序，才能被计算机识别和执行。“翻译”有两种方式：“编译”和“解释”。下列（ ）两种语言都是典型的编译型语言。 {{ select(3) }}

• A. C++、Python
• B. Python、Java
• C. Java、MATLAB
• D. Pascal、C++

4. 二进制小数 $0.1011$ 对应的八进制数是（ ）。 {{ select(4) }}

• A. $0.23$
• B. $0.51$
• C. $0.54$
• D. $0.6875$

5. 给学校的公告栏设计一种编码方案，公告中只包含 A、B、C、D 四个字符，出现频率分别为 $20\%$、$30\%$、$40\%$、$10\%$。使用哈夫曼编码后，字符（ ）的编码长度一定最短。 {{ select(5) }}

• A. A
• B. B
• C. C
• D. D

6. 扫描仪扫描了一张彩色照片，扫描分辨率为 $300\,\text{dpi}$（每英寸 300 个像素），照片尺寸为 4 英寸 $\times$ 6 英寸。扫描时设置了 24 位真彩色。在不进行任何压缩的情况下，这张扫描图片的存储容量约为（ ）。 {{ select(6) }}

• A. $2.07\,\text{MB}$
• B. $4.15\,\text{MB}$
• C. $6.22\,\text{MB}$
• D. $8.29\,\text{MB}$

7. 在磁盘上建立子目录管理文件，下列描述中，不属于建立子目录的优点的是（ ）。 {{ select(7) }}

• A. 便于文件分类管理
• B. 加快文件的查找速度
• C. 避免文件名冲突
• D. 避免文件重复，节省磁盘使用空间

8. 假设布尔变量 $a$ 为真，$b$ 为假，$c$ 为真，那么表达式 $(a \land b) \lor (c \land \neg b)$ 的结果是（ ）。 {{ select(8) }}

• A. 真
• B. 假
• C. 无法确定
• D. 语法错误

9. 哈希表长度为 10，哈希函数 $H(key)=key\%10$，采用线性探查法解决冲突。插入序列：$\{12,22,32,42,52\}$。在插入完成后，查找关键码 32 时需要探查的次数（包括第一次计算哈希地址的探查）是（ ）。 {{ select(9) }}

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

10. 一棵二叉树，中序遍历的结果为 "abc"，那么这棵二叉树有（ ）种不同的形态。 {{ select(10) }}

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

11. 给定数字 $0$、$1$、$3$、$4$、$5$、$9$，每个数字最多用一次，可能组成（ ）个 4 位偶数。 {{ select(11) }}

• A. 360
• B. 300
• C. 192
• D. 108

12. 以下代码的输出是（ ）。 {{ select(12) }}

• A. $5\ 3\ 8$
• B. $5\ 4\ 8$
• C. $6\ 4\ 9$
• D. $6\ 4\ 10$

int a = 5, b = 3, c = 0;
c = a++ + ++b;
cout << a << " " << b << " " << c;

13. 定义 $f(n)$ 为 $n$ 的各位数字之和，如：$f(123)=1+2+3=6$。数字根 $dr(n)=f(f(\cdots f(n)\cdots))$（直到结果不会变化为止），则 $dr(2026)$ 的结果是（ ）。 {{ select(13) }}

• A. 0
• B. 1
• C. 9
• D. 10

14. 在 NOI Linux 终端中，要删除一个名为 "old.exe" 的文件，应该使用命令（ ）。 {{ select(14) }}

• A. del old.exe
• B. rm old.exe
• C. remove old.exe
• D. delete old.exe

15. 以下代码的输出是（ ）。 {{ select(15) }}

• A. 10
• B. 50
• C. 60
• D. 150

const int N = 5;
int arr[N] = {10, 20, 30, 40, 50};
int *p = arr;
int sum = 0;
for (int i = 0; i < N; i++) {
    sum += (*p)++;
}
cout << sum;

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

(1)

 1 #include <bits/stdc++.h>
 2 #define int long long
 3 using namespace std;
 4 int f(int x) {
 5     int res = 0;
 6     while (x) {
 7         res += x % 10;
 8         x /= 10;
 9     }
10     return res;
11 }
12 int solve1(int x) {
13     if (x < 10) return x;
14     return solve1(f(x));
15 }
16 int solve2(int x) {
17     return (x - 1) % 9 + 1;
18 }
19 signed main() {
20     int n;
21     cin >> n;
22     cout << solve1(n) << " " << solve2(n) << endl;
23     return 0;
24 }

判断题

16. 输入 1234 时，输出的结果为 1 1。 {{ select(16) }}

• A. 正确
• B. 错误

17. 输入的数为负数时，输出的两个数肯定不一致。 {{ select(17) }}

• A. 正确
• B. 错误

18. 将 solve1() 的内容改成下面的代码，其功能不变。 {{ select(18) }}

• A. 正确
• B. 错误

while (x >= 10) x = f(x);
return x;

选择题

19. 若输入的 $n$ 为一个身份证号码（保证没有 X），则下列说法中正确的是（ ）。 {{ select(19) }}

• A. 数值超过 int 类型的最大值，产生溢出
• B. 数值太大，会导致 solve1() 函数递归深度过大，进而导致栈溢出
• C. 程序可以正常运行，但实际输出结果不对
• D. 程序可以正常运行，输出结果也正确

20. （4 分）函数 solve1() 和 solve2() 的时间复杂度分别为（ ）。 {{ select(20) }}

• A. $O(\log \log n)$，$O(1)$
• B. $O(\log n)$，$O(1)$
• C. $O(1)$，$O(\log \log n)$
• D. $O(1)$，$O(\log n)$

(2)

 1 #include <iostream>
 2 #include <iomanip>
 3 #include <cmath>
 4 using namespace std;
 5 const double ERR = 1e-7;
 6 const double CMP_EPS = 1e-12;
 7 
 8 int main() {
 9     double x;
10     scanf("%lf", &x); // 保证输入是非负实数
11     double left = 0, right = max(1.0, x);
12     while (right - left > ERR) {
13         double mid = (left + right) / 2;
14         double diff = mid * mid - x;
15         if (fabs(diff) <= CMP_EPS) {
16             left = mid;
17             break;
18         }
19         if (diff < 0) {
20             left = mid;
21         } else {
22             right = mid;
23         }
24     }
25     printf("%.6lf\n", left);
26     return 0;
27 }

判断题

21. 该程序使用二分法求非负整数的算术平方根。 {{ select(21) }}

• A. 正确
• B. 错误

22. 将 while 循环改为 while (right != left)，程序也可以正常输出，但结果不够精确。 {{ select(22) }}

• A. 正确
• B. 错误

23. 若输入的数为 $x$，则该程序的时间复杂度为 $O(\log x)$。 {{ select(23) }}

• A. 正确
• B. 错误

选择题

24. 当输入 0.625 时，输出的结果是（ ）。 {{ select(24) }}

• A. 0.025000
• B. 0.250000
• C. 0.790569
• D. 0.800569

25. （4 分）ERR 的值修改为（ ），会导致输出结果有误差。 {{ select(25) }}

• A. 1e-6
• B. 1e-7
• C. 1e-8
• D. 1e-9

(3)

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const ll N = 21;
 5 ll n, m, S[N][N];
 6 
 7 int main() {
 8     cin >> n >> m; // 保证 n,m 是不大于 20 的正整数
 9     if (n < m) {
10         cout << 0 << endl;
11         return 0;
12     }
13     if (n == m && m == 0) {
14         cout << 1 << endl;
15         return 0;
16     }
17 
18     for (int i = 1; i <= n; i++) S[i][1] = 1;
19     for (int j = 2; j <= m; j++)
20         for (int i = j; i <= n; i++)
21             S[i][j] = S[i - 1][j - 1] + j * S[i - 1][j];
22     cout << S[n][m] << endl;
23     return 0;
24 }

判断题

26. 若输入 $n=5$，$m=3$，则程序输出结果为 26。 {{ select(26) }}

• A. 正确
• B. 错误

27. 程序计算将 $n$ 个不同元素划分成 $m$ 个无序集合的方案数。 {{ select(27) }}

• A. 正确
• B. 错误

28. 若对第 22 行代码做如下修改，则程序的功能为：计算将 $n$ 个不同元素划分到不超过 $m$ 个非空集合的方案总数。 {{ select(28) }}

• A. 正确
• B. 错误

ll res = 0;
for (int i = 1; i <= m; i++) res += S[n][i];
cout << res << endl;

选择题

29. （4 分）若输入 $n=7$，$m=3$，则程序输出结果为（ ）。 {{ select(29) }}

• A. 105
• B. 140
• C. 301
• D. 305

30. （4 分）若将双重循环的内层循环条件 for (int i = j; i <= n; i++) 改为 for (int i = 1; i <= n; i++)，则程序（ ）。 {{ select(30) }}

• A. 结果不变
• B. 结果可能错误，因为会计算多余的状态
• C. 结果可能错误，因为会计算无效状态（$i < j$）
• D. 运行出错，因为数组访问越界

三、完善程序（单选题，每小题 3 分，共计 30 分）

(1)

（多重背包问题）给定 $n$ 种物品，每种物品的数量有限，计算在给定容量下背包能装入物品的最大总价值。为了降低时间复杂度，一般运用二进制拆分的方式将背包中的物品拆分为若干个独立的物品，再用 0-1 背包的动态规划方法计算能获得的最大总价值。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int MAXC = 10009;
 4 int n, c, w, v, s, f[MAXC];
 5 
 6 void bb01(int w, int v) {
 7     for (①)
 8         f[j] = max(f[j], ②);
 9 }
10 
11 int main() {
12     cin >> n >> c;
13     for (int i = 1; i <= n; i++) {
14         cin >> w >> v >> s;
15         for (int k = 1; k <= s; ③)
16             ④
17         if (⑤) bb01(s * w, s * v);
18     }
19     cout << f[c] << endl;
20     return 0;
21 }

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

• A. int j = 0; j <= c; j++
• B. int j = w; j <= c; j++
• C. int j = c; j >= 0; j--
• D. int j = c; j >= w; j--

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

• A. f[j] + v
• B. f[j] + w
• C. f[j-w] + v
• D. f[j-w] + w

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

• A. k++
• B. k *= 2
• C. s /= 2, k *= 2
• D. s -= k, k *= 2

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

• A. bb01(w, k);
• B. bb01(k*w, v);
• C. bb01(w, k*v);
• D. bb01(k*w, k*v);

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

• A. !s
• B. s
• C. s < k
• D. s <= k

(2)

（高精度除以单精度）当计算大数（超过普通整数范围，如大于 long long 类型的最大值）除以普通整数时，无法直接计算，需要使用高精度计算方法：使用数组存储大数，模拟手工除法，从高位到低位逐位计算，最终输出计算得到的商和余数。

 1 #include <iostream>
 2 #include <string>
 3 #define SIZE 209
 4 using namespace std;
 5 void converts(int *a, string s) {
 6     int i, len = s.size();
 7     for (i = 0; i < len; i++) a[i] = s[len - i - 1] - '0';
 8     for (; i < SIZE; i++) a[i] = 0;
 9 }
10 void div(int *a, int n) {
11     for (int i = SIZE - 1, c = 0; i >= 0; i--) {
12         c = ①;
13         a[i] = c / n;
14     }
15 }
16 
17 int mod(int *a, int n) {
18     int r = 0;
19     for (int i = SIZE - 1; i >= 0; i--)
20         r = (r * 10 + a[i]) % n;
21     return r;
22 }
23 void print(int *a) {
24     int i;
25     for (i = SIZE - 1; i > 0; i--)
26         if (a[i] > 0) break;
27     for (②) cout << a[i];
28     cout << endl;
29 }
30 int x[SIZE];
31 
32 int main() {
33     string s;
34     int n;
35     cin >> s >> n;
36     ③
37     int r;
38     ④
39     ⑤
40     print(x);
41     cout << r << endl;
42     return 0;
43 }

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

• A. c / n + a[i]
• B. c % n + a[i]
• C. c / n * 10 + a[i]
• D. c % n * 10 + a[i]

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

• A. i-1; i >= 0; i--
• B. i-1; i > 0; i--
• C. ; i >= 0; i--
• D. ; i > 0; i--

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

• A. converts(x, n);
• B. converts(n, x);
• C. converts(x, s);
• D. converts(s, x);

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

• A. mod(x, n);
• B. div(x, n);
• C. r = mod(x, n);
• D. r = div(x, n);

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

• A. mod(x, n);
• B. div(x, n);
• C. r = mod(x, n);
• D. r = div(x, n);