2026 SCP-J1 入门级 C++ 试题解析

温馨提示

本解析由老师整理提供，仅供参考，并非官方标准答案。

建议策略：

1. 优先做会做的题，先把基础分拿稳
2. 看不懂的题先跳过，不要卡在一道题上浪费时间
3. 程序阅读题先看功能，再逐行理解，实在不行就靠选项反推
4. 完善程序题多注意上下文逻辑，填完之后代入验证

建议先独立思考，再对照解析，毕竟，学会方法比记住答案更重要。

与其花时间死磕一道难题，不如把时间花在确保会做的题全对。

---

答案速查表

一、单项选择题（1~15）

题号	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
答案	C	D	C	A	A	C	B	C	C	A	C	A	B	B	D

二、阅读程序

程序（一）孪生素数（16~20）

题号	16	17	18	19	20
答案	T	F	T	B	C

程序（二）编辑距离（21~26）

题号	21	22	23	24	25	26
答案	T	T	F	A	B	D

程序（三）01串递归（27~32）

题号	27	28	29	30	31	32
答案	T	F	D	A	B	D

三、完善程序

程序（一）二分求第k小（33~37）

题号	33	34	35	36	37
答案	A	C	D	D	A

程序（二）走迷宫BFS（38~42）

题号	38	39	40	41	42
答案	C	A	B	D	D

---

一、单项选择题

第1题

答案：C

解析
double 占 8 字节，int 占 4 字节，bool 占 1 字节，char 占 1 字节。因此 double 最大。

---

第2题

答案：D

解析
mkdir 用于创建目录，mv 用于移动或重命名，不能创建目录。
~ 表示当前用户主目录 /home/luogu，与目标 /home/sjtu/phd 不符。
./sjtu/phd/paper 表示在当前目录下创建子目录，相对路径合理。

---

第3题

答案：C

解析
两个栈模拟队列，输入 in 1 out in 2 in 3 out out 输出应为 1 2 3，不是 132。

#include <bits/stdc++.h>
using namespace std;
stack<int> s1, s2;  // s1: 入队栈, s2: 出队栈
int T, x;
int main() {
    cin >> T;// 读取操作次数
    while (T--) {
        string op;
        cin >> op; // 读取
        if (op == "in") {   // 入队
            cin >> x;
            s1.push(x);     // 直接压入s1
        } else {            // 出队
            if (s2.empty()) {
                // 如果s2为空，将s1中所有元素倒入s2，顺序反转
                while (!s1.empty()) {
                    s2.push(s1.top());
                    s1.pop();
                }
            }
            // s2的栈顶即为队首元素
            cout << s2.top() << endl;
            s2.pop();       // 弹出队首
        }
    }
    return 0;
}

---

第4题

答案：A

解析

• (1C)₁₆ = 1×16+12 = 28
• (24)₁₀ = 24
• (31)₈ = 3×8+1 = 25
• (11011)₂ = 16+8+0+2+1 = 27
  最大为 28。

---

第5题

答案：A

解析
ALU（算术逻辑单元）是 CPU 的一部分。

---

第6题

答案：C

解析
-1 的补码为 32 位全 1，转 unsigned int 得 $2^{32}-1=4294967295$。

• 原码：-1 的原码是 1000 0001（首位1表示负号，后面是数值1）。
• 反码：负数取反，符号位不变，其余位取反：1111 1110。
• 补码：反码加 1：1111 1111。

你看，-1 的补码，所有位全都是 1！

换成 32 位的 int，就是 32 个 1：
11111111 11111111 11111111 11111111

$2^{31}+2^{30}+\cdots +2^1+2^0=2^{32}-1=4294967295$

---

第7题

答案：B

解析
unsigned int a = 2147483648; int b = 1234567890;
a+b = 3382051538，强制转 int 得 -912915758。

---

第8题

答案：C

解析
由邻接表还原边集，所有结点 1~6 连通，连通块数为 1，不是 2。

---

第9题

答案：C

解析
int& a = A, b = B; 只有 a 是引用，b 是普通变量。a=2 修改 A，b=2 不修改 B，输出 2 1。

---

第10题

答案：A

解析
贪心法在 [3,1,2,4] 上失败（选 3,4 而非最优 1,2,4），不能保证全局最优。

---

第11题

答案：C

解析

6 个字符 → 5 次合并 → 5 个内部节点 → 每个内部节点可左右互换（2 种） → 总共 $2^5=32$ 种。

每个内部节点都有 2 种分配方式（左 0 右 1 或 左 1 右 0）。

5 个内部节点相互独立，所以总方案数为：

$$2\times 2\times 2\times 2\times 2=2^5=32$$

所以答案是 C（32）。

---

第12题

答案：A

解析
由中序 CADBEFG 和后序 CBDAFGE 重建树，前序为 EACDBGF。

遍历方式	结果	是否匹配
前序（根-左-右）	E → A → C → D → B → G → F = EACDBGF	✅ 选项 A
中序（左-根-右）	C → A → D → B → E → F → G = CADBEFG	✅ 匹配
后序（左-右-根）	C → B → D → A → F → G → E = CBDAFGE	✅ 匹配

---

第13题

答案：B

解析
能被3或5整除：93 个，减去其中能被7整除的 13 个，得 80。

---

第14题

答案：B

解析
奇数、偶数各自顺序固定，只需选位置：从 6 个位置选 3 个：$\left(\genfrac{}{}{0ex}{}{6}{3}\right)=20$

---

第15题

答案：D

---

二、阅读程序

程序（一）：孪生素数判断

这道题的程序主要功能是：找出并输出所有“孪生素数对”。

所谓“孪生素数”，就是两个相差 2 的素数，比如 (3, 5)、(5, 7)、(11, 13)。

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

第16题

答案：T

解析
输入 14，输出 (3,5),(5,7),(11,13)，整数和 3+5+5+7+11+13=44。

第17题

答案：F

解析
若 i 从 1 开始，isPrime(1) 误判为 true，会输出 (1,3)，结果改变。

第18题

答案：T

解析
合法孪生素数对不可能包含 2（2 和 4 不同时为素数），所以输出的都是奇数。

第19题

答案：B

解析
输入 50，孪生素数对为 (3,5),(5,7),(11,13),(17,19),(29,31),(41,43)，总和 224。

第20题

答案：C

解析
判断素数只需检查到 sqrt(n)，即 i*i <= n。

---

程序（二）：编辑距离

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;
}

计算两个字符串的“最短公共超序列”长度。

等价于：

$$\text{答案}=|a|+|b|-\text{LCS}(a,b)$$

其中 LCS 是最长公共子序列的长度。

通俗地说：

把字符串 a 和 b 合并成一个最短的字符串，使得 a 和 b 都是这个新字符串的子序列（不要求连续，只要顺序一致就行）。

int main() {
    string a, b;                      // 定义两个字符串
    cin >> a >> b;                    // 读入 a 和 b
    int n = a.size(), m = b.size();   // n 和 m 分别为 a 和 b 的长度
    // 创建 (n+1) x (m+1) 的二维数组 dp，初始化为 0
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
    // 外层循环 i 从 0 到 n
    for(int i = 0; i <= n; ++i) {
        // 内层循环 j 从 0 到 m
        for(int j = 0; j <= m; ++j) {
            if(i == 0) {                      // 如果 i 为 0（a 为空）
                dp[i][j] = j;                 // 需要 j 次插入操作
            }
            else if(j == 0) {                 // 如果 j 为 0（b 为空）
                dp[i][j] = i;                 // 需要 i 次删除操作
            }
            else if(a[i - 1] == b[j - 1]) {   // 当前字符相等
                dp[i][j] = dp[i - 1][j - 1] + 1;  // 匹配，步数 = 前一步 + 1
            }
            else {                            // 字符不相等
                // 取删除（dp[i-1][j]）或插入（dp[i][j-1]）的较小值，再加 1
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1;
            }
        }
    }
    // 输出 dp[n][m]，即 n + m - LCS(a, b)
    cout << dp[n][m] << endl;
}

第21题

答案：T

解析
交换 a,b，n+m 不变，LCS 对称，输出不变。

第22题

答案：T

解析
对调循环变量可能使 dp 访问越界，导致运行时错误。

第23题

答案：F

解析
当 a=b 时，输出 n = min(n,m)，等于而非大于。

第24题

答案：A

解析
aba 和 bab 的 LCS=2，输出 3+3-2=4。

第25题

答案：B

解析
abcddd 和 acbbed 的 LCS=4，输出 6+6-4=8。

第26题

答案：D

解析

一、总对数

字符串长度为 2，字母表大小为 4（a, b, c, d）。

一个字符串的可能数：

$$4\times 4=4^2=16$$

有序字符串对 $(a,b)$ 的总数：

$$16\times 16=256$$

---

二、LCS = 2（完全相同）

两个字符串完全相同，a 有 16 种，b 只能等于 a。

$$\text{LCS=2}=16$$

---

三、LCS = 0（没有相同字符）

情况 1：a 的两个字符相同

• a 有 4 种选法：aa, bb, cc, dd
• b 只能从剩余 3 个字符中选，每个位置 3 种：

$$4\times 3^2=4\times 9=36$$

情况 2：a 的两个字符不同

• a 的选法：$4\times 3=12$（有序排列，两个位置不同）
• b 只能从剩余 2 个字符中选，每个位置 2 种：

$$(4\times 3)\times 2^2=12\times 4=48$$

LCS = 0 总数
$$36+48=84$$

---

四、LCS = 1

用总数减去 LCS=2 和 LCS=0：

$$256-16-84=156$$

---

五、汇总表

情况	公式	数量
总对数	$4^2\times 4^2$	256
LCS=2	$4^2$	16
LCS=0	$4\times 3^2+(4\times 3)\times 2^2$	84
LCS=1	256 - 16 - 84	156

---

答案：D（156）

---

程序（三）：01串递归搜索

int dfs(string t, int lst) {
    int ret=0;// ret记录最少步数，初始为0
    for(int i=0; i<=n; ++i)// 遍历t的每个位置
        if(t[i]!='1') ret=1e9;// 只要有一个位置不是'1'，就把ret设为无穷大（表示还没到达全1状态）
    if(ret==0) return 0;// 如果所有位置都是'1'，说明已经到达目标，返回0步
    for(int i=0; i<=n; ++i)// 尝试翻转每一个位置
        if(i!=lst && s.substr(n-i,i)==t.substr(0,i)) { // 条件1：不能翻上次翻过的位置；条件2：s的后缀匹配t的前缀
            string cur=t;// 复制当前状态
            cur[i]^=1;// 翻转第i位（'0'变'1'，'1'变'0'）
            ret=min(ret, dfs(cur,i)+1);// 递归计算后续步数，取最小值
        }
    return ret;// 返回从当前状态到全1的最少步数（不可达则返回1e9）
}

这段代码用 DFS（深度优先搜索）暴力枚举所有可能的翻牌步骤，在满足两个条件的情况下，找出从全 0 翻到全 1 的最少步数，如果不可能就返回一个很大的数字。

第27题

答案：T

解析
1e9 只作无穷大，换成 1234567 足够大，结果不变。

第28题

答案：F

解析
去掉 i!=lst 可能连续翻转同一位置，导致死循环或结果改变。

第29题

答案：D

解析
A：互为取反的串结果相同；B：不会溢出；C：'a'-cur[i] 与 ^=1 效果相同。A、B、C均错。

第30题

答案：A

解析
输入 00000001，DFS 最短步数为 341。

第31题

答案：B

解析
输入 110111101111011110，递归调用次数为 219。

第32题

答案：D

解析
输入 001000100001000001，目标状态不可达，输出 1e9，A/B/C均错。

---

三、完善程序

程序（一）：二分求第k小

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;
}

第33题

答案：A
解析：统计 a[i] <= x 的个数。

第34题

答案：C
解析：返回 k <= c（即 c >= k）。

第35题

答案：D
解析：右边界设为 2e9，因为 a_i ≤ 2×10⁹。

第36题

答案：D
解析：取中点 1 + (r-1)/2（当 l 初始为 1 时可行），也可理解为防止溢出的写法。

第37题

答案：A
解析：check 为假说明答案在右侧，l = x+1。

---

程序（二）：走迷宫BFS

const int dx[4]=①;
const int dy[4]={0,0,-1,1};
int bfs() {
    // 初始化
    while(②) {
        Node u=q.front(); q.pop();
        if(u.x==n && u.y==m) return ③;
        // 步行
        for(int i=0; i<4; ++i) { /* ... */ }
        // 传送
        if(④) {
            for(int i=0; i<4; ++i) {
                // 距离2的传送
                if(合法) {
                    // 更新
                    ⑤;
                }
            }
        }
    }
    return -1;
}

第38题

答案：C
解析：dx 应与 dy 配对表示上下左右，dx={-1,1,0,0}。

第39题

答案：A
解析：BFS 循环条件为队列非空 !q.empty()。

第40题

答案：B
解析：到达终点返回当前步数 dis[u.x][u.y][u.k]。

第41题

答案：D
解析：只有 u.k < k 时才允许传送。

第42题

答案：D
解析：入队操作为 q.push({nx, ny, nk})。