#9650. CSP-J2025 初赛模拟卷8

CSP-J2025 初赛模拟卷8

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(n/2) + 2n)，(T(1) = 1)，则其时间复杂度为（ ）。
{{ select(4) }}

  • (O(log n))
  • (O(n*n log n))
  • (O(n))
  • (O(n log n))

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

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

第 6 题 如果 (a = 2)，那么经过运算 (a = ~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] 到 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. 当输入为 15 时，输出为 10。
{{ select(16) }}

  • √
  • ×
  1. 若去除第 2 行，程序仍能正常运行。
    {{ select(17) }}
  • √
  • ×
  1. （2 分）在运行第 15 行时，可能溢出 int 上界。
    {{ select(18) }}
  • √
  • ×

选择题
19. 若输入 9 和 195，则输出为（ ）。
{{ select(19) }}

  • 0
  • 184
  • 91
  • 188
  1. （4 分）该程序的时间复杂度为（ ）。
    {{ select(20) }}
  • (O(n))
  • (O(n \log \log n))
  • (O(n \log n))
  • (O(n^2))

(2)

01 #include <bits/stdc++.h>
02 using namespace std;
03 int i, 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(l, 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 }

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

  • 对
  • 错
  1. 在运行第 12 行时，(x) 可能会溢出 int 的上界。
    {{ select(22) }}
  • 对
  • 错
  1. (l = 1), (r = 29); (l = 1), (r = 30); (l = 1), (r = 31) 这三种情况的输出均一样。
    {{ select(23) }}
  • 对
  • 错
  1. 若输入为 1020，则输出为 7。
    {{ select(24) }}
  • 对
  • 错

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

  • (O(n))
  • (O(\log n))
  • (O(\log^2 n))
  • (O(1))
  1. 若输入为 12007，则输出为（ ）。
    {{ 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 - j - 1][j]) % 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 }

判断题
27. 若输入为 71624573，则输出为 11。
{{ select(27) }}

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

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

  • 3
  • 4
  • 5
  • 6
  1. 若输入为 71624573，则输出为（ ）。
    {{ select(30) }}
  • 32
  • 23
  • 33
  • 22
  1. 若输入为 73541726，则输出为（ ）。
    {{ select(31) }}
  • 32
  • 23
  • 33
  • 22
  1. （4 分）若 (n = 13)，则输出的第二个数的最大值为（ ）。
    {{ select(32) }}
  • 6
  • 10
  • 20
  • 36

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

(1)
题目描述：给定一个长度不超过 (10^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['N'] = 8, to['M'] = 9, to['A'] = 10, to['L'] = 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 (s[++i] != ')');
37             continue;
38         }
39         ans += val[x];
40         i += (x >= 8);
41         continue;
42     }
43     if (④) printf("%.0f", ans);
44     else printf("%.1lf", ans);
45     return 0;
46 }
  1. ① 处应填（ ）。
    {{ select(33) }}
  • (s[x] == 'c') ? 10 : 12
  • (s[x] == 'l') ? 12 : 10
  • 10 + 2 * (s[x] == 'c')
  • 10 + 2 * (s[x] == 'l')
  1. ② 处应填（ ）。
    {{ select(34) }}
  • ans + (int)(s[i])
  • ans + 10 + (int)(s[i])
  • ans + s[i] - '0'
  • ans * 10 + s[i] - '0'
  1. ③ 处应填（ ）。
    {{ select(35) }}
  • read(i + 3)
  • read(j + 1)
  • read(j + 2)
  • read(i + 2)
  1. ④ 处应填（ ）。
    {{ select(36) }}
  • s[i] != ')'
  • s[i] >= 'A' && s[i] <= 'z'
  • s[i] >= '0' && s[i] <= '9'
  • i <= j
  1. ⑤ 处应填（ ）。
    {{ select(37) }}
  • ceil(ans + 0.5) == ans
  • ceil(ans) == ans
  • (int)(ans) / 2 == ans / 2
  • int(ans + 0.5) == ans

(2)
题目描述：给定整数 (m)，定义一个数列的权值为这个数列所有乘积大于或等于 (m) 的子序列（可以不连续）的和。现在给定整数 (n)，(m) 以及一个长度为 (n) 的数列 (A)，请求出 (A) 的所有前缀数列 (A_1, A_2, \ldots, A_n) 的权值。由于答案很大，输出对 (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 = 0;
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 }
  1. ① 处应填（ ）。
    {{ 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)
  1. ② 处应填（ ）。
    {{ select(39) }}
  • 1
  • a[x]
  • sum
  • a[x] * pw[i - 1]
  1. ③ 处应填（ ）。
    {{ 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
  1. ④ 处应填（ ）。
    {{ 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]
  1. ⑤ 处应填（ ）。
    {{ select(42) }}
  • sum * 2 + pw[i] * a[x]
  • sum + a[x]
  • sum * 2 + pw[i - 1] * a[x]
  • (sum + a[x]) * pw[i]
  1. 评测队列
  2. 服务状态
  3. 兼容模式
  4. 主题
  2. 陕ICP备2025061476号
  3. Worker 0, 59ms
  4. Powered Dong Dong