试卷解析 · 理解每一步

2026-06-Level-8

试卷解析总览，可直接查看每题答案与解析。

单选题

第 1 题（单选题，2 分）

从 7 本不同的算法书和 5 本不同的数学书中选出 4 本，要求两类书都至少选 1 本，共有（）种不同选法。

420

455

465

495

正确答案B

解析详情

答案 B补集计数

思路与推导

从全部 12 本书中任选 4 本，有 $\binom{12}{4}=495$ 种。
排除全选算法书的 $\binom{7}{4}=35$ 种，以及全选数学书的 $\binom{5}{4}=5$ 种，两类互不重叠。
合法方案为 $495-35-5=455$ ，选 B。

第 2 题（单选题，2 分）

6 个人排成一排照相，其中甲、乙两人不能相邻，共有（）种不同排法。

240

480

600

720

正确答案B

解析详情

答案 B不相邻排列

思路与推导

六个人任意排列有 $6!=720$ 种。
把甲乙捆在一起，相邻方案有 $5!×2=240$ 种；其中乘 2 表示甲乙、乙甲两种内部顺序。
因此不相邻方案为 $720-240=480$ ，选 B。

第 3 题（单选题，2 分）

展开式 $\left(x^2-\frac{1}{x}\right)^6$ 中，常数项的系数为（）。

正确答案C

解析详情

答案 C二项式常数项

思路与推导

设六个因子中有 k 个选 −1/x，其余选 x²，则 x 的总指数为 $2(6-k)-k=12-3k$ 。
常数项要求指数为 0，解得 k=4。系数为 $\binom{6}{4}(-1)^4=15$ ，选 C。

第 4 题（单选题，2 分）

下面代码用于预处理组合数，横线处应填入的是（）。

for (int i = 0; i <= n; i++) {
    c[i][0] = c[i][i] = 1;
    for (int j = 1; j < i; j++)
        c[i][j] = __________;
}

c[i - 1][j - 1] + c[i - 1][j]

c[i][j - 1] + c[i - 1][j - 1]

c[i - 1][j] + c[i][j + 1]

c[i][j - 1] * c[i - 1][j]

正确答案A

解析详情

答案 A杨辉三角递推

思路与推导

从 i 个元素中选 j 个，按最后一个元素是否入选分类：不选它有 C(i−1,j) 种，选它有 C(i−1,j−1) 种。
两类相加得 c[i−1][j−1]+c[i−1][j]，选 A；j=0 或 j=i 的边界已经设为 1。

第 5 题（单选题，2 分）

下列程序输出的值为（）。

#include <iostream>
using namespace std;
long long qpow(long long a, long long b, long long mod) {
    long long ans = 1 % mod;
    while (b) {
        if (b & 1)
            ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}
int main() {
    cout << qpow(3, 20, 17) << endl;
    return 0;
}

正确答案C

解析详情

答案 C模快速幂计算

思路与推导

连续平方并模 17： $3^2≡9$ ， $3^4≡81≡13$ ， $3^8≡13^2≡16$ ， $3^{16}≡16^2≡1$ 。
20=16+4，因此 $3^{20}≡3^{16}×3^4≡1×13≡13\pmod{17}$ ，选 C。

第 6 题（单选题，2 分）

归并排序每次把长度为 $n$ 的序列分成两个规模约为 $\frac{n}{2}$ 的子序列，递归排序后再用线性时间合并。该算法的时间复杂度通常为（）。

O(n)

O(n^2)

O(\log n)

O(n \log n)

正确答案D

解析详情

答案 D归并排序层次分析

思路与推导

每次把区间分成约一半大小，直到长度 1，共 $O(\log n)$ 层。
每层所有区间的总长度仍为 n，因此该层线性合并总代价为 O(n)。相乘得到 $O(n\log n)$ ，选 D。

第 7 题（单选题，2 分）

在平面直角坐标系中，三角形三个顶点为 $(1,1)$ 、 $(5,2)$ 、 $(3,6)$ ，该三角形面积为（）。

正确答案A

解析详情

答案 A叉积求三角形面积

思路与推导

以 A=(1,1) 为起点，AB=(4,1)，AC=(2,5)。
两向量的二维叉积为 $4×5-1×2=18$ ，其绝对值是对应平行四边形面积。
三角形面积为其一半，即 9，选 A。

第 8 题（单选题，2 分）

某程序需要判断点 P(x,y) 是否在以原点为圆心、半径为 5 的圆内或圆上。下列判断条件正确的是（）。

x * x + y * y <= 25

abs(x) + abs(y) <= 5

x * x - y * y <= 25

x + y <= 5

正确答案A

解析详情

答案 A圆内判定

思路与推导

点到原点的距离平方为 $x^2+y^2$ ，半径平方为 25。
因两者非负，比较平方与比较距离等价；圆内或圆上要求 $x^2+y^2≤25$ ，选 A。

第 9 题（单选题，2 分）

某无向带权图有边 (1,2,4) 、 (1,3,2) 、 (2,3,1) 、 (2,4,5) 、 (3,4,8) 、 (3,5,10) 、 (4,5,2) 。该图最小生成树的总权值为（）。

正确答案D

解析详情

答案 DKruskal 手推

思路与推导

按边权升序选边：先选 2—3（1），再选 1—3（2）和 4—5（2），此时有连通块 {1,2,3}、{4,5}。
1—2（4）会在第一个块内形成环，应跳过。再选 2—4（5）连接两块，得到 5 个顶点的 4 条树边。
总权为 $1+2+2+5=10$ ，选 D。

图解 · 看懂这一步Kruskal 选边记录

左右滑动表格，可查看完整内容。

扫描边	权重	操作	已选总权
2—3	1	选入	1
1—3	2	选入	3
4—5	2	选入	5
1—2	4	跳过：两端已连通	5
2—4	5	选入：连接两个块	10

成环的边跳过；选满 4 条边后，5 个顶点已连通。

第 10 题（单选题，2 分）

有向非负权图边为 $1\to 2(3)$ 、 $2\to 4(4)$ 、 $1\to 3(10)$ 、 $3\to 4(1)$ 、 $2\to 3(2)$ 。使用 Dijkstra 算法从 1 号顶点出发到 4 号顶点的最短距离为（）。

正确答案A

解析详情

答案 ADijkstra 松弛过程

思路与推导

从 1 出发，先得 d₂=3、d₃=10。确定顶点 2 后，更新 d₃=3+2=5，d₄=3+4=7。
下一步确定顶点 3，利用 3→4 将 d₄ 改为 5+1=6。
最短路径为 1→2→3→4，距离 6，选 A。

图解 · 看懂这一步Dijkstra 的距离变化

左右滑动表格，可查看完整内容。

刚确定的顶点	d(2)	d(3)	d(4)
初始化	∞	∞	∞
1	3	10	∞
2	3	5	7
3	3	5	6
4	3	5	6

∞ 表示尚不可达；每步选出未确定顶点中距离最小者。

第 11 题（单选题，2 分）

下列代码片段的时间复杂度为（）。

long long s = 0;
for (int i = 1; i <= n; i++) {
    for (int j = 1; j * j <= n; j++) {
        s += i + j;
    }
}

O(n)

O(n \log n)

O(n \sqrt{n})

O(n^2)

正确答案C

解析详情

答案 C嵌套循环次数

思路与推导

外层 i 从 1 到 n，执行 n 次；内层条件 j²≤n 与 i 无关，每次执行 $\lfloor\sqrt n\rfloor$ 次。
总次数为 $n\lfloor\sqrt n\rfloor$ ，每次做常数工作，因此 $O(n\sqrt n)$ ，选 C。

第 12 题（单选题，2 分）

某优化问题的答案是 [1, M] 内的整数，存在单调判定函数 check(x)，且每次判定的时间复杂度为 O(n)。使用二分答案求最小可行值，整体时间复杂度通常为（）。

O(nM)

O(n log M)

O(M log n)

O(n + M)

正确答案B

解析详情

答案 B二分答案复杂度

思路与推导

候选答案区间初始长度为 M，二分每次缩小约一半，故需 $O(\log M)$ 次 check。
每次判定耗时 O(n)，总耗时为 $O(n\log M)$ ，选 B。单调性确保可根据判定结果安全丢弃半个区间。

第 13 题（单选题，2 分）

下列线性筛的代码片段中，当枚举到质数 p 且 i % p == 0 时，使用 break; 语句停止继续枚举。这样做的主要目的是（）。

for (int i = 2; i <= n; ++i) {
    if (!is_composite[i])
        primes.push_back(i);
    for (int p : primes) {
        if (i * p > n)
            break;
        is_composite[i * p] = true;
        if (i % p == 0)
            break;  // 这条语句的目的是？
    }
}

保证递归深度不超过

O(\log n)

。

保证每个合数只被它的最小质因子筛去一次。

保证每个素数都被标记为合数。

把筛法时间复杂度提高到

O(n\log n)

。

正确答案B

解析详情

答案 B线性筛不重复原则

思路与推导

质数 p 按升序枚举，当 p 整除 i 时，p 就是 i 的最小质因子。
标记 i*p 后，如果继续用更大质数 q，i*q 的最小质因子仍是 p，会与其他位置的筛除重合。因此立即 break，保证合数只按最小质因子筛一次，选 B。

第 14 题（单选题，2 分）

在 C++ 中，关于类的继承和构造、析构顺序，下列说法正确的是（）。

派生类可以直接访问基类的 private 成员。

基类的 protected 成员在私有继承后会变成派生类的 public 成员。

创建派生类对象时，会先调用基类构造函数，再调用派生类构造函数。

销毁派生类对象时，会先调用基类析构函数，再调用派生类析构函数。

正确答案C

解析详情

答案 C构造顺序

思路与推导

创建派生类对象时，先构造其基类子对象，再执行派生类自身构造过程，因此 C 正确。
销毁顺序相反，先派生类后基类。基类 private 成员不能直接由派生类访问，private 继承也不会把 protected 成员公开。

第 15 题（单选题，2 分）

将4个元素按1,2,3,4的顺序入栈，在该过程中可随时插入出栈操作。下列序列中不可能作为出栈序列的是（）。

1, 2, 3, 4

2, 1, 4, 3

3, 2, 1, 4

3, 1, 2, 4

正确答案D

解析详情

答案 D栈序列合法性

思路与推导

要先输出 3，必须依次把 1、2、3 入栈，再弹出 3。此时栈顶为 2，1 在其下面。
因此下一个只能先弹出 2，不能绕过它输出 1；序列 3,1,2,4 不可能，选 D。

判断题

第 1 题（判断题，2 分）

若一项任务可从两种互斥的方案中选择一种完成，其中，方案A有m种做法，方案B有n种做法，则总做法数为 m+n 。

正确答案正确

解析详情

答案正确分类加法

思路与推导

两种方案互斥且任选一种即可完成任务，因此 A 的 m 种与 B 的 n 种没有重复。
合并得到 m+n 种，正确；若任务要求两步都完成，才考虑乘法原理。

第 2 题（判断题，2 分）

将 n 个不同元素围成一圈，若只把旋转视为同一种排法、翻转仍视为不同排法，则方案数为 (n-1)! 。

正确答案正确

解析详情

答案正确圆排列

思路与推导

n 个不同元素排成直线有 n! 种，每个圆排列有 n 个不同起点对应这些线性表示。
只消除旋转重复，得到 $n!/n=(n-1)!$ ，判断正确；翻转没有被视为等价，不应再除以 2。

第 3 题（判断题，2 分）

从 n 个不同元素中可重复地选取 k 个且不考虑顺序，方案数为 C(n+k,k) 。

正确答案错误

解析详情

答案错误可重复组合

思路与推导

从 n 种元素中选 k 个且不计顺序，相当于求 n 个非负整数的和为 k。
隔板法得到 $\binom{n+k-1}{k}$ ，不是 $\binom{n+k}{k}$ 。例如 n=1 时只能选同一种元素，只有 1 种，而题中式子给出 k+1，故错误。

第 4 题（判断题，2 分）

杨辉三角中的组合数满足 C(n,k)=C(n-1,k)+C(n-2,k) 。

正确答案错误

解析详情

答案错误组合数递推

思路与推导

按某个指定元素选或不选分类，正确恒等式为 $\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}$ 。
例如 n=4、k=2，左侧为 6，题中右侧为 3+1=4，直接不等，因此错误。

第 5 题（判断题，2 分）

快速幂通过二进制拆分指数，可以在 $O(\log b)$ 时间内计算 $a^b \bmod m$ 。

正确答案正确

解析详情

答案正确快速幂

思路与推导

把 b 写成二进制，每个 1 位对应一个 $a^{2^k}$ 因子，底数连续平方生成这些幂。
每轮处理一个二进制位，指数约减半，因此在固定宽度算术模型下耗时 $O(\log b)$ ，题目正确。

第 6 题（判断题，2 分）

只要图中不存在负权环，Dijkstra 算法就一定能正确处理带负权边的图。

正确答案错误

解析详情

答案错误Dijkstra 与负边

思路与推导

考虑边 s→a=2、s→b=3、b→a=−2，该图没有环，更没有负权环。
标准 Dijkstra 会先确定 a 的距离为 2，但实际最短路 s→b→a 长度为 1，已确定的距离可能被后续负边改进。
所以仅“无负环”不足以保证 Dijkstra 正确。

第 7 题（判断题，2 分）

若一张连通无向图所有边权两两不同，则它的最小生成树一定唯一。

正确答案正确

解析详情

答案正确不同边权与唯一 MST

思路与推导

设存在两棵不同 MST，取其边集差中权重最小的边 e，将 e 加入不含它的那棵树会形成环。
这个环上必有一条属于边集差的另一条边 f；边权两两不同且 e 最轻，因此 f 更重。用 e 替换 f 会得到更轻生成树，与最小性矛盾。
故 MST 唯一，判断正确。

第 8 题（判断题，2 分）

判断点 $(x,y)$ 是否在以原点为圆心、半径为 $r$ 的圆内或圆上时，可以比较 $x^2+y^2$ 与 $r^2$ ，不必先开平方。

正确答案正确

解析详情

答案正确距离平方比较

思路与推导

点到原点距离是 $\sqrt{x^2+y^2}$ ，半径 r 非负。平方函数在非负区间单调递增。
所以距离≤r 等价于 $x^2+y^2≤r^2$ ，不必先开平方，正确；实现时需防止平方溢出。

第 9 题（判断题，2 分）

若能写出判定函数 check(x)，表示“答案为 x 时是否可行”，即使 check(x) 不满足单调性，也一定可以使用二分答案求最优解。

正确答案错误

解析详情

答案错误二分所需单调性

思路与推导

二分根据 check(mid) 的结果排除一半区间，必须知道那半边不可能包含更优答案，这依赖判定的单调性。
若可行性是“真、假、真”交替分布，某个中点为假并不能决定应向哪一侧寻找，因此不一定可二分，题目错误。

第 10 题（判断题，2 分）

归并排序是一种稳定排序算法，常见实现的时间复杂度为 $O(n\log n)$ 。

正确答案正确

解析详情

答案正确归并排序

思路与推导

归并时若两侧元素相等，先取左半边元素，便能保留相等关键字的原顺序，因此标准实现稳定。
二分产生 O(log n) 层，每层总合并量 O(n)，总复杂度为 $O(n\log n)$ ，题目正确。