#75. 普及组CSP-J2025初赛模拟卷8

普及组CSP-J2025初赛模拟卷8

普及组CSP-J2025初赛模拟卷8

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

  1. 在计算机的内存储器中，每个存储单元都被赋予一个唯一的序号，称为（ ）。 {{ select(1) }}
  • 下标
  • 地址
  • 指针
  • 索引
  1. 以下关于算法的描述中正确的是（ ）。 {{ select(2) }}
  • 算法一定要用某种计算机语言写成程序才有价值
  • 要想实现算法，必须先画流程图
  • 算法只需要用到数学的计算方法
  • 算法是为解决问题而采取的方法与步骤
  1. 一张分辨率为800×600的BMP图片，若每个像素用24位表示，那么这张图片所占用的存储空间是（ ）。 {{ select(3) }}
  • 1400KB
  • 750KB
  • 600KB
  • 1000KB
  1. 若某算法的计算时间表示为递推关系式：T(N) = 2T(N/2) + 2N，T(1) = 1，则其时间复杂度为（ ）。 {{ select(4) }}
  • O(logn)
  • O(n^2 * logn)
  • O(n^2)
  • O(nlogn)
  1. 下列哪个特性不是数组和链表都可以实现的？（ ） {{ select(5) }}
  • 数据元素之间的次序关系
  • 数据元素的动态添加和删除
  • 通过索引直接访问任意位置的数据元素
  • 数据可以为任意类型
  1. 如果a = 2，那么经过运算a = ~-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(logn)
  • 二分算法的左右区间可以左闭右闭，也可以左闭右开
  • 二分算法是典型的使用分治思想的算法
  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.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 }

判断题

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

选择题

  1. 若输入91 95，则输出为（ ）。 {{ select(19) }}
  • 0
  • 184
  • 91
  • 188
  1. （4分）该程序的时间复杂度为（ ）。 {{ select(20) }}
  • O(n)
  • O(nloglogn)
  • O(n log^2 n)
  • 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. 第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(logn)
  • 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] > 0)
24             ++ans1, mi = i + 1;
25     mj = n;
26     for (int i = n; i > j + 1; --i)
27         if (suf[i] > 0)
28             ++ans2, mj = i - 1;
29     printf("%d %d\n", ans1 + ans2 + !(mi == mj), C[ans1 + ans2][ans1]);
30     return 0;
31 }

判断题

  1. 若pre数组的最大值为(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

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

(1) 题目描述：

给定一个长度不超过10^4的化学式，计算其分子质量。（分子质量即一个化学式中原子质量之和。）

化学式可能有如下两种构成：

  • 若原子只出现了一次，则直接用大写字母表示，如H代表氢元素，原子质量为1。 若化学式为两个字母，则首字母大写，第二个字母小写，如Mg代表镁元素，原子质量为24。
  • 若原子出现了多次，则用元素_{数量}代表有几个这种元素的原子，如C2C_{2}代表有两个碳原子；H2ClO4H_{2}ClO_{4}则表示H元素出现了2次，Cl元素出现了1次，O元素出现了4次。相对分子质量为1×2 + 35.5 + 16×4 = 101.5。
编号 元素 原子质量
1 H 1
2 C 12
3 N 14
4 F 16
5 P 19
6 S 31
7 Na 32
8 Mg 23
9 Al 24
10 Si 27
11 Cl 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] == '1')
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 }
  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] != '}'
  • !(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的所有前缀数列A1~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 }
  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. About
  2. Contact Us
  3. Privacy
  4. Terms of Service
  5. Copyright Complaint
  6. Language
  7. Legacy mode
  8. Theme
  2. 蜀ICP备2022008388号-1
  3. Worker 0, 213ms
  4. Powered by Hydro v4.19.1 Community