一、单项选择题(每题 2 分,共 30 分)

1. 在 $64$ 位计算机中,下列 C++ 基本类型中( )的单个变量占用内存最大。

{{ select(1) }}

• int
• bool
• double
• char

2. Ubuntu 下当前用户 admin1,工作目录/home/admin1,用( )命令可在/home/sjtu/phd 下新建子目录 paper。

{{ select(2) }}

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

3. 下面用 $s_1$、$s_2$ 两个栈模拟入队出队的代码,说法错误的一项是( )。

{{ select(3) }}

• stack 是 STL 提供的栈,特点先进后出
• 代码功能类似队列
• 输入 in $1$ out in $2$ in $3$ out out 时,输出为 $1$ $3$ $2$
• 若不对 in/out 数量做保证,代码有运行时错误风险

4. $1C_{16}$、$24_{10}$、$31_8$、$11011_2$ 中,最大的数的十进制是( )。

{{ select(4) }}

• $28$
• $30$
• $25$
• $27$

5. ALU 是算术逻辑单元,根据材料推断它属于( )的一部分。

{{ select(5) }}

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

6. int x =-1 ,强制转成 unsigned int 输出,值为( )。

{{ select(6) }}

• $‐1$
• $2147483647$
• $4294967295$
• $4294967296$

7. 下面代码输出为( )。

unsigned int a = 2147483648;
int b = 1234567890;
std::cout << int(a + b) << std::endl;

{{ 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. 下面代码输出为( )。

int A = 1, B = 1;
int& a = A, b = B;
a = 2, b = 2;
std::cout << A << ' ' << B << std::endl;

{{ select(9) }}

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

10. 关于求最长上升子序列(LIS),下列说法不能正确求解的是( )。

{{ select(10) }}

• 贪心:从第 $1$ 个数开始,每次选比上一个数更大的最小的数
• 搜索:DFS 枚举每个数选或不选
• DP:dp[i] 表示以 ai 结尾的 LIS 长度
• DP:dp[i] 表示长度为 $i$ 的上升子序列结尾的最小值,配合二分

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. 二叉树中序 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. 关于 LLM 与 CCF 有关活动,说法不正确的是( )。

{{ select(15) }}

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

二、阅读程序

判断题每题 1.5 分，选择题每题 3 分，第 32 题 4 分，共 40 分。

程序 ($1$)孪生素数判断

#include<bits/stdc++.h>
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;
}

(1) 输入 $14$ 时,输出所有整数之和为 $44$ 。

{{ select(16) }}

• 正确
• 错误

(2) 把第 $13$ 行 int i = 2 改成 int i = 1 ,输出不变。

{{ select(17) }}

• 正确
• 错误

(3) 无论输入多少,输出的所有整数均为奇数。

{{ select(18) }}

• 正确
• 错误

(4) 输入 $50$ 时,输出所有整数之和为( )。

{{ select(19) }}

• $220$
• $224$
• $227$
• $230$

(5) 把第 $5$ 行 i < n 改成以下哪个时,程序输出不变?( )

{{ select(20) }}

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

程序 ($2$)最短公共超序列(SCS)

#include<bits/stdc++.h>
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;
}

(1) 交换输入的 $a$ 和 $b$ ,输出一定不变。

{{ select(21) }}

• 正确
• 错误

(2) 输出一定 ≤ n+m。

{{ select(22) }}

• 正确
• 错误

(3) 输出一定大于 min{n, $m$}。

{{ select(23) }}

• 正确
• 错误

(4) 输入 aba bab 时,输出为( )。

{{ select(24) }}

• $4$
• $5$
• $6$
• $7$

(5) 输入 abcddd acbded 时,输出为( )。

{{ select(25) }}

• $7$
• $8$
• $9$
• $10$

(6) $a$、$b$ 都是长度为 $2$ 、字母表为 {a,$b$,$c$,$d$ } 的字符串,有多少有序对使输出为 $3$?( )

{{ select(26) }}

• $16$
• $72$
• $84$
• $156$

程序 ($3$)$01$ 串翻转搜索

#include<bits/stdc++.h>
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);
}

(1) 把第 $8$ 行的 $1e9$ 换成 $1234567$ ,程序输出不变。

{{ select(27) }}

• 正确
• 错误

(2) 去掉第 $11$ 行 if 中的 i != lst && ,程序输出不变。

{{ select(28) }}

• 正确
• 错误

(3) 下列说法正确的是( )。

{{ select(29) }}

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

(4) 输入 $00000001$ ,程序输出为( )。

{{ select(30) }}

• $341$
• $342$
• $343$
• ABC 均错

(5) 输入 $110111011110111110$ ,函数 dfs 被调用( )次。

{{ select(31) }}

• $218$
• $219$
• $220$
• ABC 均错

(6) 输入 $001000100001000001$ ,程序输出为( )。

{{ select(32) }}

• $21$
• $2$ $8$ $9$ $7$ $4$ $6$
• $5$ $2$ $5$ $7$ $3$ $9$
• ABC 均错

三、完善程序

单项选择题,每题 $3$ 分,共 $30$ 分。

程序 ($1$)查找第 $k$ 小的数。最小的 $x$ 使得数组的所有元素不大于 $x$ 的个数至少是 $k$(二分答案)

#include<bits/stdc++.h>
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;
}

(1) ① 处应填( )

{{ select(33) }}

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

(2) ② 处应填( )

{{ select(34) }}

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

(3) ③ 处应填( )

{{ select(35) }}

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

(4) ④ 处应填( )

{{ select(36) }}

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

(5) ⑤ 处应填( )

{{ select(37) }}

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

程序 ($2$)走迷宫 (BFS+传送)

#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], 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, 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;
}

(1) ① 处应填( )

{{ select(38) }}

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

(2) ② 处应填( )

{{ select(39) }}

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

(3) ③ 处应填( )

{{ 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]

(4) ④ 处应填( )

{{ select(41) }}

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

(5) ⑤ 处应填( )

{{ select(42) }}

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