一、单项选择题

第1题

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

选项：

  • A. 25
  • B. 30
  • C. 6
  • D. 120

答案：C

解析：首先，先排 5 个红色球，5 个红色球排列后会产生 6 个间隔。然后，要把 5 个蓝色球放到这 6 个间隔中，且每个间隔最多放 1 个蓝色球，这样就能保证任意两个蓝色球都不相邻。从 6 个间隔中选 5 个来放蓝色球，这是一个组合问题，组合数公式为 C65=6!5!×(6−5)!=6C_6^5 = \frac{6!}{5! \times (6-5)!} = 6。

第2题

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

选项：

  • A. (0, 0, 1, 0, 1, 2, 3)
  • B. (0, 1, 2, 3, 4, 5, 6)
  • C. (0, 0, 1, 1, 2, 2, 3)
  • D. (0, 0, 0, 1, 2, 3)

答案：A

解析：对于模式串 P = "abacaba"，计算 next 数组：

  • next[0] = 0，因为单个字符没有前后缀。
  • i = 1（字符 b），(P[0..1]) 是 "ab"，最长公共前后缀长度为 0，所以 next[1] = 0。
  • i = 2（字符 a），(P[0..2]) 是 "aba"，最长公共前后缀是 "a"，长度为 1，所以 next[2] = 1。
  • i = 3（字符 c），(P[0..3]) 是 "abac"，最长公共前后缀长度为 0，所以 next[3] = 0。
  • i = 4（字符 a），(P[0..4]) 是 "abaca"，最长公共前后缀是 "a"，长度为 1，所以 next[4] = 1。
  • i = 5（字符 b），(P[0..5]) 是 "abacab"，最长公共前后缀是 "ab"，长度为 2，所以 next[5] = 2。
  • i = 6（字符 a），(P[0..6]) 是 "abacaba"，最长公共前后缀是 "aba"，长度为 3，所以 next[6] = 3。

所以 next 数组为 (0, 0, 1, 0, 1, 2, 3)，答案是 A。

第3题

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

选项：

  • A. 7
  • B. 8
  • C. 9
  • D. 10

答案：B

解析：满段树的结构是，对于大小为 242^4（这里 16=2416 = 2^4）的数组，线段树的高度等结构有特定规律。查询区间 [3,11] 时，通过分析线段树的节点访问路径，最少需要访问 8 个树节点。

第4题

题目：将字符串 "cat", "car", "cart", "case", "dog", "do" 插入一个空的 Trie 树（前缀树）中。构建完成的 Trie 树（包括根结点）共有多少个结点？

选项：

  • A. 8
  • B. 9
  • C. 10
  • D. 11

答案：D

解析：构建 Trie 树时，根节点为 1 个。然后看各个字符串的前缀：

  • "cat"、"car"、"cart"、"case" 都以 "c" 开头，"c" 是一个节点；
  • "c" 之后，"cat" 的 "a" 和 "t"、"car" 的 "a" 和 "r"、"cart" 的 "a"、"t"、"case" 的 "a"、"s" 和 "e"，共计 7 个节点。
  • "dog"、"do" 以 "d" 开头，"d" 是一个节点，"dog" 的 "o" 和 "g"，共计 3 个节点。 包括根节点在内，共有 11 个节点，所以答案是 D。

第5题

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

选项：

  • A. 只有 1 种
  • B. 最多 n 种
  • C. 等于 n−mn - m 种
  • D. 以上都不对

答案：D

解析：有向无环图（DAG）的拓扑排序可能有很多种情况。比如简单的 DAG，可能有多个拓扑排序结果，不是只有 1 种，也不是最多 n 种，更不是等于 n−mn - m 种，所以答案是 D。

第6题

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

选项：

  • A. 5
  • B. 7
  • C. 9
  • D. 11

答案：D

解析：首先计算各关键字的哈希值：

  • H(18)=18mod  13=5H(18) = 18 \mod 13 = 5，位置 5 为空，插入 18 到位置 5。
  • H(26)=26mod  13=0H(26) = 26 \mod 13 = 0，位置 0 为空，插入 26 到位置 0。
  • H(35)=35mod  13=9H(35) = 35 \mod 13 = 9，位置 9 为空，插入 35 到位置 9。
  • H(9)=9mod  13=9H(9) = 9 \mod 13 = 9，位置 9 已被 35 占用，线性探查下一个位置 10，位置 10 为空，插入 9 到位置 10。
  • H(68)=68mod  13=3H(68) = 68 \mod 13 = 3，位置 3 为空，插入 68 到位置 3。
  • H(74)=74mod  13=9H(74) = 74 \mod 13 = 9，位置 9 有 35，探查位置 10 有 9，再探查位置 11，位置 11 为空，所以 74 最终被放置在位置 11，答案是 D。

第7题

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

选项：

  • A. 7
  • B. 8
  • C. 9
  • D. 10

答案：A

解析：对于 8 个顶点的完全图，最小生成树要选 7 条边，且总权重最小。按照边权重为两顶点编号差的绝对值，选择顶点 1-2（权重 1）、2-3（权重 1）、3-4（权重 1）、4-5（权重 1）、5-6（权重 1）、6-7（权重 1）、7-8（权重 1），总权重为 1×7=71 \times 7 = 7。

第8题

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

选项：

  • A. 6,4,2,5,10,8,12
  • B. 6,4,5,2,10,12,8
  • C. 2,4,5,6,8,10,12
  • D. 12,8,10,5,2,4,6

答案：A

解析：二叉搜索树后序遍历最后一个节点是根节点，所以根节点是 6。然后划分左子树和右子树：左子树部分是 2,5,4；右子树部分是 8,12,10。对于左子树，后序遍历最后的节点 4 是左子树的根，左子树中 2 小于 4，5 大于 4，所以 4 的左孩子是 2，右孩子是 5。对于右子树，后序遍历最后一个节点 10 是右子树的根，右子树中 8 小于 10，12 大于 10，所以 10 的左孩子是 8，右孩子是 12。前序遍历是先根，再左子树，再右子树，所以前序遍历序列为 6,4,2,5,10,8,12。

第9题

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

选项：

  • A. 43
  • B. 41
  • C. 45
  • D. 44

答案：D

解析：0-1 背包问题，用动态规划求解。设 dp[i][j] 表示前 i 个物品，背包容量为 j 时的最大价值。物品重量 w=[7,5,4,3,6]w = [7,5,4,3,6]，价值 v=[15,12,9,7,13]v = [15,12,9,7,13]，背包容量 C=20C = 20。初始化 dp[i][j] = 0。依次计算后续物品，最终计算得最大总价值为 44。答案是 D。

第10题

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

选项：

  • A. LCA(12,4)=4
  • B. LCA(12,4)=4
  • C. LCA(12,18,4)=4
  • D. LCA(12,1)=4

答案：D

解析：已知结点 12 和 18 的最近公共祖先是 4，节点 1 是根节点。对于选项 D，LCA(12,1)，因为 1 是根节点，所有节点的祖先都包含 1，所以 12 和 1 的最近公共祖先应该是 1，而不是 4，所以组合不可能出现。答案是 D。

第11题

题目：递归关系式描述了某个分治算法的时间复杂度。请问该算法的时间复杂度是多少？

选项：

  • A. O(n)O(n)
  • B. O(nlog⁡n)O(n \log n)
  • C. O(n2)O(n^2)
  • D. O(n2log⁡n)O(n^2 \log n)

答案：C

解析：用主定理（Master Theorem）来分析递归关系式 T(n)=2T(n/2)+O(n)T(n) = 2T(n/2) + O(n)。主定理形式为 T(n)=aT(n/b)+f(n)T(n) = aT(n/b) + f(n)，这里 a=2a = 2，b=2b = 2，f(n)=O(n)f(n) = O(n)。计算 log⁡ba=log⁡22=1\log_b a = \log_2 2 = 1。因为 f(n)=Ω(nlog⁡ba+ϵ)f(n) = \Omega(n^{\log_b a + \epsilon})（这里 ϵ>0\epsilon > 0，且满足正则条件），所以 T(n)=Θ(f(n))=O(n2)T(n) = \Theta(f(n)) = O(n^2)。

第12题

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

选项：

  • A. 10
  • B. 12
  • C. 15
  • D. 20

答案：A

解析：首先构建最小堆：

  • 插入 20，堆：[20]。
  • 插入 12，调整后堆：[12, 20]。
  • 插入 15，调整后堆：[12, 20, 15]。
  • 插入 8，调整后堆：[8, 12, 15, 20]。
  • 插入 10，调整后堆：[8, 10, 15, 20, 12]。
  • 插入 5，调整后堆：[5, 8, 15, 20, 12, 10]。

第一次删除最小值（5），堆调整后：[8, 10, 15, 20, 12]。 第二次删除最小值（8），堆调整后：[10, 12, 15, 20]，此时堆顶元素是 10。

第13题

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

选项：

  • A. 266
  • B. 267
  • C. 333
  • D. 734

答案：A

解析：能被 2 整除的数有 ⌊10002⌋=500\left\lfloor \frac{1000}{2} \right\rfloor = 500 个；能被 3 整除的数有 ⌊10003⌋=333\left\lfloor \frac{1000}{3} \right\rfloor = 333 个；能被 5 整除的数有 ⌊10005⌋=200\left\lfloor \frac{1000}{5} \right\rfloor = 200 个。能被 2 和 3 整除的数有 ⌊10006⌋=166\left\lfloor \frac{1000}{6} \right\rfloor = 166 个；能被 2 和 5 整除的数有 ⌊100010⌋=100\left\lfloor \frac{1000}{10} \right\rfloor = 100 个；能被 3 和 5 整除的数有 ⌊100015⌋=66\left\lfloor \frac{1000}{15} \right\rfloor = 66 个；能被 2、3 和 5 整除的数有 ⌊100030⌋=33\left\lfloor \frac{1000}{30} \right\rfloor = 33 个。根据容斥原理，能被 2、3、5 中至少一个整除的数有 500+333+200−166−100−66+33=734500 + 333 + 200 - 166 - 100 - 66 + 33 = 734 个。不能被 2、3、5 中任意一个数整除的整数有 1000−734=2661000 - 734 = 266 个。答案是 A。

第14题

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

选项：

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

答案：C

解析：朴素递归计算斐波那契数列时，会多次重复计算同一个子问题，比如计算 F(5)F(5) 时，需要计算 F(4)F(4) 和 F(3)F(3)，计算 F(4)F(4) 又需要计算 F(3)F(3) 和 F(2)F(2)，这里 F(3)F(3) 就被重复计算了。而动态规划（或迭代）方法会存储已经计算过的子问题结果，避免重复计算。所以造成时间复杂度巨大差异的根本原因是朴素递归中存在大量的重叠子问题未被重复利用。答案是 C。

第15题

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

选项：

  • A. 处理时间最短的任务 A5
  • B. 截止时间最早的 A3
  • C. 处理时间最长的任务 A4
  • D. 任何一个任务都可以

答案：B

解析：为了最小化总惩罚，要尽早完成尽可能多的任务。优先执行截止时间最早的任务，这样能确保截止早的任务不超时，减少因截止时间早的任务超时带来的惩罚。若截止早的任务超时，可能因时间紧迫导致后续更多任务超时，进而导致获得惩罚时间。所以应该优先执行截止时间最早的 A3，后续所有任务都能完成，实现总惩罚最小化。

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

(1)

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题

题目：当输入的 n=3n = 3 的时候，程序输出的答案为 3。

答案：v

解析：枚举所有 1-3 的排列（6 个），剔除含有相邻 x, x+1（后一项等于前一项+1）的排列，剩下 3 个：1 3 2、2 1 3、3 2 1 → 共 3 个。

第17题

题目：在 dfs 运行过程中，k 的取值会满足 1≤k≤n+11 \leq k \leq n+1。

答案：v

解析：dfs 从 k=1k = 1 开始，递归每次 k+1k + 1，当 k==n+1k == n + 1 时触发计数并返回，所以 kk 的取值范围确实是 1 到 n+1n+1。

第18题

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

答案：x

解析：flag[i] = false 是回溯必需的复原操作，若删掉则被选过的 i 永远无法在同层后续分支中再次使用，导致搜索树被破坏，答案会改变（一般会变小或为 0 等错误值）。

第19题

题目：当输入的 n=4n = 4 的时候，程序输出的答案为 11。

选项：

  • A. 11
  • B. 12
  • C. 24
  • D. 9

答案：A

解析：对 1-4 全排列（24 个）逐一剔除任何含有相邻 x, x+1（后一项 = 前一项 + 1）的排列，剩余计数为 11（可分首项分别计数：以 1 开头得 2，以 2、3、4 开头分别得 3、3、3，合计 11）。

第20题

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

选项：

  • A. 输出的答案比原答案要小
  • B. 无法确定输出的答案
  • C. 程序可能陷入死循环
  • D. 没有影响

答案：D

解析：在程序执行过程中，p[k] 在进入 k 层时会被赋值 p[k] = i，并且访问 p[k-1] 时该位置必然是在当前递归路径上已被赋值的（不会读取未被初始化的位置）。因此 p 初始是否为 0 不影响判定逻辑与最终计数（前提是按正常流程执行、p 的被读位置在被写之后）。

第21题

题目：假如删去第 14 行的 “if (flag[i]) continue;”，输入 3，得到的输出答案是：

选项：

  • A. 27
  • B. 3
  • C. 16
  • D. 12

答案：C

解析：删除 flag 检查后允许重复选取数字（等价于从 (1,2,3) 中有放回地取长度为 3 的序列），总序列数 33=273^3 = 27，但要删除含有相邻项对 (x, x+1) 的序列。直接用状态转移或枚举可得满足 “不含相邻后项等于前项 +1” 的长度 3 序列共有 16 个（可用递推计算：长度 1 各 1；长度 2 各结尾计数为 (3,2,2) → 总 7；长度 3 各结尾计数为 (7,4,5) → 总 16）。

(2)

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行所在分支）的情况；所有输入保证 1 ≤ k ≤ n。）

判断题

第22题

题目：当输入为 “6 5 1” 时，猜测次数为 5；当输入 “6 5 2” 时，猜测次数为 3。

答案：√

解析：

  • 输入 “6 5 1”：guess1 依次调用 check(1) 到 check(5)，共 5 次，在 i=5 时首次找到对应的值。
  • 输入 “6 5 2”：w=3（因 1+2+3=61+2+3=6）。调用顺序为 check(3) → check(5) → check(4)，共 3 次。

第23题

题目：不管输入的 n 和 k 具体为多少，t=2 时的猜测数总是小于等于 t=1 时的猜测数。

答案：×

解析：反例：n=100, k=1。

  • t=1：只需调用 check(1) 一次。
  • t=2：guess2 至少需要 2 次（先高层一次，再低层补查一次）。并非总是 t=2 不劣于 t=1。

第24题

题目：不管 t=1 或 t=2，程序都一定会猜到正确结果。

答案：√

解析：

  • t=1：线性扫描，必在 i=k 首次找到对应的值并返回正确。
  • t=2：三角数分层法，找到区间上届 nh 后在区间 [nh-ti+1, nh-1] 线性补查；若都未找到合适的值则 nh=k，均能命中。

单选题

第25题

题目：函数 guess1 在运行过程中，cnt_broken 的值最多为()。

选项：

  • A. 0
  • B. 1
  • C. 2
  • D. n

答案：B

解析：在 i < k 时未找到相应的值，到 i=k 首次找到合适的值后立即返回，因此 cnt_broken 最多增加 1 次。

第26题

题目：函数 guess2 在运行过程中，最多使用的猜测次数的量级为()。

选项：

  • A. O(n)O(n)
  • B. O(n2)O(n^2)
  • C. O(n)O(\sqrt{n})
  • D. O(log⁡n)O(\log n)

答案：C

解析：取最小 w 使得三角数 w(w+1)2≥n\frac{w(w+1)}{2} \geq n。外层至多试 w 次，找到上界后，内层最多试 ti-1 次，总次数上界为 w，量级 O(n)O(\sqrt{n})。

第27题

题目：当输入的 n=100 时，代码中 t=1 和 t=2 分别需要的猜测次数最多分别为()。

选项：

  • A. 100, 14
  • B. 100, 13
  • C. 99, 14
  • D. 99, 13

答案：A

解析：

  • t=1 最坏情况是 k=n，需检查 n 次，即 100 次。
  • t=2 时取最小 w 使得三角数 w(w+1)2≥100\frac{w(w+1)}{2} \geq 100，得 w=14（因 14×152=105\frac{14 \times 15}{2} = 105）。最坏情况下（如 k=100），外层跳到 100 才找到区间上届（12 次），随后在线性区间再查 2 次，总计 14 次。

(3)

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: }

判断题

  1. 删除第 51 行的 “std::sort (ans2.begin (),ans2.end ());” 后，代码输出的结果不会受到影响。
  • [答案] ✕
  • 解析：程序后面对 ans2 是按从大到小的顺序遍历，并使用单调递增的 las 指针在 ans1 上前进以满足 ans1[las] + ans2[i] >= 0 的条件。这个双指针策略依赖于 ans2 已经按升序排列（从而倒序访问为降序）。如果 ans2 未排序，las 的单调性就被破坏，算法结果不再可靠，因此删除排序可能改变输出。
  1. 假设计算过程中不发生溢出，函数 mpow (x,k) 的功能是求出 x^k 的取值。
  • [答案] ✓
  • 解析：mpow 使用二进制快速幂的标准实现：当 k 的二进制位为 1 时把当前 x 累乘到 ans，每一步把 x 平方并把 k 右移一位。
  1. 代码中第 39 行到第 50 行的目的是为了将 ans1 数组进行 “去重” 操作。
  • [答案] ✓
  • 解析：那段代码先对 ans1 排序，然后压缩等值连续段，把 ans1 压缩成唯一值列表，同时用 cntans1 记录每个唯一值原来的出现次数——这就是去重并统计频次的操作。

单选题

  1. 当输入为 “3 15 1 2 -1 2 1 2” 时，输出结果为（ ）
  • A. 4
  • B. 8
  • C. 0
  • D. 10
  • 答案：B
  • 解析：解析输入含义：n=3，m=15，三对 (k,p) 为 (1,2), (-1,2), (1,2)。求满足 x12+x22+x32=0x_1^2 + x_2^2 + x_3^2 = 0 即 x22=x12+x32x_2^2 = x_1^2 + x_3^2，其中 x1,x2,x3∈{1,...,15}x_1, x_2, x_3 \in \{1, ..., 15\}。已知满足条件的毕达哥拉斯三元组有 4 组，每组贡献 2 种排列，共 4×2=84 \times 2 = 8 个解。
  1. 记程序结束前 p 数组元素的最大值为 P，则该代码的时间复杂度是（ ）
  • A. O(n)
  • B. O(m^n log m^n)
  • C. O(m^{n/2} log m^{n/2})
  • D. O(m^{n/2}(log m^{n/2}+log P))
  • 答案：D
  1. 本题所求出的是（ ）。
  • A. 满足 a,b,c ∈[1, m] 的整数方程 a3+b3=c3a^3+b^3=c^3 解的数量
  • B. 满足 a,b,c ∈[1, m] 的整数方程 a2+b2=c2a^2+b^2=c^2 解的数量
  • C. 满足 xi∈[0,m]x_i ∈[0, m] 的整数方程 ∑i=1nki⋅xipi=0\sum_{i=1}^n k_i \cdot x_i^{p_i} = 0 的解的数量
  • D. 满足 xi∈[1,m]x_i ∈[1, m] 的整数方程 ∑i=1nki⋅xipi=0\sum_{i=1}^n k_i \cdot x_i^{p_i} = 0 的解的数量
  • 答案：D
  • 解析：DFS 对每个变量枚举 i ∈ 1..m，并累加 k[i]⋅ip[i]k[i] \cdot i^{p[i]}。因此变量取值范围是 [1, m]，最终统计所有组合使总和为 0 的数量。

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

（1）（特殊最短路）

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

A. 0

B. 1

C. -1

D. false

答案：A

解析：一开始，我们将起点 s 加入优先队列。此时的初始状态是：距离为 0，且还没有使用免费机会。代码中用 0 代表“未使用”，1 代表“已使用”。

  1. ②处应填()

A. d[u][!used]

B. d[u][used]

C. d[t][used]

D. INF

答案：B

解析：这是 Dijkstra 算法的一个优化。如果当前从队列中取出的路径距离 dist 比已经记录的到达该状态 (u, used) 的最短距离 d[u][used] 还要长，说明这是一条过时的、较差的路径，无需再进行扩展，可以直接跳过。

  1. ③处应填()

A. d[v][1]

B. d[v][used]

C. d[u][used]

D. d[v][0]

答案：B

解析：这行代码是在进行“松弛”操作，计算通过常规付费方式（未使用免费机会，或免费机会已用完）到达邻居节点 v 的新路径成本。新成本是 d[u][used] + w，需要和当前记录的到达 (v, used) 状态的最短距离 d[v][used] 进行比较。

  1. ④处应填()

A. d[v][0]

B. d[v][1]

C. d[u][0]

D. d[u][1]

答案：C

解析：这个代码块处理的是第一次使用免费机会的情况 if (used == 0)。从一个“未使用”状态 (u, 0) 出发，免费通过边到达 v，目标状态变为“已使用” (v, 1)。新路径的成本就是到达 (u, 0) 时的成本，即 d[u][0]。

  1. ⑤处应填()

A. d[t][1]

B. d[t][0]

C. min(d[t][0], d[t][1])

D. d[t][0] + d[t][1]

答案：C

解析：考虑这样的一个例子，如果 S 和 T 是同一个点，那么 d[T][0] = 0，但是 d[T][1] = INF。故如果只考虑 d[T][1] 是错的，所以答案是 min(d[T][0], d[T][1])。

（2）（最优测试）

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

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

以下是图片中的题目和文字解析：

  1. 处应填（ ）。

A. (1 << w) < n

B. count_patterns(w, k) < n

C. count_patterns(k, w) < n

D. comb(w, k) < n

答案：B. count_patterns(w, k) < n

解析：我们的目标是为了找到找到满足条件的最小测试次数w。为了能唯一区分n条不同的生产线，我们必须为每一条线都分配一个独一无二的“签名”。这个签名是一个长度为w的二进制码，并且由于最多只能有k次退货，所以签名中1的数量不能超过k。因此，我们能使用的有效签名的总数，必须大于或等于生产线的总数n。count_patterns(w, k)函数的功能正是计算“长度为w，且1的数量不超过k”的二进制码的总数，while循环的条件应该是在“条件不满足时继续循环”。因此，当可用签名的总数count_patterns(w, k)还小于n时，意味着w不够大，无法满足为每条生产线分配唯一签名的要求，所以需要执行++w来增加测试次数。A选项是不考虑k限制时的条件，与本题题意不符；B选项完全符合上述逻辑推导；C选项参数位置错误；D选项只计算了1的数量恰好为k的情况，忽略了1的数量小于k的情况。

  1. 处应填（ ）。

A. next_permutation(bits.begin(), bits.end())

B. prev_permutation(bits.begin(), bits.end())

C. next_permutation(bits.begin(), bits.begin()+ones)

D. prev_permutation(bits.begin(), bits.begin()+ones)

答案：B. prev_permutation(bits.begin(), bits.end())

解析：next_permutation会导致循环提前终止；prev_permutation逻辑正确，能从最大排列开始完整遍历；C和D选项只对向量的前半部分（全是1）进行排列，没有任何效果。

  1. 处应填（ ）。

A. (j >> i) & 1

B. (i >> j) & 1

C. code[i][j] == 1

D. code[j][i] == 1

答案：D. code[j][i] == 1

解析：A和B选项与精心构造的code矩阵无关，是一种不同的测试方案；C选项索引颠倒，可能导致程序越界错误；D选项索引正确，准确地表达了“检查生产线j的签名中对应于测试i的那一位”。

  1. 处应填（ ）。

A. (signature >> i) & 1

B. (signature >> i) ^ 1

C. signature | (1 << i)

D. (signature >> i) | 1

答案：A. (signature >> i) & 1

解析：这段代码将测试接口返回的整数signature解码成一个二进制向量sig_bits。signature是一个位掩码（bitmask），其二进制的第i位代表第i次测试的结果。B选项是异或操作，不是用来检查位的；C选项是或操作，这是用来将第i位置为1，而不是检查；D选项移位后与1进行或操作，结果几乎总是真，逻辑错误。

  1. 处应填（ ）。

A. is_permutation(code[j].begin(), code[j].end(), sig_bits.begin())

B. code[j] == sig_bits

C. plan[j] == sig_bits

D. code[j][i] == sig_bits[i]

答案：B. code[j] == sig_bits

解析：当前选项为最后一步，是为了找到有缺陷的生产线。方法是将实际测试得到的结果签名sig_bits与我们预先为每一条生产线j生成的签名code[j]进行比较。sig_bits是一个vector，代表实际的测试结果。code[j]也是一个vector，代表生产线j的预设签名。if语句需要判断这两个向量是否完全相等。C++标准库为std::vector重载了==运算符。当使用vector1 == vector2时，它会首先比较两个向量的大小，如果大小不同则返回false；如果大小相同，则会逐一比较对应位置的元素，只有所有元素都相等时才返回true。这完美地满足了我们“精确匹配签名”的需求。A选项is_permutation检查一个向量是否是另一个的排列，但排列关系不代表相同的测试结果；C选项plan是测试计划，plan[j]存储的是参与测试j的生产线列表，其数据结构和含义都与签名sig_bits不匹配；D选项是一个元素的比较，而if语句需要一个对整个签名的判断，此外，变量i在这个for循环中没有定义。

  1. Language
  2. 兼容模式
  3. 主题
  3. Worker 0, 114ms
  4. Powered by Hydro v5.0.0-beta.9 Community