一、单项选择题（共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位的整数的补码为1111101，则它的原码是（）

{{ 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 vector<vector<string>> solve(vector<string> strs) {
18     map<i64, vector<string>> mp;
19     for (auto s : strs)
20         mp[toint(s)].push_back(s);
21     vector<vector<string>> ans;
22     for (auto v : mp)
23         ans.push_back(v.second);
24     return ans;
25 }
26
27 int main() {
28     int n;
29     cin >> n;
30     vector<string> vec(n);
31     for (int i = 0; i < n; i++)
32         cin >> vec[i];
33     auto ans = solve(vec);
34     for (auto v : ans) {
35         for (int i = 0; i < v.size(); i++)
36             cout << v[i] << "\n"[i == v.size() - 1];
37     }
38     return 0;
39 }

假设$1 \leq n \leq 10^4$，$1 \leq vec[i].length() \leq 10$，回答下面的问题。

判断题

16. 若程序输入6 eat tea tan ate nat bat，则程序输出bat（换行）eat tea ate（换行）tan nat（换行）。（）

{{ select(16) }}

• 正确
• 错误

17. 对于这段代码，toint("aaf") != toint("atmoa")。（）

{{ select(17) }}

• 正确
• 错误

18. 若将头文件#include <bits/stdc++.h>换为#include <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(n \log n)$
• $O(n^2 \log n)$

（2）

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

判断题

21. 若输入3 3 0 0 0 0 1 0 0 0 0，则输出为2。（）

{{ select(21) }}

• 正确
• 错误

22. 第15行的作用是累加当前位置上方和左方的dp[j]。（）

{{ select(22) }}

• 正确
• 错误

23. （2分）若将第23行的代码改为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~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     using i64 = long long;
08     int i = 0, j = 0;
09     while (i < v1.length() || j < v2.length()) {
10         i64 num1 = 0, num2 = 0;
11         while (i < v1.length() && v1[i] != '.')
12             num1 = num1 * 10 + (v1[i++] - '0');
13         while (j < v2.length() && v2[j] != '.')
14             num2 = num2 * 10 + (v2[j++] - '0');
15         if (num1 > num2)
16             return 1;
17         else if (num1 < num2)
18             return -1;
19         i++, j++;
20     }
21     return 0;
22 }
23
24 int main() {
25     int n;
26     cin >> n;
27     vector<string> s(n);
28     for (int i = 0; i < n; i++) {
29         cin >> s[i];
30         if (s[i][0] == '.') {
31             cout << "err" << endl;
32             return 0;
33         }
34     }
35     for (int i = 0; i < n; i++) {
36         for (int j = 0; j < n; j++)
37             cout << cmp(s[i], s[j]) << "\n"[j == n - 1];
38     }
39     return 0;
40 }

假设$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分）若删除第30~33行代码，则当输入的s数组为{"1.2.3", "4.5", ".2"}时，$f[0][2]$的值为（）

{{ select(31) }}

• -1
• 0
• 1
• 未计算

32. 阅读代码可知，当两个点之间的数为（）时，cmp函数将无法得到正确的结果。

{{ select(32) }}

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

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

（1）题目描述： 输入$n(3 \leq n \leq 2 \times 10^5)$和长为n的数组$a(1 \leq a[i] \leq 1 \times 10^9)$。你需要从a中恰好删除一个数，得到长为n-1的数组a'。然后生成一个长为n-2的数组b，其中$b[i] = GCD(a'[i], a'[i+1])$。你需要让数组b是非降序列，即$b[i] \leq b[i+1]$。能否做到？输出YES或NO。

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;
```cpp
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     return;
32 }
33
34 int main() {
35     int t = 1;
36     // cin >> t;
37     while (t--)
38         solve();
39     return 0;
40 }

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^6)$。 对于数组B，如果满足$B[0] + 1 = len(B)$，那么称数组B为“块”。对于数组A，如果可以将其划分成若干个“块”，那么称数组A是合法的。 例如$A = [3, 3, 4, 5, 2, 6, 1]$是合法的，因为$A = [3, 3, 4, 5] + [2, 6, 1]$，这两段都是块。 把数组a变成合法数组，至少要删除多少个元素？

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]