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

1. 在NOI Linux系统终端中，（ ）命令可以用来修改文件名。 {{ select(1) }}

• mkdir
• cp -a
• mv
• touch

2. 以下关于二叉排序树的表述中，不恰当的一项是（ ）。 {{ select(2) }}

• 若左子树不空，则其所有结点的值均小于根结点的值
• 二叉排序树的根结点一定有最小值或者最大值
• 若右子树不空，则其所有结点的值均大于根结点的值
• 二叉排序树的左右子树也分别为二叉排序树

3. 计算机病毒最不容易攻击的是（ ）。 {{ select(3) }}

• 硬盘
• 内存
• 只读光盘
• U盘

4. 假设我们有以下C++代码：

unsigned char a = 143, b = 3, c = 4;
a <<= 2;
int res = a | (b + c >> 1);

则res的值是（ ）。 {{ select(4) }}

• 63
• 61
• 573
• 575

5. 使用邻接表表示一个简单有向图，图中包含n个顶点、m条边，则该出边表中边结点的个数为（ ）。 {{ select(5) }}

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

6. （ ）问题不是典型的与动态规划算法相关的问题。 {{ select(6) }}

• 最长公共子序列
• 打水
• 多重背包
• 最长递增子序列

7. 解决RMQ问题通常使用（ ）。 {{ select(7) }}

• 哈夫曼树
• 并查集
• 哈希表
• 稀疏表

8. 以下关于强连通图的说法中，正确的是（ ）。 {{ select(8) }}

• 图中一定有环
• 每个顶点的度数都大于0
• 对于大于1个点的强连通图，任意两个顶点之间都有路径相连
• 每个顶点至少都连有一条边

9. 甲乙两人进行比赛，每局比赛获胜的概率相同，均为甲获胜的概率为0.4，乙获胜的概率为0.6，现规定两人持续比赛，直到有一方比对方获胜局数多两局时获得一场比赛的胜利，则甲获胜的概率是（ ）。 {{ select(9) }}

• 2/5
• 4/9
• 4/13
• 1/3

10. 给定地址区间为0~12的哈希表，哈希函数为$h(x) = x \% 13$，采用二次探查的冲突解决策略（出现冲突后会往后依次探查以下位置：$h(x)$，$h(x)+1$，$h(x)-1$，$h(x)+2^2$，$h(x)-2^2$，$h(x)+3^2$，$h(x)-3^2$，...）。哈希表初始为空表，依次存储(26, 36, 13, 18, 39, 3, 0)后，请问0存储在哈希表的哪个地址中？（ ） {{ select(10) }}

• 7
• 6
• 5
• 9

11. STL模板中的容器可以分为顺序容器和关联容器，下列选项中，（ ）不属于容器适配器。 {{ select(11) }}

• iterator
• stack
• queue
• priority_queue

12. 下面关于C++类继承的说法中，错误的是（ ）。 {{ select(12) }}

• 一个类可以继承多个类
• 一个类可以继承另一个类的子类
• 一个类可以被多个类继承
• 抽象类必须被至少一个类继承，否则会发生编译错误

13. 假设G是一张有m个点、n条边的图，小明想找一棵有n个结点的最小生成树，必须删去若干点和（ ）条边才能将其变成这样的一棵树。 {{ select(13) }}

• m - n - 1
• m + n - 1
• 1
• m - n + 1

14. 一只蚂蚁从一个棱长为2的正方体的一个顶点出发，沿着棱爬，则其爬过所有棱长且回到出发的顶点的最短路径长是（ ）。 {{ select(14) }}

• 28
• 32
• 36
• 40

15. 二叉堆算法插入操作和删除操作的时间复杂度分别为（ ）。 {{ select(15) }}

• $O(log n)、O(log n)$
• $O(n)、O(n)$
• $O(n)、O(log n)$
• $O(log n)、O(n)$

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

(1)

01 #include <bits/stdc++.h>
02 using namespace std;
03 
04 const int N = 3e5 + 10;
05 const int mod = 1e9 + 7;
06 
07 int n, a[N];
08 
09 using ii = pair<int, int>;
10 
11 int dp[N];
12 int sum[N];
13 
14 int main() {
15     ios::sync_with_stdio(0);
16     cin.tie(0);
17     cin >> n;
18     for (int i = 1; i <= n; ++i) cin >> a[i];
19     set<ii> s;
20     sum[0] = 1;
21     for (int i = 1, res = 0; i <= n; ++i) {
22         ii u;
23         while (!s.empty()) {
24             u = (*s.rbegin()); // rbegin是反向迭代器
25             if (u.first > a[i]) {
26                 res = (res - dp[u.second] + mod) % mod;
27                 s.erase(u);
28             } else break;
29         }
30         if (s.empty()) dp[i] = sum[i - 1];
31         else dp[i] = (res + sum[i - 1] - sum[u.second]) % mod;
32         if (dp[i] < 0) dp[i] += mod;
33         sum[i] = (sum[i - 1] + dp[i]) % mod;
34         s.insert({a[i], i});
35         res = (res + dp[i]) % mod;
36     }
37     int ans = 0;
38     for (auto u : s) ans = (ans + dp[u.second]) % mod;
39     cout << ans << endl;
40     return 0;
41 }

保证输入$1 ≤ N ≤ 300000$，a是一个排列。

■ 判断题（每题2分）

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

• 正确
• 错误

17. 本段代码不可能输出负数。（ ） {{ select(17) }}

• 正确
• 错误

18. 第18行代码从i=1改成i++后，程序仍能正常运行，并且输出结果不变。（ ） {{ select(18) }}

• 正确
• 错误

■ 选择题

19. 对于输入

3
2 3 1

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

• 1
• 2
• 3
• 4

20. 对于输入

4
2 1 4 3

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

• 2
• 4
• 6
• 8

(2)

01 #include <bits/stdc++.h>
02 #define v first
03 #define id second
04 using namespace std;
05 
06 typedef long long ll;
07 
08 const int N = 100010;
09 int n, d, cnt;
10 ll a[N], num[N];
11 int f[N], g[N];
12 typedef pair<int, int> pii;
13 
14 pii mx[N << 2];
15 
16 pii query(int u, int l, int r, int ql, int qr) {
17     if (ql > qr) return {-1, 0};
18     if (ql <= l && r <= qr) return (mx[u].v ? mx[u] : make_pair(-1, 0));
19     int mid = (l + r) >> 1;
20     if (ql <= mid && qr > mid) return max(query(u << 1, l, mid, ql, qr),
21                                        query(u << 1 | 1, mid + 1, r, ql, qr));
22     else if (ql <= mid) return query(u << 1, l, mid, ql, qr);
23     else return query(u << 1 | 1, mid + 1, r, ql, qr);
24 }
25 
26 void modify(int u, int l, int r, int pos, pii v) {
27     if (l == r) { mx[u] = max(mx[u], v); return; }
28     int mid = (l + r) >> 1;
29     if (pos <= mid) modify(u << 1, l, mid, pos, v);
30     else modify(u << 1 | 1, mid + 1, r, pos, v);
31     mx[u] = max(mx[u << 1], mx[u << 1 | 1]);
32 }
33 
34 void print() {
35     int mx = 0;
36     for (int i = 1; i <= n; i++) if (f[i] > f[mx]) mx = i;
37     printf("%d\n", f[mx]);
38     vector<int> ans;
39     ans.push_back(mx);
40     while (g[mx]) mx = g[mx], ans.push_back(mx);
41     reverse(ans.begin(), ans.end());
42     for (int x : ans) printf("%d ", x); puts("");
43 }
44 
45 int main() {
46     scanf("%d%d", &n, &d);
47     for (int i = 1; i <= n; i++) {
48         scanf("%lld", &a[i]);
49         num[i] = a[i];
50     }
51     sort(num + 1, num + n + 1);
52     cnt = unique(num + 1, num + n + 1) - num - 1;
53     for (int i = 1; i <= n; i++) {
54         int x = lower_bound(num + 1, num + cnt + 1, a[i]) - num;
55         int l = upper_bound(num + 1, num + cnt + 1, a[i] - d) - num - 1;
56         int r = lower_bound(num + 1, num + cnt + 1, a[i] + d) - num;
57         pii ans = max({make_pair(0, 0), query(1, 1, cnt, 1, l),
58                      query(1, 1, cnt, r, cnt)});
59         f[i] = ans.v + 1, g[i] = ans.id;
60         modify(1, 1, cnt, x, {f[i], i});
61     }
62     print();
63     return 0;
64 }

保证输入数据中$1 ≤ n ≤ 10^5$，$0 ≤ d ≤ 10^9$，$1 ≤ a[i] ≤ 10^{15}$。

■ 判断题（每题2分）

21. d非0时，第55行与第56行代码中的l与r值一定不一样。（ ） {{ select(21) }}

• 正确
• 错误

22. 第23行后应该再加一行代码else return make_pair(-1, 0);，否则在一些情况下，函数不会返回值，导致未定义行为。（ ） {{ select(22) }}

• 正确
• 错误

■ 选择题

23. 这段代码的时间复杂度是（ ）。 {{ select(23) }}

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

24. 如果a[i]的值为10，d的值为3，a的值为15 6 8 10 12 14 17，那么l和r的值分别为（ ）。 {{ select(24) }}

• 3 7
• 4 7
• 3 6
• 4 6

25. 以下说法中正确的是（ ）。 {{ select(25) }}

• 如果需要单点修改，区间查询max值，在本段代码中也可以使用树状数组，时间复杂度不变。
• 如果输入合法，在本段代码中，upper_bound(num + 1, num + cnt + 1, a[i] - d)和lower_bound(num + 1, num + cnt + 1, a[i] + d)一定不同。
• modify(1, 1, cnt, x, {f[i], i})这段代码会递归$\left\lceil\frac{cnt}{2}\right\rceil$次。
• 第55行代码中，int l后面的内容可以改成= lower_bound(num + 1, num + cnt + 1, a[i] - d) - num，与原来l = upper_bound(num + 1, num + cnt + 1, a[i] - d) - num - 1的作用相同。

(3)

01 #include <bits/stdc++.h>
02 #define int long long
03 using namespace std;
04 const int N = 5e5 + 10;
05 vector<int> e[N];
06 int w[N];
07 int L[N], R[N];
08 int n, m, res;
09 
10 void add(int a, int b) {
11     e[a].push_back(b), e[b].push_back(a);
12 }
13 
14 void dfs(int u, int fa) {
15     vector<int> s;
16     if (u <= m) return;
17     for (auto v : e[u]) {
18         if (v == fa) continue;
19         dfs(v, u);
20         s.push_back(L[v]), s.push_back(R[v]);
21     }
22     sort(s.begin(), s.end());
23     int sz = s.size();
24     if (sz & 1) L[u] = R[u] = s[sz / 2];
25     else L[u] = s[sz / 2 - 1], R[u] = s[sz / 2];
26     for (auto v : e[u]) {
27         if (v == fa) continue;
28         if (L[u] > R[v]) res += L[u] - R[v];
29         else if (L[u] < L[v]) res += L[v] - L[u];
30         else res += 0;
31     }
32 }
33 
34 signed main() {
35     ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
36     cin >> n >> m;
37     for (int i =1; i < n; i++) {
38         int a, b;
39         cin >> a >> b;
40         add(a, b);
41     }
42     for (int i = 1; i <= m; i++) cin >> w[i], L[i] = R[i] = w[i];
43     if (n == 2) {
44         cout << abs(w[1] - w[2]) << "\n";
45         return 0;
46     }
47     dfs(m + 1, 0);
48     cout << res << "\n";
49     return 0;
50 }

题目保证输入是一棵树，其中叶子结点标号为$[1, M]$，$2 ≤ M ≤ N ≤ 500000$，其他读入的数据均不会大于500000。

■ 判断题（每题2分）

26. 不考虑vector的复杂度，这段代码的时间复杂度为$O(N)$。（ ） {{ select(26) }}

• 正确
• 错误

27. 删除第24行代码，并删除第25行代码，程序仍然可以输出相同的结果。（ ） {{ select(27) }}

• 正确
• 错误

28. 当$n = 2$的时候，程序输出不会大于500000。（ ） {{ select(28) }}

• 正确
• 错误

■ 选择题

29. 本段代码中res可能达到的最大值为多少？（ ） {{ select(29) }}

• 250000000000
• 125000000000
• 124999250001
• 62500000000

30. 假如$n = 5$，$m = 3$，$w[1] = 10$，$w[2] = 20$，$w[3] = 30$，在程序正确运行的前提下，理论上本题res的最小值是多少？（ ） {{ select(30) }}

• 20
• 15
• 10
• 5

31. 以下说法中正确的是（ ）。 {{ select(31) }}

• 本段代码中每次sort的复杂度最大为$O(n \log n)$，因此，该程序的复杂度为$O(n^2 \log n)$。
• 本段代码中的dfs(m + 1, 0)改成dfs(1, 0)，结果不变。
• 如果读入n条边，程序一定会读入一个环，导致dfs过程出现死循环。
• 如果给定的是一条链，则输出一定是$|w[1] - w[2]|$。

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

(1) 题目描述： 给定一个只有左右括号的字符串，然后用H、G两种字符来标记这个序列，所有标记H的括号可以组成一个正确的括号序列，所有标记G的括号也组成一个正确的括号序列，然后输出这种标记方案的总数mod2012的值。可以用一个dp来解决问题。

01 #include <iostream>
02 #include <cstring>
03 #include <cmath>
04 #include <cstdio>
05 using namespace std;
06 
07 const int mod = 2012;
08 char s[1005];
09 int n, f[1005][1005], g[1005][1005];
10 
11 int main() {
12     scanf("%s", s + 1);
13     n = ①;
14     int oo = 0;
15     f[0][0] = 1;
16     for (int i = 1; i <= n; ++i) {
17         if (s[i] == '(') {
18             oo++;
19             for (int j = 0; j <= oo; ++j) {
20                 g[j][oo - j] = (g[j][oo - j] + f[j][oo - j - 1]) % mod;
21                 if (oo - j) ②;
22             }
23         } else if (s[i] == ')') {
24             ③;
25             for (int j = 0; j <= oo; ++j) {
26                 g[j][oo - j] = ④;
27                 g[j][oo - j] = (g[j][oo - j] + f[j][oo - j + 1]) % mod;
28             }
29             for (int j = 0; j <= oo; ++j) ⑤;
30         }
31     }
32     printf("%d", f[0][0]);
33     return 0;
34 }

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

• strlen(s)
• strlen(s + 1)
• strlen(s) + 1
• strlen(s + 1) - 1

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

• g[j][oo - j] = (g[j][oo - j] + f[j][oo - j - 1]) % mod
• g[j][oo - j] = (g[j][oo - j] + f[j - 1][oo - j]) % mod
• g[j][oo - j] = (g[j][oo - j] + f[j][oo - j]) % mod
• g[j][oo - j] = (g[j][oo - j] + f[j - 1][oo - j - 1]) % mod

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

• oo++
• oo--
• oo = 0
• oo = n

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

• (g[j][oo - j] + f[j][oo - j + 1]) % mod
• (g[j][oo - j] + f[j][oo - j]) % mod
• (g[j][oo - j] + f[j + 1][oo - j + 1]) % mod
• (g[j][oo - j] + f[j + 1][oo - j]) % mod

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

• f[j][oo - j] = g[j][oo - j], g[j][oo - j] = 0
• f[j][oo - j + 1] = g[j][oo - j], g[j][oo - j] = 0
• f[j][j] = g[j][oo - j], g[j][oo - j] = 0
• f[j][j + 1] = g[j][oo - j], g[j][oo - j] = 0

(2) 题目描述： 对n个单词进行加密，过程如下。 选择一个英文字母表的排列作为密钥。 将单词中的a替换为密钥中的第一个字母，b替换为密钥中的第二个字母，以此类推。 请你构造一组密钥，使得对所有单词加密并且按照字典序升序排列后，最初的第ai个单词位于第i个位置，如果不能，输出NE，否则输出DA并且下一行输出一种可行的密钥。 可以想到，如果把字典序限制看成一条有序边，可以按照拓扑排序来分配密钥，如果出现环，则说明无解。

01 #include <bits/stdc++.h>
02 #define LL long long
03 using namespace std;
04 
05 const LL M1 = 300, M2 = 30;
06 LL n;
07 string a[M1], a_sort[M1];
08 LL du[M1];
09 queue<LL> qu;
10 vector<LL> ve[M2];
11 LL ans[M2];
12 
13 int main() {
14     cin >> n;
15     for (LL i = 1; i <= n; i++) cin >> a[i];
16     for (LL i = 1; i <= n; i++) {
17         LL b;
18         cin >> b;
19         ①;
20     }
21 
22     for (LL i = 1; i < n; i++) {
23         bool flag = true;
24         for (LL j = 0; j < ②; j++) {
25             if (a_sort[i][j] != a_sort[i + 1][j]) {
26                 ③;
27                 du[a_sort[i + 1][j] - 'a']++;
28                 flag = false;
29                 break;
30             }
31         }
32         if (flag && ④) {
33             cout << "NE";
34             return 0;
35         }
36     }
37 
38     for (LL i = 0; i < 26; i++) if (du[i] == 0) qu.push(i);
39 
40     LL cnt = 0;
41     while (!qu.empty()) {
42         LL v = qu.front();
43         qu.pop();
44         ans[v] = cnt;
45         cnt++;
46         for (LL i = 0; i < (LL)ve[v].size(); i++) {
47             du[ve[v][i]]--;
48             if (⑤) qu.push(ve[v][i]);
49         }
50     }
51 
52     if (cnt != 26) cout << "NE";
53     else {
54         cout << "DA\n";
55         for (LL i = 0; i < 26; i++) {
56             cout << (char)(ans[i] + 'a');
57         }
58     }
59     return 0;
60 }

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

• a_sort[i] = a[b]
• a_sort[i] = a[i]
• a_sort[b] = a[b]
• a_sort[b] = a[i]

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

• a_sort[i].size()
• a_sort[i + 1].size()
• min(a_sort[i].size(), a_sort[i + 1].size())
• max(a_sort[i].size(), a_sort[i + 1].size())

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

• ve[a_sort[i][j] - 'a'].push_back(a_sort[i + 1][j] - 'a')
• ve[a_sort[i][j] - 'a'].push_back(a_sort[i][j] - 'a')
• ve[a_sort[i + 1][j] - 'a'].push_back(a_sort[i][j] - 'a')
• ve[a_sort[i + 1][j] - 'a'].push_back(a_sort[i + 1][j] - 'a')

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

• a_sort[i].size() >= a_sort[i + 1].size()
• a_sort[i].size() <= a_sort[i + 1].size()
• a_sort[i].size() > a_sort[i + 1].size()
• a_sort[i].size() < a_sort[i + 1].size()

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

• !du[ve[v][i]]
• du[ve[v][i]]
• ~du[ve[v][i]]
• -du[ve[v][i]]

---