2026 LUOGU 非专业级别收容能力认证第一轮 (SCP-J1) 入门级 C++ 语言试题

一、单项选择题（共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. 阅读下面的代码，其中说法错误的是（ ）。

#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(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. 下面代码的输出为（ ）。 {{ select(7) }}

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

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

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

{{ select(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(9) }}

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

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

• 贪心。从第 1 个数开始选择，每次选取比上一个数更大的最小的数。
• 搜索。通过深度优先搜索，枚举每一个数应该选哪一个。
• 动态规划。用 $dp[i]$ 表示以 $a_i$ 结束的最长上升子序列的长度。此时有 $dp[i] = \max(dp[j]) + 1$，其中 $j$ 满足 $1 \leq 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(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)

#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。 {{ 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)

#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$，程序的输出一定不变。 {{ 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)

#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，程序的输出结果不变。 {{ 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. 假设输入为 110111101111011110，那么函数 dfs 将被调用（ ）次。 {{ select(31) }}

• 218
• 219
• 220
• ABC 均错

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

• 21
• 289746
• 525739
• ABC 均错

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

(1) 序列第 k 小

给出一个长度为 $n$ 的数列 $a_1, a_2, \ldots, a_n$ 和一个正整数 $k$，你需要输出第 $k$ 小的数字。输入保证 $1 \leq k \leq n \leq 10^5$，$1 \leq a_i \leq 2 \times 10^9$，且 $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(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 \times m$ 的网格迷宫。记第 $i$ 行第 $j$ 列的格子为 $(i,j)$。迷宫由空地（用 . 表示）和墙壁（用 # 表示）组成。起点是 $(1,1)$，终点是 $(n,m)$，保证起点和终点都是空地。小 R 希望使用两种操作从起点到达终点：

• 步行：移动到上下左右相邻的空地。
• 传送：移动到上下左右距离为 2 的空地。中间跨越的格子可以是空地也可以是墙壁。

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

输入保证 $1 \leq n, m \leq 100$，$0 \leq k \leq 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(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})