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

1. 在NOI Linux系统终端的调试工具GDB的使用中，以下（ ）命令可以用来查看某个变量的值，并一直显示直到关闭或者程序结束。 {{ select(1) }}

• print
• printf
• show
• display

2. 以下关于数据结构的表述中不恰当的一项是（ ）。 {{ select(2) }}

• 并查集常用森林来表示
• AVL树插入破坏平衡的情况只有两种类型--LR和RL
• 线段树维护的常见区间信息包括区间最大值、区间最小值、区间和等
• 树状数组是主要用于前缀信息维护的一维数组

3. 在C++语言中，以下（ ）函数声明是合法的。 {{ select(3) }}

• int InsertSort(char a[][], int n);
• int InsertSort(char a[10][], int n);
• int InsertSort(char a[][20], int n);
• int InsertSort(char[,] a, int n);

4. 对于给定的代码，调用fun(5,6)得到的结果是（ ）。

int fun(int n, int m) {
    if (1 == n) return 1;
    else if (1 == m) return n;
    else return fun(n - 1, m) + fun(n, m - 1);
}

{{ select(4) }}

• 210
• 126
• 252
• 240

5. 二项展开式$(x + y)^5$的系数正好满足杨辉三角的规律，二项展开式中$x^3y^2$项的系数是（ ）。 {{ select(5) }}

• 5
• 9
• 10
• 8

6. 以下不属于TCP/IP协议族中网络协议的是（ ）。 {{ select(6) }}

• IMAP
• HTML
• TELNET
• UDP

7. 构建具有n个元素的笛卡儿树的时间复杂度是（ ）。 {{ select(7) }}

• $O(\log n)$
• $O(n)$
• $O\left(n^2\right)$
• $O(n \log n)$

8. 考虑对n个数进行排序，以下方法中最坏情况下时间复杂度最差的排序方法是（ ）。 {{ select(8) }}

• 桶排序
• 快速排序
• 堆排序
• 归并排序

9. 下面关于序列$\{2, 7, 1, 5, 6, 4, 3, 8, 9\}$的说法中正确的是（ ）。 {{ select(9) }}

• $\{6, 4, 3\}$是它的唯一最长连续下降子序列
• $\{1, 5, 6\}$是它的唯一最长连续上升子序列
• $\{1, 5, 6, 8, 9\}$是它的唯一最长上升子序列
• $\{7, 5, 4, 3\}$是它的唯一最长下降子序列

10. 给定地址区间为0~13的哈希表，哈希函数为$h(x) = x \% 13$，采用线性探查的冲突解决策略（如果出现冲突情况，会往后探查第一个空的地址存储；若地址13冲突了，则从地址0重新开始探查）。哈希表初始为空表，依次存储(65, 34, 27, 80, 22, 57, 78)后，请问78存储在哈希表的哪个地址中？（ ） {{ select(10) }}

• 1
• 2
• 3
• 4

11. 对于一个无向连通图G，顶点之间的强连通关系不具有（ ）。 {{ select(11) }}

• 传递性
• 自反性
• 对称性
• 偏序性

12. 以下C++程序运行后的输出结果为（ ）。

#include <bits/stdc++.h>
using namespace std;
int sum = 0;
int main() {
    for (int i = 0; i <= 10; ++i)
        for (int j = 0; j <= 10; ++j)
            for (int k = 0; k <= 10; ++k)
                if (i + j + k == 15)
                    sum++;
    cout << sum << endl;
    return 0;
}

{{ select(12) }}

• 84
• 90
• 91
• 96

13. 下面的程序使用出边的邻接表表示有向图，则下列选项中哪个是它表示的图？（ ）

#include <bits/stdc++.h>
struct Edge {
    int e;
    Edge *next;
};
struct Node {
    Edge *first;
};
int main() {
    Edge e[5] = {{1, nullptr}, {2, &e[2]}, {3, nullptr}, {3, nullptr}, {0, nullptr}};
    Node n[4] = {&e[0], &e[1], &e[3], &e[4]};
    // 处理功能
    return 0;
}

{{ select(13) }}

• 

• 

• 

• 

14. 从不超过30的质数中随机抽取2个质数组成质数对$(m, n)$，其中$m ≤ n$，则这2个质数组成的质数对中满足$n - m ≤ 3$的概率为（ ）。 {{ select(14) }}

• 2/15
• 17/30
• 11/15
• 7/12

15. 在4×4方格表中，将若干格子染成黑色，每行每列恰有两个黑色格子的染色方法数为（ ）。 {{ select(15) }}

• 90
• 72
• 84
• 96

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

(1)

01 #include <bits/stdc++.h>
02 using namespace std;
03 const int N = 3e5 + 10;
04 int n, k; char temp;
05 bool a[N]; int dp[N];
06 int sum1[N]; int sum2[N];
07 int Stack[N]; int head = 1; int tail = 0;
08 int main() {
09     scanf("%d%d", &n, &k);
10     getchar();
11     for (int i = 1; i <= n; i++) {
12         temp = getchar();
13         if (temp == 'H') a[i] = 0, sum1[i]++;
14         else a[i] = 1, sum2[i]++;
15         sum1[i] += sum1[i - 1]; sum2[i] += sum2[i - 1];
16     }
17     Stack[++tail] = 0;
18     for (int i = 1; i <= n; i++) {
19         while (head <= tail && i - Stack[head] > k) ++head;
20         dp[i] = dp[Stack[head]] + (sum1[i] - sum2[i]);
21         while (head <= tail && ((dp[i] < dp[Stack[tail]]) || 
22             (dp[i] == dp[Stack[tail]] && (sum1[i] - sum2[i]) <= (sum1[Stack[tail]] - sum2[Stack[tail]])))
23             tail--;
24         Stack[++tail] = i;
25     }
26     printf("%d", dp[n]);
27     return 0;
28 }

假设输入满足$1 ≤ k ≤ n ≤ 3e5$，s的长度为n且只含有'H'和'G'。

■ 判断题

16. 这段代码的时间复杂度为$O(N)$。（ ） {{ select(16) }}

• 正确
• 错误

17. 代码运行到第20行时，head永远小于tail。（ ） {{ select(17) }}

• 正确
• 错误

18. 删除第10行代码，程序运行结果可能改变。（ ） {{ select(18) }}

• 正确
• 错误

■ 选择题

19. 若程序输入

5 2
GGHGG

则程序的输出是（ ）。 {{ select(19) }}

• 0
• 1
• 2
• 3

20. 若程序输入

7 2
HGHGGHG

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

• 1
• 2
• 3
• 4

21. 程序运行到最后一行时，以下哪个选项不成立？（ ） {{ select(21) }}

• sum1[n] + sum2[n] == n
• tail - head <= k
• stack[1] = 0
• dp[n]不一定是dp数组中的最小值

(2)

01 #include <bits/stdc++.h>
02 #define int long long
03 using namespace std;
04 int n, a[1000010], b[1000010], now, ans, front, N = 1000000, c[3000010], id;
05 
06 int lowbit(int x) { return x & -x; }
07 
08 void update(int x, int v) {
09     x += N;
10     for (; x <= 2 * N; x += lowbit(x)) c[x] += v;
11 }
12 
13 int sum(int x) {
14     x += N;
15     int ans = 0;
16     for (; x; x -= lowbit(x)) ans += c[x];
17     return ans;
18 }
19 
20 signed main() {
21     ios::sync_with_stdio(0);
22     cin.tie(0), cout.tie(0);
23     cin >> n;
24     for (int i = 0; i < n; i++) {
25         cin >> a[i];
26         b[i] = a[i] - (i + 1);
27         now += abs(b[i]);
28         update(b[i], 1);
29     }
30     ans = now, id = 0;
31     for (int i = 1; i < n; i++) {
32         front = (front - 1 + n) % n;
33         b[front] -= i - 1;
34         now -= abs(b[front]);
35         update(b[front], -1);
36         b[front] += n - 1;
37         now += abs(b[front]);
38         int x = sum(0);
39         update(b[front], 1);
40         now += x * 2 - n + 1;
41         if (ans > now) ans = now, id = i;
42     }
43     cout << ans << " " << id;
44     return 0;
45 }

假设输入的是一个长度为n的排列，并且$1 ≤ n ≤ 1e6$。

■ 判断题（每题2分）

22. lowbit(114514)的结果是2。（ ） {{ select(22) }}

• 正确
• 错误

23. 当$n = 3$时，程序输出的ans值为6。（ ） {{ select(23) }}

• 正确
• 错误

24. 第32行代码front = (front - 1 + n) % n可以改成front = (front) % n - 1。（ ） {{ select(24) }}

• 正确
• 错误

■ 选择题

25. 第35行中update(b[front], -1)的作用是（ ）。 {{ select(25) }}

• 将$[1, b[front]]$的元素都减去1
• 将$(b[front], n]$的元素都减去1
• 将$b[front]$位置的元素减去1
• 以上说法都不对

26. 若程序输入

3
2 3 1

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

• 0 0
• 0 1
• 1 0
• 1 1

27. （4分）若程序输入

5
1 3 4 5 2

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

• 1 1
• 1 2
• 2 1
• 2 2

(3)

01 #include <iostream>
02 #include <cstdio>
03 #include <cstring>
04 using namespace std;
05 const int N = 1e7 + 10, INF = 1e9;
06 int n, m;
07 char a[N], b[N];
08 int z[N], p[N], f[N];
09 int l, r, q[N];
10 void z_function(char *s, int n) {
11     z[1] = n;
12     for (int i = 2, L = 0, r = 0; i <= n; i++) {
13         if (i <= r) z[i] = min(z[i - L + 1], r - i + 1);
14         while (i + z[i] <= n && s[i + z[i]] == s[z[i] + 1]) z[i]++;
15         if (i + z[i] - 1 > r) L = i, r = i + z[i] - 1;
16     }
17 }
18 void exkmp(char *s, int n, char *t, int m) {
19     z_function(t, m);
20     for (int i = 1, L = 0, r = 0; i <= n; i++) {
21         if (i <= r) p[i] = min(z[i - L + 1], r - i + 1);
22         while (i + p[i] <= n && t[p[i] + 1] == s[i + p[i]]) p[i]++;
23         if (i + p[i] - 1 > r) L = i, r = i + p[i] - 1;
24     }
25 }
26 int main() {
27     scanf("%d%d%s%s", &m, &n, b + 1, a + 1);
28     exkmp(a, n, b, m);
29     for (int i = 1, j = 0; i <= n; i++)
30         j = max(j, i + p[i] - 1);
31     memset(f, 0x3f, sizeof(f));
32     f[q[l = r = 1] = n + 1] = 0;
33     for (int i = n; i; i--) {
34         if (!p[i]) continue;
35         while (l <= r && q[l] > i + p[i] - 1) l++;
36         f[i] = f[q[l]] + 1;
37         q[++r] = i;
38     }
39     if (f[1] <= INF) printf("%d\n", f[1]);
40     else puts("Fake");
41     return 0;
42 }

假设输入满足$1 ≤ n, m ≤ 1e7$，并且$|a| = n$，$|b| = m$。

■ 判断题

28. 如果字符串a和b不能完全匹配，代码会输出Fake。（ ） {{ select(28) }}

• 正确
• 错误

29. a的长度必须小于或等于b的长度，否则只能输出Fake。（ ） {{ select(29) }}

• 正确
• 错误

30. 本段代码的时间复杂度是$O(N)$。（ ） {{ select(30) }}

• 正确
• 错误

■ 选择题

31. 若程序读入

3 5
aba
ababa

则z数组为（ ）。 {{ select(31) }}

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

32. 程序读入

3 5
aba
ababa

后，f[i]（1 < i ≤ 5）数组中INF（即0x3f3f3f3f）的个数为（ ）。 {{ select(32) }}

• 0
• 1
• 2
• 3

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

(1) 题目描述： 有n株草，第i株的高度为$a_i (10^9)$，你可以预先拔掉不超过k株草，然后按如下方式操作：选取没拔掉的草中最高的草（高度为h），一次拔掉所有高度$>\frac{h}{2}$的草。你需要在操作次数最少的情况下，最小化预先拔掉的草的数量。

01 #include <bits/stdc++.h>
02 using namespace std;
03 
04 const int N = 2e5 + 1;
05 int n, k, a[N], f[N][55];
06 
07 int main() {
08     scanf("%d %d", &n, &k);
09     for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
10     sort(a + 1, a + n + 1);
11     memset(f, 127, sizeof(f));
12     f[0][0] = 0;
13     int P = ①;
14     for (int i = 1; i <= n; ++i) {
15         if (i <= k) f[i][0] = i;
16         int p = ②;
17         for (int j = 1; j < P; ++j)
18             f[i][j] = min(③);
19     }
20     for (int i = 0; i < P; ++i)
21         if (④) {
22             printf("%d %d", i, f[n][i]);
23             ⑤;
24         }
25     return 0;
26 }

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

• 30
• 31
• 63
• 64

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

• upper_bound(a + 1, a + i + 1, a[i] / 2) - a - 1
• upper_bound(a + 1, a + i + 1, a[i]) - a - 1
• upper_bound(a + 1, a + i + 1, a[i] / 2) - a
• upper_bound(a + 1, a + i + 1, a[i]) - a

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

• f[i - 1][j] + 1, f[i][j]
• f[i - 1][j] + 1, f[i][j - 1]
• f[i - 1][j] + 1, f[p][j]
• f[i - 1][j] + 1, f[p][j - 1]

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

• f[n][i] <= P
• f[n][i] < P
• f[n][i] <= k
• f[n][i] < k

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

• 不填
• return 0;
• printf("\n");
• continue;

(2) 题目描述： 构建一个序列a，满足m条限制。限制形如$(l, r, q)$：$(a_l \& a_{l+1} \& \cdots \& a_r) = q$（此处&为位运算的AND操作）。

01 #include <bits/stdc++.h>
02 using namespace std;
03 const int maxn = 4e5 + 10, maxm = 4e5 + 10;
04 
05 int n, m;
06 int x, y, z;
07 int sm[maxn], lazy[maxn];
08 int s[maxm], h[maxm], t[maxm];
09 
10 void pushdown(int o) {
11     if (!lazy[o]) return;
12     lazy[o << 1] |= lazy[o];
13     lazy[o << 1 | 1] |= lazy[o];
14     sm[o << 1] |= lazy[o];
15     sm[o << 1 | 1] |= lazy[o];
16     ①;
17 }
18 
19 void update(int o, int l, int r) {
20     if (②) {
21         lazy[o] |= z;
22         sm[o] |= z;
23         return;
24     }
25     pushdown(o);
26     int mid = (l + r) >> 1;
27     if (x <= mid) update(o << 1, l, mid);
28     if (y > mid) update(o << 1 | 1, mid + 1, r);
29     ③;
30 }
31 
32 int query(int o, int l, int r) {
33     if (x <= l && r <= y) return sm[o];
34     pushdown(o);
35     int res = ④;
36     int mid = (l + r) >> 1;
37     if (x <= mid) res &= query(o << 1, l, mid);
38     if (y > mid) res &= query(o << 1 | 1, mid + 1, r);
39     return res;
40 }
41 
42 int main() {
43     memset(sm, 0, sizeof(sm));
44     memset(lazy, 0, sizeof(lazy));
45     scanf("%d%d", &n, &m);
46     for (int i = 1; i <= m; i++) {
47         scanf("%d%d%d", &s[i], &h[i], &t[i]);
48         x = s[i], y = h[i], z = t[i];
49         update(1, 1, n);
50     }
51     for (int i = 1; i <= m; i++) {
52         x = s[i], y = h[i];
53         if (⑤) {
54             printf("NO\n");
55             return 0;
56         }
57     }
58     printf("YES\n");
59     for (int i = 1; i <= n; i++) {
60         x = y = i;
61         printf("%d ", query(1, 1, n));
62     }
63     return 0;
64 }

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

• return;
• lazy[o] = 0;
• lazy[o] = 1;
• lazy[o] ^= 1;

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

• x <= l || r <= y
• x <= l && r <= y
• !(x >= l) && !(r >= y)
• !(x >= l) || !(r >= y)

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

• sm[o] = (sm[o << 1] | sm[o << 1 | 1]);
• sm[o] = (sm[o << 1] ^ sm[o << 1 | 1]);
• sm[o] = (sm[o << 1] + sm[o << 1 | 1]);
• sm[o] = (sm[o << 1] & sm[o << 1 | 1]);

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

• (1ULL << 29) - 1
• (1ULL << 30) - 1
• (1ULL << 31) - 1
• (1ULL << 32) - 1

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

• query(1, 1, n) != t[i]
• query(1, 1, n) == t[i]
• query(1, 1, n) > t[i]
• query(1, 1, n) <= t[i]