A. CSP-J初赛模拟卷25-8

A
    客观题

CSP-J初赛模拟卷25-8

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

普及组 CSP-J 2025 初赛模拟卷 8

一、单项选择题

  1. 在计算机的内存储器中，每个存储单元都被赋予一个唯一的序号，称为（ ）。 {{ select(1) }}
  • 下标
  • 地址
  • 指针
  • 索引
  1. 以下关于算法的描述中正确的是（ ）。 {{ select(2) }}
  • 算法一定要用某种计算机语言写成程序才有价值
  • 要想实现算法，必须先画流程图
  • 算法只需要用到数学的计算方法
  • 算法是为解决问题而采取的方法与步骤
  1. 一张分辨率为 \(800 \times 600\) 的 BMI 图片，若每个像素用 24 位表示，那么这张图片所占用的存储空间是（ ）。 {{ select(3) }}
  • 1400KB
  • 750KB
  • 600KB
  • 1000KB
  1. 若某算法的计算时间表示为递推关系式：\(T(N)=2T(N/2)+2N, T(1)=1\)，则其时间复杂度为（ ）。 {{ select(4) }}
  • \(O(\log n)\)
  • \(O(n^2\log n)\)
  • \(O(n^2)\)
  • \(O(n\log n)\)
  1. 下列哪个特性不是数组和链表都可以实现的？（ ） {{ select(5) }}
  • 数据元素之间的次序关系
  • 数据元素的动态添加和删除
  • 通过索引直接访问任意位置的数据元素
  • 数据可以为任意类型
  1. 如果 a = 2，那么经过运算 a = \(\sim\)-a+2，最后 a 的值为（ ）。 {{ select(6) }}
  • 3
  • 1
  • 0
  • 4
  1. 用一个小为 7 的数组来实现循环队列，且 tail 和 head 的值分别为 0 和 4。当从队列中删除 2 个元素，再加入 3 个元素后，tail 和 head 的值分别为（ ）和（ ）。 {{ select(7) }}
  • 6 3
  • 2 0
  • 3 6
  • 0 2
  1. 关于二分算法，下列说法中错误的是（ ）。 {{ select(8) }}
  • 二分算法可以用于二分查找、二分答案等不同应用
  • n 个数的随机序列先排序再进行二分查找，总时间复杂度是 \(O(\log n)\)
  • 二分算法的左右区间可以左闭右闭，也可以左闭右开
  • 二分算法是典型的使用分治思想的算法
  1. 如下代码主要表示什么数据结构？（ ）
typedef int LTDataType;
typedef struct ListNode
{
    struct ListNode* next;
    LTDataType data;
} LTNode;

{{ select(9) }}

  • 单向链表
  • 双向链表
  • 循环链表
  • 优先队列
  1. 关于字符串和字符串函数，以下说法中错误的是（ ）。 {{ select(10) }}
  • s = "ccfgesp"占用 8 字节内存空间
  • 在字典序下，字符串 s1="123"比字符串 s2="99"要小
  • s.substr(2,4)表示截取字符串 s[2]-s[4]这一段的字符
  • cstring 标准库包含了 strcpy、strlen 等函数
  1. 在计算机历史上，科学家冯·诺依曼的主要贡献是（ ）。 {{ select(11) }}
  • 发明了第一台计算机 ENIAC
  • 破解了德军的 ENIGMA 密码
  • 发明了二进制并应用到电子计算机中
  • 提出存储程序的思想
  1. 如下代码对树的操作是（ ）。
void order(tree bt)
{
    if(bt)
    {
        cout << bt->value;
        order(bt->lchild);
        order(bt->rchild);
    }
}

{{ select(12) }}

  • 前序遍历
  • 中序遍历
  • 后序遍历
  • 层次遍历
  1. 给一排 10 个同样的玩偶的头发分别染红色和绿色，要求任意两个绿色头发的玩偶不能相邻，不同的染色方案共有（ ）种。 {{ select(13) }}
  • 136
  • 140
  • 144
  • 150
  1. 一棵完全二叉树共有 2026 个结点，则该树中共有（ ）个叶子结点。 {{ select(14) }}
  • 1014
  • 1013
  • 1012
  • 1011
  1. 无向图 G 中有 2025 个度为 1 的结点，2 个度为 2 的结点，3 个度为 3 的结点，4 个度为 4 的结点，则无向图 G 有（ ）条边。 {{ select(15) }}
  • 1025
  • 1026
  • 1027
  • 1028

二、阅读程序

(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
14     for (int i = 1; i < N; ++i) {
15         sum[i] = sum[i - 1];
16         if (is_prime[i]) sum[i] += i;
17     }
18     scanf("%d %d", &x, &y);
19     if(x > y) swap(x, y);
20     printf("%d\n", sum[y] - sum[x - 1]);
21     return 0;
22 }

■ 判断题

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

■ 选择题

  1. 若输入 91 95，则输出为 ( )。 {{ select(19) }}
  • 0
  • 184
  • 91
  • 188
  1. (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(1, r));
19     return 0;
20 }

已知 \(1 \leq r \leq 10^9\)，回答以下问题。

■ 判断题

  1. 第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. 若输入为10 20，则输出为7。 （ ） {{ select(24) }}
  • √
  • ×

■ 选择题

  1. 该程序的时间复杂度为（ ）。 {{ select(25) }}
  • \(O(n)\)
  • \(O(\log n)\)
  • \(O(\log^2 n)\)
  • \(O(1)\)
  1. 若输入为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 ≤ 5000，n 为奇数，a 是长度为 n 的排列。完成下列各题。

■ 判断题

  1. 若 pre 数组的最大值为 \(\frac{n-1}{2}\)，则输出为 1 1。（ ） {{ select(27) }}
  • √
  • ×
  1. 第 29 行中的 C[ans1 + ans2][ans1] 可以改成 C[ans1 + ans2][ans2]。（ ） {{ select(28) }}
  • √
  • ×

■ 选择题

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

三、完善程序

(1) 题目描述：

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

  • 若原子只出现了一次，则直接用大写字母表示，如 H 代表氢元素，原子质量为 1。
  • 若化学式为两个字母，则首字母大写，第二个字母小写，如 Mg 代表镁元素，原子质量为 24。
  • 若原子出现了多次，则用元素（数量）代表有几个这种元素的原子，如 C_2 (2) 代表有两个碳原子；H_2 (2)ClO_4 (4) 则表示 H 元素出现了 2 次，Cl 元素出现了 1 次，O 元素出现了 4 次。相对分子质量为 \(1 \times 2 + 35.5 + 16 \times 4 = 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] == 'j') 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("%.01f", ans);
44     else printf("%.11f", ans);
45     return 0;
46 }
  1. ①处应填（ ）。 {{ select(33) }}
  • (s[x] == 'C') ? 10 : 12
  • (s[x] == 'A') ? 12 : 10
  • 10 + 2 * (s[x] == 'C')
  • 10 + 2 * (s[x] == 'A')
  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]!='1'
  • !(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 的子序列（可以不连续）的和。例如数列 [1, 2, 3]，当 m = 4 时，子序列 [2, 3] 和 [1, 2, 3] 满足条件，这时此数列的权值为 11。

现在给定整数 n，m 以及一个长度为 n 的数列 A，请求出 A 的所有前缀数列 A_{i-1} 的权值。由于答案很大，输出对 10^7 取模。

01 #include <bits/stdc++.h>
02 using namespace std;
03 const int N = 165 + 5;
04 const int mod = 169 + 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 }
  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]

CSP-J初赛模拟卷25-8

未参加
状态
已结束
规则
IOI(严格)
题目
1
开始于
2025-9-12 0:00
结束于
2025-10-2 20:00
持续时间
2 小时
主持人
参赛人数
0
  1. Language
  2. 兼容模式
  3. 主题
  3. Worker 0, 138ms
  4. Powered by Hydro v5.0.0-beta.9 Community