CSP-J 2025初赛模拟卷 7

一、单项选择题（共 15 题，每题 2 分，共计 30 分）

第 1 题 八进制数 $2025$ 用二进制表示是（ ）。
{{ select(1) }}

• 10000000101
• 10000010101
• 10000001101
• 10000100101

第 2 题 $C$++ 语言的创始人是（ ）。
{{ select(2) }}

• 林纳斯·托瓦茨
• 丹尼斯·里奇
• 吉多·范罗苏姆
• 本贾尼·斯特劳斯特卢普

第 3 题 以下设备中，（ ）不是输出设备。
{{ select(3) }}

• 扫描仪
• 触摸屏
• 绘图仪
• 音箱

第 4 题 当执行以下 $C$++ 程序段后输出结果为（ ）。

char c1 = '2' + '0';
char c2 = '2' + '5';
cout << c1 << c2 << endl;

{{ select(4) }}

• 2025
• 27
• bg
• ch

第 5 题 应用二分算法的思想，在一个有 $n$ 个数的有序序列中查找某个指定的数，其程序时间复杂度为（ ）。
{{ select(5) }}

• $O(nlog n)$
• $O(n)$
• $O(log n)$
• $O(mlog n)$

第 6 题 贝希要参加 $CSP-J$ 比赛，在 $CCF$ 官网注册时需设置登录密码，下列选项中最安全的是（ ）。
{{ select(6) }}

• 12345678
• abcd1234
• 20010911
• F1@CcfGq6dh

第 7 题 双向链表的优点是（ ）。
{{ select(7) }}

• 查找速度快
• 插入和删除方便
• 节省内存
• 后进先出

第 8 题 小明买了一块 1TB 的固态硬盘，相当于（ ）MB 的存储容量。
{{ select(8) }}

• $2^{10}$
• $2^{20}$
• $2^{30}$
• $2^{40}$

第 9 题 下面（ ）没有用到有关人工智能的技术。
{{ select(9) }}

• 智能手机设置的闹钟定时叫我起床
• 智能手环收集患者的数据并上传至医疗系统云端进行分析
• 国家围棋队棋手和围棋机器人下围棋
• 大学校园用人脸识别门禁系统控制人员出入

第 10 题 下列选项中（ ）不是 $C$++ 标准库 $string$ 类的函数。
{{ select(10) }}

• substr
• size
• replace
• strcmp

第 11 题 有一个 $2025$ 位的正整数，它的各位数字按照如下规则排列：123456789123456789123456789...，请问这个数被 $9$ 除的余数是多少？（ ）
{{ select(11) }}

• 3
• 2
• 0
• 1

第 12 题 九宫格数独游戏是一种训练推理能力的数字谜题游戏。九宫格分为九个小宫格，某小九宫格如图所示，小明需要在 $9$ 个小格子中填上 $1$ 至 $9$ 中不重复的整数。小明通过推理已经得到了 $4$ 个小格子中的准确数字，其中，$a、b、c、d、e$ 这 $5$ 个数字未知，且 $b$ 和 $d$ 为奇数，则 $a + b > 5$ 的概率为（ ）。

$9$	$a$	$7$
$b$	$c$	$d$
$4$	$e$	$5$

{{ select(12) }}

• $3/5$
• $1/2$
• $2/3$
• $1/3$

第 13 题 四位同学进行篮球传球练习，要求每个人接球后再传给别人。开始时甲同学发球，并作为第一次传球，第五次传球后，球又回到甲同学手中，则不同的传球方法有（ ）种。
{{ select(13) }}

• $60$
• $65$
• $70$
• $75$

第 14 题 字符串 CCCSSSPPP 共有（ ）种不同的非空子串。
{{ select(14) }}

• $45$
• $36$
• $37$
• $39$

第 15 题 向一个栈顶指针为 $head$ 的链式栈中插入一个指针 $p$ 指向的节点时，应执行（ ）。
{{ select(15) }}

• head->next = p;
• p->next = head; head = p;
• p->next = head->next; head->next = p;
• p->next = head; head = head->next;

二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填 V，错误填 ×）

(1)

01 #include <bits/stdc++.h>
02 using namespace std;
03 int t, p, a, b, c;
04 int f(int a, int b) {
05    if (a % b == 0) return 0;
06    return b - a % b;
07 }
08 void solve() {
09    scanf("%d%d%d%d", &p, &a, &b, &c);
10    printf("%d\n", min(min(f(p, a), f(p, b)), f(p, c)));
11 }
12 int main() {
13    scanf("%d", &t);
14    while (t--) solve();
15    return 0;
16 }

判断题

16. 若程序输入

1
2 6 10 9

则最终输出为 $4$。（ ）
{{ select(16) }}

• 对
• 错

17. ($2$ 分) 若将第 $5$ 行删除，程序的输出结果一定不会改变。（ ）
    {{ select(17) }}

• 对
• 错

18. 若将头文件 <bits/stdc++.h> 改成 <stdio.h>，程序仍能正常运行。（ ）
    {{ select(18) }}

• 对
• 错

选择题

19. 若程序输入 2 9 5 4 8 10 9 9 9，则输出是（ ）。
    {{ select(19) }}

• 1 8
• 1 1
• 0 8
• 0 1

20. ($4$ 分) 若将第 $10$ 行的输出内容改为 f(f(f(p, a), b), c)，则输入

1 
2 6 10 9

时，输出是（ ）。
{{ select(20) }}

• $3$
• $4$
• $5$
• $6$

(2)

01 #include <bits/stdc++.h>
02 using namespace std;
03 const int N = 2e5 + 5;
04 int a, b, n, k;
05 char s[N];
06 void solve(int &a, int &b, int k) {
07    while (k--)
08    	putchar(a ? --a, '1' : (--b, '0'));
09 }
10 int main() {
11    cin >> a >> b >> k;
12    n = a + b;
13    for (int i = 1; i <= a; ++i) s[i] = '1';
14    for (int i = 1; i <= b; ++i) s[i + a] = '0';
15    while ((s[n - k] == '0' || s[n] == '1') && n > k) --n;
16    if (n <= k + 1 && k) 
17		return printf("No\n"), 0;
18    printf("Yes\n");
19    if (!k)
20        return printf("%s\n%s", s + 1, s + 1), 0;
21    a -= 2, b -= 1;
22    int A = a, B = b;
23    printf("11");
24    solve(A, B, k - 1);
25    putchar('0');
26    solve(A, B, a + b - k + 1);
27    A = a, B = b;
28    printf("\n10");
29    solve(A, B, k - 1);
30    putchar('1');
31    solve(A, B, a + b - k + 1);
32    return 0;
33 }

判断题

21. 去掉第 $6$ 行的两个 &，程序的输出一定不改变。（ ）
    {{ select(21) }}

• 对
• 错

22. 如果 $a = 0，k \ne 0$，则必定输出 No。（ ）
    {{ select(22) }}

• 对
• 错

23. 当 a + b < k + 3 时，必定输出 No。（ ）
    {{ select(23) }}

• 对
• 错

24. 若输出 Yes，则输出的两个数在二进制下的差一定有 k 位 1。（ ）
    {{ select(24) }}

• 对
• 错

选择题

25. 若输入为 2 4 3，则输出为（ ）。
    {{ select(25) }}

• Yes 101000 100001
• Yes 110000 100010
• Yes 110000 100001
• No

26. 若输入为 2 3 4，则输出为（ ）。
    {{ select(26) }}

• Yes 10100 10001
• Yes 11000 10001
• Yes 10001 00011
• No

(3)

01 #include <bits/stdc++.h>
02 using namespace std;
03 const int N = 2e5 + 5;
04 int n, m, ans, pos[2][N];
05 char a[N], b[N];
06 int main() {
07    scanf("%d%d%s%s", &n, &m, a, b);
08    reverse(a, a + n); reverse(b, b + m);
09    for (int i = 0, now = 0; i < n && now < m; ++i)
10        if (a[i] == b[now])
11            pos[0][now++] = i;
12    for (int i = n - 1, now = m - 1; ~i && ~now; --i)
13        if (a[i] == b[now])
14            pos[1][now--] = i;
15    for (int i = 1; i < m; ++i)
16        ans = max(pos[1][i] - pos[0][i - 1], ans);
17    printf("%d", ans);
18    return 0;
19 }

假设 $m\le n\le 200000$

判断题

27. 若 m 不为 n 的子序列，则输出必定为 $0$。（ ） {{ select(27) }}

• 对
• 错

28. 若将第 $8$ 行删除，程序输出结果一定不会改变。（ ）
    {{ select(28) }}

• 对
• 错

选择题

29. 若输入为 5 3 abaab abb，则输出为（ ）。
    {{ select(29) }}

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

30. 若 a = "ababcdc"，b 的长度为 5，则使答案取到最大值的 b 可能有（ ）个。
    {{ select(30) }}

• $3$
• $4$
• $6$
• $7$

31. (4分) 当 a 为 1010101 时，b 的长度为 $3$，b 的每一位上要么是 $0$，要么是 $1$。总共有 $8$ 种情况，对应 $8$ 个输出。这 $8$ 个输出的和为（ ）。
    {{ select(31) }}

• $18$
• $24$
• $30$
• $36$

32. 当 a 为 1010101 时，b 的长度为 $4$，b 的每一位上要么是 $0$，要么是 $1$。总共有 $16$ 种情况，对应 $16$ 个输出。这 $16$ 个输出的和为（ ）。
    {{ select(32) }}

• $32$
• $38$
• $46$
• $52$

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

(1) 题目描述

​ 给定一个数组 {a} 表示一排蘑菇的数量。有一个篮子。每次到一个新的 $a_i$ 时，篮子中会增加 $a_i$ 个蘑菇。如果篮子里的蘑菇超过 x 个，则篮子里的蘑菇会清空。

​ 询问有多少组 $[l, r]$，使得从 $l$ 采摘到 $r$，蘑菇数量不为 $0$。

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;

int n, X, a[N], cnt[N], dp[N];

int main() {
    cin >> n >> X;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    int l = 1, r = 0, sum = 0;
    while (l <= n) {
        while ( ① ) 
            ②;
        cnt[l] = r;
        ③;
    }
    sum = 0;
    for (int i = n; i >= 1; i--){
        if (cnt[i] == n + 1) continue;
        dp[i] = ④;
    	sum += dp[i];
    }
    cout << ⑤ << endl;
    return 0;
}

33. ①处应填（ ）。
    {{ select(33) }}

• r <= n && sum <= x
• l <= n && sum > x
• sum <= x
• sum > x

34. ②处应填（ ）。
    {{ select(34) }}

• sum += a[++r]
• sum += a[r++]
• sum -= a[++l]
• sum -= a[l++]

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

• sum -= a[r--]
• sum -= a[--r]
• sum -= a[++l]
• sum -= a[l++]

36. ④处应填（ ）。
    {{ select(36) }}

• dp[cnt[i]] + 1
• dp[cnt[i] + 1] + 1
• dp[cnt[i + 1]] + 1
• dp[cnt[i + 1] + 1] + 1

37. ⑤处应填（ ）。
    {{ select(37) }}

• dp[1]
• n - dp[1]
• n * (n + 1) / 2 - sum
• sum

(2) 题目描述

​ 一个字符串 $s\ (|s| \le 5000)$ 由小写字母组成，有 $q\ (q \le 10^6)$ 组询问，每组询问给你两个数 $l$ 和 $r$。

​ 问：在字符串区间 $[l, r]$ 的字串中包含多少回文串？

#include <bits/stdc++.h>
using namespace std;
const int N = 5005;

char s[N];
int n, f[N][N], dp[N][N];

bool check(int l, int r) {
    if ( ① )
        return f[l][r];
    if (l >= r)
        return f[l][r] = 1;
    if (s[l] ^ s[r])
        return f[l][r] = 0;
    return f[l][r] = ②;
}

int main() {
    memset(f, -1, sizeof(f));
    scanf("%s", s + 1);
    n = strlen(s + 1);
    for (int i = 1; i <= n; ++i) ③;
    for (int l = 2; l <= n; ++l) {
        for (int i = 1; i <= n - l + 1; ++i) {
            int j = i + l - 1;
            dp[i][j] = ④;
            if (check(i, j)) ⑤;
        }
    }
    int T;
    scanf("%d", &T);
    while (T--) {
        int x, y;
        scanf("%d%d", &x, &y);
        printf("%d\n", dp[x][y]);
    }
    return 0;
}

38. ①处应填（ ）。
    {{ select(38) }}

• ~f[l][r]
• !f[l][r]
• r > l
• r - l > 1

39. ②处应填（ ）。
    {{ select(39) }}

• check(l + 1, r - 1)
• check(l + 1, r) + 1
• f[l + 1][r - 1] + 1
• f[l + 1][r] + 1

40. ③处应填（ ）。
    {{ select(40) }}

• dp[i][i] = 1
• dp[i][i + 1] = 1
• dp[i][i + 1] = (s[i] == s[i + 1]) + 2
• dp[i][i + 1] = s[i] == s[i + 1]

41. ④处应填（ ）。
    {{ select(41) }}

• dp[i + 1][j] + dp[i][j - 1] + dp[i + 1][j - 1]
• dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1]
• dp[i + 1][j] + dp[i][j - 1] + (s[i] == s[j])
• dp[i + 1][j] + dp[i][j - 1] - (s[i] == s[j])

42. ⑤处应填（ ）。
    {{ select(42) }}

• dp[i][j] ++
• dp[i][j] += dp[i + 1][j - 1]
• dp[i][j] --
• dp[i][j] -= dp[i + 1][j - 1]