CSP-J 2025初赛模拟卷 9

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

第 1 题 两个十六进制数 $(1ACF)_{16}$ 和 $(0456)_{16}$ 做加法的结果是（ ）。
{{ select(1) }}

• $(1F25)_{16}$
• $(7975)_{10}$
• $(17455)_{8}$
• $(1111100100111)_2$

第 2 题 一个 $64$ 位无符号长整型变量占用（ ）字节。
{{ select(2) }}

• 32
• 4
• 16
• 8

第 3 题 下列选项中，( )判断字符串 s1 是否为回文串，如果是就输出 "yes"，否则输出 "no"。

int main() {
    string s1, s2;
    cin >> s1;
    s2 = s1;
    ________________________
    if (s1 == s2) 
      cout << "yes";
    else 
       cout << "no";
    return 0;
}

{{ select(3) }}

• reverse(s1.begin(), s1.end());
• reverse(s1[0], s1[s1.size()]);
• s1.reverse(begin(), end());
• reverse(s1, s1 + s1.size());

第 4 题 已知 x、y、z 都是 int 类型的整数，x = 1、y = 1、z = 3。那么执行 bool ans = x++ || --y && ++z 后，x、y、z 和 ans 的值各为多少？（ ）
{{ select(4) }}

• x = 2, y = 0, z = 4, ans = 1
• x = 2, y = 1, z = 3, ans = 1
• x = 2, y = 1, z = 3, ans = 0
• x = 2, y = 0, z = 4, ans = 0

第 5 题 指针 p 指向变量 a，q 指向变量 c。能够把 c 插入到 a 和 b 之间并形成新链表的语句组是（ ）。

{{ select(5) }}

• p.next = q; q.next = p.next;
• p->next = &c; q->next = p->next;
• (*p).next = q; (*q).next = &b;
• a.next = c; c.next = b;

第 6 题 以下哪个特性是数组和链表共有的？（ ）
{{ select(6) }}

• 动态分配
• 元素之间的次序关系
• 通过索引访问
• 存储连续

第 7 题 下面关于哈夫曼树的描述中，正确的是（ ）。
{{ select(7) }}

• 哈夫曼树一定是完全二叉树
• 哈夫曼树一定是平衡二叉树
• 哈夫曼树中权值最小的两个结点互为兄弟结点
• 哈夫曼树中左子结点小于父结点，右子结点大于父结点

第 8 题 已知一棵二叉树有 $2025$ 个结点，则其中至多有（ ）个结点有 $2$ 个子结点。
{{ select(8) }}

• $1010$
• $1011$
• $1012$
• $1013$

第 9 题 下面的说法中正确的是（ ）。
{{ select(9) }}

• 计算机网络按照拓扑结构分为星型、环型、总线型等
• 互联网的基础是 $OSI$ 七层协议而不是 $TCP/IP$ 协议族
• 现代计算机网络主要采用电路交换技术
• 10.10.1.1 是 $D$ 类 $IP$ 地址

第 10 题 下面关于图的说法中正确的是（ ）。
{{ select(10) }}

• 所有点数为奇数的连通图，一定可以一笔画成
• 所有只有两个奇度点（其余均为偶度点）的连通图，一定可以一笔画成
• 哈密顿图一定是欧拉图，而欧拉图未必是哈密顿图
• 哈密顿图不一定是欧拉图，而欧拉图一定是哈密顿图

第 11 题 （ ）是一种选优搜索法，按选优条件向前搜索以达到目标。当搜索到某一步时，如果发现原先的选择并不优或者达不到目标，就后退一步重新选择。
{{ select(11) }}

• 二分算法
• 动态规划
• 回溯法
• 贪心算法

第 12 题 动态规划是将一个问题分解为一系列子问题后来求解，下面（ ）属于动态规划问题。
{{ select(12) }}

• 多重背包
• 排队打水
• 有序数组找数
• 全排列

第 13 题 设无向图 $G$ 的邻接矩阵如下图所示，则 $G$ 的顶点数和边数分别为（ ）。

$$\begin{bmatrix} 0\ \ 1\ \ 1\ \ 0\ \ 0\\ 1\ \ 0\ \ 0\ \ 1\ \ 1\\ 1\ \ 0\ \ 0\ \ 0\ \ 0\\ 0\ \ 1\ \ 0\ \ 0\ \ 1\\ 0\ \ 1\ \ 0\ \ 1\ \ 0\\ \end{bmatrix} $$

{{ select(13) }}

• 4, 5
• 5, 8
• 4, 10
• 5, 5

第 14 题 某条道路从东到西有 $8$ 个路灯，巡查员为了维护方便，在每根灯杆上都安装了开关，第 $t$ 个开关能够切换前 $t$ 个灯的状态（$t=1\sim 8$,开或关），一开始灯全是开的。巡查员通过控制开关一共能得到（ ）种不同灯的开或者关的组合状态。
{{ select(14) }}

• 128
• 256
• 127
• 255

第 15 题 某四位正整数 $abcd$ 满足如下条件($a,n$也是正整数, $b, c, d$ 是非负整数)：$abcd=1^3+2^3+...+n^3,abcd=(1+2+3+...+n)^2,abcd=(ab+cd)^2$，这样的正整数 $abcd$ 共有（ ）个。
{{ select(15) }}

• 0
• 1
• 2
• 3

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

(1)

1 #include <bits/stdc++.h>
2 using namespace std;
3 const int N = 100 + 5;
4 int n, c, x, y, len, l[N], r[N], cha[N];
5 char a[N];
6 int main() {
7    scanf("%d%d%s", &n, &c, a + 1);
8    len = n;
9    for (int i = 1; i <= c; i++) {
10        scanf("%d%d", &l[i], &r[i]);
11        cha[i] = len - l[i] + 1;
12        len += r[i] - l[i] + 1;
13    }
14    scanf("%d", &x);
15    for (int i = c; i; i--) 
16        if (x >= l[i] + cha[i] && x <= r[i] + cha[i])
17            x -= cha[i];
18    printf("%c\n", a[x]);
19    return 0;
20 }

输入保证 $1\le l_i\le r_i\le n\le 100,1\le c\le 100$。回答以下问题。

判断题
16. 第 17 行最多会运行一次。（ ）
{{ select(16) }}

• 对
• 错

17. (2分) 当程序运行至第 19 行时，x 一定在 [1, n] 范围内。（ ）
    {{ select(17) }}

• 对
• 错

18. 若将第 3 行改成 const int N = 100;，一定不会出现数组越界问题。（ ）
    {{ select(18) }}

• 对
• 错

选择题
19. 若输入 4 2 mark 1 4 5 7 10，则输出为（ ）。
{{ select(19) }}

• m
• a
• r
• k

20. (4分) 若输入 7 3 creamii 2 3 3 4 2 9 11，则输出为（ ）。
    {{ select(20) }}

• m
• e
• a
• i

(2)

1 #include <bits/stdc++.h>
2 using namespace std;
3 const int N = 2e5 + 5;
4 int n, ans, a[N], cnt[20];
5 int main() {
6    scanf("%d", &n);
7    for (int i = 1; i <= n; ++i) {
8        scanf("%d", &a[i]);
9        for (int j = 0; j <= 14; ++j) {
10            cnt[j] += a[i] % 2;
11            a[i] /= 2;
12        }
13    }
14    for (int i = 1; i <= n; ++i) {
15        int sum = 0, x = 1;
16        for (int j = 0; j <= 14; ++j) {
17            if (cnt[j])
18                sum += x , --cnt[j];
19            x *= 2;
20        }
21        ans += sum * sum;
22    }
23    return printf("%d\n", ans), 0;
24 }

已知 $1\le n,a\lt 2^{15}$, 完成下列各题

判断题
21. 第 10 行可以写成 cnt[j] += a[i] % 2。（ ） {{ select(21) }}

• 对
• 错

22. 第 21 行一定不会溢出 int 上界。（ ）
    {{ select(22) }}

• 对
• 错

23. 若输入为 $1\ \ a_1$，则输出为 ${a_1}^2$。（ ）
    {{ select(23) }}

• 对
• 错

24. 若输入为 3 1 3 5，则输出为 51。（ ） {{ select(24) }}

• 对
• 错

选择题
25. 该程序的时间复杂度为（ ）。
{{ select(25) }}

• O$(n)$
• O$(n log n)$
• O$(n^2)$
• O$(n log^2 n)$

26. 若输入为 2 123 69，则程序运行至第 13 行时，cnt 数组的和为（ ）。
    {{ select(26) }}

• 6
• 7
• 9
• 10

(3)

1 #include <bits/stdc++.h>
2 using namespace std;
3 const int N = 10005, M = 15;
4 char c[N];
5 int d, num[N], dp[N][M][2];
6 int dfs(int pos, int res, int sta) {
7    if (pos == 0)
8        return res == 0;
9    if (dp[pos][res][sta] != -1)
10        return dp[pos][res][sta];
11    int ret = 0, maxx = 9;
12    if (sta) maxx = num[pos];
13    for (int i = 0; i <= maxx; i++)
14        ret += dfs(pos - 1, (res + i) % d, sta && (i == maxx));
15    dp[pos][res][sta] = ret;
16    return ret;
17 }
18 int main() {
19    scanf("%s%d", c + 1, &d);
20    memset(dp, -1, sizeof(dp));
21    for (int i = 1; i <= strlen(c + 1); i++)
22        num[i] = c[strlen(c + 1) - i + 1] - '0';
23    printf("%d\n", dfs(strlen(c + 1), 0, 1) - 1);
24    return 0;
25 }

已知 $1\le d\lt 10,1\le |c| \le 10000$,完成下列各题

判断题
27. 将程序中的第 2 行去除，程序依然能正常运行。（ ） {{ select(27) }}

• 对
• 错

28. 该程序的时间复杂度为 O($|c|^2$)。（ ）
    {{ select(28) }}

• 对
• 错

选择题
29. 若将程序中的第 15 行去除，则程序的时间复杂度为（ ）。
{{ select(29) }}

• O($10^{|c|}$)
• O($100d * |c|$)
• O($10d|c|$)
• O($10^{d|c|}$)

30. 若输入为 9 2，则输出为（ ）。
    {{ select(30) }}

• 1
• 2
• 4
• 7

31. 若输入为 30 4，则输出为（ ）。
    {{ select(31) }}

• 3
• 4
• 6
• 7

32. (4分) 若输入为 2025 6，则输出为（ ）。
    {{ select(32) }}

• 240
• 256
• 280
• 338

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

(1) 题目描述

有一个长度为 $n$ 的数组 $a$，满足 $a[i]$ 只能是 $0、1$ 或 $2$，一开始所有元素均为蓝色。可以执行如下操作：

• (i) 用一枚硬币，把一个蓝色元素涂成红色；
• (ii) 选择一个不等于 $0$ 的红色元素和一个与其相邻的蓝色元素，将所选的红色元素减少 $1$，并将所选的蓝色元素涂成红色。

求要将所有元素涂红，最少需要多少枚硬币？

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n, pre[N], a[N], dp[N][3];
int main() {
    scanf("%d", &n);
    memset(dp, 0x3f, sizeof(dp));
    dp[0][0] = dp[0][1] = dp[0][2] = 0;
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    ①
    for (int i = 1; i <= n; i++)
        pre[i] = ②
    for (int i = 2, j; i <= n; i++) {
        dp[i][a[i]] = min({③});
        if (④)
            dp[i][a[i] - 1] = 1 + min({⑤});
    }
    printf("%d", min({dp[n][0], dp[n][1], dp[n][2]}));
    return 0;
}

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

• dp[1][a[1] == 2] = 1
• dp[1][a[1] == 1] = 1
• dp[1][a[1] == 0] = 1
• dp[1][a[1]] = 1

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

• a[i] ? pre[i - 1] : i
• a[i] ? i : pre[i - 1]
• a[i] == 2 ? pre[i - 1] : i
• a[i] == 2 ? i : pre[i - 1]

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

• dp[i - 1][0] + 1, dp[i - 1][1], dp[i - 1][2]
• dp[i - 1][0] + 2, dp[i - 1][1] + 1, dp[i - 1][2]
• dp[i - 1][0] + 2, dp[i - 1][1], dp[i - 1][2]
• dp[i - 1][0], dp[i - 1][1], dp[i - 1][2]

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

• a[i]
• a[i] == 2
• a[i] == 1
• a[i - 1]

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

• dp[pre[i] - 1][0] + 1, dp[pre[i] - 1][1], dp[pre[i] - 1][2]
• dp[pre[i] - 1][0] + 2, dp[pre[i] - 1][1] + 1, dp[pre[i] - 1][2]
• dp[pre[i] - 1][0] + 2, dp[pre[i] - 1][1], dp[pre[i] - 1][2]
• dp[pre[i] - 1][0], dp[pre[i] - 1][1], dp[pre[i] - 1][2]

(2) 题目描述

给你一个长度为 $n\ (n\le 300000)$ 的整数数组 $a$。你可以执行以下操作：选择数组中的一个元素，并用其邻近元素的值替换它。 计算在执行上述操作最多 $k\ (k\le 10)$ 次的情况下，数组的总和可能达到的最小值。

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5;
int n, k, a[N], p[N][11], ans[N][11];
int main() {
	scanf("%d%d", &n, &k);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
		①;
	}
	for (int j = 1; j <= k; j++)
		for (int i = 1; i + j <= n; i++)
			p[i][j] = min(p[i][j - 1], a[i + j]);
	for (int j = 1; j <= k; j++)
		for (int i = 1; i + j <= n; i++)
			②;
	for (int i = 1; i <= n; i++){
		ans[i][0] = ③
		for (int j = 1; j <= k; j++) {
				ans[i][j] = min(ans[i - 1][j] + a[i], ans[i][j - 1]);
			for (int h = 0; ④ ; h++)
				ans[i][j] = min(ans[i][j], ⑤);
		}
	}
	printf("%d\n", ans[n][k]);
	return 0;
}

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

• p[i][0] = i
• p[i][0] = a[i]
• p[i][i] = i
• p[i][i] = a[i]

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

• p[i][j] *= j
• p[i][j] *= (j + 1)
• p[i][j] *= i
• p[i][j] *= (i + 1)

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

• ans[i - 1][0] + a[i]
• ans[i - k][0] + p[i - k + 1][k]
• ans[i - 1][0] + a[i] * i
• ans[i - k][0] + p[i - k + 1][k] * k

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

• h <= i && h <= j
• h < i && h <= j
• h < i && h < j
• h <= i && h < j

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

• ans[i - h - 1][j - h] + p[i - h][h]
• ans[i - h][j - h] + p[i - h][h]
• ans[i][j - h] + p[i][h]
• ans[i][j - h] + p[i - h][h]