普及组CSP-J2025初赛模拟卷7

一、单项选择题（共15题，每题2分，共计30分；每题有且仅有一个正确选项）

1. 八进制数2025用二进制表示是（ ）。 {{ select(1) }}

• 10000000101
• 10000010101
• 10000001101
• 10000100101

2. C++语言的创始人是（ ）。 {{ select(2) }}

• 林纳斯·托瓦茨
• 丹尼斯·里奇
• 吉多·范罗苏姆
• 本贾尼·斯特劳斯特卢普

3. 以下设备中，（ ）不是输出设备。 {{ select(3) }}

• 扫描仪
• 触摸屏
• 绘图仪
• 音箱

4. 当执行以下C++程序段后输出结果为（ ）。

   char c1 = '2' + '0';
   char c2 = '2' + '5';
   cout << c1 < c2 << endl;
   

{{ select(4) }}

• 2025
• 27
• bg
• ch

5. 应用二分算法的思想，在一个有n个数的有序序列中查找某个指定的数m，其程序时间复杂度为（ ）。 {{ select(5) }}

• O(nlogn)
• O(n)
• O(logn)
• O(mlogn)

6. 贝希要参加CSP-J比赛，在CCF官网注册时需设置登录密码，下列选项中最安全的是（ ）。 {{ select(6) }}

• 12345678
• abcd1234
• 20010911
• F1@CcfGq6dh

7. 双向链表的优点是（ ）。 {{ select(7) }}

• 查找速度快
• 插入和删除方便
• 节省内存
• 后进先出

8. 小明买了一块1TB的固态硬盘，相当于（ ）MB的存储容量。 {{ select(8) }}

• 2^10
• 2^20
• 2^30
• 2^40

9. 下面（ ）没有用到有关人工智能的技术。 {{ select(9) }}

• 智能手机设置的闹钟定时叫我起床
• 智能手环收集患者的数据并上传至医疗系统云端进行分析
• 国家围棋队棋手和围棋机器人下围棋
• 大学校园用人脸识别门禁系统控制人员出入

10. 下列选项中（ ）不是C++标准库string类的函数。 {{ select(10) }}

• substr
• size
• replace
• strcmp

11. 有一个2025位的正整数，它的各位数字按照如下规则排列：123456789123456789123456789...，请问这个数被9除的余数是多少？（ ） {{ select(11) }}

• 3
• 2
• 0
• 1

12. 九宫格数独游戏是一种训练推理能力的数字谜题游戏。九宫格分为九个小宫格，某小九宫格下图所示，小明需要在9个小格子中填上1至9中不重复的整数。小明通过推理已经得到了4个小格子中的准确数字，其中，a、b、c、d、e这5个数字未知，且b和d为奇数，则a + b > 5的概率为（ ）。

    9   a   7   
    b   c   d
    4   e   5
    

{{ select(12) }}

• 3/5
• 1/2
• 2/3
• 1/3

13. 四位同学进行篮球传球练习，要求每个人接球后再传给别人。开始时甲同学发球，并作为第一次传球，第五次传球后，球又回到甲同学手中，则不同的传球方法有（ ）种。 {{ select(13) }}

• 60
• 65
• 70
• 75

14. 字符串CCCSSSPPP共有（ ）种不同的非空子串。 {{ select(14) }}

• 45
• 36
• 37
• 39

15. 向一个栈顶指针为head的链式栈中插入一个指针p指向的结点时，应执行（ ）。 {{ select(15) }}

• head->next = p;
• p->next = head; head = p;
• p->next = head->next; head->next = p;
• p->next = head; head = head->next;

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

(1)

01 #include <bits/stdc++.h>
02 using namespace std;
03 int t, p, a, b, c;
04 int f(int a, int b) {
05     if (a % b == 0) return 0;
06     return b - a % b;
07 }
08 void solve() {
09     scanf("%d%d%d%d", &p, &a, &b, &c);
10     printf("%d\n", min(min(f(p, a), f(p, b)), f(p, c)));
11 }
12 int main() {
13     scanf("%d", &t);
14     while (t--) solve();
15     return 0;
16 }

判断题

16. 若程序输入1 2 6 10 9，则最终输出为4。 （ ） {{ select(16) }}

• 正确
• 错误

17. （2分）若将第5行删除，程序的输出结果一定不会改变。 （ ） {{ select(17) }}

• 正确
• 错误

18. 若将头文件#include<bits/stdc++.h>改成#include<stdio.h>，程序仍能正常运行。 （ ） {{ select(18) }}

• 正确
• 错误

选择题

19. 若程序输入2 9 5 4 8 10 9 9 9，则输出是（ ）。 {{ select(19) }}

• 1 8
• 1 1
• 0 8
• 0 1

20. （4分）若将第10行的输出内容改为f(f(f(p, a), b), c)，则输入1 2 6 10 9时，输出是（ ）。 {{ select(20) }}

• 3
• 4
• 5
• 6

(2)

01 #include <bits/stdc++.h>
02 using namespace std;
03 const int N = 2e5 + 5;
04 int a, b, n, k;
05 char s[N];
06 void solve(int &a, int &b, int k) {
07     while (k--)
08         putchar(a ? --a, '1' : (--b, '0'));
09 }
10 int main() {
11     cin >> a >> b >> k; n = a + b;
12     for (int i = 1; i <= a; ++i) s[i] = '1';
13     for (int i = 1; i <= b; ++i) s[i + a] = '0';
14     while ((s[n - k] != '1' && s[n] != '1') && n > k)
15         --n;
16     if (n <= k + 1 && k) return printf("No\n"), 0;
17     printf("Yes\n");
18     if (!k) return printf("%s\n%s", s + 1, s + 1), 0;
19     a -= 2, b -= 1;
20     int A = a, B = b;
21     printf("11");
22     solve(A, B, k - 1);
23     putchar('0');
24     solve(A, B, a + b - k + 1);
25     A = a, B = b;
26     printf("\n10");
27     solve(A, B, k - 1);
28     putchar('1');
29     solve(A, B, a + b - k + 1);
30     return 0;
31 }

判断题

21. 去掉第6行的两个&，程序的输出一定不改变。 （ ） {{ select(21) }}

• 正确
• 错误

22. 如果a = 0且k ≠ 0，则必定输出No。 （ ） {{ select(22) }}

• 正确
• 错误

23. 当a + b < k + 3时，必定输出No。 （ ） {{ select(23) }}

• 正确
• 错误

24. 若输出Yes，则输出的两个数在二进制下的差一定有k位1。 （ ） {{ select(24) }}

• 正确
• 错误

选择题

25. 若输入为2 4 3，则输出为（ ）。 {{ select(25) }}

• Yes 101000 100001
• Yes 110000 100010
• Yes 110000 100001
• No

26. 若输入为2 3 4，则输出为（ ）。 {{ select(26) }}

• Yes 10100 10001
• Yes 11000 10001
• Yes 10001 00011
• No

(3)

01 #include <bits/stdc++.h>
02 using namespace std;
03 const int N = 2e5 + 5;
04 int n, m, ans, pos[2][N];
05 char a[N], b[N];
06 int main() {
07     scanf("%d%d%s%s", &n, &m, a, b);
08     reverse(a, a + n); reverse(b, b + m);
09     for (int i = 0, now = 0; i < n && now < m; ++i)
10         if (a[i] == b[now])
11             pos[0][now++] = i;
12     for (int i = n - 1, now = m - 1; ~i && ~now; --i)
13         if (a[i] == b[now])
14             pos[1][now--] = i;
15     for (int i = 1; i < m; ++i)
16         ans = max(pos[1][i] - pos[0][i - 1], ans);
17     printf("%d", ans);
18     return 0;
19 }

判断题

27. 若m不为n的子序列，则输出必定为0。 （ ） {{ select(27) }}

• 正确
• 错误

28. 若将第8行删除，程序输出结果一定不会改变。 （ ） {{ select(28) }}

• 正确
• 错误

选择题

29. 若输入为5 3 abaab abb，则输出为（ ）。 {{ select(29) }}

• 1
• 2
• 3
• 4

30. 若a = "ababcdc"，b的长度为5，则使答案取到最大值的b可能有（ ）个。 {{ select(30) }}

• 3
• 4
• 6
• 7

31. （4分）当a = "1010101"时，b的长度为3，b的每一位上要么是0，要么是1。总共有8种情况，对应8个输出。这8个输出的和为（ ）。 {{ select(31) }}

• 18
• 24
• 30
• 36

32. 当a = "1010101"时，b的长度为4，b的每位上要么是0，要么是1。总共有16种情况，对应16个输出。这16个输出的和为（ ）。 {{ select(32) }}

• 32
• 38
• 46
• 52

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

(1) 题目描述：

给定一个数组{a}表示一排蘑菇的数量。有一个篮子。每次到一个新的a_i时，篮子中会增加a_i个蘑菇。如果篮子里的蘑菇超过x个，则篮子里的蘑菇会清空。询问有多少组[L, R]，使得从L采摘到R，蘑菇数量不为0。

01 #include <bits/stdc++.h>
02 using namespace std;
03 const int N = 2e5 + 5;
04 int n, x, a[N], cnt[N], dp[N];
05 int main() {
06     cin >> n >> x;
07     for (int i = 1; i <= n; i++)
08         cin >> a[i];
09     int l = 1, r = 0, sum = 0;
10     while (l <= n) {
11         while (①)
12             ②
13         cnt[l] = r;
14         ③
15     }
16     sum = 0;
17     for (int i = n; i >= 1; i--) {
18         if (cnt[i] == n + 1) continue;
19             dp[i] = ④;
20         sum += dp[i];
21     }
22     cout << ⑤ << endl;
23     return 0;
24 }

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

• r <= n && sum <= x
• l <= n && sum > x
• sum <= x
• sum > x

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

• sum += a[++r]
• sum += a[r++]
• sum -= a[++l]
• sum -= a[l++]

35. ③处应填（ ）。 {{ select(35) }}

• sum -= a[r--]
• sum -= a[--r]
• sum -= a[++l]
• sum -= a[l++]

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

• dp[cnt[i]] + 1
• dp[cnt[i] + 1] + 1
• dp[cnt[i + 1]] + 1
• dp[cnt[i + 1] + 1] + 1

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

• dp[1]
• n - dp[1]
• n * (n + 1) / 2 - sum
• sum

(2) 题目描述：

一个字符串s（|s| ≤ 5000）由小写字母组成，有g（g ≤ 1e6）组询问，每组询问给你两个数l和r，问：在字符串区间[l, r]的子串中包含多少回文串？

01 #include <bits/stdc++.h>
02 using namespace std;
03 const int N = 5005;
04 char s[N];
05 int n, f[N][N], dp[N][N];
06 bool check(int l, int r) {
07     if (①) return f[l][r];
08     if (l >= r) return f[l][r] = 1;
09     if (s[l] ^ s[r]) return f[l][r] = 0;
10     return f[l][r] = ②;
11 }
12 int main() {
13     memset(f, -1, sizeof(f));
14     scanf("%s", s + 1); n = strlen(s + 1);
15     for (int i = 1; i <= n; ++i) ③ ；
16     for (int l = 2; l <= n; ++l) {
17         for (int i = 1; i <= n - l + 1; ++i) {
18             int j = i + l - 1;
19             dp[i][j] = ④;
20             if (check(i, j)) ⑤;
21         }
22     }
23     int T; scanf("%d", &T);
24     while (T--) {
25         int x, y; scanf("%d%d", &x, &y);
26         printf("%d\n", dp[x][y]);
27     }
28     return 0;
29 }

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

• ~f[l][r]
• !f[l][r]
• r > l
• r - l > 1

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

• check(l + 1, r - 1)
• check(l + 1, r) + 1
• f[l + 1][r - 1] + 1
• f[l + 1][r] + 1

40. ③处应填（ ）。 {{ select(40) }}

• dp[i][i] = 1
• dp[i][i + 1] = 1
• dp[i][i + 1] = (s[i] == s[i + 1]) + 2
• dp[i][i + 1] = s[i] == s[i + 1]

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

• dp[i + 1][j] + dp[i][j - 1] + dp[i + 1][j - 1]
• dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1]
• dp[i + 1][j] + dp[i][j - 1] + (s[i] == s[j])
• dp[i + 1][j] + dp[i][j - 1] - (s[i] == s[j])

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

• dp[i][j]++
• dp[i][j] += dp[i + 1][j - 1]
• dp[i][j]--
• dp[i][j] -= dp[i + 1][j - 1]