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

1. 已知开放集合$S$规定，如果正整数$x$属于该集合，则$2x$和$3x$同样属于该集合。若该集合包含1，则该集合一定包含（ ）。 {{ select(1) }}

• 2024
• 1536
• 2025
• 2026

2. 在C++语言中，STL deque类型不包含函数（ ）。 {{ select(2) }}

• pop()
• front()
• back()
• size()

3. 在NOI Linux系统中，改变当前工作路径到上一级目录的命令是（ ）。 {{ select(3) }}

• pwd
• ls
• cd ..
• mv

4. 在C++语言中，(-5) % 5的值为（ ）。 {{ select(4) }}

• -1
• 0
• 1
• 5

5. 简单无向图有24条边且每个顶点的度数都是4，则图中有（ ）个顶点。 {{ select(5) }}

• 24
• 10
• 16
• 12

6. 算法的复杂度分析中常用的大O表示法是（ ）科学家最先引入的。 {{ select(6) }}

• 美国
• 德国
• 英国
• 法国

7. 稀疏表预处理的时间复杂度为（ ）。 {{ select(7) }}

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

8. 以下选项中，（ ）不属于AVL树插入结点破坏平衡的情况。 {{ select(8) }}

• RS型
• RL型
• LL型
• LR型

9. 数据结构中单调栈的特点不包括（ ）。 {{ select(9) }}

• 单调栈这种优秀的数据结构简洁明了
• 单调栈的空间复杂度为$O(n)$
• 单调栈中的所有元素都会多次出入栈
• 顾名思义，单调栈中的元素呈单调性

10. 关于C++语言中的构造函数，下列说法中哪个是正确的？（ ） {{ select(10) }}

• 构造函数的名称与类的名称相同，且没有返回值
• 构造函数不能被override
• 构造函数是用来销毁类对象的成员函数
• 每个类只有一个构造函数

11. 下面有关C++重载的说法中错误的是（ ）。 {{ select(11) }}

• 两个参数个数不同的函数可以用相同的名字
• 两个参数类型不同的函数可以用相同的名字
• 两个类的方法可以用相同的名字
• 所有C++运算符均可以重载

12. 有$n$个顶点、$m$条边的图的深度优先搜索遍历算法的时间复杂度为（ ）。 {{ select(12) }}

• $O(nm)$
• $O(n + m)$
• $O(n)$
• $O(m)$

13. 甲乙两人参加知识竞赛，每人抽1次（抽到的题目不再放回），共有6道选择题、4道判断题，甲乙两人至少有一个抽到选择题的概率是（ ）。 {{ select(13) }}

• 3/5
• 2/3
• 13/15
• 3/4

14. 正整数$n ≥ 3$称为理想数，若存在正整数$k(1 ≤ k ≤ n - 1)$使得$C(n, k - 1)$，$C(n, k)$，$C(n, k + 1)$构成等差数列，其中$C(n, k)$为从$n$个数中取$k$个数的组合数，$C(n, k) = n! / (k! * (n - k)!)$，则不超过2025的理想数的个数为（ ）。 {{ select(14) }}

• 46
• 45
• 44
• 43

15. 已知一棵二叉树有10个结点，则其中至多有（ ）个结点有2个子结点。 {{ select(15) }}

• 6
• 5
• 4
• 3

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

(1)

01 #include <bits/stdc++.h>
02 using namespace std;
03 const int N = 1e5 + 5;
04 using ll = long long;
05 ll A, B, C;
06 int n, k, T, p[N], m, mr, a[N], b[N];
07 bitset<N> vs;
08 
09 inline bool ck(int P) {
10     int x, d = 0, R = 2;
11     for (x = 1; x <= n; ++x) if (p[x] << 1 < P) p[x] = 1e9, ++d;
12     for (x = 1; x < n; ++x) R = min(R, (p[x] < P) + (p[x + 1] < P));
13     for (x = 1; x <= n; ++x) p[x] = b[x];
14     return d + R <= k;
15 }
16 
17 int main() {
18     ios::sync_with_stdio(false);
19     int i, j, x, y, z, l, r, md;
20     cin >> T;
21     while (T--) {
22         cin >> n >> k;
23         for (i = 1; i <= n; ++i) cin >> p[i], b[i] = p[i], a[i] = i;
24         if (n == k) {
25             printf("%d\n", 100000000);
26             continue;
27         } else if (n == 2) {
28             printf("%d\n", max(p[1], p[2]));
29             continue;
30         }
31         sort(a + 1, a + n + 1, [&](int x, int y) { return b[x] < b[y]; });
32         l = 0, r = 1e9, A = 0;
33         while (l <= r) {
34             md = l + r >> 1;
35             if (ck(md)) A = md, l = md + 1;
36             else r = md - 1;
37         }
38         printf("%d\n", A);
39     }
40     return 0;
41 }

假设$1 ≤ k ≤ 1e5$，$2 ≤ n ≤ 1e5$，$1 < a_i ≤ 1e9$，回答下列问题。

■ 判断题

16. 这段代码的时间复杂度为$O(T n \log n + T n \log A)$。（ ） {{ select(16) }}

• 正确
• 错误

17. 第31行中的sort没必要这么写，只需要写sort(a + 1, a + n + 1)，程序执行能得到一样的结果。（ ） {{ select(17) }}

• 正确
• 错误

18. 这段代码的输出不会大于$k$。（ ） {{ select(18) }}

• 正确
• 错误

19. 当$P$越大时，check函数中的$R$也越大，但是不会大于2。（ ） {{ select(19) }}

• 正确
• 错误

■ 选择题

20. 假设读入时b数组为1 9 1 9 8 1 0，则程序执行完毕后，b数组为（ ）。 {{ select(20) }}

• 1 1 0 1 9 8 9
• 1 9 1 9 8 1 0
• 1 8 9 1 0 1 9
• 1 1 4 5 1 4

21. 假设输入为

1
4 1
1 4 6 13 2

则输出为（ ）。 {{ select(21) }}

• 4
• 5
• 6
• 7

(2)

01 #include <bits/stdc++.h>
02 const int maxn = 200100;
03 int n, a[maxn];
04 void solve() {
05     scanf("%d", &n);
06     for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
07     int lst = 0;
08     for (int i = 1; i <= n; ++i) {
09         if (a[i] != -1) {
10             if (!lst) {
11                 for (int j = i - 1, o = 1; j >= 1; --j, o ^= 1) a[j] = (o ? a[i] * 2 : a[i]);
12                 lst = i;
13                 continue;
14             }
15             int x = lst, y = i;
16             while (y - x > 1) {
17                 if (a[x] > a[y]) a[x + 1] = a[x] / 2, ++x;
18                 else if (a[x] < a[y]) a[y - 1] = a[y] / 2, --y;
19                 else a[x + 1] = a[x] > 1 ? a[x] / 2 : a[x] * 2, ++x;
20             }
21             if (a[y] != a[x] / 2 && a[x] != a[y] / 2) return (void)puts("-1");
22             lst = i;
23         }
24     }
25     if (!lst) {
26         for (int i = 1; i <= n; ++i) printf("%d\n", (i & 1) + 1);
27         return;
28     }
29     for (int i = lst + 1, o = 1; i <= n; ++i, o ^= 1) a[i] = (o ? a[lst] * 2 : a[lst]);
30     for (int i = 1; i <= n; ++i) printf("%d\n", a[i]);
31 }
32 int main() {
33     int T;
34     scanf("%d", &T);
35     while (T--) solve();
36     return 0;
37 }

假设$T ≤ 10$，$1 ≤ n ≤ 200000$，$-1 ≤ a_i ≤ 100000000$，回答下列问题。

■ 判断题

22. 这段代码的时间复杂度为$O(n \log n)$。（ ） {{ select(22) }}

• 正确
• 错误

23. 如果输入的$a_i$全为-1，那么输出的第一个数是1。（ ） {{ select(23) }}

• 正确
• 错误

24. 第11行中的o ^= 1的作用是让o在0和1之间切换，使得填充的数交替为a[i]和a[i] * 2。（ ） {{ select(24) }}

• 正确
• 错误

■ 选择题

25. 若程序输入为

1
8
-1 -1 -1 2 -1 -1 1 -1

则输出（不考虑换行）是（ ）。 {{ select(25) }}

• 4 2 4 2 1 2 1 2
• 4 2 4 2 1 1 1 2
• 1 2 4 2 1 2 1 2
• 1 2 4 2 1 1 1 2

26. 假设$a[x] = 15$，$a[y] = 29$，并且$x = 5$，$y = 12$，那么程序执行完第16~20行代码后，$a[6]$到$a[11]$的值分别是多少？（ ） {{ select(26) }}

• 7 3 1 3 7 14
• 7 14 29 14 29 14
• 7 3 7 14 29 14
• 7 7 3 7 14 29

27. 当第16行中的$y - x$的差大于（ ）时，这段代码一定不会输出-1。 {{ select(27) }}

• 54
• 60
• 63
• 无法保证

(3)

01 #include <bits/stdc++.h>
02 using namespace std;
03 const int INF = 5e5 + 5;
04 struct _node_data {
05     int l, r;
06 } aa[INF];
07 int n;
08 struct _set {
09     int v, id;
10     bool operator<(const _set &x) const {
11         return x.v > v;
12     }
13 };
14 multiset<_set> s;
15 bool cmp(_node_data xx, _node_data yy) {
16     return xx.l < yy.l;
17 }
18 struct _node_edge {
19     int to_, next_;
20 } edge[INF << 1];
21 int head[INF], tot, vis[INF];
22 void add_edge(int x, int y) {
23     edge[++tot] = (_node_edge){y, head[x]};
24     head[x] = tot;
25     return;
26 }
27 void DFS(int x) {
28     if (vis[x]) return;
29     vis[x] = 1;
30     for (int i = head[x]; i; i = edge[i].next_) {
31         int v = edge[i].to_;
32         DFS(v);
33     }
34     return;
35 }
36 int check() {
37     DFS(1);
38     for (int i = 1; i <= n; i++)
39         if (!vis[i]) return false;
40     return true;
41 }
42 signed main() {
43     ios::sync_with_stdio(false);
44     cin >> n;
45     for (int i = 1; i <= n; i++) cin >> aa[i].l >> aa[i].r;
46     sort(aa + 1, aa + 1 + n, cmp);
47     int cnt = 0;
48     s.insert((_set){aa[1].r, 1});
49     for (int i = 2; i <= n; i++) {
50         set<_set>::iterator it = s.lower_bound((_set){aa[i].l, -1});
51         for (; it != s.end(); it++) {
52             if (it->v >= aa[i].r) break;
53             cnt++;
54             if (cnt == n) {
55                 cout << "NO\n";
56                 return 0;
57             }
58             add_edge(i, it->id);
59             add_edge(it->id, i);
60         }
61         s.insert((_set){aa[i].r, i});62     }
63     if (cnt != n - 1) {
64         cout << "NO\n";
65         return 0;
66     }
67     if (!check()) {
68         cout << "NO\n";
69         return 0;
70     }
71     cout << "YES\n";
72     return 0;
73 }

假设(1 ≤ n ≤ 5e5)，(1 ≤ l_i ≤ r_i ≤ 2n)，并且输入均为整数，不会出现相同的((l_i, r_i))。

■ 判断题

28. 此题是判断一些线段满足一些性质后是否能构成一棵树，因为第63行判断(cnt)是否为(n-1)，即边的数量是否为(n-1)条。（ ） {{ select(28) }}

• 正确
• 错误

29. 这段代码的时间复杂度是(O(n^2 \log n))。（ ） {{ select(29) }}

• 正确
• 错误

30. _set类型在set中按照id从大到小排序。（ ） {{ select(30) }}

• 正确
• 错误

■ 选择题

31. 如果输入

6
9 12
2 11
1 3
6 10
5 7
4 8

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

• YES
• NO
• NULL
• TRUE

32. 以下哪种情况一定会导致代码输出"NO"？（ ） {{ select(32) }}

• 在本段代码中，DFS函数执行了(n)次
• 存在(i)使得(l_i = r_i = 0)
• 存在重复出现的((l_i, r_i))
• 所有线段都相交

33. （4分）下列说法中正确的是（ ）。 {{ select(33) }}

• 如果(l_i, r_i)数据范围扩大十倍，则时间复杂度变大
• check函数中的DFS(1)改成DFS(n)，程序输出不变
• multiset完全没有必要，这会导致重复连边，但是因为本题要求一棵树，所以没有出现问题
• 其实可以只连单向边，考虑(x, y)：当扫到(x)的时候会有((x, y))和((y, x))，而扫到(y)时也会有((x, y))和((y, x))

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

(1) 题目描述： 给你一棵有(n)个结点的树，结点从1到(n)编号。你会按编号从小到大的顺序访问每个结点。经过树上的边需要收费。第(i)条边有单程票（只能用1次）价格(c_{i1})和多程票（可以用无限次）价格(c_{i2})。你在访问途中可能会重复走一条边，所以多程票有时更划算。请你求出从1访问到(n)最少需要多少费用。

01 #include <cstdio>
02 #include <iostream>
03 #include <cstring>
04 using namespace std;
05 
06 const int N = 2e5 + 10;
07 
08 int n, fir[N], tot, fa[N][40], dep[N];
09 long long ans, val[N];
10 struct node { int to, nex, oned, twod; } e[N << 1];
11 
12 void add(int u, int v, int xgf, int xrc) {
13     e[++tot].to = v;
14     e[tot].oned = xgf;
15     e[tot].twod = xrc;
16     e[tot].nex = fir[u];
17     fir[u] = tot;
18     return;
19 }
20 
21 void swap(int &x, int &y) { ①; return; }
22 
23 void dfs(int x, int dad) {
24     dep[x] = dep[dad] + 1;
25     fa[x][0] = dad;
26     for (int i = 1; (1 << i) <= dep[x]; ++i)
27         fa[x][i] = ②;
28     for (int i = fir[x]; i; i = e[i].nex)
29         if (e[i].to != dad) dfs(e[i].to, x);
30     return;
31 }
32 
33 int lca(int x, int y) {
34     if (dep[x] < dep[y]) swap(x, y);
35     for (int i = 35; i >= 0; --i) {
36         if (dep[fa[x][i]] >= dep[y]) x = fa[x][i];
37     }
38     if (x == y) return y;
39     for (int i = 35; i >= 0; --i) {
40         if (③) { x = fa[x][i]; y = fa[y][i]; }
41     }
42     return fa[x][0];
43 }
44 
45 void solve(int x) {
46     int u;
47     for (int i = fir[x]; i; i = e[i].nex) {
48         if (e[i].to != fa[x][0]) {
49             solve(e[i].to);
50             val[x] += val[e[i].to];
51         } else u = i;
52     }
53     ④;
54     else ans += e[u].twod;
55     return;
56 }
57 
58 int main() {
59     scanf("%d", &n);
60     for (int i = 1, u, v, c1, c2; i < n; ++i) {
61         scanf("%d%d%d%d", &u, &v, &c1, &c2);
62         add(u, v, c1, c2); add(v, u, c1, c2);
63     }
64     dfs(1, 0);
65     for (int i = 1; i < n; ++i) {
66         val[i]++; val[i + 1]++;
67         ⑤;
68     }
69     solve(1);
70     printf("%lld", ans);
71     return 0;
72 }

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

• x ^= y; y ^= x; x ^= y
• x ^= x; x ^= x; x ^= y
• x ^= y; y ^= x; y ^= x
• x ^= y; y ^= x; y ^= x

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

• fa[x][i + 1]
• fa[x][i - 1]
• fa[fa[x][i + 1]][i + 1]
• fa[fa[x][i - 1]][i - 1]

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

• fa[x][i] & fa[y][i]
• fa[x][i] ^ fa[y][i]
• fa[x][i] == fa[y][i]
• fa[x][i] != fa[y][i]

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

• if (e[u].oned * val[x] < e[u].twod) ans += e[u].oned * val[x]
• if (e[u].oned * val[x] < e[u].twod) ans += e[u].twod
• if (e[u].oned < e[u].twod) ans += e[u].oned * val[x]
• if (e[u].oned < e[u].twod) ans += e[u].twod

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

• val[lca(i, i + 1)] -= 2
• val[lca(i, i - 1)] -= 2
• val[lca(i, i + 1)] -= 1
• val[lca(i, i - 1)] -= 1

(2) 题目描述： 给定一个(n×m)的矩阵(h)，求出所有大小为(a×b)的子矩阵中的最小值的和。矩阵的给定方式：给定(g(0), x, y, z)，它们表示一个序列(g(i))，而(h_{i,j})由该序列生成。其中(g(i) = [g(i - 1) * x + y] \mod z)；(h_{i,j} = g[(i - 1)m + j - 1])。

01 #include <bits/stdc++.h>
02 using namespace std;
03 
04 int n, m, a, b;
05 long long x, y, z;
06 long long g[9000010];
07 int h[3005][3005];
08 int minn[3005][3005];
09 long long ans;
10 deque<int> p;
11 
12 int main() {
13     scanf("%d%d%d%d", &n, &m, &a, &b);
14     scanf("%lld%lld%lld%lld", &g[0], &x, &y, &z);
15     for (int i = 1; i <= 9000000; ++i) g[i] = (g[i - 1] * x + y) % z;
16     for (int i = 1; i <= n; ++i) {
17         for (int j = 1; j <= m; ++j)
18             h[i][j] = ①;
19     }
20     for (int i = 1; i <= n; ++i) {
21         while (!p.empty()) p.pop_back();
22         for (int j = 1; j <= m; ++j) {
23             while (!p.empty() && p.front() <= j - b) ②;
24             while (!p.empty() && h[i][p.back()] >= h[i][j]) p.pop_back();
25             p.push_back(j);
26             if (j >= b) minn[i][j] = ③;
27         }
28     }
29     while (!p.empty()) p.pop_back();
30     for (int j = 1; j <= m; ++j) {
31         while (!p.empty()) p.pop_back();
32         for (int i = 1; i <= n; ++i) {
33             while (!p.empty() && p.front() <= i - a) p.pop_front();
34             while (!p.empty() && ④) p.pop_back();
35             p.push_back(i);
36             if (i >= a && j >= b)
37                 ans += ⑤;
38         }
39     }
40     printf("%lld\n", ans);
41     return 0;
42 }

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

• g[(i - 1) * m + j]
• g[(i - 1) * m + j - 1]
• g[i * m + j - 1]
• g[i * m + j]

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

• p.pop_front();
• p.pop_back();
• p.push_back(++j);
• p.push_front(++j);

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

• h[i][1]
• h[i][0]
• h[i][p.front()]
• h[i][p.back()]

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

• minn[p.back()][j] >= minn[i][j]
• minn[p.front()][j] >= minn[i][j]
• minn[p.back()][j] <= minn[i][j]
• minn[p.front()][j] <= minn[i][j]

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

• h[p.back()][j]
• h[p.front()][j]
• minn[p.back()][j]
• minn[p.front()][j]

---