2025 CSP-J初赛模拟卷 8

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

第 1 题 在计算机的内存储器中，每个存储单元都被赋予一个唯一的序号，称为（ ）。
{{ select(1) }}

• 下标
• 地址
• 指针
• 索引

第 2 题 以下关于算法的描述中正确的是（ ）。
{{ select(2) }}

• 算法一定要用某种计算机语言写成程序才有价值
• 要想实现算法，必须先画流程图
• 算法只需要用到数学的计算方法
• 算法是为解决问题而采取的方法与步骤

第 3 题 一张分辨率为 $800×600$ 的 $BMP$ 图片，若每个像素用 $24$ 位表示，那么这张图片所占用的存储空间是（ ）。
{{ select(3) }}

• $1400KB$
• $750KB$
• $600KB$
• $1000KB$

第 4 题 若某算法的计算时间表示为递推关系式：$T(N)=2T(\frac{N}{2})+2N，T(1)=1$，则其时间复杂度为（ ）。
{{ select(4) }}

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

第 5 题 下列哪个特性不是数组和链表都可以实现的？（ ）
{{ select(5) }}

• 数据元素之间的次序关系
• 数据元素的动态添加和删除
• 通过索引直接访问任意位置的数据元素
• 数据可以为任意类型

第 6 题 如果 $a = 2$，那么经过运算 $a = \sim -a + 2$，最后 $a$ 的值为（ ）。
{{ select(6) }}

• 3
• 1
• 0
• 4

第 7 题 用一个大小为 $7$ 的数组来实现循环队列，且 tail 和 head 的值分别为 $0$ 和 $4$。当从队列中删除 $2$ 个元素，再加入 $3$ 个元素后，tail 和 head 的值分别为（ ）和（ ）。
{{ select(7) }}

• 6 3
• 2 0
• 3 6
• 0 2

第 8 题 关于二分算法，下列说法中错误的是（ ）。
{{ select(8) }}

• 二分算法可以用于二分查找、二分答案等不同应用
• $n$ 个数的随机序列先排序再进行二分查找，总时间复杂度是 $O(log n)$
• 二分算法的左右区间可以左闭右闭，也可以左闭右开
• 二分算法是典型的使用分治思想的算法

第 9 题 如下代码主要表示什么数据结构？（ ）

typedef int LTDataType;
typedef struct ListNode {
    struct ListNode* next;
    LTDataType data;
} LTNode;

{{ select(9) }}

• 单向链表
• 双向链表
• 循环链表
• 优先队列

第 10 题 关于字符串和字符串函数，以下说法中错误的是（ ）。
{{ select(10) }}

• s = "ccfgesp" 占用 8 字节内存空间
• 在字典序下，字符串 s1 = "123" 比字符串 s2 = "99" 要小
• s.substr(2, 4) 表示截取字符串 s[2] $\sim$ s[4] 这一段的字符
• cstring 标准库包含了 strcpy、strlen 等函数

第 11 题 在计算机历史上，科学家冯·诺依曼的主要贡献是（ ）。
{{ select(11) }}

• 发明了第一台计算机 $ENIAC$
• 破解了德军的 $ENIGMA$ 密码
• 发明了二进制并应用到电子计算机中
• 提出存储程序的思想

第 12 题 如下代码对树的操作是（ ）。

void order(tree bt) {
    if (bt) {
        cout << bt->value;
        order(bt->lchild);
        order(bt->rchild);
    }
}

{{ select(12) }}

• 前序遍历
• 中序遍历
• 后序遍历
• 层次遍历

第 13 题 给一排 $10$ 个同样的玩偶的头发分别染红色和绿色，要求任意两个绿色头发的玩偶不能相邻，不同的染色方案共有（ ）种。
{{ select(13) }}

• $136$
• $140$
• $144$
• $150$

第 14 题 一棵完全二叉树共有 $2026$ 个结点，则该树中共有（ ）个叶子结点。
{{ select(14) }}

• $1014$
• $1013$
• $1012$
• $1011$

第 15 题 无向图 $G$ 中有 $2025$ 个度为 $1$ 的结点，$2$ 个度为 $2$ 的结点，$3$ 个度为 $3$ 的结点，$4$ 个度为 $4$ 的结点，则无向图 $G$ 有（ ）条边。
{{ select(15) }}

• $1025$
• $1026$
• $1027$
• $1028$

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

(1)

01 #include <bits/stdc++.h>
02 using namespace std;
03 const int N = 1e5 + 5;
04 int n, T, x, y, sum[N], is_prime[N];
05 int main() {
06     memset(is_prime, true, sizeof(is_prime));
07     for (int i = 2; i < N; ++i) {
08         if (is_prime[i]) {
09             for (int j = i + i; j < N; j += i)
10                 is_prime[j] = false;
11         }
12     }
13     for (int i = 1; i < N; ++i) {
14         sum[i] = sum[i - 1];
15         if (is_prime[i]) sum[i] += i;
16     }
17     scanf("%d%d", &x, &y);
18     if (x > y) swap(x, y);
19     printf("%d\n", sum[y] - sum[x - 1]);
20     return 0;
21 }

判断题

16. 当输入为 1 5 时，输出为 10。
    {{ select(16) }}

• √
• ×

17. 若去除第 $2$ 行，程序仍能正常运行。
    {{ select(17) }}

• √
• ×

18. （2 分）在运行第 15 行时，可能溢出 int 上界。
    {{ select(18) }}

• √
• ×

选择题

19. 若输入 91 和 95，则输出为（ ）。
    {{ select(19) }}

• $0$
• $184$
• $91$
• $188$

20. （4 分）该程序的时间复杂度为（ ）。
    {{ select(20) }}

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

(2)

01 #include <bits/stdc++.h>
02 using namespace std;
03 int l, r, x;
04 int restrict(int ql, int qr) {
05     return max(0, qr - max(l, ql) + 1);
06 }
07 int calc(int l, int r) {
08     if (l > r)
09         return 0;
10     x = 1;
11     while (x <= r)
12         x *= 2;
13     x /= 2;
14     return restrict(x, r) + calc(1, 2 * x - r - 1);
15 }
16 int main() {
17     scanf("%d%d", &l, &r);
18     printf("%d\n", calc(l, r));
19     return 0;
20 }

已知 $1\le l\le r\le 10^9$ , 回答以下问题

判断题

21. 第 $14$ 行中的 2 * x - r - 1 一定比 $r$ 小。
    {{ select(21) }}

• 对
• 错

22. 在运行第 $12$ 行时，$x$ 可能会溢出 int 的上界。
    {{ select(22) }}

• 对
• 错

23. $l=1,r=29$ 、 $l=1,r=30$ 、$l=1,r=31$ 这三种情况的输出均一样。
    {{ select(23) }}

• 对
• 错

24. 若输入为 10 20，则输出为 $7$。
    {{ select(24) }}

• 对
• 错

选择题

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

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

26. 若输入为 1 2007，则输出为（ ）。
    {{ select(26) }}

• $1003$
• $1004$
• $1006$
• $1007$

(3)

01 #include <bits/stdc++.h>
02 using namespace std;
03 const int N = 5e3 + 5, mo = 998244353;
04 int n, j, ans1, ans2, mi, mj;
05 int C[N][N], a[N], pre[N], suf[N];
06 signed main() {
07     scanf("%d", &n);
08     C[0][0] = 1;
09     for (int i = 1; i <= n; ++i)
10         for (int j = 0; j <= i; ++j)
11             C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mo;
12     for (int i = 1; i <= n; ++i) {
13         scanf("%d", &a[i]);
14         if (a[i] == (n + 1) / 2) j = i;
15         else a[i] = (a[i] > (n + 1) / 2) ? 1 : -1;
16     }
17     for (int i = 1; i <= j - 1; ++i)
18         pre[i] = pre[i - 1] + a[i];
19     for (int i = n; i >= j + 1; --i)
20         suf[i] = suf[i + 1] + a[i];
21     mi = 0;
22     for (int i = 1; i <= j - 1; ++i)
23         if (!pre[i])
24             ++ans1, mi = i + 1;
25     mj = n;
26     for (int i = n; i >= j + 1; --i)
27         if (!suf[i])
28             ++ans2, mj = i - 1;
29     printf("%d %d\n", ans1 + ans2 + !(mi == mj), C[ans1 + ans2][ans1]);
30     return 0;
31 }

已知 $n\le 5000$ ，$n$ 为奇数，$a$ 是长度为 $n$ 的排列。完成下列各题。

判断题

27. 若 $pre$ 数组的最大值为 $\frac{n-1}{2}$，则输出为 1 1。
    {{ select(27) }}

• 对
• 错

28. 第 $29$ 行中的 C[ans1 + ans2][ans1] 可以改成 C[ans1 + ans2][ans2]。
    {{ select(28) }}

• 对
• 错

选择题

29. 若 $n=9$，则输出的第一个数的最大值为（ ）。
    {{ select(29) }}

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

30. 若输入为 7 1 6 2 4 5 7 3，则输出为（ ）。
    {{ select(30) }}

• 3 2
• 2 3
• 3 3
• 2 2

31. 若输入为 7 3 5 4 1 7 2 6，则输出为（ ）。
    {{ select(31) }}

• 3 2
• 2 3
• 3 3
• 2 2

32. （4 分）若 $n=13$，则输出的第二个数的最大值为（ ）。
    {{ select(32) }}

• $6$
• $10$
• $20$
• $36$

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

(1) 题目描述

​ 给定一个长度不超过 $10^4$ 的化学式，计算其分子质量（分子质量即一个化学式中原子质量之和）。
化学式可能由如下两种构成。

• 若原子只出现一次，则直接用大写字母表示，如 H 代表氢元素，原子质量为 $1$
  若化学式为两个字母，则首字母大写，第二个字母小写，如 Mg 代表镁元素，原子质量为 $24$
• 若原子出现了多次，则用元素_{数量}代表有几个这种元素的原子，如 C_{2} 代表有 $2$ 个碳原子；H_{2}ClO_{4} 则代表 H 元素出现了 $2$ 次，Cl 元素出现了 $1$ 次，O 元素出现了 $4$ 次。相对分子质量为 1x2 + 35.5 + 16x4 = 101.5

编号	1	2	3	4	5	6	7	8	9	10	11	12
元素	H	C	N	O	F	P	S	Na	Mg	Al	Si	Cl
原子质量	$1$	$12$	$14$	$16$	$19$	$31$	$32$	$23$	$24$	$27$	$28$	$35.5$

01 #include <bits/stdc++.h>
02 using namespace std;
03 const int N = 5e5 + 5;
04 const double val[N] = {0, 1, 12, 14, 16, 19, 31, 32, 23, 24, 27, 28, 35.5};
05 int n, to[N];
06 char s[N];
07 double ans;
08 int Hash(int x) {
09     if (to[s[x + 1]] >= 8) {
10         if (s[x + 1] == 'l')
11             return ①;
12         return to[s[x + 1]];
13     }
14     return to[s[x]];
15 }
16 int read(int x) {
17     int ans = 0;
18     for (int i = x; i <= n; i++) {
19         if (s[i] == '}') break;
20         ans = ②;
21     }
22     return ans;
23 }
24 int main() {
25     to['H'] = 1, to['C'] = 2, to['N'] = 3, to['O'] = 4;
26     to['F'] = 5, to['P'] = 6, to['S'] = 7;
27     to['a'] = 8, to['g'] = 9, to['l'] = 10, to['i'] = 11;
28     scanf("%s", s + 1);
29     n = strlen(s + 1);
30     for (int i = 1; i <= n; ++i) {
31         int x = Hash(i);
32         int j = i + 1 + (x >= 8);
33         if (s[j] == '_') {
34             int k = ③;
35             ans += val[x] * k;
36             while ( ④ ) ++i;
37             continue;
38         }
39         ans += val[x];
40         i += (x >= 8);
41         continue;
42     }
43     if ( ⑤ ) printf("%.0lf", ans);
44     else printf("%.1lf", ans);
45     return 0;
46 }

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

• (s[x] == 'C') ? 10 : 12
• (s[x] == 'A') ? 12 : 10
• 10 + 2 * (s[x] == 'C')
• 10 + 2 * (s[x] == 'A')

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

• ans + (int)(s[i])
• ans * 10 + (int)(s[i])
• ans + s[i] - '0'
• ans * 10 + s[i] - '0'

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

• read(i + 3)
• read(j + 1)
• read(j + 2)
• read(i + 2)

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

• s[i] != '}'
• !(s[i] >= 'A' && s[i] <= 'Z')
• !(s[i] >= '0' && s[i] <= '9')
• i <= j

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

• ceil(ans + 0.5) == ans
• ceil(ans) == ans
• (int(ans)) / 2 == ans / 2
• int(ans + 0.5) != ans

(2) 题目描述
给定整数 $m$，定义一个数列的权值为这个数列所有乘积大于或等于 $m$ 的子序列（可以不连续）的和。例如数列 $[1,2,3]$，当 $m=4$ 时，子序列 $[2,3]$ 和 $[1,2,3]$ 满足条件，这时数列的权值为 $11$
现在给定整数 $n, m$ 以及一个长度为 $n$ 的数列 $A$，请求出 $A$ 的所有前缀数列 $A_1, A_2, \ldots, A_i$ 的权值。由于答案很大，输出对 $10^9 + 7$ 取模。

01 #include <bits/stdc++.h>
02 using namespace std;
03 const int N = 1e5 + 5;
04 const int mod = 1e9 + 7;
05 int n, m, sum, K, tot, f[2][1000], g[2][1000];
06 int a[N], r[N], to[N], pw[N] = {1};
07 int main() {
08     scanf("%d%d", &n, &m); --m;
09     for (int i = 1; i <= n; ++i) pw[i] = pw[i - 1] * 2 % mod;
10     for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
11     for (int i = 1; i <= m; ++i) {
12         if (①) ++tot;
13         r[tot] = i, to[i] = tot;
14     }
15     for (int x = 1; x <= n; ++x) {
16         int i = x & 1, k = i ^ 1;
17         for (int j = 1; j <= tot; ++j)
18             f[k][j] = g[k][j] = 0;
19         if (a[x] <= m) {
20             f[i][to[a[x]]] += 1;
21             g[i][to[a[x]]] += ②;
22         }
23         for (int j = 1; j <= tot; ++j) {
24             f[k][j] += f[i][j];
25             g[k][j] += g[i][j];
26             if (a[x + 1] * r[j] <= m) {
27                 int mj = ③;
28                 f[k][mj] += f[i][j];
29                 g[k][mj] += ④;
30             }
31         }
32         sum = ⑤;
33         int rs = 0;
34         for (int j = 1; j <= tot; ++j)
35             rs += g[i][j];
36         printf("%d\n", sum - rs);
37     }
38     return 0;
39 }

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

• i == 1 || m / i != m / (i - 1)
• i == 1 || m / i != m / (i + 1)
• m / i != m % (i - 1)
• m / i != m / (i + 1)

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

• 1
• a[x]
• sum
• a[x] * pw[i - 1]

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

• to[a[x + 1] * r[j]] - 1
• to[a[x] * r[j]]
• to[a[x + 1] * r[j]]
• to[a[x + 1] * r[j]] + 1

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

• g[i][j] + f[i][j] * a[x + 1]
• g[i][j] + f[i][j] * a[x + 1] * pw[i - 1]
• f[i][j] * a[x + 1]
• f[i][j] * a[x + 1] * pw[i - 1]

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

• sum * 2 + pw[i] * a[x]
• sum + a[x]
• sum * 2 + pw[i - 1] * a[x]
• (sum + a[x]) * pw[i]