问题 A：2026 CSP-J TP原创初赛模拟卷1
文件提交：无需freopen
内存限制：128 MB
时间限制：1.000 S
评测方式：文本裁判
金币值：
命题人：
提交：40
解决：0
题目描述
## 单项选择题15题（每题2分），阅读程序17题（共40分），完善程序10题（每题3分），共100分
## 一、单项选择题（共 15 题，每题 2 分，共计 30 分）
1. **深度优先搜索时，控制与记录搜索过程的数据结构是（ ）。**
- 队列
- 栈
- 链表
- 哈希表
2. **下列不属于图像格式的是（ ）。**
- jpg
- png
- mp4
- gif
3. **一个正整数在十六进制下有 200 位，则它在二进制下最多可能有（ ）位。**
- 801
- 798
- 799
- 800
4. **对于一个长度为 $n$ 的数组，使用堆排序算法对其排序的时间复杂度是（ ）。**
- $O(1)$
- $O(n)$
- $O(n\log n)$
- $O(n^2)$
5. **无向完全图 $G$ 有 10 个顶点，它有（ ）条边。**
- 45
- 90
- 72
- 36
6. **在 8 位二进制补码中，`10110110` 表示的是十进制下的（ ）。**
- -202
- -74
- 202
- 74
7. **某市有 2025 名学生参加编程竞赛选拔，试卷中有 20 道选择题，每题答对得 5 分，答错或者不答得 0 分，那么至少有（ ）名同学得分相同。**
- 99
- 98
- 97
- 96
8. **以下哪个操作运算符优先级最高？（ ）**
- `&&`
- `||`
- `>>`
- `++`
9. **对于一个含有 26 个节点的完全二叉树，其有（ ）个结点没有子结点。**
- 10
- 11
- 12
- 13
10. **现代通用计算机之所以可以表示比较大或者比较小的浮点数，是因为使用了（ ）。**
- 原码
- 补码
- 反码
- 阶码
11. **在 C++ 语言中，一个数组定义为 `int a[6] = {1, 2, 3, 4, 5, 6}`，一个指针定义为 `int *p = &a[3];`，则执行 `a[2] = *p;` 后，数组 `a` 中的值会变为（ ）。**
- `{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++ 代码执行后的输出是（ ）。**
```cpp
01 #include < bits/stdc++.h>
02 using namespace std;
03 int print(int x) {
04 cout << x << "$";
05 if (x == 1 || x == 2)
06 return x;
07 else
08 return print(x - 1) + print(x - 2);
09 }
10 int main() {
11 cout << print(4) << endl;
12 return 0;
13 }
```
- `4$3$2$2$4`
- `4$3$2$2$1$5`
- `4$3$2$1$2$4`
- `4$3$2$1$2$5`
13. **小明往一个图书馆送书，第 1 天送 1 本，第 2 天送 2 本，第 3 天送 3 本……第 $n$ 天送 $n$ 本，他准备累计送到图书馆的书的总数能整除 106 就停止，那么小明应连续送（ ）天。**
- 50
- 51
- 52
- 53
14. **$7 + 77 + 777 + \dots + 77\dots77$（共 2025 个连续的 7）的和的末 2 位数是（ ）。**
- 45
- 55
- 65
- 75
15. **计算后缀表达式 `2 3 + 5 * 6 -` 的结果是（ ）。**
- 13
- 15
- 17
- 19
## 二、阅读程序（判断题正确填√，错误填×；除特殊说明外，判断题每题 1.5 分，选择题每题 3 分，共计 40 分）
### (1)
```cpp
01 #include < bits/stdc++.h>
02 using namespace std;
03 using i64 = long long;
04
05 i64 check(const string &s, int p) {
06 return (p >= 1 && ((s[p-1]-'0')*10 + (s[p]-'0'))%4 == 0) ?
07 1ll * p : 0ll;
08 }
09
10 int main() {
11 string s;
12 cin >> s;
13 i64 ans = 0;
14 for (int i = 0; i < s.length(); i++)
15 ans += ((s[i] - '0') % 4 == 0);
16 for (int i = s.length() - 1; i >= 0; i--)
17 ans += check(s, i);
18 cout << ans << endl;
19 cout << check("114514", 3) << endl;
20 return 0;
21 }
```
**判断题**
16. 若程序输入 `124`，则程序输出 `4`（换行）`0`。（ ）
- 正确
- 错误
17. 对于这段代码，`check("1234510", 2)` 的返回值为 `2`。（ ）
- 正确
- 错误
18. 若将头文件 `#include < bits/stdc++.h>` 换为 `#include < cstdio>`，程序依然可以正常运行。（ ）
- 正确
- 错误
**选择题**
19. 若输入 `5810438174`，则输出是（ ）。
- `7`（换行）`0`
- `8`（换行）`0`
- `9`（换行）`0`
- `10`（换行）`0`
20. 下面哪个选项是正确的？（ ）
- 把 `check` 函数中的第一个参数 `const` 去掉也可以正常运行
- 把 `check` 函数中的 `p >= 1` 去掉依然可以得到正确的答案
- `check` 函数用来判断由 `s[p-1]` 和 `s[p]` 组成的两位数是否为 4 的倍数
- 整段程序的时间复杂度为 $O(n\log n)$
### (2)
```cpp
01 #include < bits/stdc++.h>
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< char, int> 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 < n; i++) {
15 if (mp[s[i]] > 0)
16 cnt--;
17 mp[s[i]]--;
18 if (cnt == 0) {
19 while (mp[s[j]] < 0)
20 mp[s[j++]]++;
21 int len = i - j + 1;
22 if (ans.empty() || ans.size() > len)
23 ans = s.substr(j, len);
24 mp[s[j++]]++;
25 cnt++;
26 }
27 }
28 return ans;
29 }
30 int main() {
31 string s, t;
32 cin >> s >> t;
33 cout << calc(s, t) << endl;
34 return 0;
35 }
```
**判断题**
21. 若输入 `ADOBECODEBANC ABC`，则输出为 `BANC`。（ ）
- 正确
- 错误
22. `calc` 函数中的变量 `j` 只会增大，不会减小。（ ）
- 正确
- 错误
23. （2 分）若删除第 13 行中的 `len` 变量，程序将不能正常运行。（ ）
- 正确
- 错误
**选择题**
24. 当输入为 `a aa` 时，程序的输出为（ ）。
- `"a"`
- `"aa"`
- `""`
- `"-1"`
25. 若删除第 19 行代码，则当输入为 `cabwefgewcwaefgcf cae` 时，程序的输出为（ ）。
- `"cwae"`
- `"abwe"`
- `"cabwe"`
- `"fgewc"`
26. （4 分）设 $n = \text{s.size()}$，$m = \text{t.size()}$，则这段程序的时间复杂度为（ ）。
- $O(n)$
- $O(m)$
- $O(m + n)$
- $O((m + n)\log n)$
### (3)
```cpp
01 #include
02 #include < cstdio>
03 #include < algorithm>
04
05 using namespace std;
06
07 const int N = 1e5 + 10;
08
09 int n, s, cnt, ans, res;
10 int a[N], b[N];
11
12 bool check(int mid) {
13 for (int i = 1; i <= n; i++)
14 b[i] = a[i] + i * mid;
15 sort(b + 1, b + 1 + n);
16 res = 0;
17 for (int i = 1; i <= mid && res <= s; i++)
18 res += b[i];
19 return res <= s;
20 }
21
22 int main() {
23 scanf("%d%d", &n, &s);
24 for (int i = 1; i <= n; i++)
25 scanf("%d", &a[i]);
26 int l = 0, r = n;
27 while (l <= r) {
28 int mid = (l + r) >> 1;
29 if (check(mid)) cnt = mid, ans = res, l = mid + 1;
30 else r = mid - 1;
31 }
32 printf("%d %d\n", cnt, ans);
33 return 0;
34 }
```
**判断题**
27. 若输入 `4 100 1 2 5 6`，则程序的输出为 `4 54`。（ ）
- 正确
- 错误
28. 对于任意的输入，`cnt` 的一个必定合法的取值为 $n$。（ ）
- 正确
- 错误
29. 这个程序的时间复杂度为 $O(n\log n)$。（ ）
- 正确
- 错误
**选择题**
30. 当输入为 `3 11 2 3 5` 时，程序的输出为（ ）。
- `1 11`
- `2 11`
- `3 8`
- `0 0`
31. 代码中 `check` 函数的作用是什么？（ ）
- 判断当前数组是否有序
- 检查是否能从数组中选出 `mid` 个数，使得它们的总和小于或等于 `s`
- 判断数组的所有元素是否大于某个值
- 计算数组元素的平均值
32. （4 分）变量 `cnt` 和 `ans` 的作用分别是什么？（ ）
- `cnt` 记录满足条件的最大 `mid` 值，`ans` 记录对应的总和
- `cnt` 记录数组的长度，`ans` 记录数组中的最大值
- `cnt` 表示排序后的最小值索引，`ans` 记录当前结果的最小值
- `cnt` 表示满足条件的元素个数，`ans` 记录最终的目标值
## 三、完善程序（单选题，每小题 3 分，共计 30 分）
### (1) 题目描述：
有 $T$ 组数据，每组数据输入 $n$ ($1 \le n \le 1 \times 10^4$) 和长为 $n$ 的数组 $a$ ($1 \le a[i] \le 1 \times 10^6$)。
你可以执行如下操作任意次：选择 $a[i]$ 和 $a[j]$ ($i \neq j$)，以及 $a[i]$ 的一个因子 $x$。然后执行 $a[i] /= x$ 和 $a[j] *= x$。能否使 $a$ 中所有元素都相同？
输出 `YES` 或 `NO`。
```cpp
01 #include < bits/stdc++.h>
02 using namespace std;
03 int a[500005];
04 map q;
05 void check(int x) {
06 for (int i = 2; i <= [1]; i++) {
07 while (x % i == 0) {
08 q[i] ++;
09 x /= i;
10 }
11 }
12 if (x > 1) [2];
13 }
14 void solve() {
15 int n; cin >> n;
16 [3];
17 for (int i = 1; i <= n; i++) {
18 scanf("%d", &a[i]);
19 [4];
20 }
21 for (auto i : q) {
22 int k = i.second;
23 if ([5]){
24 cout << "No" << endl;
25 return;
26 }
27 }
28 cout << "YES" << endl;
29 return ;
30 }
31 int main() {
32 int T = 1;
33 cin >> T;
34 while (T--)
35 solve();
36 return 0;
37 }
```
33. [1] 处应填（ ）。
- `sqrt(x)`
- `pow(x, 2)`
- `pow(x, 3)`
- `log(x)`
34. [2] 处应填（ ）。
- `q[x]--`
- `q[x] /= 2`
- `q[x]++`
- `q[x] *= 2`
35. [3] 处应填（ ）。
- `q.clear()`
- `q.erase(q.begin())`
- `q.swap(a)`
- `q.erase(q.end())`
36. [4] 处应填（ ）。
- `check(q)`
- `check(a)`
- `check(a[i])`
- `check(a[i - 1])`
37. [5] 处应填（ ）。
- `k / n == 0`
- `k / n != 0`
- `k % n == 0`
- `k % n != 0`
### (2) 题目描述：
输入 $n$ ($1 \le n \le 1 \times 10^5$)，表示有 $n$ 座激光塔。然后输入 $n$ 行，每行有两个数 $p[i]$ ($0 \le p[i] \le 1 \times 10^6$) 和 $k[i]$ ($1 \le k[i] \le 1 \times 10^6$)，分别表示第 $i$ 座激光塔的位置和威力。保证所有激光塔的位置互不相同。
游戏规则：按照 $p[i]$ 从大到小依次激活激光塔。当一座激光塔被激活时，它会摧毁它左侧所有满足 $p[i] - p[j] \le k[i]$ 的激光塔 $j$。被摧毁的激光塔无法被激活。
在游戏开始前，你可以在最右边的激光塔的右侧，再添加一座激光塔，位置和威力由你决定。
你希望被摧毁的激光塔的数量尽量少。输出这个最小值。
```cpp
01 #include < bits/stdc++.h>
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 [1];
14 }
15
16 int main() {
17 cin >> n;
18 for (int i = 1; i <= n; ++i)
19 cin >> beacons[i].pos >> beacons[i].power;
20 sort(beacons + 1, beacons + n + 1, cmp);
21 [2];
22 for (int i = 2; i <= n; ++i) {
23 beacon find;
24 find.pos = max(0, [3]);
25 int destroy = [4] - (beacons + 1);
26 dp[i] = dp[destroy];
27 dp[i] += (i - destroy - 1);
28 }
29 for (int i = 1; i <= n; ++i) {
30 int destruction = [5];
31 if (destruction < ans) ans = destruction;
32 }
33 cout << ans << endl;
34 return 0;
35 }
```
38. [1] 处应填（ ）。
- `a.power < b.power`
- `a.pos > b.pos`
- `a.pos < b.pos`
- `a.power > b.power`
39. [2] 处应填（ ）。
- `dp[1] = 0`
- `dp[1] = inf`
- `dp[1] = 1`
- `dp[1] = -inf`
40. [3] 处应填（ ）。
- `beacons[i].pos`
- `beacons[i].power`
- `beacons[i].pos + beacons[i].power`
- `beacons[i].pos - beacons[i].power`
41. [4] 处应填（ ）。
- `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 + i, beacons + n, find, cmp)`
42. [5] 处应填（ ）。
- `n - dp[i]`
- `dp[i] - i`
- `dp[i]`
- `dp[i] + n - i`