试卷解析 · 理解每一步

2026-09-Level-8

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

单选题

第 1 题（单选题，2 分）

用数字 $0$ 、 $1$ 、 $2$ 、 $3$ 、 $4$ 、 $5$ 组成没有重复数字的三位数，且该三位数能被 $3$ 整除，共有（）个。

36

40

44

48

正确答案B

解析详情

答案 B整除条件与分类计数

思路与推导

一个数能被 3 整除，当且仅当各位数字和能被 3 整除。将 0 到 5 按模 3 分为 {0,3}、{1,4}、{2,5}。
三个数字互异且和为 3 的倍数，只能每类取一个，共 $2^3=8$ 组。含 0 的 4 组各有 3!−2!=4 个合法三位数，不含 0 的 4 组各有 3!=6 个。
因此总数为 $4×4+4×6=40$ ，选 B。

第 2 题（单选题，2 分）

$6$ 个人围成一圈就座，座位没有区分，但区分时针方向，且甲、乙两人必须相邻，则共有（）种不同坐法。

24

36

48

120

正确答案C

解析详情

答案 C相邻圆排列

思路与推导

把甲乙捆成一个整体，与其他四人共五个单位。座位无区别，绕圆排列有 $(5-1)!=24$ 种。
甲乙整体内部有甲乙、乙甲两种次序，因此共 $24×2=48$ 种，选 C。
题目区分时针方向，所以镜像排列不再合并。

第 3 题（单选题，2 分）

有 $4$ 堆石子，数量分别为 $1$ 、 $2$ 、 $3$ 、 $4$ 。每次可以合并相邻两堆，合并代价为两堆石子数之和。将所有石子合并成一堆的最小总代价为（）。

17

19

20

23

正确答案B

解析详情

答案 B区间动态规划

思路与推导

令 dp[l][r] 表示合并连续第 l 到 r 堆的最小代价，最后一次在 k 处分成两段，代价为两段 dp 之和再加整个区间石子数。
长度 2 的区间代价分别为 3、5、7；长度 3 的 [1,2,3] 最小为 9，[2,3,4] 最小为 14。
最后一次分割的三种总代价分别为 0+14+10=24、3+7+10=20、9+0+10=19，最小为 19，选 B。实现顺序为先合并 1、2，再与 3 合并，最后与 4 合并。

图解 · 看懂这一步比较最后一次合并的位置

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

最后分成两段	左段代价	右段代价	最终总代价
[1] 和 [2,3,4]	0	14	24
[1,2] 和 [3,4]	3	7	20
[1,2,3] 和 [4]	9	0	19

全部石子总数为 10，最后一次合并固定再付出 10；子区间已按最优方案合并。

第 4 题（单选题，2 分）

某二叉树的先序遍历序列为 A B D E C F G ，中序遍历序列为 D B E A F C G ，则其后序遍历序列为（）。

D E B F G C A

D B E F G C A

D E B G F C A

D E B F C G A

正确答案A

解析详情

答案 A二叉树遍历重建

思路与推导

先序首项 A 是根，中序在 A 处分成左子树 D B E 和右子树 F C G。
结合先序，左子树根为 B、左右孩子为 D、E；右子树根为 C、左右孩子为 F、G。
后序按左、右、根访问：先 D E B，再 F G C，最后 A，得到 D E B F G C A，选 A。

图解 · 看懂这一步由先序和中序重建二叉树

B（左子树）
- D（左）
- E（右）
C（右子树）
- F（左）
- G（右）

这是原题完整的三层树，孩子按左、右顺序排列；后序先读叶子再读父结点。

第 5 题（单选题，2 分）

关于快速幂算法，下列说法正确的是（）。

快速幂可以处理任意负指数的情况

快速幂将指数按二进制拆分，能够把乘法次数从朴素乘幂时的

O(b)

优化为

O(\log b)

快速幂只能在模数为质数时使用

快速幂的空间复杂度通常为

O(b)

正确答案B

解析详情

答案 B快速幂原理

思路与推导

把非负整数指数 b 写成二进制，通过连续平方得到 $a,a^2,a^4,a^8,\ldots$ ，只在对应二进制位为 1 时乘入答案。
每轮处理一个指数位，乘法次数降为 $O(\log b)$ ，因此 B 正确。普通模快速幂不要求模数为质数；负指数需要额外的逆元等条件。

第 6 题（单选题，2 分）

杨辉三角中，第 $7$ 行第 $3$ 个数（行、列均从 $0$ 开始计数）是（）。

21

35

42

56

正确答案B

解析详情

答案 B杨辉三角组合数

思路与推导

行列均从 0 计数时，第 n 行第 k 项为 $\binom{n}{k}$ 。
所求为 $\binom{7}{3}=7×6×5/(3×2×1)=35$ ，选 B。

第 7 题（单选题，2 分）

一个长方形的长是宽的 $3$ 倍，周长为 $48$ ，则该长方形的面积为（）。

72

96

108

144

正确答案C

解析详情

答案 C长方形方程

思路与推导

设宽为 w，长为 3w。周长为 $2(w+3w)=8w=48$ ，所以宽 w=6，长为 18。
面积为 $6×18=108$ ，选 C。

第 8 题（单选题，2 分）

若 $x+y=7$ ， $x-y=1$ ，则 $x\times y$ 的值为（）。

7

8

10

12

正确答案D

解析详情

答案 D二元一次方程

思路与推导

两式相加得 2x=8，所以 x=4；代入 x+y=7，得 y=3。
因此乘积 xy=12，选 D。也可用 $4xy=(x+y)^2-(x-y)^2=49-1$ 验证。

第 9 题（单选题，2 分）

关于最小生成树（MST）算法，下列说法正确的是（）。

Prim 算法适用于稠密图，Kruskal 算法适用于稀疏图

Prim 算法和 Kruskal 算法得到的最小生成树边集一定完全相同

Kruskal 算法必须使用邻接矩阵存储图

Prim 算法只能处理有向图

正确答案A

解析详情

答案 AMST 算法选型

思路与推导

常见朴素 Prim 使用邻接矩阵，复杂度为 $O(V^2)$ ，适合稠密图；Kruskal 排序边并用并查集选边，主要耗时为 $O(E\log E)$ ，常适合稀疏图，因此 A 正确。
两算法得到的最小总权相同，但有同权边时具体边集可能不同。Kruskal 可直接用边表，不要求邻接矩阵。

第 10 题（单选题，2 分）

某连通带权无向简单图的边集合为 $\{(1,2,5),(1,3,1),(2,3,3),(2,4,4),(3,4,2),(3,5,6),(4,5,7)\}$ ，其中，每条边的三元组 $(u,v,w)$ 表示结点 $u$ 和结点 $v$ 之间有一条权值为 $w$ 的无向边。使用 Kruskal 算法按边权从小到大扫描，第 $3$ 条被选入最小生成树的边是（）。

(1,2,5)

(2,3,3)

(3,4,2)

(4,5,7)

正确答案B

解析详情

答案 BKruskal 逐边选择

思路与推导

按权重升序首先扫描 (1,3,1)，两端尚未连通，选入；其次 (3,4,2) 连接新顶点 4，也选入。
此时连通块为 {1,3,4}，顶点 2 尚在另一块。第三条边 (2,3,3) 连接两个不同块，可以选入。
所以第三条选中的边是 (2,3,3)，对应 B。

第 11 题（单选题，2 分）

在使用小根堆（优先队列）优化的 Dijkstra 算法中，堆中每个元素通常存储的是（）。

顶点编号和该顶点当前的最短距离

边的权值和边的终点

顶点的入度

父结点编号和边权

正确答案A

解析详情

答案 ADijkstra 堆元素

思路与推导

算法需要知道“哪个顶点具有多小的候选距离”，因此堆元素保存顶点编号和到源点的候选距离，选 A。
小根堆按距离排序；松弛得到更短距离时插入新候选。常见实现允许旧条目留在堆中，弹出时用当前 dis 检查是否过期。

第 12 题（单选题，2 分）

在 Floyd 算法的经典三重循环 for (k) for (i) for (j) 中，最外层变量 k 表示（）。

当前允许作为中间顶点的最大编号（即只允许编号不超过 k 的顶点作为中间点）

当前起点

当前终点

当前最短路径的长度

正确答案A

解析详情

答案 AFloyd 阶段含义

思路与推导

第 k 轮允许编号不超过 k 的顶点作为路径中间点，在此基础上更新所有起点 i、终点 j。
转移比较原 dist[i][j] 与经过新中间点 k 的 dist[i][k]+dist[k][j]，所以 k 对应 A。

第 13 题（单选题，2 分）

下列常见复杂度量级，按渐近增长速度从慢到快排列，正确的是（）。

O(n^2)

、

O(n\log n)

、

O(n)

、

O(\log n)

O(\log n)

、

O(n)

、

O(n^2)

、

O(n\log n)

O(\log n)

、

O(n)

、

O(n\log n)

、

O(n^2)

O(n\log n)

、

O(\log n)

、

O(n)

、

O(n^2)

正确答案C

解析详情

答案 C渐近增长顺序

思路与推导

当 n 足够大时，log n 比 n 增长慢；n log n 比 n 多一个逐渐增长的 log n 因子，但仍比 n² 慢，因为 log n 远小于 n。
所以顺序为 $O(\log n),O(n),O(n\log n),O(n^2)$ ，选 C。

第 14 题（单选题，2 分）

对长度为 $n$ 的数组使用差分数组支持 $m$ 次区间加操作，最后通过一次前缀和还原每个位置的最终值，整个过程的渐进时间复杂度为（）。

O(mn)

O((n+m)\log n)

O(n\log m)

O(n+m)

正确答案D

解析详情

答案 D差分数组

思路与推导

建立长度 n 的差分数组需 O(n)。给 [l,r] 加上 c，只需 diff[l]+=c、diff[r+1]−=c，每次 O(1)，m 次共 O(m)。
最后一次前缀和还原需 O(n)，总时间为 $O(n+m)$ ，选 D。

第 15 题（单选题，2 分）

下列程序的输出结果为（）。

#include <iostream>
using namespace std;
class A {
    public:
    A() {
        cout << "A";
    }
    ~A() {
        cout << "~A";
    }
};
class B : public A {
    public:
    B() {
        cout << "B";
    }
    ~B() {
        cout << "~B";
    }
};
int main() {
    B b;
    return 0;
}

BA~A~B

BA~B~A

AB~A~B

AB~B~A

正确答案D

解析详情

答案 D继承构造与析构

思路与推导

创建 B b 时，先构造基类 A，输出 A；再执行 B 构造函数，输出 B。
main 退出销毁 b 时顺序相反：先执行 B 析构输出
B，再执行 A 析构输出
A。
完整输出是 AB
B
A，选 D。

判断题

第 1 题（判断题，2 分）

从 $4$ 本不同的书中选出 $3$ 本，分别分给甲、乙、丙 $3$ 人，每人至多 $1$ 本，共有 $P(4,3)=24$ 种不同分法。

正确答案正确

解析详情

答案正确不同对象分配

思路与推导

三本书分别给甲乙丙，每人至多一本，所以最终每人恰好一本。
按人依次选书，甲有 4 种、乙有 3 种、丙有 2 种，共 $4×3×2=24$ ，题目正确。

第 2 题（判断题，2 分）

对任意正整数 $n$ ，二项式 $(a+b)^n$ 的展开式中，按项序从第 $0$ 项起计数，奇数项系数之和等于偶数项系数之和。

正确答案正确

解析详情

答案正确奇偶项系数

思路与推导

令偶数项系数之和为 E、奇数项为 O。在二项式中代入 a=b=1，得到 E+O=2ⁿ。
再代入 a=1、b=−1；因为 n 为正整数，得到 E−O=(1−1)ⁿ=0。
因此 E=O=2ⁿ⁻¹，判断正确。

第 3 题（判断题，2 分）

若一个连通无向图的最小生成树中存在权值相同的边，则最小生成树一定不唯一。

正确答案错误

解析详情

答案错误MST 唯一性反例

思路与推导

考虑原图本身就是三顶点路径，两条边权都为 1。
任何生成树都必须包含原图这两条边，因而最小生成树唯一，却含同权边，所以题目错误。

第 4 题（判断题，2 分）

使用邻接表存储图时，Dijkstra 算法的朴素实现（不使用堆优化）的时间复杂度为 $O(V^2)$ ，其中 $V$ 为结点数。

正确答案正确

解析详情

答案正确朴素 Dijkstra

思路与推导

不使用堆时，每轮仍需在线性扫描中找最小未确定距离，至多 V 轮，因此选点耗时 O(V²)。
邻接表的全部松弛共 O(E)，总计 $O(V^2+E)$ ；在通常简单图中 E=O(V²)，故记为 O(V²)，判断正确。

第 5 题（判断题，2 分）

堆排序是一种稳定的排序算法。

正确答案错误

解析详情

答案错误堆排序稳定性

思路与推导

堆排序会把堆顶与末尾交换，即使两个元素关键字相等，也可能因此改变原有先后关系。
例如带标签的相等元素 2a、2b 在建堆和取顶过程中可能倒序，故堆排序通常不稳定。

第 6 题（判断题，2 分）

每个大于 $1$ 的整数都可以唯一地分解为若干个质因数的乘积（不考虑因子顺序）。

正确答案正确

解析详情

答案正确算术基本定理

思路与推导

每个大于 1 的整数都能不断分解成更小因子，最终得到质数乘积；其各质因子的指数唯一。
例如 $60=2^2×3×5$ ，把因子重排不改变分解结果，因此题目正确。

第 7 题（判断题，2 分）

循环队列通过牺牲一个存储单元，可以区分队空和队满两种状态。

正确答案正确

解析详情

答案正确循环队列判空判满

思路与推导

设底层容量为 N，front 指向队首、rear 指向下一插入位置。保留一个空位后，front==rear 表示空，(rear+1)%N==front 表示满。
两种状态不会重合，可用容量为 N−1，题目正确。

第 8 题（判断题，2 分）

在 C++ 语言的私有继承中，基类的 public 成员在派生类中仍为 public 成员。

正确答案错误

解析详情

答案错误私有继承访问权限

思路与推导

private 继承使基类原来的 public、protected 成员在派生类接口中成为 private 级别，而非保持 public。
因此外部不能通过派生类对象直接访问这些基类 public 成员，题目错误；基类原本 private 成员仍不能被派生类直接访问。

第 9 题（判断题，2 分）

使用滚动数组优化动态规划时，通常只能降低空间复杂度，不能降低时间复杂度。

正确答案正确

解析详情

答案正确滚动数组

思路与推导

若第 i 层 DP 只依赖上一层，可循环复用两行数组，把保存全部层的空间压缩为少量层。
但每层状态和转移通常仍要照常计算，所以一般只降低空间复杂度，不改变时间数量级，判断正确。

第 10 题（判断题，2 分）

一个三角形的三条边的边长分别为 $5$ 、 $12$ 、 $13$ ，则它的面积为 $30$ 。

正确答案正确

解析详情

答案正确勾股关系与面积

思路与推导

$5^2+12^2=25+144=169=13^2$ ，所以这是以 5、12 为直角边、13 为斜边的直角三角形。
面积为 $5×12/2=30$ ，判断正确。