2025CSP-J初赛模拟卷 2

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

第 1 题 在 $C$++ 程序中，假设一个字符占用的内存空间是 $1$ 字节，则下列程序中，s 占用的内存空间是 ( ) 字节。

char s[] = "hello oiers";
size_t cnt = sizeof(s);
cout << cnt << endl;

{{ select(1) }}

• $10$
• $11$
• $13$
• $12$

第 2 题 十六进制数 B2025 转换成八进制数是 ( )。 {{ select(2) }}

• 2620045
• 2004526
• 729125
• 2420045

第 3 题 以下能正确定义二维数组的是 ( )。 {{ select(3) }}

• int a[3][];
• int a[][];
• int a[][4];
• int a[][2] = {{1, 2},{1, 2}, {3, 4}};

第 4 题 二进制 $[10000011]_{原码}$和 $[10000011]_{补码}$表示的十进制数值分别是 ( )。 {{ select(4) }}

• -125, -3
• -3, -125
• -3, -3
• -125, -125

第 5 题 在 $C$++ 中，下列定义方式中，变量的值不能被修改的是 ( )。 {{ select(5) }}

• unsigned int a = 5;
• static double d = 3.14;
• string s = "ccf csp-j";
• const char c = 'k';

第 6 题 走迷宫的深度优先搜索算法经常用到的数据结构是 ( )。 {{ select(6) }}

• 向量
• 栈
• 链表
• 队列

第 7 题 关于递归，以下叙述中正确的是 ( )。 {{ select(7) }}

• 动态规划算法都是用递归实现的
• 递归比递推更高级，占用的内存空间更少
• $A$ 函数调用 $B$ 函数，$B$ 函数再调用 $A$ 函数不属于递归的一种
• 递归是通过调用自身来求解问题的编程技术

第 8 题 以下不属于计算机输入设备的是 ( )。 {{ select(8) }}

• 扫描仪
• 显示器
• 鼠标
• 麦克风

第 9 题 关于排序算法，下面的说法中正确的是 ( )。 {{ select(9) }}

• 快速排序算法在最坏情况下的时间复杂度是 $O(nlogn)$
• 插入排序算法的时间复杂度是 $O(nlogn)$
• 归并排序算法的时间复杂度是 $O(nlogn)$
• 冒泡排序算法是不稳定的

第 10 题 下列关于 $C$++ 语言的叙述中不正确的是 ( )。 {{ select(10) }}

• 变量没有定义也能使用
• 变量名不能以数字开头，且中间不能有空格
• 变量名不能和 $C$++ 语言中的关键字重复
• 变量在定义的时候可以不用赋值

第 11 题 如果 x 和 y 均为 int 类型的变量，下列表达式中能正确判断“x 等于 y”的是 ( )。 {{ select(11) }}

• (1 == (x / y))
• (x == (x & y))
• (0 == (x ^ y))
• (y == (x | y))

第 12 题 在如今的智能互联网时代，$AI$ 如火如荼，除了计算机领域以外，通信领域的技术发展也做出了很大贡献。被称为“通信之父”的是 ( )。 {{ select(12) }}

• 克劳德·香农
• 莱昂哈德·欧拉
• 约翰·冯·诺依曼
• 戈登·摩尔

第 13 题 一棵满二叉树的深度为 $3$（根结点的深度为 $1$），按照后序遍历的顺序从 $1$ 开始编号，根结点的右子结点的编号是 ( )。 {{ select(13) }}

• $3$
• $6$
• $7$
• $5$

第 14 题 三头奶牛 $Bessie、Elise$ 和 $Nancy$ 去参加考试，考场是连续的 $6$ 间牛棚，用栅栏隔开。为了防止作弊，任意两头奶牛都不能在相邻的牛棚，则考场安排共有 ( ) 种不同的方法。 {{ select(14) }}

• $18$
• $24$
• $30$
• $48$

第 15 题 为强化安全意识，某学校准备在某消防月连续 $10$ 天内随机抽取 $3$ 天进行消防紧急疏散演习，抽取的 $3$ 天为连续 $3$ 天的概率为 ( )。 {{ select(15) }}

• 3/10
• 3/20
• 1/15
• 1/18

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

程序 (1)

01 #include <iostream>
02 #include <vector>
03 #include <algorithm>
04 using namespace std;
05 using i64 = long long;
06
07 int clz(i64 x) {
08    for (int i = 0; i != 64; i++) {
09        if ((x >> (63 - i)) & 1)
10            return i;
11    }
12    return 64;
13 }
14
15 bool cmp(i64 x, i64 y) {
16    if (clz(x) == clz(y))
17        return x < y;
18    return clz(x) < clz(y);
19 }
20
21 int main() {
22    int n;
23    cin >> n;
24    vector<int> a(n);
25    for (int i = 0; i < n; i++) {
26        cin >> a[i];
27    }
28    sort(a.begin(), a.end(), cmp);
29    for (int i = 0; i < n; i++) {
30        cout << a[i] << " \n"[i == n - 1];
31    }
32    return 0;
33 }

判断题 16 若程序输入为 5 0 4 2 1 3，则程序输出为 4 2 3 1 0。 ( ) {{ select(16) }}

• 对
• 错

判断题 17 若将第 $17$ 行中的 < 换为 >，则当程序输入为 5 0 4 2 1 3 时，程序输出为 4 3 2 1 0。 ( ) {{ select(17) }}

• 对
• 错

判断题 18 当调用 cmp(3, 3) 时，函数的返回值为 false。 ( ) {{ select(18) }}

• 对
• 错

选择题 19 若输入为 5 4 2 1 3 1，则输出是什么？( ) {{ select(19) }}

• 3 4 2 1 1
• 3 2 4 1 1
• 4 3 2 1 1
• 4 2 3 1 1

选择题 20 这个程序实现了什么功能？( ) {{ select(20) }}

• 将输入的数组按照二进制位上从左到右第一个 $1$ 前 $0$ 的个数由多到少进行排序
• 将输入的数组按照二进制位上从左到右第一个 $1$ 前 $0$ 的个数由少到多进行排序
• 将输入的数组按照二进制位上从左到右第一个 $1$ 前 $0$ 的个数由多到少进行排序，当 $0$ 的个数相同时，按照原数字由小到大进行排序
• 将输入的数组按照二进制位上从左到右第一个 $1$ 前 $0$ 的个数由少到多进行排序，当 $0$ 的个数相同时，按照原数字由小到大进行排序

程序 (2)

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

假设 $m\le 100, n\le 10000$

判断题 21 若输入为 2 3 1 2 3 4 5 6，则输出为 10。 ( ) {{ select(21) }}

• 对
• 错

判断题 22 计算 dp 数组的时间复杂度为 $O(n^2)$。 ( ) {{ select(22) }}

• 对
• 错

判断题 23 ($2$ 分) 在 calc 函数中，访问 dp[m][n] 不会发生越界错误。 ( ) {{ select(23) }}

• 对
• 错

选择题 24 当输入的 a 数组为 {{1, 3, 1}, {1, 5, 1}, {4, 2, 1}} 时，程序输出为 ( )。 {{ select(24) }}

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

选择题 25 若将第 $17$ 行改为 dp[i][j] = min(dp[i][j], dp[i - 1][j] - grid[i][j]);，则当输入的 a 数组为 {{1, 2, 3}, {4, 5, 6}} 时，程序的输出为 ( )。 {{ select(25) }}

• $-3$
• $-2$
• $-1$
• $0$

选择题 26 ($4$ 分) 若将第 $10$ 行中的 & 符号去除，可能出现什么情况？( ) {{ select(26) }}

• dp 数组计算错误
• calc 函数中的 grid 数组和 a 数组不一致
• 无影响
• 发生编译错误

程序 (3)

01 #include <iostream>
02 #include <vector>
03 #include <algorithm>
04 #include <set>
05 #include <string>
06 using namespace std;
07
08 const int N = 1010;
09 vector<int> E[N];
10 int V[N];
11 int n;
12
13 void add(int x, int y) {
14   E[x].push_back(y);
15 }
16
17 int gcd(int x, int y) {
18    return !y ? x : gcd(y, x % y);
19 }
20
21 void calc(int cur, int fa) {
22    V[cur] = (gcd(cur, fa) != 1);
23    for (auto v : E[cur]) {
24        if (v == fa)
25            continue;
26        calc(v, cur);
27        V[cur] += V[v];
28    }
29 }
30
31 int main() {
32    cin >> n;
33    for (int i = 1; i < n; i++) {
34        int x, y;
35        cin >> x >> y;
36        add(x, y);
37        add(y, x);
38    }
39    calc(1, 1);
40    for (int i = 1; i <= n; i++)
41        cout << V[i] << " \n"[i == n];
42    return 0;
43 }

已知 gcd(x,y) 的时间复杂度为 $O(log(min(x,y))$ ,输入中 $1\le x,y\le n$ 且 $x\ne y$ 有，回答下面的问题。

判断题 27 当输入为 4 1 2 1 3 1 4 时，程序的输出为 0 0 0 0。 ( ) {{ select(27) }}

• 对
• 错

判断题 28 gcd 函数用来计算两个数 x 和 y 的最大公约数。 ( ) {{ select(28) }}

• 对
• 错

判断题 29 对于树上的一条边 (x, y)，若 x 为 y 的父结点，则必然有 V[x] ≤ V[y]。 ( ) {{ select(29) }}

• 对
• 错

选择题 30 当输入为 4 1 2 1 3 2 4 时，程序的输出为 ( )。 {{ select(30) }}

• 0 0 0 0
• 1 1 0 1
• 0 0 1 0
• 1 1 1 1

选择题 31 ($4$ 分) calc 函数的时间复杂度为 ( )。 {{ select(31) }}

• $O(nlog n)$
• $O(n^2)$
• $O(n)$
• $O(logn)$

选择题 32 若将第 $27$ 行中的代码改为 V[cur] *= V[v];，则当输入为 4 1 2 1 3 2 4 时，得到的输出为 ( )。 {{ select(32) }}

• 1 1 1 0
• 1 1 0 1
• 0 0 1 0
• 0 0 0 1

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

(1)题目描述

给定一个长为 $n\ (1\le n\le 2 \times 10^5$ )的数组 $a\ (-10^9\le a[i]\le 10^9 )$，执行如下操作，直到 $a$ 中只剩下 $1$ 个数

• 删除 $a[i]$。如果 $a[i]$ 左右两边都有数字，则把 $a[i-1]$ 和 $a[i+1]$ 合并成一个数。

输出最后剩下的那个数的最大值。

#include <bits/stdc++.h>
using namespace std;
using i64 = long  long;

void solve() {
    int n, flag = 0, mx = ①;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if (a[i] < 0)
            flag++;
        mx = max(mx, a[i]);
    }
    if (②) {
        cout << mx << endl;
        return;
    }
    ③ sum1 = 0, sum2 = 0;
    for (int i = 1; i <= n; i += 2)
        sum1 += max(a[i], 0);
    for (int i = 2; i <= n; i += 2)
        ④;
    cout << ⑤ << endl;
}

int main() {
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

选择题 33 ①处应填 ( ) {{ select(33) }}

• 0
• 1E9
• -1E8
• -2E9

选择题 34 ②处应填 ( ) {{ select(34) }}

• flag == n
• flag == 0
• flag != 0
• flag != n

选择题 35 ③处应填 ( ) {{ select(35) }}

• int
• i64
• i32
• unsigned int

选择题 36 ④处应填 ( ) {{ select(36) }}

• sum2 += max(a[i], 0)
• sum2 += min(a[i], 0)
• sum2 -= min(a[i], 0)
• sum2 -= max(a[i], 0)

选择题 37 ⑤处应填 ( ) {{ select(37) }}

• min(sum1, sum2)
• max(sum1, sum2)
• sum1 + sum2
• sum1 - sum2

(2)题目描述

给定一个字符串 t 和一个字符串列表 s 作为字典。保证 s 中的字符串互不相同，且 t 和 s[i] 中均只包含小写英文字母。

如果可以利用字典中出现的一个或多个单词拼接出 t，则返回 true。

注意：不要求字典中出现的单词全部使用，并且字典中的单词可以重复使用。

数据限制：$1\le t.length()\le 300 , 1\le s.size()\le 1000, 1\le s[i].length()\le 20$。

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <string>
using namespace std;

const int N = 100005;

int n, mx, m;
vector<string> s;
vector<int> mem;
string t;
set<string> st;

int dfs(int i) {
    if (i == 0)
        return 1;
    if (①)
        return mem[i];
    for (int j = i - 1; j >= max(i - mx, 0); j--) {
        if (st.find(②) != st.end() && dfs(j))
            return mem[i] = 1;
    }
    return ③;
}

int main() {
    cin >> n;
    s.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> s[i];
        mx = max(mx, ④);
    }
    st = set<string>(s.begin(), s.end());
    cin >> t;
    m = (int)t.length();
    mem.resize(m + 1, -1);
    if (⑤)
        cout << "Yes\n";
    else
        cout << "No\n";
    return 0;
}

选择题 38 ①处应填 ( ) {{ select(38) }}

• mem[i] != -1
• mem[i] == -1
• mem[i] == 0
• mem[i] != 0

选择题 39 ②处应填 ( ) {{ select(39) }}

• t.substr(i, j - i)
• t.substr(j, i - j)
• t.substr(j)
• t.substr(i)

选择题 40 ③处应填 ( ) {{ select(40) }}

• 1
• mem[i] = 1
• 0
• mem[i] = 0

选择题 41 ④处应填 ( ) {{ select(41) }}

• s[i].length()
• (int)s[i].length()
• s[i].length() - 1
• (int)s[i].length() - 1

选择题 42 ⑤处应填 ( ) {{ select(42) }}

• !dfs(m)
• !dfs(n)
• dfs(m)
• dfs(n)