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

第 1 题

在 64 位计算机中，下列 C++ 基本类型中（ ）的单个变量占用的内存最大。 {{ select(1) }}

• int
• bool
• double
• char

第 2 题

Ubuntu 是常见的 Linux 操作系统。假设当前登录的用户为 luogu，当前所在的工作目录为 /home/luogu，使用（ ）命令，可以在 /home/sjtu/phd 下新建子目录 paper。 {{ select(2) }}

• mv ./sjtu/phd/paper
• mkdir ~/sjtu/phd/paper
• mv /home/sjtu/phd/paper
• mkdir ../sjtu/phd/paper

第 3 题

阅读下面的代码，其中说法错误的是（ ）。

01 #include <bits/stdc++.h>
02 using namespace std;
03 stack <int> s1, s2;
04 int T, x;
05
06 int main() {
07     cin >> T;
08     while(T--) {
09         string op; cin >> op;
10         if(op == "in") {
11             cin >> x; s1.push(x);
12         }
13         else {
14             if(s2.empty()) {
15                 while(!s1.empty()) {
16                     s2.push(s1.top());
17                     s1.pop();
18                 }
19             }
20             cout << s2.top() << endl;
21             s2.pop();
22         }
23     }
24     return 0;
25 }

{{ select(3) }}

• 代码中使用的 stack 是 STL 提供的栈的容器，栈的特点是先进后出。
• 代码所实现的功能和队列的功能类似。
• 输入为 6 in 1 out in 2 in 3 out out 时，输出为 1 3 2。
• 若不对输入数据的操作类型做 in 和 out 数量的保证，代码存在运行时错误的风险。

第 4 题

(1C)₁₆、(24)₁₀、(31)₈ 和 (11011)₂ 中，最大的数的十进制表示为（ ）。 {{ select(4) }}

• 28
• 30
• 25
• 27

阅读下面的材料，完成第 5 - 7 题。

在计算机底层，int 类型与 unsigned int 类型的加法运算在 ALU（算术逻辑单元）中的执行路径完全一致——ALU 仅对两个操作数进行二进制补码加法，得到相同的 32 位二进制和，并同时设置状态标志位（如进位标志 CF 和溢出标志 OF）。二者的差异仅在于如何解释这个二进制结果：若解释为有符号数（int），则按补码规则读取；若解释为无符号数（unsigned int），则按普通二进制数值读取，因此同一个二进制和可能对应不同的十进制值。当加法结果超出该类型的表示范围时，即发生溢出，ALU 并不会抛出异常或中断，而是直接截断高位，仅保留低 32 位作为结果，并更新标志位——对于无符号数溢出，ALU 将进位标志 CF 置 1（表示最高位产生进位），而对于有符号数溢出，ALU 将溢出标志 OF 置 1（表示符号位错误），但计算结果本身仍被保存为截断后的低 32 位，后续程序需根据类型和标志位自行判断是否发生了溢出，ALU 本身不对溢出做额外处理。

第 5 题

ALU 是算术逻辑单元，根据材料可以推断其属于（ ）的一部分。 {{ select(5) }}

• CPU
• 外存
• 内存
• 操作系统

第 6 题

int 类型变量 x 的值为 -1，将其强制类型转换为 unsigned int 类型输出，输出的值为（ ）。 {{ select(6) }}

• -1
• 2147483647
• 4294967295
• 4294967296

第 7 题

下面代码的输出为（ ）。

01 #include <iostream>
02 int main() {
03     unsigned int a = 2147483648;
04     int b = 1234567890;
05     std::cout << int(a + b) << std::endl;
06 }

{{ select(7) }}

• 3382051538
• -912915758
• 1234567889
• 每一次运行输出可能不同

第 8 题

下面的表格是图 G 的邻接表，关于图 G 说法错误的是（ ）。

顶点	邻接点
1	2 3 4 5
2	1 3
3	1 2 6
4	1 5
5	1 4
6	3
{{ select(8) }}

• 图 G 可能是无向图。
• 图 G 中度最大的结点为结点 1。
• 图 G 中共有 2 个连通块。
• 可以使用 vector 实现图 G 的邻接表结构。

第 9 题

下列代码的输出为（ ）。

01 #include <iostream>
02 using namespace std;
03 int main(){
04     int A = 1, B = 1;
05     int& a = A, b = B;
06     a = 2, b = 2;
07     std::cout << A << ' ' << B << std::endl;
08 }

{{ select(9) }}

• 1 1
• 1 2
• 2 1
• 2 2

第 10 题

给定一个长度为 n 的数列 A = [a₁, a₂, …, aₙ]，从中选择若干个元素，并保持它们在原数列中的相对顺序不变，组成一个新序列 B = [b₁, b₂, …, bₖ]。若该新序列满足从第二项起每一项都严格大于前一项（即 b₁ < b₂ < … < bₖ），则称 B 为原数列的一个上升子序列。在所有可能的上升子序列中，长度 k 达到最大值的那个，称为该数列的最长上升子序列（LIS），其长度记为最长上升子序列的长度。下列方法中，（ ）不能正确求解一个序列的最长上升子序列。 {{ select(10) }}

• 贪心。从第 1 个数开始选择，每次选取比上一个数更大的最小的数。
• 搜索。通过深度优先搜索，枚举每一个数应该选哪一个。
• 动态规划。用 dp[i] 表示以 aᵢ 结束的最长上升子序列的长度。此时有 dp[i] = max(dp[j]) + 1，其中 j 满足 1 ≤ j < i 且 aⱼ < aᵢ。
• 动态规划。用 dp[i] 表示长度为 i 的上升子序列中，结尾数值可以取得的最小值。枚举 aⱼ，每次二分查找到 dp[i] 大于等于 aⱼ 的最小的 i，将 dp[i] 设置为 aⱼ。

第 11 题

哈夫曼编码是实现信息压缩的常见编码方式。假设有一组字符 {a, b, c, d, e, f}，对应的频率分别为 0.05, 0.09, 0.12, 0.13, 0.16, 0.45。那么字符串 abcdef 共有（ ）种可能的哈夫曼编码。 {{ select(11) }}

• 8
• 16
• 32
• 64

第 12 题

二叉树 T 的中序遍历为 CADBEFG，后序遍历为 CBDAFGE，则其前序遍历为（ ）。 {{ select(12) }}

• EACDBGF
• ECADBGF
• EACBDGF
• EACDFGB

第 13 题

在 1 到 200 的正整数中，能被 3 或 5 整除，但不能被 7 整除的整数共有（ ）个。 {{ select(13) }}

• 79
• 80
• 81
• 93

第 14 题

数字 1, 2, 3, 4, 5, 6 排成一列，要求奇数之间的相对顺序保持不变，偶数之间的相对顺序也保持不变，则共有（ ）种不同的排列。 {{ select(14) }}

• 10
• 20
• 30
• 40

第 15 题

大语言模型（LLMs）技术发展日新月异。关于 LLM 与 CCF 有关活动，说法不正确的是（ ）。 {{ select(15) }}

• CCF 在 NOI 冬令营等活动中开展了 LLM 协助编程的试点比赛。
• CCF 主办了大模型能力认证 LMCC。
• CCF SPP 系列活动中举办了一系列紧贴 LLM 的讲座。
• CSP-J/S 第一轮中，选手可以使用 LLM 辅助完成试题。

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

阅读程序（1）

01 #include <iostream>
02 using namespace std;
03
04 bool isPrime(int n) {
05     for(int i = 2; i < n; ++i) {
06         if(n % i == 0) {
07             return false;
08         }
09     }
10     return true;
11 }
12
13 int main() {
14     int n;
15     cin >> n;
16     for(int i = 2; i + 2 <= n; ++i) {
17         if(isPrime(i) && isPrime(i + 2)) {
18             cout << i << " " << i + 2 << endl;
19         }
20     }
21     return 0;
22 }

假设输入的 n 是 5 到 1000 之间的正整数，完成下面的判断题和单选题。

判断题

第 16 题

当输入为 14 时，输出的所有整数之和为 44。（ ） {{ select(16) }}

• 正确（T）
• 错误（F）

第 17 题

将第 16 行的 int i = 2 修改为 int i = 1，程序输出不变。（ ） {{ select(17) }}

• 正确（T）
• 错误（F）

第 18 题

无论输入为多少，输出的所有整数均为奇数。（ ） {{ select(18) }}

• 正确（T）
• 错误（F）

单选题

第 19 题

当输入为 50 时，输出的所有整数之和为（ ）？ {{ select(19) }}

• 220
• 224
• 227
• 230

第 20 题

将第 5 行的 i < n 修改为以下哪个时，程序输出不变？（ ） {{ select(20) }}

• i <= n
• i * i < n
• i * i <= n
• i * i * i < n

阅读程序（2）

01 #include <iostream>
02 #include <string>
03 #include <vector>
04 #include <algorithm>
05 using namespace std;
06 int main() {
07     string a, b;
08     cin >> a >> b;
09     int n = a.size(), m = b.size();
10     vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
11     for(int i = 0; i <= n; ++i) {
12         for(int j = 0; j <= m; ++j) {
13             if(i == 0) {
14                 dp[i][j] = j;
15             }
16             else if(j == 0) {
17                 dp[i][j] = i;
18             }
19             else if(a[i - 1] == b[j - 1]) {
20                 dp[i][j] = dp[i - 1][j - 1] + 1;
21             }
22             else {
23                 dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1;
24             }
25         }
26     }
27     cout << dp[n][m] << endl;
28     return 0;
29 }

假设输入的 a, b 是长度不超过 1000 的仅包含小写字母的字符串，完成下面的判断题和单选题。

判断题

第 21 题

若交换输入的 a 和 b，程序的输出一定不变。（ ） {{ select(21) }}

• 正确（T）
• 错误（F）

第 22 题

程序的输出一定小于等于 n + m。（ ） {{ select(22) }}

• 正确（T）
• 错误（F）

第 23 题

程序的输出一定大于 min{n, m}。（ ） {{ select(23) }}

• 正确（T）
• 错误（F）

单选题

第 24 题

当输入为 aba bab 时，程序的输出为（ ）。 {{ select(24) }}

• 4
• 5
• 6
• 7

第 25 题

当输入为 abcddd acbded 时，程序的输出为（ ）。 {{ select(25) }}

• 7
• 8
• 9
• 10

第 26 题

假设输入的 a, b 都是长度为 2 且仅包含 abcd 四种字母的字符串。有多少种不同的有序字符串对 a, b 使得程序的输出为 3？（ ） {{ select(26) }}

• 16
• 72
• 84
• 156

阅读程序（3）

01 #include <iostream>
02 #include <string>
03 #include <algorithm>
04 using namespace std;
05 int n;
06 string s;
07 int dfs(string t, int lst) {
08     int ret = 0;
09     for (int i = 0; i <= n; i++)
10         if (t[i] != '1')
11             ret = 1e9;
12     if (ret == 0)return 0;
13     for (int i = 0; i <= n; i++)
14         if (i != lst && s.substr(n - i, i) == t.substr(0, i)) {
15             string cur = t;
16             cur[i] ^= 1;
17             ret = min(ret, dfs(cur, i) +1);
18         }
19     return ret;
20 }
21 int main() {
22     cin >> s;
23     n = s.size();
24     string t0(n + 1, '0');
25     cout << dfs(t0, -1);
26     return 0;
27 }

假设若无特殊说明，输入的字符串 s 是一个长度不超过 18 的非空 01 串，完成下面的判断题和单选题。

判断题

第 27 题

将第 11 行的 1e9 换成 1234567，程序的输出结果不变。（ ） {{ select(27) }}

• 正确（T）
• 错误（F）

第 28 题

将第 14 行的 if 语句中，i!=lst && 去掉，程序的输出结果不变。（ ） {{ select(28) }}

• 正确（T）
• 错误（F）

选择题

第 29 题

下列说法中正确的是（ ）。 {{ select(29) }}

• 设输入 10011101010 和 01100010101 得到的结果分别为 a, b，那么 a < b。
• 存在一种输入，使得程序发生自然溢出。
• 把第 16 行改成 cur[i] = 'a' - cur[i];，程序的输出结果会改变。
• 前三个选项都不对。

第 30 题

假设输入为 00000001，那么程序的输出为（ ）？ {{ select(30) }}

• 341
• 342
• 343
• ABC 均错

第 31 题

假设输入为 110111011110111110，那么函数 dfs 将被调用（ ）次。 {{ select(31) }}

• 2¹⁸
• 2¹⁹
• 2²⁰
• ABC 均错

第 32 题

（4 分）假设输入为 001000100001000001，那么程序的输出为（ ）？ {{ select(32) }}

• 21
• 289746
• 525739
• ABC 均错

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

（1）（序列第 k 小）

给出一个长度为 n 的数列 a₁, a₂, …, aₙ 和一个正整数 k，你需要输出第 k 小的数字。输入保证 1 ≤ k ≤ n ≤ 10⁵，1 ≤ aᵢ ≤ 2 × 10⁹，且 aᵢ 均为整数。

下面的程序采用二分答案的方法，通过二分法找到最小的 x 使得至少 k 个数字不超过 x。试补全程序。

01 #include <iostream>
02
03 using namespace std;
04
05 int n, k, a[100'005];
06 bool check(int x) {
07     int c = 0;
08     for (int i = 1; i <= n; i++)
09         if ( ① )
10             c++;
11     return ②;
12 }
13 int main() {
14     cin >> n >> k;
15     for (int i = 1; i <= n; i++)
16         cin >> a[i];
17     int l = 1, r = ③;
18     while (l < r) {
19         int x = ④;
20         if (check(x))
21             r = x;
22         else
23             ⑤;
24     }
25     cout << l << endl;
26     return 0;
27 }

第 33 题

① 处应填（ ） {{ select(33) }}

• a[i]<=x
• a[i] < x
• x <= a[i]
• x < a[i]

第 34 题

② 处应填（ ） {{ select(34) }}

• c <= k
• c < k
• k <= c
• k < c

第 35 题

③ 处应填（ ） {{ select(35) }}

• n
• a[n]
• 1 << 32
• 2e9

第 36 题

④ 处应填（ ） {{ select(36) }}

• (l + r) / 2
• (l + r + 1) >> 1
• l + (r - l) >> 1
• l + (r - l) / 2

第 37 题

⑤ 处应填（ ） {{ select(37) }}

• l = x + 1
• l = x
• break
• l += x

（2）（走迷宫）

有一个 n × m 的网格迷宫。记第 i 行第 j 列的格子为 (i, j)。迷宫由空地（用 . 表示）和墙壁（用 # 表示）组成。起点是 (1, 1)，终点是 (n, m)，保证起点和终点都是空地。小 R 希望使用两种操作从起点到达终点：步行，即移动到上下左右相邻的空地；传送，即移动到上下左右距离为 2 的空地，中间跨越的格子可以是空地也可以是墙壁。

小 R 最多使用 k 次传送。请计算她到达终点的最少操作次数。如果无法到达，输出 -1。

输入保证 1 ≤ n, m ≤ 100，0 ≤ k ≤ 10。输入的 grid[i][j] 只有 . 和 # 两种字符。

下面的程序使用了广度优先搜索的方式完成本题。试补全程序。

01 #include <bits/stdc++.h>
02 using namespace std;
03 const int MAXN = 105, MAXK = 15;
04 const int dx[4] = ①;
05 const int dy[4] = {0, 0, -1, 1};
06 int n, m, k, dis[MAXN][MAXN][MAXK];
07 char grid[MAXN][MAXN];
08 struct Node {
09     int x, y, k;
10 };
11 int bfs() {
12     memset(dis, 0x3f, sizeof(dis));
13     queue<Node> q;
14     q.push({1, 1, 0});
15     dis[1][1][0] = 0;
16     while( ② ) {
17         Node u = q.front();
18         q.pop();
19         if(u.x == n && u.y == m) {
20             return ③ ;
21         }
22         for(int i = 0; i < 4; i++) {
23             int nx = u.x + dx[i];
24             int ny = u.y + dy[i];
25             if(nx >= 1 && nx <= n && ny >= 1 && ny <= m && grid[nx][ny] != '#') {
26                 if(dis[nx][ny][u.k] > dis[u.x][u.y][u.k] + 1) {
27                     dis[nx][ny][u.k] = dis[u.x][u.y][u.k] + 1;
28                     q.push({nx, ny, u.k});
29                 }
30             }
31         }
32         if( ④ ) {
33             for(int i = 0; i < 4; i++) {
34                 int nx = u.x + dx[i] * 2;
35                 int ny = u.y + dy[i] * 2;
36                 int nk = u.k + 1;
37                 if(nx >= 1 && nx <= n && ny >= 1 && ny <= m && grid[nx][ny] != '#') {
38                     if(dis[nx][ny][nk] > dis[u.x][u.y][u.k] + 1) {
39                         dis[nx][ny][nk] = dis[u.x][u.y][u.k] + 1;
40                         ⑤;
41                     }
42                 }
43             }
44         }
45     }
46     return -1;
47 }
48
49 int main() {
50     cin >> n >> m >> k;
51     for(int i = 1; i <= n; i++) {
52         for(int j = 1; j <= m; j++) {
53             cin >> grid[i][j];
54         }
55     }
56     cout << bfs() << endl;
57     return 0;
58 }

第 38 题

① 处应填（ ）？ {{ select(38) }}

• {0, 0, -1, 1}
• {0, -1, 1, 0}
• {-1, 1, 0, 0}
• {-1, 1, -1, 1}

第 39 题

② 处应填（ ）？ {{ select(39) }}

• !q.empty()
• !q.size()
• !q.clear()
• q.front()

第 40 题

③ 处应填（ ）？ {{ select(40) }}

• dis[u.x][u.y][u.k] + 1
• dis[u.x][u.y][u.k]
• dis[u.x][u.y][k]
• dis[u.x][u.y][0]

第 41 题

④ 处应填（ ）？ {{ select(41) }}

• u.k == k
• u.k > 0
• u.k <= k
• u.k < k

第 42 题

⑤ 处应填（ ）？ {{ select(42) }}

• q.push(nx, ny, nk)
• q.push_back({nx, ny, nk})
• q.insert({nx, ny, nk})
• q.push({nx, ny, nk})