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

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

• int
• bool
• double
• char

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

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

3. 阅读下面的代码：

#include <bits/stdc++.h>
using namespace std;
stack <int> s1, s2;
int T, x;

int main() {
    cin >> T;
    while(T--) {
        string op; cin >> op;
        if(op == "in") {
            cin >> x; s1.push(x);
        }
        else {
            if(s2.empty()) {
                while(!s1.empty()) {
                    s2.push(s1.top());
                    s1.pop();
                }
            }
            cout << s2.top() << endl;
            s2.pop();
        }
    }
    return 0;
}

其中说法错误的是（ ）{{ select(1-3) }}

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

4. (1C)₁₆、(24)₁₀、(31)₈ 和 (11011)₂ 中，最大的数的十进制表示为（ ）。（ ）{{ select(1-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(1-5) }}

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

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

• -1
• 2147483647
• 4294967295
• 4294967296

7. 阅读下面的代码：

#include <iostream>
int main() {
    unsigned int a = 2147483648;
    int b = 1234567890;
    std::cout << int(a + b) << std::endl;
}

该程序的输出为（ ）{{ select(1-7) }}

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

8. 下面的表格是图 G 的邻接表：

1	2  3  4  5
2	1  3
3	1  2  6
4	1  5
5	1  4
6	3

关于图 G 说法错误的是（ ）{{ select(1-8) }}

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

9. 阅读下面的代码：

#include <iostream>
using namespace std;
int main(){
    int A = 1, B = 1;
    int& a = A, b = B;
    a = 2, b = 2;
    std::cout << A << ' ' << B << std::endl;
}

该代码的输出为（ ）{{ select(1-9) }}

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

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

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

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

• 8
• 16
• 32
• 64

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

• EACDBGF
• ECADBGF
• EACBDGF
• EACDFGB

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

• 79
• 80
• 81
• 93

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

• 10
• 20
• 30
• 40

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

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

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

（1）

#include <iostream>
using namespace std;

bool isPrime(int n) {
    for(int i = 2; i < n; ++i) {
        if(n % i == 0) {
            return false;
        }
    }
    return true;
}

int main() {
    int n;
    cin >> n;
    for(int i = 2; i + 2 <= n; ++i) {
        if(isPrime(i) && isPrime(i + 2)) {
            cout << i << " " << i + 2 << endl;
        }
    }
    return 0;
}

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

判断题

16. 当输入为 14 时，输出的所有整数之和为 44。（ ）{{ dropdown(2-1)[√, ×] }}

17. 将第 16 行的 int i = 2 修改为 int i = 1，程序输出不变。（ ）{{ dropdown(2-2)[√, ×] }}

18. 无论输入为多少，输出的所有整数均为奇数。（ ）{{ dropdown(2-3)[√, ×] }}

单选题

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

• 220
• 224
• 227
• 230

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

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

（2）

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    string a, b;
    cin >> a >> b;
    int n = a.size(), m = b.size();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
    for(int i = 0; i <= n; ++i) {
        for(int j = 0; j <= m; ++j) {
            if(i == 0) {
                dp[i][j] = j;
            }
            else if(j == 0) {
                dp[i][j] = i;
            }
            else if(a[i - 1] == b[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }
            else {
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1;
            }
        }
    }
    cout << dp[n][m] << endl;
    return 0;
}

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

判断题

21. 若交换输入的 a 和 b，程序的输出一定不变。（ ）{{ dropdown(2-6)[√, ×] }}

22. 程序的输出一定小于等于 n + m。（ ）{{ dropdown(2-7)[√, ×] }}

23. 程序的输出一定大于 min{n, m}。（ ）{{ dropdown(2-8)[√, ×] }}

单选题

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

• 4
• 5
• 6
• 7

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

• 7
• 8
• 9
• 10

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

• 16
• 72
• 84
• 156

（3）

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int n;
string s;
int dfs(string t, int lst) {
    int ret = 0;
    for (int i = 0; i <= n; i++)
        if (t[i] != '1')
            ret = 1e9;
    if (ret == 0)return 0;
    for (int i = 0; i <= n; i++)
        if (i != lst && s.substr(n - i, i) == t.substr(0, i)) {
            string cur = t;
            cur[i] ^= 1;
            ret = min(ret, dfs(cur, i) +1);
        }
    return ret;
}
int main() {
    cin >> s;
    n = s.size();
    string t0(n + 1, '0');
    cout << dfs(t0, -1);
    return 0;
}

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

判断题

27. 将第 11 行的 1e9 换成 1234567，程序的输出结果不变。（ ）{{ dropdown(2-12)[√, ×] }}

28. 将第 14 行的 if 语句中，i != lst && 去掉，程序的输出结果不变。（ ）{{ dropdown(2-13)[√, ×] }}

单选题

29. 下列说法中正确的是（ ）{{ select(2-14) }}

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

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

• 341
• 342
• 343
• ABC 均错

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

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

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

• 21
• 289746
• 525739
• ABC 均错

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

（1）（序列第 k 小）

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

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

#include <iostream>

using namespace std;

int n, k, a[100'005];
bool check(int x) {
    int c = 0;
    for (int i = 1; i <= n; i++)
        if ( ① )
            c++;
    return ②;
}
int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    int l = 1, r = ③;
    while (l < r) {
        int x = ④;
        if (check(x))
            r = x;
        else
            ⑤;
    }
    cout << l << endl;
    return 0;
}

33. ① 处应填（ ）{{ select(3-1) }}

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

34. ② 处应填（ ）{{ select(3-2) }}

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

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

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

36. ④ 处应填（ ）{{ select(3-4) }}

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

37. ⑤ 处应填（ ）{{ select(3-5) }}

• 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] 只有 . 和 # 两种字符。

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

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 105, MAXK = 15;
const int dx[4] = ①;
const int dy[4] = {0, 0, -1, 1};
int n, m, k, dis[MAXN][MAXN][MAXK];
char grid[MAXN][MAXN];
struct Node {
    int x, y, k;
};
int bfs() {
    memset(dis, 0x3f, sizeof(dis));
    queue<Node> q;
    q.push({1, 1, 0});
    dis[1][1][0] = 0;
    while( ② ) {
        Node u = q.front();
        q.pop();
        if(u.x == n && u.y == m) {
            return ③;
        }
        for(int i = 0; i < 4; i++) {
            int nx = u.x + dx[i];
            int ny = u.y + dy[i];
            if(nx >= 1 && nx <= n && ny >= 1 && ny <= m && grid[nx][ny] != '#') {
                if(dis[nx][ny][u.k] > dis[u.x][u.y][u.k] + 1) {
                    dis[nx][ny][u.k] = dis[u.x][u.y][u.k] + 1;
                    q.push({nx, ny, u.k});
                }
            }
        }
        if( ④ ) {
            for(int i = 0; i < 4; i++) {
                int nx = u.x + dx[i] * 2;
                int ny = u.y + dy[i] * 2;
                int nk = u.k + 1;
                if(nx >= 1 && nx <= n && ny >= 1 && ny <= m && grid[nx][ny] != '#') {
                    if(dis[nx][ny][nk] > dis[u.x][u.y][u.k] + 1) {
                        dis[nx][ny][nk] = dis[u.x][u.y][u.k] + 1;
                        ⑤;
                    }
                }
            }
        }
    }
    return -1;
}

int main() {
    cin >> n >> m >> k;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            cin >> grid[i][j];
        }
    }
    cout << bfs() << endl;
    return 0;
}

38. ① 处应填（ ）{{ select(3-6) }}

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

39. ② 处应填（ ）{{ select(3-7) }}

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

40. ③ 处应填（ ）{{ select(3-8) }}

• 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(3-9) }}

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

42. ⑤ 处应填（ ）{{ select(3-10) }}

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