CSP-J 2025 初赛模拟卷 6
2025CSP-J初赛模拟卷 6
一、单项选择题（共 15 题，每题 2 分，共计 30 分；每题有且仅有一个正确选项）
第 1 题 深度优先搜索时，控制与记录搜索过程的数据结构是（ ）。
{{ select(1) }}
- 队列
- 栈
- 链表
- 哈希表
第 2 题 计算机的中央处理器的组成部件是（ ）。
{{ select(2) }}
- 控制器和存储器
- 运算器和存储器
- 控制器、存储器和运算器
- 运算器和控制器
第 3 题 一个正整数在十六进制下有 200 位，则它在二进制下最多可能有（ ）位。
{{ select(3) }}
- 801
- 798
- 799
- 800
第 4 题 一个由 2025 个元素组成的数组已经从小到大排好序，采用二分查找，最多需要（ ）次能够判断是否存在所查找的元素。
{{ select(4) }}
- 2025
- 12
- 11
- 10
第 5 题 无向完全图 G 有 10 个顶点，它有（ ）条边。
{{ select(5) }}
- 45
- 90
- 72
- 36
第 6 题 在 8 位二进制补码中，10110110 表示的是十进制下的（ ）。
{{ select(6) }}
- -202
- -74
- 202
- 74
第 7 题 某市有 2025 名学生参加编程竞赛选拔，试卷中有 20 道选择题，每题答对得 5 分，答错或者不答得 0 分，那么至少有（ ）名同学得分相同。
{{ select(7) }}
- 99
- 98
- 97
- 96
第 8 题 以下哪个操作运算符优先级最高？（ ）
{{ select(8) }}
&&||>>++
第 9 题 如果根结点的深度是 1，则一棵恰好有 2025 个叶子结点的二叉树的深度不可能是（ ）。
{{ select(9) }}
- 11
- 12
- 13
- 2025
第 10 题 现代通用计算机之所以可以表示比较大或者比较小的浮点数，是因为使用了（ ）。
{{ select(10) }}
- 原码
- 补码
- 反码
- 阶码
第 11 题 在 C++ 语言中，一个数组定义为 int a[6] = {1, 2, 3, 4, 5, 6};，一个指针定义为 int *p = &a[3];，则执行 a[2] *= *p; 后，数组 a 中的值会变为（ ）。
{{ select(11) }}
{1, 2, 4, 4, 5, 6}{2, 2, 3, 4, 5, 6}{1, 2, 2, 4, 5, 6}{1, 2, 3, 4, 5, 6}
第 12 题 下面的 C++ 代码执行后的输出是（ ）。
#include
using namespace std;
int print(int x) {
cout 1)
return x;
else
return print(x - 1) + print(x - 2);
}
int main() {
cout a_3\)，\(a_3 a_5\)，则称该五位数为波形数，如 89674 就是一个波形数。由 1、2、3、4、5 组成的没有重复数字的五位数是波形数的概率是（ ）。
{{ select(15) }}
- \(1/5\)
- \(1/6\)
- \(2/15\)
- \(1/3\)
## 二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填√，错误填×；除特殊说明外，判断题每题 1.5 分，选择题每题 3 分，共计 40 分）
**(1)**
```cpp
01 #include
02 using namespace std;
03 using i64 = long long;
04
05 i64 check(const string &s, int p) {
06 if (p > s;
13 i64 ans = 0;
14 for (int i = 0; i = 0; i--) {
18 ans += check(s, i);
19 }
20 cout ` 换为 ``，程序依然可以正常运行。
{{ select(18) }}
- 对
- 错
**选择题**
19. 若输入 `5810438174`，则输出是（ ）。
{{ select(19) }}
- `7`（换行）`0`
- `8`（换行）`0`
- `9`（换行）`0`
- `10`（换行）`0`
20. 下面哪个选项是正确的？（ ）
{{ select(20) }}
- 把 `check` 函数中的第一个参数 `const` 去掉也可以正常运行
- 把 `check` 函数中的 `p >= 1` 去掉依然可以得到正确的答案
- `check` 函数用来判断由 `s[p-1]` 和 `s[p]` 组成的两位数是否为 4 的倍数
- 整段程序的时间复杂度为 \(O(n \log n)\)
**(2)**
```cpp
01 #include
02 using namespace std;
03
04 string calc(string s, string t) {
05 const int n = s.size();
06 if (t.size() > s.size())
07 return "";
08 unordered_map mp;
09 int cnt = t.size();
10 for (auto v : t)
11 mp[v]++;
12 string ans;
13 int len = 0x3f3f3f3f;
14 for (int i = 0, j = 0; i 0)
16 cnt--;
17 mp[s[i]]--;
18 while (mp[s[j]] cur_len)
23 ans = s.substr(j, cur_len);
24 }
25 }
26 return ans;
27 }
28
29 int main() {
30 string s, t;
31 cin >> s >> t;
32 cout
02 #include
03 #include
04
05 using namespace std;
06
07 const int N = 1e5 + 10;
08 int n, s, cnt, ans, res;
09 int a[N], b[N];
10
11 bool check(int mid) {
12 for (int i = 1; i > 1;
28 if (check(mid)) {
29 cnt = mid;
30 ans = res;
31 l = mid + 1;
32 } else
33 r = mid - 1;
34 }
35 printf("%d %d\n", cnt, ans);
36 return 0;
37 }
判断题
27. 若输入 4 100 12 5 6，则程序的输出为 4 54。
{{ select(27) }}
- 对
- 错
- 对于任意的输入，
cnt的一个必定合法的取值为n。
{{ select(28) }}
- 对
- 错
- 这个程序的时间复杂度为 (O(n \log n))。
{{ select(29) }}
- 对
- 错
选择题
30. 当输入为 3 11 2 3 5 时，程序的输出为（ ）。
{{ select(30) }}
1 112 113 80 0
- 代码中
check函数的作用是什么？（ ）
{{ select(31) }}
- 判断当前数组是否有序
- 检查是否能从数组中选出
mid个数，使得它们的总和小于或等于s - 判断数组的所有元素是否大于某个值
- 计算数组元素的平均值
- （4 分）变量
cnt和ans的作用分别是什么？（ ）
{{ select(32) }}
cnt记录满足条件的最大mid值，ans记录对应的总和cnt记录数组的长度，ans记录数组中的最大值cnt表示排序后的最小值索引，ans记录当前结果的最小值cnt表示满足条件的元素个数，ans记录最终的目标值
三、完善程序（单选题，每小题 3 分，共计 30 分）
(1)
题目描述：有 T 组数据，每组数据输入 n (1
02 using namespace std;
03 #define maxn 500005
04 int a[maxn];
05 map q;
06 void check(int x) {
07 for (int i = 2; i 1) ②;
14 }
15 void solve() {
16 int n;
17 cin >> n;
18 for (int i = 1; i > T;
34 while (T--) {
35 solve();
36 }
37 return 0;
38 }
33. ① 处应填（ ）。
{{ select(33) }}
- `sqrt(x)`
- `pow(x, 2)`
- `pow(x, 3)`
- `log(x)`
34. ② 处应填（ ）。
{{ select(34) }}
- `q[x]--`
- `q[x] /= 2`
- `q[x]++`
- `q[x] *= 2`
35. ③ 处应填（ ）。
{{ select(35) }}
- `k / n != 0`
- `k / n == 0`
- `k % n != 0`
- `k % n == 0`
**(2)**
题目描述：输入 n(1 ≤ n ≤ 1 X $10^5$)，表示有 n 座激光塔。然后输入 n 行，每行有两个数 p[i](1 ≤ p[i] ≤ 1 X $10^6$)和 k[i](1 ≤ k[i] ≤ 1 X $10^5$)，分别表示第 i 座激光塔的位置和威力。保证所有激光塔的位置互不相同。游戏规则：按照 p[i] 从大到小依次激活激光塔。当一座激光塔被激活时，它会摧毁它左侧所有满足 p[i] - p[j] ≤ k[i] 的激光塔j。被毁的激光塔无法被激活。在游戏开始前，你可以在最右边的激光塔的右侧，再添加一座激光塔，位置和威力由你决定。你希望被摧毁的激光塔的数量尽量少。输出这个最小值。
```cpp
01 #include
02 using namespace std;
03 const int N = 100000;
04 const int inf = 2147483647;
05 struct beacon {
06 int pos;
07 int power;
08 };
09
10 int n, ans = inf, dp[N + 5];
11 beacon beacons[N + 5];
12 bool cmp(beacon a, beacon b) {
13 return ①;
14 }
15
16 int main() {
17 cin >> n;
18 for (int i = 1; i > beacons[i].pos >> beacons[i].power;
20 }
21 sort(beacons + 1, beacons + n + 1, cmp);
22 ②;
23 for (int i = 2; i b.pos`
- `a.pos b.power`
39. ② 处应填（ ）。
{{ select(39) }}
- `dp[1] = 0`
- `dp[1] = inf`
- `dp[1] = 1`
- `dp[i] = inf`
40. ③ 处应填（ ）。
{{ select(40) }}
- `beacons[i].pos`
- `beacons[i].power`
- `beacons[i].pos + beacons[i].power`
- `beacons[i].pos - beacons[i].power`
41. ④ 处应填（ ）。
{{ select(41) }}
- `lower_bound(beacons + 1, beacons + n, find, cmp)`
- `upper_bound(beacons + 1, beacons + n + 1, find, cmp)`
- `lower_bound(beacons + 1, beacons + n + 1, find, cmp)`
- `upper_bound(beacons + 1, beacons + n, find, cmp)`
42. ⑤ 处应填（ ）。
{{ select(42) }}
- `n - dp[i]`
- `dp[i] - i`
- `dp[i]`
- `dp[i] + n - i`