普及组CSP-J2025初赛模拟卷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 <bits/stdc++.h>
    using namespace std;
    int print(int x) {
        cout << x << "$";
        if (x == 1 || x == 2)
            return x;
        else
            return print(x - 1) + print(x - 2);
    }
    int main() {
        cout << print(4) << endl;
        return 0;
    }
    

{{ select(12) }}

• 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就停止，那么小明应连续送（ ）天。 {{ select(13) }}

• 50
• 51
• 52
• 53

14. 7 + 77 + 777 + ... + 77...77（共2025个连续的7）的和的末2位数是（ ）。 {{ select(14) }}

• 45
• 55
• 65
• 75

15. 在无重复数字的五位数a1a2a3a4a5中，若a1 < a2，a2 > a3，a3 < a4，a4 > a5，则称该五位数为波形数，如89674就是一个波形数，由1、2、3、4、5组成的没有重复数字的五位数是波形数的概率是（ ）。 {{ select(15) }}

• 1/5
• 1/6
• 2/15
• 1/3

二、阅读程序（程序输入不超过数组或字符串定义的范围；判断题正确填√，错误填×；除特殊说明外，判断题每题1.5分，选择题每题3分，共计40分）

(1)

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) ? 1ll * p : 0ll;
07 }
08 
09 int main() {
10     string s;
11     cin >> s;
12     i64 ans = 0;
13     for (int i = 0; i < s.length(); i++)
14         ans += ((s[i] - '0') % 4 == 0);
15     for (int i = s.length() - 1; i >= 0; i--)
16         ans += check(s, i);
17     cout << ans << endl;
18     cout << check("114514", 3) << endl;
19     return 0;
20 }

判断题

16. 若程序输入124，则程序输出4（换行）0。 （ ） {{ select(16) }}

• 正确
• 错误

17. 对于这段代码，check("1234510", 2)的返回值为2。 （ ） {{ select(17) }}

• 正确
• 错误

18. 若将头文件#include <bits/stdc++.h>换为#include <cstdio>，程序依然可以正常运行。 （ ） {{ 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(nlogn)

(2)

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 
31 int main() {
32     string s, t;
33     cin >> s >> t;
34     cout << calc(s, t) << endl;
35     return 0;
36 }

判断题

21. 若输入ADOBECODEBANC ABC，则输出为BANC。 （ ） {{ select(21) }}

• 正确
• 错误

22. calc函数中的变量j只会增大，不会减小。 （ ） {{ select(22) }}

• 正确
• 错误

23. （2分）若删除第13行中的len变量，程序将不能正常运行。 （ ） {{ select(23) }}

• 正确
• 错误

选择题

24. 当输入为a aa时，程序的输出为（ ）。 {{ select(24) }}

• "a"
• "aa"
• ""
• "-1"

25. 若删除第19行代码，则当输入为cabwefgewcwaefgcf cae时，程序的输出为（ ）。 {{ select(25) }}

• "cwae"
• "abwe"
• "cabwe"
• "fgewc"

26. （4分）设n = s.size()，m = t.size()，则这段程序的时间复杂度为（ ）。 {{ select(26) }}

• O(n)
• O(m)
• O(m + n)
• O((m + n)logn)

(3)

01 #include <iostream>
02 #include <cstdio>
03 #include <algorithm>
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 <= n; i++)
13         b[i] = a[i] + i * mid;
14     sort(b + 1, b + 1 + n);
15     res = 0;
16     for (int i = 1; i <= mid && res <= s; i++)
17         res += b[i];
18     return res <= s;
19 }
20 
21 int main() {
22     scanf("%d%d", &n, &s);
23     for (int i = 1; i <= n; i++)
24         scanf("%d", &a[i]);
25     int l = 0, r = n;
26     while (l <= r) {
27         int mid = (l + r) >> 1;
28         if (check(mid)) cnt = mid, ans = res, l = mid + 1;
29         else r = mid - 1;
30     }
31     printf("%d %d\n", cnt, ans);
32     return 0;
33 }

判断题

27. 若输入4 100 1 2 5 6，则程序的输出为4 54。 （ ） {{ select(27) }}

• 正确
• 错误

28. 对于任意的输入，cnt的一个必定合法的取值为n。 （ ） {{ select(28) }}

• 正确
• 错误

29. 这个程序的时间复杂度为O(nlogn)。 （ ） {{ select(29) }}

• 正确
• 错误

选择题

30. 当输入为3 11 2 3 5时，程序的输出为（ ）。 {{ select(30) }}

• 1 11
• 2 11
• 3 8
• 0 0

31. 代码中check函数的作用是什么？（ ） {{ select(31) }}

• 判断当前数组是否有序
• 检查是否能从数组中选出mid个数，使得它们的总和小于或等于s
• 判断数组的所有元素是否大于某个值
• 计算数组元素的平均值

32. （4分）变量cnt和ans的作用分别是什么？（ ） {{ select(32) }}

• cnt记录满足条件的最大mid值，ans记录对应的总和
• cnt记录数组的长度，ans记录数组中的最大值
• cnt表示排序后的最小值索引，ans记录当前结果的最小值
• cnt表示满足条件的元素个数，ans记录最终的目标值

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

(1) 题目描述：

有T组数据，每组数据输入n（1 ≤ n ≤ 1 × 10^4）和长为n的数组a（1 ≤ a[i] ≤ 1 × 10^6）。 你可以执行如下操作任意次：选择a[i]和a[j]（i!=j），以及a[i]的一个因子x。然后执行a[i] /= x和a[j] *= x。能否使a中所有元素都相同？ 输出YES或NO。

01 #include <bits/stdc++.h>
02 using namespace std;
03 #define maxn 500005
04 int a[maxn];
05 map<int, int> q;
06 
07 void check(int x) {
08     for (int i = 2; i <= ①; i++) {
09         while (x % i == 0) {
10             q[i] ++;
11             x /= i;
12         }
13     }
14     if (x > 1)
15         ②;
16 }
17 
18 void solve() {
19     int n;
20     cin >> n;
21     ③;
22     for (int i = 1; i <= n; i++) {
23         scanf("%d", &a[i]);
24         ④;
25     }
26     for (auto i : q) {
27         int k = i.second;
28         if (⑤)
29             cout << "No" << endl;
30             return;
31     }
32     cout << "YES" << endl;
33     return ;
34 }
35 int main() {
36     int T = 1;
37     cin >> T;
38     while (T--)
39         solve();
40     return 0;
41 }

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) }}

• q[x]--
• q[x] /= 2
• q[x]++
• q[x] *= 2

36. ④处应填（ ）。 {{ select(36) }}

• check(q)
• check(a)
• check(a[i])
• check(a[i - 1])

37. ⑤处应填（ ）。 {{ select(37) }}

• k / n == 0
• k / n != 0
• k % n == 0
• k % n != 0

(2) 题目描述：

输入n（1 ≤ n ≤ 1 × 10^5），表示有n座激光塔。然后输入n行，每行有两个数p[i]（0 ≤ p[i] ≤ 1 × 10^6）和k[i]（1 ≤ k[i] ≤ 1 × 10^6），分别表示第i座激光塔的位置和威力。保证所有激光塔的位置互不相同。 游戏规则：按照p[i]从大到小依次激活激光塔。当一座激光塔被激活时，它会摧毁它左侧所有满足p[i] - p[j] ≤ k[i]的激光塔j。被摧毁的激光塔无法被激活。 在游戏开始前，你可以在最右边的激光塔的右侧，再添加一座激光塔，位置和威力由你决定。 你希望被摧毁的激光塔的数量尽量少。输出这个最小值。

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 ①;
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     ②;
22     for (int i = 2; i <= n; ++i) {
23         beacon find;
24         find.pos = max(0, ③);
25         int destroy = ④ - (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 = ⑤;
31         if (destruction < ans) ans = destruction;
32     }
33     cout << ans << endl;
34     return 0;
35 }

38. ①处应填（ ）。 {{ select(38) }}

• a.power < b.power
• a.pos > b.pos
• a.pos < b.pos
• a.power > b.power

39. ②处应填（ ）。 {{ select(39) }}

• dp[1] = 0
• dp[1] = inf
• dp[1] = 1
• dp[1] = -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 + i, beacons + n, find, cmp)

42. ⑤处应填（ ）。 {{ select(42) }}

• n - dp[i]
• dp[i] - i
• dp[i]
• dp[i] + n - i