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

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

第 1 题 正整数 $2025$ 与 $1800$ 的最大公约数是（ ）。 {{ select(1) }}

• $15$
• $25$
• $45$
• $225$

第 2 题 表达式(('0'==0)+'s'+5+2.0)的结果类型为（ ）。 {{ select(2) }}

• $double$
• $int$
• $char$
• $bool$

第 3 题 对一个 $int$ 类型的值，执行以下哪个操作后，一定会变回原来的值？（ ） {{ select(3) }}

• 左移 $5$ 位，再右移 $5$ 位
• 右移 $5$ 位，再左移 $5$ 位
• 按位或 $15$，再按位与 $15$
• 按位异或 $15$，再按位异或 $15$

第 4 题 在数组 $H[x]$ 中，若存在 $(i<j)\ \&\&\ (H[i]>H[j])$，则称 $(H[i],H[j])$ 为数组 $H[x]$ 的一个逆序对。对于序列 $27, 4, 1, 59, 3, 26, 38, 15$，在不改变顺序的情况下，去掉（ ）会使逆序对的个数减少 $4$。 {{ select(4) }}

• $1$
• $3$
• $26$
• $15$

第 5 题 如果字符串 $s$ 在字符串 $str$ 中出现，则称字符串 $s$ 为字符串 $str$ 的子串。设字符串 str="oiers"，则 str 的非空子串的数目是（ ）。 {{ select(5) }}

• $17$
• $16$
• $15$
• $14$

第 6 题 以下哪种排序算法的平均时间复杂度最好？（ ） {{ select(6) }}

• 插入排序
• 归并排序
• 选择排序
• 冒泡排序

第 7 题 如果 $x$ 和 $y$ 均为 $int$ 类型的变量，且 $y$ 的值不为 $0$，那么能正确判断 x 是 y 的 2 倍 的表达式是（ ） {{ select(7) }}

• (x >> 2 == y)
• (x - 2 * y) % 2 != 0
• (x / y == 2)
• (x == 2 * y)

第 8 题 表达式 a*(b+c)-d 的后缀表达式为（ ）。 {{ select(8) }}

• abcd*+-
• abc+*d-
• abc*+d-
• -+*abcd

第 9 题 关于计算机网络，下列说法中正确的是（ ） {{ select(9) }}

• $SMTP$ 和 $POP3$ 都是电子邮件发送协议
• $IPv6$ 地址是从 $IPv4、IPv5$ 一路升级过来的
• 计算机网络是一个在协议控制下的多机互连系统
• 192.168.0.1 是 $A$ 类地址

第 10 题 下列哪种语言不是面向对象的语言？（ ） {{ select(10) }}

• $Java$
• $C$++
• $Python$
• $Fortran$

第 11 题 信息学奥赛的所有课程和课程间的先修关系构成一个有向图 $G$，我们用有向边 $<A,B>$ 表示课程 $A$ 是课程 $B$ 的先修课，则要找到某门课程 $C$ 的全部先修课，下面哪种方法不可行？（ ） {{ select(11) }}

• $BFS$
• $DFS$
• $枚举$
• $BFS+DFS$

第 12 题 一个字长为 $8$ 位的整数的补码为 11111001，则它的原码是（ ）。 {{ select(12) }}

• 00000111
• 10000110
• 10000111
• 11111001

第 13 题 元素 A、B、C、D、E、F 入栈的顺序为 A,B,C,D,E,F，如果第一个出栈的是 C，则最后一个出栈的不可能是（ ）。 {{ select(13) }}

• $A$
• $B$
• $D$
• $F$

第 14 题 一个三位数等于它的各位数字的阶乘之和，则此三位数的各位数字之和为（ ） {{ select(14) }}

• $9$
• $10$
• $11$
• 多于一种情况

第 15 题 在一个非连通无向图 $G$ 中有 $36$ 条边，则该图至少有（ ）个顶点。 {{ select(15) }}

• $8$
• $9$
• $10$
• $7$

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

（1）

01 #include <bits/stdc++.h>
02 using namespace std;
03
04 using i64 = long long;
05
06 const i64 k = 3;
07 const i64 mod = 8;
08
09 i64 toint(string s) {
10     sort(s.begin(), s.end());
11     i64 ans = 0;
12     for (int i = 0; i < s.length(); i++)
13         ans = (ans * k + (s[i] - 'a' + 1)) % mod;
14     return ans;
15 }
16
17
18 vector<vector<string>> solve(vector<string>& strs) {
19     map<i64, vector<string>> mp;
20     for (auto s : strs)
21         mp[toint(s)].push_back(s);
22     vector<vector<string>> ans;
23     for (auto v : mp)
24         ans.push_back(v.second);
25     return ans;
26 }
27
28
29 int main() {
30     int n;
31     cin >> n;
32     vector<string> vec(n);
33     for (int i = 0; i < n; i++)
34         cin >> vec[i];
35     auto ans = solve(vec);
36     for (auto v : ans)
37         for (int i = 0; i < v.size(); i++)
38             cout << v[i] << (i == v.size() - 1 ? "\n" : " ");
39     return 0;
40 }

假设 $1\le n\le 10^3, 1\le vec[i].length() \le 10^3$。回答下面问题。

第 16 题 若程序输入 6 eat tea tan ate nat bat，则程序输出 bat (换行) eat tea ate (换行) tan nat (换行)。 {{ select(16) }}

• √
• ×

第 17 题 对于这段代码，toint("aaf") = toint("atmoa")。 {{ select(17) }}

• √
• ×

第 18 题 若将头文件 <bits/stdc++.h> 换为 <iostream>，程序依然可以正常运行。 {{ select(18) }}

• √
• ×

第 19 题 若输入 4 aad zpf zpz yyl，则输出是什么？（ ） {{ select(19) }}

• aad (换行) zpf (换行) zpz (换行) yyl(换行)
• aad zpf (换行) zpz yyl (换行)
• aad zpf zpz (换行) yyl (换行)
• aad zpf zpz yyl (换行)

第 20 题 这个程序的时间复杂度是多少？（ ） {{ select(20) }}

• $O(n)$
• $O(n^2)$
• $O(nlogn)$
• $O(n^2logn)$

（2）

01 #include <bits/stdc++.h>
02 using namespace std;
03
04 int calc(vector<vector<int>> &grid) 
05 {
06     int n = grid.size(), m = grid[0].size();
07     vector<int> dp(m);
08     dp[0] = (grid[0][0] == 0);
09     for (int i = 0; i < n; i++)
10         for (int j = 0; j < m; j++) 
11		   {
12             if (grid[i][j] == 1) 
13			   {
14                 dp[j] = 0;
15                 continue;
16             }
17             if (j - 1 >= 0 && grid[i][j - 1] == 0)
18                 dp[j] += dp[j - 1];
19         }
20     return dp[m - 1];
21 }
22
23 int main() 
24 {
25     int n, m;
26     cin >> n >> m;
27     vector<vector<int>> a(n, vector<int>(m));
28     for (int i = 0; i < n; i++)
29         for (int j = 0; j < m; j++)
30             cin >> a[i][j];
31     cout << calc(a) << endl;
32     return 0;
33 }

第 21 题 若输入 3 3 0 0 0 0 1 0 0 0 0，则输出为 2。 {{ select(21) }}

• √
• ×

第 22 题 若 f[i][j] 表示从 (0,0) 走到 (i,j) 的路径数，则在第 $10\sim 19$ 行的循环中，f[i][j] = dp[j]。 {{ select(22) }}

• √
• ×

第 23 题 （2 分）若将第 $27$ 行的代码改为 vector<vector<int>> a(n+1, vector<int>(m+1))，则当输入的 n = 3,m = 3 时，$calc$ 函数中的 n = 3,m = 3。 {{ select(23) }}

• √
• ×

第 24 题 当输入的 $a$ 数组为 {{0,0,1}, {1,1,0}, {0,1,0}, {1,0,1}, {0,0,0}} 时，程序的输出为（ ） {{ select(24) }}

• 0
• $1$
• $2$
• $3$

第 25 题 若删除第 $12\sim 16$ 行的代码，则当输入的 $a$ 数组为 {{0,0,0}, {0,1,0}, {0,0,0}} 时，程序的输出为（ ） {{ select(25) }}

• $1$
• $2$
• $3$
• $4$

第 26 题 （4 分）当输入的 $a$ 数组为 {{0,0,2}, {0,1,2}, {5,3,4}} 时，程序的输出为（ ） {{ select(26) }}

• $0$
• $1$
• $2$
• $3$

（3）

01 #include<bits/stdc++.h>
02 using namespace std;
03
04 using i64 = long long;
05
06 int cmp(string v1, string v2) 
07 {
08     int i = 0, j = 0;
09     while (i < v1.length() || j < v2.length()) 
10 	   {
11         i64 num1 = 0, num2 = 0;
12         while (i < v1.length() && v1[i] != '.')
13             num1 = num1 * 10 + (v1[i++] - '0');
14         while (j < v2.length() && v2[j] != '.')
15             num2 = num2 * 10 + (v2[j++] - '0');
16         if (num1 > num2)
17             return 1;
18         else if (num1 < num2)
19             return -1;
20         i++, j++;
21     }
22     return 0;
23 }
24
25
26 int main() 
27 {
28     int n;
29     cin >> n;
30     vector<string> s(n);
31     for (int i = 0; i < n; i++)
32	   {
33         	cin >> s[i];
34     		if (s[i][0] == '.')
35			{
36         		cout << "err" << endl;
37     			return 0;
38			}
39		}
40     for (int i = 0; i < n; i++)
41         for (int j = 0; j < n; j++)
42             cout << cmp(s[i], s[j]) << (j == n - 1 ? "\n" : " ");
43     return 0;
44 }

假设 f[i][j] = cmp(s[i],s[j]) 。完成下面问题。

第 27 题 任取 $0 \leq i < n$，都有 f[i][i] = 0。 {{ select(27) }}

• √
• ×

第 28 题 若输入 3 1.0.1 2.1 1.1.0，则 f[0][1] = 1。 {{ select(28) }}

• √
• ×

第 29 题 任取 $0 \leq i, j < n$，都有 f[i][j] + f[j][i] = 0。 {{ select(29) }}

• √
• ×

第 30 题 当输入的 $s$ 数组为 {"1.2.3", "4.5", ".2"} 时，程序输出中第一行第二个数为（ ） {{ select(30) }}

• $-1$
• $0$
• $1$
• 不存在

第 31 题 （4 分）若删除第 $34\sim 38$ 行代码，则当输入的 $s$ 数组为 {"1.2.3", "4.5", ".2"} 时，f[0][2] 的值为（ ） {{ select(31) }}

• $-1$
• $0$
• $1$
• 未计算

第 32 题 阅读代码可知，当两个点之间的数为（ ）时，$cmp$ 函数将无法得到正确的结果。 {{ select(32) }}

• $1 * 10^9$
• $2 * 10^9$
• $4 * 10^{18}$
• $-1$

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

（1） 题目描述

输入 $n$（$3 \le n\le 10^5$）和长为 $n$ 的数组 $a$（$1 \le a[i] \le10^9$）。你需要从 $a$ 中恰好删除一个数，得到长为 $n-1$ 的数组 $a'$。然后生成一个长为 $n-2$ 的数组 $b$，其中 $b[i] = \text{GCD}(a'[i], a'[i+1])$。你需要让数组 $b$ 是非降序列，即 $b[i] \leq b[i+1]$。能否做到？输出 $YES$ 或 $NO$。 （提示：枚举 $i$，考察删除 $a[i]$ 后对 $b$ 数组产生的影响。）

01 #include <bits/stdc++.h>
02 using namespace std;
03
04 int gcd(int x, int y) {
05     return !y ? x : gcd(y, x % y);
06 }
07
08 void solve() {
09     int n;
10     cin >> n;
11     vector<int> a(n + 1), b(n + 2);
12     for (int i = 1; i <= n; i++)
13         cin >> a[i];
14     b[n] = b[n + 1] = ①;
15     for (int i = 1; i < n; i++)
16         b[i] = gcd(a[i], a[i + 1]);
17     vector<int> pre(n + 1), suf(n + 2);
18     pre[0] = 1;
19     for (int i = 1; i <= n; i++)
20         pre[i] = pre[i - 1] && (②);
21     suf[n + 1] = 1;
22     for (int i = n; i >= 1; i--)
23         suf[i] = suf[i + 1] && (b[i] <= b[i + 1]);
24     bool flag = ③;
25     for (int i = 2; i < n; i++) {
26         int cur = ④;
27         if (⑤ && b[i - 2] <= cur && cur <= b[i + 1])
28             flag = true;
29     }
30     cout << (flag ? "YES\n" : "NO\n");
31 }
32
33 int main() {
34     int t = 1;
35     // cin >> t;
36     while (t--)
37         solve();
38     return 0;
39 }

第 33 题 ①处应填（ ） {{ select(33) }}

• $0$
• $3E9$
• $-1E9$
• $2E9$

第 34 题 ②处应填（ ） {{ select(34) }}

• b[i] >= b[i - 1]
• b[i] <= b[i - 1]
• b[i] > b[i - 1]
• b[i] < b[i - 1]

第 35 题 ③处应填（ ） {{ select(35) }}

• pre[n - 2] & suf[2]
• pre[n - 2] | suf[2]
• pre[n - 2] ^ suf[2]
• pre[n - 2] - suf[2]

第 36 题 ④处应填（ ） {{ select(36) }}

• gcd(a[i], b[i])
• gcd(a[i], a[i + 1])
• gcd(a[i - 1], a[i + 1])
• gcd(a[i - 1], a[i])

第 37 题 ⑤处应填（ ） {{ select(37) }}

• pre[i - 2] && suf[i + 1]
• pre[i - 1] && suf[i + 1]
• pre[i - 2] || suf[i + 1]
• pre[i - 1] || suf[i + 1]

（2）题目描述

输入 $n$（$1 \leq n \leq 2 \times 10^5$）和长为 $n$ 的数组 $a$（$1 \leq a[i] \leq 1 \times 10^9$）。

对于数组 $B$，如果满足 $B[i] + 1 = \text{len}(B)$，那么称数组 $B$ 为“块”。

对于数组 $A$，如果可以将其划分成若干个“块”，那么称数组 $A$ 是合法的。

• 例如 $A = [3, 3, 4, 5, 2, 6, 1]$ 是合法的，因为 $A = [3, 3, 4, 5] + [2, 6, 1]$，这两段都是块。

把数组 $a$ 变成合法数组，至少要删除多少个元素？

（提示：令 $dp[i]$ 表示将 $a[i]$ 到 $a[n]$ 变成合法数组最少要删除的元素个数。）

01 #include <bits/stdc++.h>
02 using namespace std;
03
04 const int inf = 0x3f3f3f3f;
05
06 int main() {
07     int n;
08     cin >> n;
09     vector<int> a(n + 1), dp(①, inf);
10     for (int i = 1; i <= n; i++)
11         cin >> a[i];
12     dp[n + 1] = ②;
13     for (int i = n; i >= 1; i--) {
14         dp[i] = ③;
15         if (i + a[i] + 1 <= n + 1)
16             dp[i] = min(dp[i], ④);
17     }
18     cout << ⑤ << endl;
19     return 0;
20 }

第 38 题 ①处应填（ ） {{ select(38) }}

• n - 1
• n
• n + 1
• n + 2

第 39 题 ②处应填（ ） {{ select(39) }}

• 0
• 1
• -1
• inf

第 40 题 ③处应填（ ） {{ select(40) }}

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

第 41 题 ④处应填（ ） {{ select(41) }}

• dp[i + a[i] + 1]
• dp[i + a[i]]
• dp[a[i] + 1]
• dp[i + a[i] - 1]

第 42 题 ⑤处应填（ ） {{ select(42) }}

• dp[n]
• dp[1]
• dp[n - 1]
• dp[0]