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

1. 以下列扩展名结尾的文件，不是多媒体文件的是（）

{{ select(1) }}

• mp3
• txt
• avi
• jpg

2. 以下关于链表和数组的描述中，错误的是（）

{{ select(2) }}

• 数组和链表都可以排序
• 数组中查询元素的效率比较高
• 链表中插入和删除元素的效率比较高
• 向量和静态数组一样，不能动态调整数组大小

3. 与C++语言中的cout << a > b ? 'a' : 'b';功能类似的是（）

{{ select(3) }}

• 顺序结构
• 循环结构
• 条件结构
• 递推函数

4. 下面的C++代码中data占用（）字节内存空间

union Data {
    int no;
    double score;
    char name[6];
};
union Data data;

{{ select(4) }}

• 4
• 8
• 18
• 6

5. 学号为1到30的幼儿园小朋友顺时针围成一圈，从1号小朋友开始按顺时针方向报数，报数从0开始，依次为0，1，2，3，…，29，30，31，32，…一圈又一圈，问数到数字n的小朋友的学号是多少？（）

{{ select(5) }}

• n % 30 + 1
• (n + 1) % 30
• (n + 1) % 30 + 1
• n % 30

6. 以下哪个不属于STL模板中队列的操作函数？（）

{{ select(6) }}

• push
• pop
• empty
• top

7. 在C++语言中，（）算法的时间复杂度是$O(n \log n)$

{{ select(7) }}

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

8. 以下关于字符串的判定语句中正确的是（）

{{ select(8) }}

• 字符串一般以字符'\0'结尾
• 串的长度必须大于零
• string s;中定义的s也可以看作字符数组，首字母是s[0]
• 全部都由空格字符组成的串就是空串

9. 以下算法中，（）算法用到了栈

{{ select(9) }}

• BFS
• 二分查找
• DFS
• 贪心

10. 32位计算机系统中一个非负长整型指针变量unsigned long long *p占（）字节

{{ select(10) }}

• 1
• 2
• 8
• 4

11. 某山峰型数列有1~2025共2025个各不相同的数，先是奇数由小到大，后是偶数由大到小，即1，3，5，7，9，…，2023，2025，2024，2022，2020，…，8，2。现要对该数列进行检索，查找某正整数x的下标（x为1~2025中的某正整数，包含1和2025）最多检索（）次即可

{{ select(11) }}

• 2025
• 11
• 10
• 9

12. 在C++程序中，Lowbit(x)函数返回整数x在二进制表示下最低一位1以及后续0一起表示的数字，如Lowbit(12) = 4。下面的表达式中，（）能得到相同的结果

{{ select(12) }}

• x ^ (x - 1)
• x & (x - 1)
• x & (~x + 1)
• x | (x - 1)

13. 某二叉树的中序遍历序列为BDCEAFHG，后序遍历序列为DECBHGFA，其前序遍历序列为（）

{{ select(13) }}

• ABCDEFGH
• ABDCEFHG
• ABCDFEHG
• ABDCEFGH

14. 有5条线段，长度分别为1，3，5，7，9，从中任取3条能构成一个三角形的概率为（）

{{ select(14) }}

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

15. 对于非负整数组$\{x, y, z\}$，满足$x + 2y + 3z = 100$的非负整数解组数为（）个

{{ select(15) }}

• 886
• 885
• 884
• 883

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

（1）

01 #include <bits/stdc++.h>
02 using namespace std;
03 const int N = 2e4 + 5, inf = 2e9 + 7;
04 int n, a[N], ans = inf;
05 int main() {
06     scanf("%d", &n);
07     for (int i = 1; i <= n; i++)
08         scanf("%d", &a[i]);
09     sort(a + 1, a + n + 1);
10     for (int i = 2; i <= n; i += 2) {
11         int mi = inf, ma = -inf, x = 0;
12         for (int j = 1; j <= i; ++j) {
13             x = a[j] + a[i - j + 1];
14             mi = min(mi, x), ma = max(ma, x);
15         }
16         if (i != n)
17             ans = min(ans, max(a[n], ma) - min(a[i + 1], mi));
18         else
19             ans = min(ans, ma - mi);
20     }
21     return printf("%d\n", ans), 0;
22 }

判断题

16. 若将头文件#include <bits/stdc++.h>改成#include <iostream>，程序仍能正常运行。（）

{{ select(16) }}

• 正确
• 错误

17. 当n为偶数时，第16行的判断条件i != n永远为假。（）

{{ select(17) }}

• 正确
• 错误

18. 若输入的数组a中所有元素均相等，则输出为0。（）

{{ select(18) }}

• 正确
• 错误

选择题

19. 若输入4 1 3 6 7，则输出为（）

{{ select(19) }}

• 0
• 1
• 2
• 3

20. （4分）若输入7 2 8 9 15 17 18 16，则输出为（）

{{ select(20) }}

• 2
• 3
• 4
• 5

（2）

01 #include <bits/stdc++.h>
02 using namespace std;
03 int n, m, k, l, r, mid;
04 int check(int g) {
05     int st = 1, ed = m, cnt = 0;
06     while (st <= n && ed >= 1) {
07         if (st * ed > g)
08             ed--;
09         else {
10             cnt += ed;
11             st++;
12         }
13     }
14     return cnt >= k;
15 }
16 int main() {
17     scanf("%d%d%d", &n, &m, &k);
18     l = 1, r = n * m;
19     while (l < r) {
20         mid = (l + r) / 2;
21         if (check(mid)) r = mid;
22         else l = mid + 1;
23     }
24     cout << l << endl;
25 }

已知$k \leq nm$，保证n，m同阶，完成以下问题。

判断题

21. 每次运行check时，第7行必定运行n次。（）

{{ select(21) }}

• 正确
• 错误

22. 如果保证$m = 1$，则输出一定为$k$。（）

{{ select(22) }}

• 正确
• 错误

23. 若将第21行中的r = mid改成r = mid - 1，程序输出一定不变。（）

{{ select(23) }}

• 正确
• 错误

24. 第24行可以改成cout << r << endl;。（）

{{ select(24) }}

• 正确
• 错误

选择题

25. 该程序的时间复杂度为（）

{{ select(25) }}

• $O(n)$
• $O(n \log n)$
• $O(n^2)$
• $O(nk)$

26. 若输入为2 3 4，则输出为（）

{{ select(26) }}

• 1
• 2
• 3
• 6

（3）

01 #include <bits/stdc++.h>
02 using namespace std;
03 const int N = 10, dx[10] = {0, 1, 0, -1, 0}, dy[10] = {0, 0, 1, 0, -1};
04 int n, m, ans;
05 char c[N][N];
06 void dfs(int x) {
07     if (!x) return ++ans, void();
08     vector<int> v; v.clear();
09     for (int i = 1; i <= n; ++i)
10         for (int j = 1; j <= n; ++j)
11             if (c[i][j] == '.') {
12                 bool flag = 0;
13                 for (int k = 1; k <= 4; ++k) {
14                     int tx = i + dx[k], ty = j + dy[k];
15                     flag |= tx >= 1 && tx <= n && ty >= 1 && ty <= n && c[tx][ty] == '1';
16                 }
17                 if (flag) {
18                     v.push_back(i * 10 + j), c[i][j] = '1', dfs(x - 1), c[i][j] = '#';
19                 }
20             }
21     if (!v.empty())
22         for (int i = 0; i < v.size(); ++i)
23             c[v[i] / 10][v[i] % 10] = '.';
24 }
25 int main() {
26     scanf("%d%d", &n, &m);
27     for (int i = 1; i <= n; ++i)
28         scanf("%s", c[i] + 1);
29     for (int i = 1; i <= n; ++i)
30         for (int j = 1; j <= n; ++j)
31             if (c[i][j] == '.')
32                 c[i][j] = '1', dfs(m - 1), c[i][j] = '#';
33     return printf("%d\n", ans), 0;
34 }

判断题

27. 将第18行中的c[i][j] = '#'去除，结果一定不变。（）

{{ select(27) }}

• 正确
• 错误

28. 第6行运行的次数不超过$n^2 4^m$。（）

{{ select(28) }}

• 正确
• 错误

选择题

29. 若输入为2 2 #. ..，则输出为（）

{{ select(29) }}

• 0
• 1
• 2
• 3

30. 若输入为3 5 #.# ... #.，则输出为（）

{{ select(30) }}

• 2
• 3
• 4
• 5

31. （4分）若$n = 3$，$m = 3$，则输出的最大值为（）

{{ select(31) }}

• 16
• 18
• 22
• 26

32. 若$n = 4$，$m = 13$，则输出的最大值为（）

{{ select(32) }}

• 488
• 496
• 512
• 560

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

（1）题目描述： 给定两个由小写字母构成的字符串s1和s2，同时给定一个由数字1，2，3…组成的排列operation。按该排列顺序依次删除字符串s1相应位置上的字母，在删除过程中，约定各个字符的位置不变。请计算最多可以删除几次，字符串s1中仍然包含字符串s2（即字符串s2仍然是字符串s1的子串）。

01 #include <bits/stdc++.h>
02 using namespace std;
03 const int N = 2e5 + 5;
04 bool book[N];
05 char s1[N], s2[N];
06 vector<int> num;
07 int n = 1, len1, len2, ans, operation[N];
08 bool check(int x) {
09     num.clear();
10     for (int i = x + 1; i <= n; i++)
11         if (①)
12             num.push_back(operation[i]);
13     sort(num.begin(), num.end());
14     int i = 0, j = 1;
15     while (②)
16         j += ③;
17     return j == len2 + 1;
18 }
19 inline void fuc(int l, int r) {
20     if (④) return;
21     int mid = (l + r) >> 1;
22     if (check(mid)) ans = mid, fuc(mid + 1, r);
23     else fuc(l, mid - 1);
24 }
25 int main() {
26     scanf("%s", s1 + 1);
27     scanf("%s", s2 + 1);
28     len1 = strlen(s1 + 1);
29     len2 = strlen(s2 + 1);
30     while (⑤) ++n;
31     n--;
32     for (int i = 1; i <= len2; i++)
33         book[int(s2[i])] = true;
34     fuc(1, n);
35     printf("%d\n", ans);
36     return 0;
37 }

33. ①处应填（）

{{ select(33) }}

• book[s1[operation[i]]]
• book[s1[i]]
• !book[s1[operation[i]]]
• !book[s1[i]]

34. ②处应填（）

{{ select(34) }}

• i < num.size() && j <= len2
• i <= num.size() && j <= len2
• i <= num.size() && j < len2
• i < num.size() && j < len2

35. ③处应填（）

{{ select(35) }}

• s1[num[i++]] == s2[j]
• s1[num[++i]] == s2[j]
• s1[num[i++]] == s2[j++]
• s1[num[++i]] == s2[j++]

36. ④处应填（）

{{ select(36) }}

• l >= r
• l == r
• l > r
• l^r

37. ⑤处应填（）

{{ select(37) }}

• scanf("%d", operation[n])
• ~scanf("%d", operation[n])
• ~(cin >> operation[n])
• !scanf("%d", operation[n])

（2）题目描述： 如果存在一个长度为n的排列（即该排列由1，2，3，…，n这n个数字各出现一次组成），对于所有满足(2 \leq i \leq n - 1)的整数i，都有(p_i \leq p_{i-1})，(p_i \leq p_{i+1})或者(p_i \geq p_{i-1})，(p_i \geq p_{i+1})成立，则称这个序列为一个山峰山谷序列。 对所有长度为n的山峰山谷序列排序，求字典序第k大的排列。 (dp_{i,j,0/1})表示长度为i的排列中第一个数为j，其中第一个数小于/大于第二个数。

01 #include <bits/stdc++.h>
02 using namespace std;
03 const int N = 105;
04 int n, k, dp[N][N][2], ans[N], vis[N];
05 signed main() {
06     scanf("%d%d", &n, &k);
07     dp[1][1][0] = dp[1][1][1] = 1;
08     dp[2][1][0] = dp[2][2][1] = 1;
09     for (int i = 2; i < n; ++i)
10         for (int j = 1; j <= i; ++j)
11             for (int k = 1; k <= i + 1; ++k)
12                 if (①) dp[i + 1][k][1] += dp[i][j][0];
13                 else ②;
14     for (int i = 1; i <= n; ++i) {
15         int las = 0, mk = 1;
16         if (i > 2 && ans[i - 1] < ans[i - 2])
17             mk = ③;
18         for (int j = mk; j <= n; ++j) if (!vis[j]) {
19             int cnt = 0;
20             for (int k = 1; k <= n; ++k) if (!vis[k]) cnt++;
21             int x = ④;
22             if (i != 1) x += dp[n][j][0];
23             if (x >= k) { las = j; break; }
24             ⑤;
25         }
26         ans[i] = las, vis[las] = 1;
27     }
28     for (int i = 1; i <= n; ++i)
29         printf("%d", ans[i]);
30     return 0;
31 }

38. ①处应填（）

{{ select(38) }}

• j < k
• j < n k
• 1 < k
• i < mk

39. ②处应填（）

{{ select(39) }}

• dp[i + 1][k][1] += dp[i][j][0]
• dp[i + 1][k][0] += dp[i][j][1]
• dp[i + 1][j][1] += dp[i][k][0]
• dp[i + 1][j][0] += dp[i][k][1]

40. ③处应填（）

{{ select(40) }}

• ans[i - 1] + 1
• ans[i - 2] + 1
• i + 1
• ans[i - 1]

41. ④处应填（）

{{ select(41) }}

• dp[n - i + 1][cnt][ans[i - 1] < j]
• dp[n - i + 1][cnt][ans[i - 1] > j]
• dp[n - i + 1][j - cnt][ans[i - 1] > j]
• dp[n - i + 1][j - cnt][ans[i - 1] < j]

42. ⑤处应填（）

{{ select(42) }}

• k -= x
• k -= x * (n - i + 1)
• k -= x * cnt
• k -= x * mk

---