CSP-S 第一轮初赛模拟试卷 · 第 1 套
CSP-S 第一轮（初赛）模拟试卷 · 第 1 套
适用对象： 高一学生（赛前训练） 满分： 100 分 考试时间： 100 分钟 语言： C++
试卷结构：
| 板块 | 题型 | 题量 | 分值 |
|---|---|---|---|
| 一、单项选择题 | 单选 | 15 题 | 每题 2 分，共 30 分 |
| 二、阅读程序 | 判断 + 选择 | 3 题（每题 3 判断 + 3 选择） | 共 40 分 |
| 三、完善程序 | 单选（填空） | 2 题（每题 5 空） | 每题 15 分，共 30 分 |
说明：阅读程序部分，判断题每题 2 分；选择题每题 2 分，其中标注「3 分」的选择题每题 3 分（共 4 题），合计 40 分。
一、单项选择题（共 15 题，每题 2 分，共 30 分。每题有且仅有一个正确选项。）
1. 设 a = (0x2F)₁₆，b = (0x3C)₁₆，则 a ^ b（按位异或）的十进制值为（ ）。
{{ select(1) }}
- 19
- 25
- 27
- 15
2. 在 8 位补码表示中，整数 -57 的机器数为（ ）。
{{ select(2) }}
- 11000111
- 10111001
- 11000110
- 00111001
3. 已知字符 '0' 的 ASCII 码为 48，'A' 的 ASCII 码为 65。C++ 表达式 (char)('D' - 'A' + '0') 的值为（ ）。
{{ select(3) }}
'3''4''D''C'
4. 某 U 盘标称容量 32 GB（按 1 GB = 2^30 B 计算），现要存储大小均为 4 MB（按 1 MB = 2^20 B 计算）的照片，最多可存储（ ）张。
{{ select(4) }}
- 8000
- 8192
- 8388
- 10240
5. 下列程序段的时间复杂度为（ ）。
int s = 0;
for (int i = 1; i <= n; i *= 2)
for (int j = 1; j <= i; ++j)
++s;
{{ select(5) }}
- O(log n)
- O(n)
- O(n log n)
- O(n²)
6. 元素 1、2、3、4 依次入栈（允许边入边出），下列出栈序列中不合法的是（ ）。
{{ select(6) }}
- 1 2 3 4
- 4 3 2 1
- 2 4 3 1
- 3 1 2 4
7. 循环队列用数组 Q[0..5] 存储，队头指针 front 指向队头元素，队尾指针 rear 指向队尾元素的下一个位置。若 front = 2，rear = 5，则当前队列中元素个数为（ ）。
{{ select(7) }}
- 2
- 3
- 4
- 5
8. 在不带头结点的单链表中，指针 p 指向某结点（非尾结点），现要将新结点 q 插入到 p 之后，正确的操作序列是（ ）。
{{ select(8) }}
q->next = p->next; p->next = q;p->next = q; q->next = p->next;q->next = p; p->next = q;p->next = q; q->next = p;
9. 一棵完全二叉树有 2023 个结点，其叶子结点数为（ ）。
{{ select(9) }}
- 1011
- 1012
- 1013
- 1000
10. 无向图 G 有 7 个顶点，若每个顶点的度数均为 4，则 G 的边数为（ ）。
{{ select(10) }}
- 14
- 28
- 7
- 12
11. 下列排序算法中，属于稳定排序的是（ ）。
{{ select(11) }}
- 快速排序
- 堆排序
- 归并排序
- 选择排序
12. 在含 1000 个元素的有序数组中用二分查找某个元素，最坏情况下需要比较的次数为（ ）。
{{ select(12) }}
- 9
- 10
- 11
- 1000
13. 用递归求解 n 阶汉诺塔问题，设最少移动次数为 T(n)，满足 T(1) = 1，T(n) = 2T(n-1) + 1，则 T(5) 的值为（ ）。
{{ select(13) }}
- 15
- 31
- 63
- 32
14. gcd(2024, 748) 的值为（ ）。
{{ select(14) }}
- 4
- 22
- 44
- 88
15. 下列关于计算机系统的叙述，正确的是（ ）。
{{ select(15) }}
- C++ 是编译型语言，程序在运行前一次性翻译为机器码，运行效率较高
- Python 是编译型语言，程序在运行前一次性翻译为机器码
- ROM 是易失性存储器，断电后其中数据会丢失
- 1 个字节（Byte）由 4 个比特（bit）组成
二、阅读程序（共 3 题，40 分。判断题正确填「√」，错误填「×」；选择题每题有且仅有一个正确选项。）
阅读程序（一）
#include <iostream>
#include <string>
using namespace std;
int main() {
int n, b;
cin >> n >> b;
string s = "";
while (n > 0) {
int r = n % b;
if (r < 10) s = char('0' + r) + s;
else s = char('A' + r - 10) + s;
n /= b;
}
if (s == "") s = "0";
cout << s << endl;
return 0;
}
判断题（每题 2 分）
16. 输入 10 2，输出为 1010。（ ）
{{ select(16) }}
- 正确
- 错误
17. 输入 0 8，输出为 0。（ ）
{{ select(17) }}
- 正确
- 错误
18. 输入 255 16，输出为 0xFF。（ ）
{{ select(18) }}
- 正确
- 错误
选择题（每题 2 分）
19. 输入 100 2，输出为（ ）。
{{ select(19) }}
- 1100100
- 110010
- 1000000
- 1010100
20. 输入 31 16，输出为（ ）。
{{ select(20) }}
- 1F
- F1
- 31
- 1E
21. （3 分）输入 64 8，输出为（ ）。
{{ select(21) }}
- 100
- 80
- 64
- 8
阅读程序（二）
#include <iostream>
using namespace std;
int f(int n) {
if (n == 0) return 1;
if (n == 1) return 1;
return f(n - 1) + 2 * f(n - 2);
}
int main() {
int n;
cin >> n;
cout << f(n) << endl;
return 0;
}
判断题（每题 2 分）
22. 输入 5，输出为 21。（ ）
{{ select(22) }}
- 正确
- 错误
23. 输入 3，输出为 7。（ ）
{{ select(23) }}
- 正确
- 错误
24. f(6) 的值为 43。（ ）
{{ select(24) }}
- 正确
- 错误
选择题（每题 2 分）
25. 输入 7，输出为（ ）。
{{ select(25) }}
- 85
- 127
- 43
- 171
26. 输入 10，输出为（ ）。
{{ select(26) }}
- 341
- 683
- 1023
- 511
27. （3 分）该函数的时间复杂度为（ ）。
{{ select(27) }}
- O(n)
- O(n²)
- O(2ⁿ)
- O(log n)
阅读程序（三）
#include <iostream>
#include <cstring>
using namespace std;
int n, m;
int g[105][105];
bool vis[105];
void dfs(int u) {
vis[u] = true;
for (int v = 1; v <= n; v++)
if (g[u][v] && !vis[v]) dfs(v);
}
int main() {
memset(g, 0, sizeof(g));
memset(vis, 0, sizeof(vis));
cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v; cin >> u >> v;
g[u][v] = g[v][u] = 1;
}
int cnt = 0;
for (int i = 1; i <= n; i++)
if (!vis[i]) { dfs(i); cnt++; }
cout << cnt << endl;
return 0;
}
判断题（每题 2 分）
28. 该程序统计的是无向图的连通分量个数。（ ）
{{ select(28) }}
- 正确
- 错误
29. 输入 4 3 及边 1 2、2 3、3 4，输出为 1。（ ）
{{ select(29) }}
- 正确
- 错误
30. 输入 4 2 及边 1 2、3 4，输出为 3。（ ）
{{ select(30) }}
- 正确
- 错误
选择题（每题 2 分）
31. 输入 5 0（无任何边），输出为（ ）。
{{ select(31) }}
- 0
- 1
- 5
- 4
32. （3 分）输入 6 5 及边 1 2、2 3、4 5、5 6、4 6，输出为（ ）。
{{ select(32) }}
- 2
- 3
- 4
- 1
33. （3 分）该程序用邻接矩阵存储图，对 n 个顶点执行一次深度优先搜索（覆盖所有连通块）的时间复杂度为（ ）。
{{ select(33) }}
- O(n + m)
- O(n²)
- O(m²)
- O(n·m)
三、完善程序（共 2 题，每题 15 分，共 30 分。每题有 5 处空缺，每处空缺对应一道单选。）
完善程序（一） 快速幂
给定正整数 a、b 和 m，计算 a^b mod m 的值。为避免结果过大并降低时间复杂度，采用「快速幂」算法：将指数 b 按二进制拆分，利用 a^(2^k) 可平方递推的性质，在 O(log b) 时间内完成。程序如下，其中 ① ~ ⑤ 为待填代码。
#include <iostream>
using namespace std;
long long power(long long a, long long b, long long m) {
long long ans = ①;
a %= ②;
while (b > 0) {
if (b % 2 == 1)
③;
a = a * a % m;
④;
}
return ⑤;
}
int main() {
long long a, b, m;
cin >> a >> b >> m;
cout << power(a, b, m) << endl;
return 0;
}
34. ① 处应填（ ）
{{ select(34) }}
- 0
- 1
- a
- m
35. ② 处应填（ ）
{{ select(35) }}
- b
- m
- a
- 1
36. ③ 处应填（ ）
{{ select(36) }}
ans = ans * a % mans = ans * b % ma = a * a % mb = b - 1
37. ④ 处应填（ ）
{{ select(37) }}
b = b + 1b = b - 1b /= 2b *= 2
38. ⑤ 处应填（ ）
{{ select(38) }}
abans0
完善程序（二） 并查集
给定一个包含 n 个结点（编号 1 ~ n）的无向图，以及 m 条边。用并查集维护结点的连通关系，并统计图中连通块的个数。程序采用「按大小合并」与「路径压缩」两种优化。程序如下，其中 ① ~ ⑤ 为待填代码。
#include <iostream>
using namespace std;
int fa[100005], sz[100005];
int find(int x) {
if (fa[x] == x) return x;
return fa[x] = ①;
}
void merge(int x, int y) {
int fx = find(x), fy = find(y);
if (fx == fy) ②;
if (sz[fx] < sz[fy]) ③;
fa[fy] = fx;
sz[fx] += ④;
}
int main() {
int n, m, ans = 0;
cin >> n >> m;
for (int i = 1; i <= n; i++) { fa[i] = i; sz[i] = 1; }
for (int i = 0; i < m; i++) {
int x, y; cin >> x >> y;
merge(x, y);
}
for (int i = 1; i <= n; i++) if (find(i) == i) ⑤;
cout << ans << endl;
return 0;
}
39. ① 处应填（ ）
{{ select(39) }}
fa[x]find(fa[x])fa[fa[x]]x
40. ② 处应填（ ）
{{ select(40) }}
returnbreakcontinuefa[fx] = fy
41. ③ 处应填（ ）
{{ select(41) }}
swap(fx, fy)swap(x, y)fx = fyreturn
42. ④ 处应填（ ）
{{ select(42) }}
1sz[fy]sz[fx]sz[fy] + 1
43. ⑤ 处应填（ ）
{{ select(43) }}
ans = ans + 1ans = 1merge(i, i)continue
—— 试卷结束 ——
冀公网安备13098402000493号