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

1. 在NOI Linux 2.0环境下，以下哪条命令能够实现指定C++特定版本进行编译？（ ） {{ select(1) }}

• g++ -g -std=c++11 main.cpp -o main
• g++ -g -std=c++14 main.cpp -o main
• g++ -g -std=C++17 main.cpp -o main
• g++ -g -std=C++20 main.cpp -o main

2. 下面有关格雷码的说法中，错误的是（ ）。 {{ select(2) }}

• 在格雷码中，任意两个相邻的代码在二进制下有且仅有一位不同
• 长度为3的格雷码依次为000, 001, 010, 011, 100, 101, 110, 111
• 格雷码由贝尔实验室的Frank Gray在20世纪40年代提出
• 格雷码是一种可靠性编码

3. 以下哪个选项不属于STL中链表的操作函数？（ ） {{ select(3) }}

• resize
• push_back
• pop
• front

4. 下列关于namespace的说法中错误的是（ ）。 {{ select(4) }}

• namespace可以嵌套，例如namespace X { namespace Y { int i; }}
• namespace只可以在全局定义
• namespace中可以存放变量和函数
• 如果程序中使用using命令同时引用了多个namespace，并且namespace中存在相同的函数，会出现程序错误

5. 某哈夫曼树（根结点为第1层）共有7个叶子结点，这棵树的高度不可能是（ ）。 {{ select(5) }}

• 8
• 6
• 5
• 4

6. 现有一段3分钟的视频，它的播放速度是每秒24帧图像，每帧图像是一幅分辨率为$1920像素×1080像素$的32位真彩色图像。请问要存储这段原始无压缩视频，大约需要多少字节的存储空间？（ ） {{ select(6) }}

• 286.6 GB
• 71.6 GB
• 142.3 GB
• 35.8 GB

7. 在桶排序算法中，对于一个长度为n的序列，设桶的个数为m，在桶内使用插入排序，则其平均时间复杂度是（ ）。 {{ select(7) }}

• $O(nm)$
• $O\left(n^2\right)$
• $O\left(n + m + \frac{n^2}{m}\right)$
• $O(n + m)$

8. 以下判断一个整数n是否为奇数的代码中，错误的是（ ）。 {{ select(8) }}

• if (n % 2)
• if (n & 1)
• if (n % 2 == 1)
• if (!(n % 2 == 0))

9. 下面关于计算机软硬件历史的说法中，错误的是（ ）。 {{ select(9) }}

• 第三代计算机使用了集成电路，降低了计算机的空间占用和成本
• 20世纪80年代，微软公司开发出了MS-DOS操作系统
• 图灵发明了名为“巨人”的计算机，破解了德军的ENIGMA密码
• 第一台基于冯·诺依曼思想的计算机是1946年发明的ENIAC

10. p, q为质数，p整除7q + 1，q整除7p + 1，则有（ ）组不同的p和q组合。 {{ select(10) }}

• 4
• 6
• 8
• 10

11. KMP算法属于与（ ）相关的算法。 {{ select(11) }}

• 并查集
• 线段树
• 字符串
• 二分图

12. 若集合$I = \{1, 2, 3, 4, 5\}$，选择集合I的两个非空子集A和B，要使得B中最小的数大于A中最大的数，一共有（ ）种不同的选择。 {{ select(12) }}

• 50
• 48
• 47
• 49

13. 如果今天是星期一，那么对于任意正整数n，经过$2^{2025n} + 2023n + 2025$天后是（ ）。 {{ select(13) }}

• 星期四
• 星期三
• 星期二
• 星期一

14. 6名参加信息学竞赛的学生A、B、C、D、E、F站成一排拍照，要求A一定要在B的左边（不一定相邻），一共有（ ）种排列方法。 {{ select(14) }}

• 720
• 360
• 480
• 540

15. 设甲、乙两人每次射击命中目标的概率分别为0.75和0.8，且各次射击相互独立，若按甲、乙、甲、乙…的次序轮流射击，直到有一人击中目标就停止射击，则停止射击时，甲射击了两次的概率是（ ）。 {{ select(15) }}

• 7/120
• 11/240
• 19/400
• 23/480

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

(1)

01 #include <bits/stdc++.h>
02 
03 const int Max = 100005;
04 long long t, n, p[Max], s[Max], a[Max], E;
05 
06 int main() {
07     scanf("%lld", &t);
08     while (t--) {
09         scanf("%lld", &n);
10         for (int i = 1; i <= n; i++)
11             scanf("%lld", &p[i]);
12         for (int i = 1; i <= n; i++)
13             scanf("%lld", &s[i]);
14         for (int i = 0; i <= n; i++)
15             if (p[i] != -1 && s[i + 1] != -1) {
16                 E = p[i] ^ s[i + 1];
17                 break;
18             }
19         for (int i = 0; i <= n; i++) {
20             if (p[i] == -1 && s[i + 1] != -1)
21                 p[i] = E ^ s[i + 1];
22             else if (p[i] != -1 && s[i + 1] == -1)
23                 s[i + 1] = E ^ p[i];
24             else if (p[i] == -1 && s[i + 1] == -1)
25                 p[i] = 1;
26             if (i) printf("%lld ", p[i] ^ p[i - 1]);
27         }
28         puts("");
29     }
30 }

保证每组数据均有$-1 ≤ p_i, s_i ≤ 2^{60}$，且$\sum [p_i = -1] + \sum [s_i = -1] = n$，回答下列问题。

■ 判断题

16. 如果p[i]是int类型，则与原程序相比，不一定能输出正确答案。（ ） {{ select(16) }}

• 正确
• 错误

17. 将第28行中的puts()函数改成putchar()，程序的输出不变。（ ） {{ select(17) }}

• 正确
• 错误

18. （2分）当$n = 1$时，程序输出p[1]与s[1]中非-1的那个数。（ ） {{ select(18) }}

• 正确
• 错误

19. （2分）E不会大于p[i]和s[i]的最大值。（ ） {{ select(19) }}

• 正确
• 错误

■ 选择题

20. 若程序输入为

1
4
-1 -1 -1 -1
2 3 5 7

则程序输出为（ ）。 {{ select(20) }}

• 1 6 2 7
• 7 2 6 1
• 2 6 1 2
• 2 1 6 2

21. 若程序输入为

1
4
-1 343 67 -1
31 78 -1 -1 3333

则程序输出中的第三个数为（ ）。 {{ select(21) }}

• 3333
• 333
• 3178
• 267

(2)

01 #include <bits/stdc++.h>
02 using namespace std;
03 const int NR = 1e3 + 10;
04 int n, s, t, ans = 1000, a[NR], b[NR], f[2][NR];
05 
06 int main() {
07     cin >> n >> s >> t;
08     for (int i = 1; i <= n; i++) cin >> a[i] >> b[i];
09     if (s >= t) {
10         puts("0");
11         return 0;
12     }
13     memset(f[0], -999999, sizeof(f[0])); f[0][0] = s;
14     for (int i = 0; i < ans; i++) {
15         int now = i % 2, pre = now ^ 1;
16         for (int j = 0; j <= t; j++)
17             for (int k = 1; k <= n; k++)
18                 if (f[now][j] >= a[k]) {
19                     if (j + b[k] <= t)
20                         f[now][j + b[k]] = max(f[now][j + b[k]], f[now][j] - a[k]);
21                     else ans = i + 1;
22                 }
23         memset(f[pre], -999999, sizeof(f[pre]));
24         for (int j = 0; j <= t; j++) {
25             if (f[now][j] + j >= t) ans = i + 1;
26             else f[pre][j] = f[now][j] + j;
27         }
28     }
29     cout << ans << endl;
30     return 0;
31 }

假设数据满足$1 ≤ n ≤ 100$，$1 ≤ s, t ≤ 1000$，$1 ≤ a_i, b_i ≤ 2^{31}$，回答下列问题。

■ 判断题（每题2分）

22. 将第23行中的-999999改为-1，程序输出不变。（ ） {{ select(22) }}

• 正确
• 错误

23. 本段代码的时间复杂度为$O(n^3)$。（ ） {{ select(23) }}

• 正确
• 错误

24. 本段代码使用了滚动数组优化f数组空间。（ ） {{ select(24) }}

• 正确
• 错误

■ 选择题

25. 假设某组输入为

1 1 8
1 1

则程序输出为（ ）。 {{ select(25) }}

• 1
• 2
• 3
• 4

26. 假设某组输入为

2 1 8
1 1
2 8

则程序输出为（ ）。 {{ select(26) }}

• 1
• 2
• 3
• 4

27. 如果删除第23行代码，则在输入相同时，程序输出与原来相比（ ）。 {{ select(27) }}

• 变大或不变
• 不变
• 变小或不变
• 以上情况都有可能

(3)

01 #include <bits/stdc++.h>
02 
03 #define int long long
04 using namespace std;
05 
06 const int INF = 3e5 + 5;
07 
08 string s1;
09 int sum[INF][35], t[35], la[35], la1[35];
10 
11 int check(int l, int r) {
12     int ans = 0;
13     for (int i = 0; i < 26; i++)
14         if (sum[r][i] - sum[l - 1][i]) ans++;
15     return ans;
16 }
17 
18 signed main() {
19     ios::sync_with_stdio(false);
20     cin >> s1; int len = s1.size(); s1 = " " + s1;
21     for (int i = 1; i <= len; i++) {
22         for (int j = 0; j < 26; j++)
23             sum[i][j] = sum[i - 1][j] + ((s1[i] - 'a') == j);
24     }
25     for (int i = 1; i <= 26; i++) {
26         int j1 = 0, j2 = 0, sum1 = 0, sum2 = 0;
27         memset(la, 0, sizeof(la));
28         memset(la1, 0, sizeof(la1));
29         for (int k = 1; k <= len; k++) {
30             j1 = max(j1, k - 1); j2 = max(j2, k - 1);
31             while (j1 + 1 <= len && sum1 <= i) {
32                 if (la[s1[j1 + 1] - 'a'] == 0 && sum1 == i) break;
33                 la[s1[j1 + 1] - 'a']++;
34                 if (la[s1[j1 + 1] - 'a'] == 1) sum1++;
35                 j1++;
36             }
37             while (j2 + 1 <= len && sum2 < i) {
38                 la1[s1[j2 + 1] - 'a']++;
39                 if (la1[s1[j2 + 1] - 'a'] == 1) sum2++;
40                 j2++;
41             }
42             if (sum2 == i && sum1 == i) t[i] += j1 - j2 + 1;
43             la1[s1[k] - 'a']--;
44             if (la1[s1[k] - 'a'] == 0) sum2--;
45             la[s1[k] - 'a']--;
46             if (la[s1[k] - 'a'] == 0) sum1--;
47         }
48     }
49     cout << check(1, len) << "\n";
50     for (int i = 1; i <= 26; i++)
51         if (t[i]) cout << t[i] << "\n";
52     return 0;
53 }

输入数据满足$1 \leqslant |s1| \leqslant 10^5$，且为小写字母组成的字符串。

■ 判断题

28. 程序第一个输出的数字可能为0。（ ） {{ select(28) }}

• 正确
• 错误

29. 在第9行声明数组时，如果将声明t[35]改成t[25]，程序一定发生运行错误。（ ） {{ select(29) }}

• 正确
• 错误

■ 选择题

30. 若程序输入abca，则程序输出的最大值是（ ）。 {{ select(30) }}

• 1
• 2
• 3
• 4

31. 程序在第50行输出的数字之和与字符串s1长度n的关系为（ ）。 {{ select(31) }}

• 等于$(n*(n+1))/2$
• 小于$(n*(n+1))/2$
• 大于$(n*(n+1))/2$
• 以上都有可能

32. 当输入一个长度为n的字符串时，代码中j1和j2移动的最大次数约为（ ）。 {{ select(32) }}

• n
• n*n
• 26 * n
• 26*n*n

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

(1) 题目描述： 有一个H行W列的网格，每一格都被涂成黑色或白色。 形式化地，有H个长为W的字符串S₁, S₂, ..., Sₕ。若Sᵢⱼ是#，则网格中第i行第j列被涂为黑色；若Sᵢⱼ是.，则网格中第i行第j列被涂为白色。 若有一条从黑色方格到达白色方格的路径，途中只沿水平或垂直方向移动，所经相邻方格颜色不同，我们将这条路径称为合法路径。 求网格中有多少合法路径。

01 #include <bits/stdc++.h>
02 #define ll long long
03 #define ri register
04 #define all(x) x.begin(), x.end()
05 using namespace std;
06 const int N = 401, M = N*N;
07 int n, m, f[M], g[M], sz[M];
08 ll ans;
09 char a[N][N];
10 inline int ord(int x, int y) { ①; } // 压成一维
11 inline int find(int z) { return ②; } // 并查集
12 inline void merge(int x, int y) {
13     x = find(x), y = find(y);
14     if (x == y) return;
15     f[x] = y, sz[y] += sz[x], g[y] += g[x];
16     sz[x] = g[x] = 0;
17 }
18 int main() {
19     scanf("%d%d", &n, &m);
20     for (int i = 1; i <= n; i++) scanf("%s", a[i] + 1);
21     for (int i = 1; i <= n; i++)
22         for (int j = 1; j <= m; j++)
23             if (③) ④, g[ord(i, j)]++;
24     for (int i = 1; i <= n*m; i++) sz[i] = 1, f[i] = i;
25     for (int i = 1; i <= n; i++)
26         for (int j = 1; j <= m; j++) {
27             if (i < n && a[i][j] == a[i+1][j])
28                 merge(ord(i, j), ord(i+1, j));
29             if (j < m && a[i][j] == a[i][j+1])
30                 merge(ord(i, j), ord(i, j+1));
31         }
32     for (int i = 1; i <= n*m; i++)
33         if (f[i] == i) ans += ⑤;
34     printf("%lld\n", ans);
35     return 0;
36 }

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

• y * m + x
• (y - 1) * m + x
• (x - 1) * m + y
• (x - 1) * n + y

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

• f[z] ? z : f[z] = find(f[z])
• f[z] == z ? z : f[z] = find(f[z])
• z ? f[z] = find(z) : z
• z ? f[z] = find(f[z]) : z

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

• (i + j) == 1
• (i + j) % 2 == 0
• (i - j) % 2 == 1
• (i * j) % 2 == 0

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

• a[i][j] = (a[i][j] == '#') ? '.' : '#'
• a[i][j] = (a[i][j] == '.') ? '.' : '#'
• a[i][j] = ~a[i][j]
• a[i][j]

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

• (ll)g[i] * sz[i]
• (ll)g[i] * (sz[i] - g[i])
• (ll)g[i] * (sz[i] - 1)
• (ll)g[i]

(2) 题目描述： 给定n个由大写字母组成的字符串，选择尽量多的串，使得每个大写字母都出现偶数次。$n ≤ 24$ （提示：采用折半搜索策略。）

01 #include <bits/stdc++.h>
02 #define MAXN 35
03 #define MAXM 10005
04 using namespace std;
05 map<int, int> m;
06 int n, has[MAXN];
07 char ch[MAXM];
08 
09 int Lowbit(int x) {
10     return x & -x;
11 }
12 
13 int Calc(int x) {
14     int res = 0;
15     for (①) res++;
16     return res;
17 }
18 
19 int main() {
20     while (cin >> n) {
21         m.clear();
22         memset(has, 0, sizeof(has));
23         for (int i = 0; i < n; i++) {
24             scanf("%s", ch + 1);
25             int len = strlen(ch + 1);
26             for (int j = 1; j <= len; j++) has[i] ^= 1 << (ch[j] - 'A');
27         }
28         int ans = 0, n1 = ②, n2 = n - n1;
29         for (int i = 0; i < (1 << n1); i++) {
30             int x = 0;
31             for (int j = 0; j < n1; j++) if (i & (1 << j)) x ^= has[j];
32             if (③) m[x] = i;
33         }
34         for (int i = 0; i < (1 << n2); i++) {
35             int x = 0;
36             for (int j = 0; j < n2; j++) if (i & (1 << j)) x ^= has[n1 + j];
37             if (④) ans = max(ans, Calc((i << n1) | m[x]));
38         }
39         printf("%d\n", Calc(ans));
40         for (int i = 0; i < n; i++) if (⑤) printf("%d ", i + 1);
41         puts("");
42     }
43     return 0;
44 }

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

• x; x <= n; x += Lowbit(x)
• x; x <= n; x -= Lowbit(x)
• x; x; x -= Lowbit(x)
• x; x; x += Lowbit(x)

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

• 1
• n / 2
• n - 1
• n

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

• !m.count(x) || Calc(m[x]) < Calc(i)
• !m.count(x) || Calc(m[x]) > Calc(i)
• m.count(x) && Calc(m[x]) < Calc(i)
• m.count(x) && Calc(m[x]) > Calc(i)

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

• m.count(x) && Calc(ans) < Calc((i << n1) | m[x])
• m.count(x) || Calc(ans) < Calc((i << n1) | m[x])
• m.count(x) && Calc(ans) > Calc((i << n1) | m[x])
• m.count(x) || Calc(ans) > Calc((i << n1) | m[x])

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

• ans & (1 << i)
• ans & (1 << (i - 1))
• ans | (1 << i)
• ans | (1 << (i - 1))

---