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 \log n))
- (O(n))
- (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]到s[4]这一段的字符cstring标准库包含了strcpy、strlen等函数
第 11 题 在计算机历史上，科学家冯·诺依曼的主要贡献是（ ）。
{{ select(11) }}
- 发明了第一台计算机 ENIAC
- 破解了德军的 ENIGMA 密码
- 发明了二进制并应用到电子计算机中
- 提出存储程序的思想
第 12 题 如下代码对树的操作是（ ）。
void order(tree bt) {
if (bt) {
cout 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
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 y) swap(x, y);
19 printf("%d\n", sum[y] - sum[x - 1]);
20 return 0;
21 }
判断题
16. 当输入为 15 时，输出为 10。
{{ select(16) }}
- √
- ×
- 若去除第 2 行，程序仍能正常运行。
{{ select(17) }}
- √
- ×
- （2 分）在运行第 15 行时，可能溢出
int上界。
{{ select(18) }}
- √
- ×
选择题
19. 若输入 9 和 195，则输出为（ ）。
{{ select(19) }}
- 0
- 184
- 91
- 188
- （4 分）该程序的时间复杂度为（ ）。
{{ select(20) }}
- (O(n))
- (O(n \log \log n))
- (O(n \log n))
- (O(n^2))
(2)
01 #include
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
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 + 1) / 2) ? 1 : -1;
16 }
17 for (int i = 1; i j + 1; --i)
20 suf[i] = suf[i + 1] + a[i];
21 mi = 0;
22 for (int i = 1; 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) }}
- 对
- 错
- 第 29 行中的
C[ans1 + ans2][ans1]可以改成C[ans1 + ans2][ans2]。
{{ select(28) }}
- 对
- 错
选择题
29. 若 (n = 9)，则输出的第一个数的最大值为（ ）。
{{ select(29) }}
- 3
- 4
- 5
- 6
- 若输入为 71624573，则输出为（ ）。
{{ select(30) }}
- 32
- 23
- 33
- 22
- 若输入为 73541726，则输出为（ ）。
{{ select(31) }}
- 32
- 23
- 33
- 22
- （4 分）若 (n = 13)，则输出的第二个数的最大值为（ ）。
{{ select(32) }}
- 6
- 10
- 20
- 36
三、完善程序（单选题，每小题 3 分，共计 30 分）
(1)
题目描述：给定一个长度不超过 (10^5) 的化学式，计算其分子质量。化学式可能由大写字母表示单个原子，或由大写字母加小写字母表示双原子，或由元素后跟数字表示多个原子。
01 #include
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 = 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 }
- ① 处应填（ ）。
{{ select(33) }}
(s[x] == 'c') ? 10 : 12(s[x] == 'l') ? 12 : 1010 + 2 * (s[x] == 'c')10 + 2 * (s[x] == 'l')
- ② 处应填（ ）。
{{ select(34) }}
ans + (int)(s[i])ans + 10 + (int)(s[i])ans + s[i] - '0'ans * 10 + s[i] - '0'
- ③ 处应填（ ）。
{{ select(35) }}
read(i + 3)read(j + 1)read(j + 2)read(i + 2)
- ④ 处应填（ ）。
{{ select(36) }}
s[i] != ')'- `s[i] >= 'A' && s[i] = '0' && s[i] 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 }
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]`