一、单项选择题

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

【第 1 题】

有 $5$ 个红球和 $5$ 个蓝球，它们除了颜色之外完全相同。将这 $10$ 个球排成一排，要求任意两个蓝色球都不能相邻，有多少种不同的排列方法？

{{ select(1) }}

• $25$
• $30$
• $6$
• $120$

【第 2 题】

在 $KMP$ 算法中，对于模式串 $P=\text{"abacaba"}$，其 $next$ 数组（$next[i]$ 定义为模式串 $P[0..i]$ 最长公共前后缀的长度，其数组下标从 $0$ 开始）的值是什么？

{{ select(2) }}

• $\{0,0,1,0,1,2,3\}$
• $\{0,1,2,3,4,5,6\}$
• $\{0,0,1,1,2,2,3\}$
• $\{0,0,0,0,1,2,3\}$

【第 3 题】

对一个大小为 $16$（下标 $0$–$15$）的数组构建线段树，查询区间 $[3,\,11]$ 时，最少需要访问多少个树结点（包括路径上的父结点和完全包含在查询区间内的结点）？

{{ select(3) }}

• 7
• 8
• 9
• 10

【第 4 题】

将字符串 “cat”、“car”、“cart”、“case”、“dog”、“do” 插入一个空的 Trie 树（前缀树）中，构建完成 Trie 树（包括根节点）共有多少个结点？

{{ select(4) }}

• 8
• 9
• 10
• 11

【第 5 题】

对于一个包含 $n$ 个结点和 $m$ 条边的有向无环图（$DAG$），其拓扑排序的结果有多少种可能？

{{ select(5) }}

• 只有 $1$ 种
• 最多 $n$ 种
• 等于 $n-m$ 种
• 以上都不对

【第 6 题】

在一个大小为 $13$ 的哈希表中，使用闭散列法的线性探查来解决冲突。哈希函数为 $H(\text{key})=\text{key}\bmod 13$。依次插入关键字 $18,\,26,\,35,\,9,\,68,\,74$，插入 $74$ 后，它最终被放置在哪个索引位置？

{{ select(6) }}

• 5
• 7
• 8
• 11

【第 7 题】

一个包含 $8$ 个顶点的完全图（顶点的编号为 $1$ 到 $8$），任意两点之间的边权等于两顶点编号的差的绝对值。例如，顶点 $3$ 和 $7$ 之间的边权重为 $|7-3|=4$。该图的最小生成树的权重是多少？

{{ select(7) }}

• 7
• 8
• 9
• 10

【第 8 题】

如果一棵二叉搜索树的后序遍历序列是 $2,\,5,\,4,\,8,\,12,\,10,\,6$，那么该树的前序遍历是什么？

{{ select(8) }}

• $6,\,4,\,2,\,5,\,10,\,8,\,12$
• $6,\,4,\,5,\,2,\,10,\,12,\,8$
• $2,\,4,\,5,\,6,\,8,\,10,\,12$
• $12,\,8,\,10,\,5,\,2,\,4,\,6$

【第 9 题】

一个 $0$-$1$ 背包问题，背包容量为 $20$。现有 $5$ 个物品，重量和价值分别为 $7,\,5,\,4,\,3,\,6$ 和 $15,\,12,\,9,\,7,\,13$。装入背包的物品能获得的最大总价值是多少？

{{ select(9) }}

• 43
• 41
• 45
• 44

【第 10 题】

在一棵以结点 $1$ 为根的树中，结点 $12$ 和结点 $18$ 的最近公共祖先（$LCA$）是结点 $4$。那么下列哪个结点的 $LCA$ 组合是不可出现的？

{{ select(10) }}

• $LCA(12,\,4)=4$
• $LCA(18,\,4)=4$
• $LCA(12,\,18,\,4)=4$
• $LCA(12,\,1)=4$

【第 11 题】

递归关系式 $T(n)=2T(n/2)+O(n^{2})$ 描述了某个分治算法的时间复杂度。请问该算法的时间复杂度是多少？

{{ select(11) }}

• $O(n)$
• $O(n\log n)$
• $O(n^{2})$
• $O(n^{2}\log n)$

【第 12 题】

在一个初始为空的最小堆（min-heap）中，依次插入元素 $20,\,12,\,15,\,8,\,10,\,5$。然后连续执行两次“删除最小值（delete-min）”操作。请问此时堆顶元素是什么？

{{ select(12) }}

• 10
• 12
• 15
• 20

【第 13 题】

$1$ 到 $1000$ 之间，不能被 $2$、$3$、$5$ 中任意一个整除的整数有多少个？

{{ select(13) }}

• 266
• 267
• 333
• 334​

【第 14 题】

斐波那契数列的定义为 $F(0)=0,\ F(1)=1,\ F(n)=F(n-1)+F(n-2)$。使用朴素递归方法计算 $F(n)$ 的时间复杂度是指数级的，而使用动态规划（或迭代）方法的时间复杂度是线性的。造成这两种巨大差异的根本原因是？

{{ select(14) }}

• 递归函数调用开销过大
• 操作系统对递归深度有限制
• 朴素递归中存在大量的重复子问题未被重复利用
• 动态规划使用了更少的数据存储空间

【第 15 题】

有 $5$ 个独立、不可抢占的任务 $A_1, A_2, A_3, A_4, A_5$ 需要在一台机器上执行（从时间 $0$ 开始执行），每个任务都有对应的处理时长和截止时刻，按顺序分别为 $3,\,4,\,2,\,5,\,1$ 和 $5,\,10,\,3,\,15,\,11$。如果某一个任务超时，相应的惩罚等于其处理时长。为了最小化总惩罚，应该优先执行哪个任务？

{{ select(15) }}

• 处理时间最短的任务 $A_5$
• 截止时间最早的任务 $A_3$
• 处理时间最长的任务 $A_4$
• 任选一个任务都可以

二、阅读程序

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

阅读程序（一）

01 #include <algorithm>
02 #include <cstdio>
03 #include <cstring>
04 bool flag[27];
05 int n;
06 int p[27];
07 int ans = 0;
08 void dfs(int k) {
09     if (k == n + 1){
10         ++ ans;
11         return;
12     }
13     for (int i = 1; i <= n; ++i) {
14         if (flag[i]) continue;
15         if (k > 1 && i == p[k - 1] + 1) continue;
16         p[k] = i;
17         flag[i] = true;
18         dfs(k + 1);
19         flag[i] = false;
20     }
21     return;
22 }
23 int main() {
24     scanf("%d", &n);
25     dfs(1);
26     printf("%d\n", ans);
27     return 0;
28 }

判断题

16. （1 分）当输入的 $n=3$ 的时候，程序输出的答案为 $3$。

    {{ select(16) }}

• 正确
• 错误

17. 在 dfs 函数运行过程中，$k$ 的取值会满足 $1\le k\le n+1$。

    {{ select(17) }}

• 正确
• 错误

18. 删除第 $19$ 行的 “flag[i]=false;”，对答案不会产生影响。

    {{ select(18) }}

• 正确
• 错误

单选题

19. 当输入的 $n=4$ 的时候，程序输出的答案为（ ）。 {{ select(19) }}

• 11
• 12
• 24
• 9

20. 如果因为某些问题，导致程序运行到第 $25$ 行的 $dfs$ 函数之前，数组 $p$ 的初值并不全为 $0$，则对程序的影响是（ ）。

    {{ select(20) }}

• 输出的答案比原答案更小
• 无法确定能输出的答案
• 程序可能陷入死循环
• 没有影响

21. 假如删去第 $14$ 行的 “if(flag[i]) continue;”，输入 $3$，得到的输出答案是（ ）。 {{ select(21) }}

• 27
• 3
• 16
• 12

阅读程序（二）

01 #include <algorithm>
02 #include <cstdio>
03 #include <cstring>
04 #define ll long long
05 int cnt_broken = 0;
06 int cnt_check = 0;
07 int n, k;
08 inline bool check(int h) {
09     printf("now check:%d\n", h);
10     ++cnt_check;
11     if (cnt_broken == 2) {
12         printf("You have no egg!\n");
13         return false;
14     }
15     if (h >= k) {
16         ++cnt_broken;
17         return true;
18     } else {
19         return false;
20     }
21 }
22 inline bool assert_ans(int h) {
23     if (h == k) {
24         printf("You are Right using %d checks\n", cnt_check);
25         return true;
26     } else {
27         printf("Wrong answer!\n");
28         return false;
29     }
30 }
31 inline void guess1(int n) {
32     for (int i = 1; i <= n; ++i) {
33         if (check(i)) {
34             assert_ans(i);
35             return;
36         }
37     }
38 }
39 inline void guess2(int n) {
40     int w = 0;
41     for (w = 1; w * (w + 1) / 2 < n; ++w)
42     ;
43     for (int ti = w, nh = w;; --ti, nh += ti, nh = std::min(nh, n)) {
44         if (check(nh)) {
45             for (int j = nh - ti + 1; j < nh; ++j) {
46                 if (check(j)) {
47                     assert_ans(j);
48                     return;
49                 }
50             }
51             assert_ans(nh);
52             return;
53         }
54     }
55 }
56 int main() {
57     scanf("%d%d", &n, &k);
58     int t;
59     scanf("%d", &t);
60     if (t == 1) {
61         guess1(n);
62     } else {
63         guess2(n);
64     }
65     return 0;
66 }

（注意：下述的“猜测次数”为调用 $check$ 函数的次数（即 $cnt\_check$ 的值）；“猜测正确”的含义为 $assert\_ans$ 函数 $return\ true$（执行第 $25$ 行 $if$ 语句）的时候。所有输入满足 $1\le k\le n$。）

判断题

22. 当输入为 “$6\ 5\ 1$” 时，猜测次数为 $5$；当输入 “$6\ 5\ 2$” 时，猜测次数为 $3$。 {{ select(22) }}

• 正确
• 错误

23. 不管输入的 $n$ 和 $k$ 具体为多少，$t=2$ 时的猜测次数总是小于等于 $t=1$ 时的猜测次数。 {{ select(23) }}

• 正确
• 错误

24. 不管 $t=1$ 或 $t=2$，程序都一定会得出正确答案。 {{ select(24) }}

• 正确
• 错误

单选题

25. 函数 $guess1$ 在运行过程中，$cnt\_broken$ 的值最多为（ ）。 {{ select(25) }}

• 0
• 1
• 2
• n

26. 函数 $guess2$ 在运行过程中，最多使用的猜测次数的量级为（ ）。

    {{ select(26) }}

• $O(n)$
• $O(n^2)$
• $O(\sqrt{n})$
• $O(\log n)$

27. 当输入的 $n=100$ 的时候，代码中 $t=1$ 和 $t=2$ 分别需要的猜测次数最多分别为（ ）。

    {{ select(27) }}

• $100,\,14$
• $100,\,13$
• $99,\,14$
• $99,\,13$

阅读程序（三）

01 #include <algorithm>
02 #include <cstdio>
03 #include <cstring>
04 #include <vector>
05 #define ll long long
06 int n, m;
07 std::vector<int> k, p;
08 inline int mpow(int x, int k) {
09     int ans = 1;
10     for (; k; k = k >> 1, x = x * x) {
11         if (k & 1)
12             ans = ans * x;
13     }
14     return ans;
15 }
16 std::vector<int> ans1, ans2;
17 int cnt1, cnt2;
18 inline void dfs(std::vector<int>& ans, int& cnt, int l, int r, int v) {
19     if (l > r) {
20         ++cnt;
21         ans.push_back(v);
22         return;
23     }
24     for (int i = 1; i <= m; ++i) {
25         dfs(ans, cnt, l + 1, r, v + k[l] * mpow(i, p[l]));
26     }
27     return;
28 }
29 std::vector<int> cntans1;
30 int main() {
31     scanf("%d%d", &n, &m);
32     k.resize(n + 1);
33     p.resize(n + 1);
34     for (int i = 1; i <= n; ++i) {
35         scanf("%d%d", &k[i], &p[i]);
36     }
37     dfs(ans1, cnt1, 1, n >> 1, 0);
38     dfs(ans2, cnt2, (n >> 1) + 1, n, 0);
39     std::sort(ans1.begin(), ans1.end());
40     int newcnt1 = 1;
41     cntans1.push_back(1);
42     for (int i = 1; i < cnt1; ++i) {
43         if (ans1[i] == ans1[newcnt1 - 1]) {
44             ++cntans1[newcnt1 - 1];
45         } else {
46             ans1[newcnt1++] = ans1[i];
47             cntans1.push_back(1);
48         }
49     }
50     cnt1 = newcnt1;
51     std::sort(ans2.begin(), ans2.end());
52     int las = 0;
53     ll ans = 0;
54     for (int i = cnt2 - 1; i >= 0; --i) {
55         for (; las < cnt1 && ans1[las] + ans2[i] < 0; ++las)
56             ;
57         if (las < cnt1 && ans1[las] + ans2[i] == 0)
58             ans += cntans1[las];
59     }
60     printf("%lld\n", ans);
61     return 0;
62 }

判断题

28. 删除第 $51$ 行的 “std::sort(ans2.begin(), ans2.end());” 后，代码输出的结果不会受到影响。

    {{ select(28) }}

• 正确
• 错误

29. 假设计算过程中不发生溢出，函数 $mpow(x,k)$ 的功能是求出 $x^k$ 的取值。 {{ select(29) }}

• 正确
• 错误

30. 代码中第 $39$ 行到第 $50$ 行的目的是为了将 $ans1$ 数组进行“去重”操作。 {{ select(30) }}

• 正确
• 错误

单选题

31. 当输入为 “$3\ 15\ 1\ 2\ -1\ 2\ 1\ 2$” 时，输出结果为（ ） {{ select(31) }}

• 4
• 8
• 0
• 10

32. 记程序结束前 $p$ 数组元素的最大值为 $P$，则该代码的时间复杂度是（）。 {{ select(32) }}

• $O(n)$
• $O\left(m^n \log m^n\right)$
• $O\left(m^{n/2} \log m^{n/2}\right)$
• $O\left(m^{n/2}\left(\log m^{n/2} + \log P\right)\right)$

33. 本题所求出的是（ ）。 {{ select(33) }}

• 满足 $a,b,c\in[1,m]$ 的整数方程 $a^3+b^3=c^3$ 的解的数量
• 满足 $a,b,c\in[1,m]$ 的整数方程 $a^2+b^2=c^2$ 的解的数量
• 满足 $x_i\in[0,m]$ 的整数方程 $\sum_{i=1}^n k_i\cdot x_i^{\,p}=0$ 的解的数量
• 满足 $x_i\in[1,m]$ 的整数方程 $\sum_{i=1}^n k_i\cdot x_i^{\,p}=0$ 的解的数量

三、完善程序

（单选题，每小题 3 分，共计 30 分）

完善程序(一)

（特殊最短路）给定一个含 $N$ 个点、$M$ 条边的带权无向图，边权非负。起点为 $S$，终点为 $T$；对于一条从 $S$ 到 $T$ 的路径，可以在整条路径中至多选择一条边作为“免费边”。当第一次经过这条被选中的边时，费用视为 $0$；如果之后再次经过该边，则仍按其原有权值计算。点和边均允许重复经过。求从 $S$ 到 $T$ 的最小总费用。

以下代码求解了上述问题，试补全程序。

01 #include <algorithm>
02 #include <iostream>
03 #include <queue>
04 #include <vector>
05 using namespace std;
06 const long long INF = 1e18;
07
08 struct Edge {
09     int to;
10     int weight;
11 };
12
13 struct State {
14     long long dist;
15     int u;
16     int used_freebie; // 0 for not used, 1 for used
17     bool operator>(const State &other) const {
18         return dist > other.dist;
19     }
20 };
21
22 int main() {
23     int n, m, s, t;
24     cin >> n >> m >> s >> t;
25
26     vector<vector<Edge>> adj(n + 1);
27     for (int i = 0; i < m; ++i) {
28         int u, v, w;
29         cin >> u >> v >> w;
30         adj[u].push_back({v, w});
31         adj[v].push_back({u, w});
32     }
33
34     vector<vector<long long>> d(n + 1, vector<long long>(2, INF));
35     priority_queue<State, vector<State>, greater<State>> pq;
36
37     d[s][0] = 0;
38     pq.push({0, s, ___①___});
39
40     while (!pq.empty()) {
41         State current = pq.top();
42         pq.pop();
43
44         long long dist = current.dist;
45         int u = current.u;
46         int used = current.used_freebie;
47
48         if (dist > ___②___) {
49             continue;
50         }
51
52         for (const auto &edge : adj[u]) {
53             int v = edge.to;
54             int w = edge.weight;
55
56             if (d[u][used] + w < ___③___) {
57                 ___③___ = d[u][used] + w;
58                 pq.push({___③___, v, used});
59             }
60
61             if (used == 0) {
62                 if (___④___ < d[v][1]) {
63                     d[v][1] = d[u][used];
64                     pq.push({d[v][1], v, 1});
65                 }
66             }
67         }
68     }
69
70     cout << __⑤__ << endl;
71     return 0;
72 }

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

• 0
• 1
• -1
• false

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

• d[u][!used]
• d[u][used]
• d[t][used]
• INF

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

• d[v][1]
• d[v][used]
• d[u][used]
• d[v][0]

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

• d[v][0]
• d[v][1]
• d[u][0]
• d[u][1]

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

• d[t][1]
• d[t][0]
• min(d[t][0], d[t][1])
• d[t][0]+d[t][1]

完善程序(二)

工厂打算通过客户反馈来间接测试生产线，从而找到存在缺陷的生产线。工厂有 $n$ 条生产线（编号 $0 \sim n-1$），已知其中恰有一条生产线存在缺陷。每一轮测试为，从若干生产线的产品取样混合成一个批次发给客户。若该批次中包含缺陷生产线的产品，客户将要求退货（结果记为 $1$），否则正常收货（记为 $0$）。受售后压力限制，在所有发货批次中，最多只能有 $k$ 次退货（即结果为 $1$ 的次数 $\le k$）。工厂的目标是，设计最少的间接测试轮数 $w$（发货总批次），保证根据客户收货或退货的反馈结果，唯一确定存在缺陷的生产线。

以下程序实现了工厂的目标，包含两部分： i) 确定 $w$ 的最小值，并设计最优测试方案； ii) 根据测试结果推断存在缺陷的生产线。 该程序确定 $w$ 最小值的方法为：由于不同的生产线故障时，测试应当返回不同的结果，因此 $w$ 轮测试的可能结果总数不应少于生产线数量。

test_subset() 函数为抽象测试接口，输入所有批次的方案并返回一个二进制编码；该编码表示为每批次的检测结果（即最低位是第 $1$ 批次、最高位是第 $w$ 批次）；其实现在此处未给出。

01 #include <algorithm>
02 #include <cstddef>
03 #include <iostream>
04 #include <vector>
05 using namespace std;
06 long long comb(int w, int i) {
07     if (i < 0 || i > w) {
08         return 0;
09     }
10     long long res = 1;
11     for (int t = 1; t <= i; ++t) {
12         res = res * (w - t + 1) / t;
13     }
14     return res;
15 }
16 
17 // 计算长度为w、1的个数 ≤ k 的码字总数
18 long long count_patterns(int w, int k) {
19     long long total = 0;
20     for (int t = 0; t <= min(w, k); ++t) {
21         total += comb(w, t);
22     }
23     return total;
24 }
25 
26 // 抽象测试接口
27 int test_subset(const vector<vector<int>> &plan);
28 int solve(int n, int k) {
29     // === 第 1 步: 求最小 w ===
30     int w = 1;
31     while (___①___) {
32         ++w;
33     }
34     cout << w << endl;
35 
36     // === 第 2 步: 生成测试方案 ===
37     vector<vector<int>> code(n, vector<int>(w, 0));
38     int idx = 0;
39     for (int ones = 0; ones <= k && idx < n; ++ones) {
40         vector<int> bits(w, 0);
41         fill(bits.begin(), bits.begin() + ones, 1);
42         do {
43             for (int b = 0; b < w; ++b) {
44                 code[idx][b] = bits[b];
45             }
46             ++idx;
47             if (idx >= n) {
48                 break;
49             }
50         } while (std::___②___);
51     }
52 
53     vector<vector<int>> plan(w);
54     for (int i = 0; i < w; ++i) {
55         for (int j = 0; j < n; ++j) {
56             if (___③___) {
57                 plan[i].push_back(j);
58             }
59         }
60     }
61 
62     // === 第 3 步: 调用测试接口 ===
63     int signature = test_subset(plan);
64 
65     // === 第 4 步: 结果解码 ===
66     vector<int> sig_bits(w, 0);
67     for (int i = 0; i < w; ++i) {
68         if (___④___) {
69             sig_bits[i] = 1;
70         }
71     }
72 
73     for (int j = 0; j < n; ++j) {
74         if (___⑤___) return j;
75     }
76 }
77 
78 int main() {
79     int n,k;
80     cin >> n >> k;
81     int ans = solve();
82     cout << ans << endl;
83     return 0;
84 }

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

• (1 << w) < n
• count_patterns(w, k) < n
• count_patterns(k, w) < n
• comb(w, k) < n

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

• next_permutation(bits.begin(), bits.end())
• prev_permutation(bits.begin(), bits.end())
• next_permutation(bits.begin(), bits.begin()+ones)
• prev_permutation(bits.begin(), bits.begin()+ones)

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

• (j >> i) & 1
• (i >> j) & 1
• code[i][j] == 1
• code[j][i] == 1

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

• (signature >> i) & 1
• (signature >> i) ^ 1
• signature | (1 << i)
• (signature >> i) | 1

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

• is_permutation(code[j].begin(), code[j].end(), sig_bits.begin())
• code[j] == sig_bits
• plan[j] == sig_bits
• code[j][i] == sig_bits[i]