试卷解析 · 理解每一步

2026-03-Level-8

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

单选题

第 1 题（单选题，2 分）

某班级有8名男生和6名女生，现要选出3人组成学习小组，要求小组中至少有1名男生和1名女生，则不同的选法共有（）种。

112

168

224

288

正确答案D

解析详情

答案 D互补计数

思路与推导

从 14 人任意选 3 人，有 $\binom{14}{3}=364$ 种。
不满足要求的是全男和全女，分别为 $\binom{8}{3}=56$ 、 $\binom{6}{3}=20$ ，两类不重叠。
因此合法方案数为 $364-56-20=288$ ，选 D。

第 2 题（单选题，2 分）

在杨辉三角中，从第0行开始计数，第10行的所有数之和为（）。

512

1024

2048

4096

正确答案B

解析详情

答案 B杨辉三角行和

思路与推导

从 0 行开始时，第 10 行对应 $(a+b)^{10}$ 的各项系数。
令 a=b=1，系数之和即 $2^{10}=1024$ ，选 B。

第 3 题（单选题，2 分）

下列代码实现了快速幂算法，其时间复杂度为（）。

long long fastPow(long long b, long long e, long long mod) {
    long long result = 1;
    while (e > 0) {
        if (e & 1)
            result = result * b % mod;
        b = b * b % mod;
        e >>= 1;
    }
    return result;
}

O(\log b)

O(\log e)

O(\log mod)

O(e)

正确答案B

解析详情

答案 B快速幂复杂度

思路与推导

每轮用 e&1 判断最低二进制位，再把底数平方、指数右移一位。
右移使 e 约减半，直到变为 0，循环次数等于 e 的二进制位数，为 $O(\log e)$ ，选 B。每轮只做常数次算术操作。

第 4 题（单选题，2 分）

从5本不同的数学书和4本不同的物理书中选取3本书，要求至少包含1本数学书，则不同的选法有（）种。

正确答案C

解析详情

答案 C至少一本数学书

思路与推导

先从全部 9 本不同书中选 3 本，有 $\binom{9}{3}=84$ 种。
唯一不满足要求的类别是全选物理书，共 $\binom{4}{3}=4$ 种，因此合法方案有 $84-4=80$ ，选 C。

第 5 题（单选题，2 分）

在二叉搜索树（BST）中，若中序遍历的序列为 $\{1, 2, 3, 4, 5\}$ ，且先序遍历的第一个序列元素为 3，则下列说法正确的是（）。

该树一定是一棵完全二叉树

元素4和5不可能是兄弟节点

元素1所在节点的深度可能大于3（根节点深度为1）

元素2一定是元素1的父节点

正确答案B

解析详情

答案 B遍历与 BST 结构

思路与推导

先序第一个元素为根，因此根是 3。BST 性质使 1、2 位于左子树，4、5 位于右子树。
右子树只有 4、5 两个结点，二者必为父子关系，不可能作为两个兄弟同时挂在另一个右子树结点下，所以 B 正确。
左子树两结点可由 1 或 2 为根，不能确定 2 一定是 1 的父亲，且全树最大深度不超过 3。

第 6 题（单选题，2 分）

在一个有向带权图中，使用Dijkstra算法求单源最短路时，若使用优先队列（小根堆）优化，其时间复杂度为（）。

O(V^2)

O(V \cdot E)

O((V + E) \log V)

O(V^2 \log V)

正确答案C

解析详情

答案 C堆优化最短路

思路与推导

Dijkstra 在非负权前提下，用小根堆维护候选距离。顶点相关操作与边松弛总计 O(V+E)，堆操作通常带来 log V 因子。
因此常见二叉堆实现的复杂度为 $O((V+E)\log V)$ ，选 C。

第 7 题（单选题，2 分）

对于含 $n$ 个顶点（ $n \geq 2$ ）的连通加权有向图，若图中不存在负权环，则任意两点之间的最短路径（简单路径）最多包含（）条边。

n

n - 1

n + 1

无法确定，取决于图的具体边数

正确答案B

解析详情

答案 B简单路径边数

思路与推导

简单路径不能重复顶点。n 个顶点的图中，一条简单路径最多经过全部 n 个顶点，因此最多包含 n−1 条连接边。
没有负权环时，已存在的最短路线可去掉不必要的环而不变长；故所问边数上限为 n−1，选 B。

第 8 题（单选题，2 分）

在使用Floyd算法求任意两点间最短路径时，时间复杂度为 $O(V^{3})$ 。若在某次算法执行前，已经用Dijkstra算法正确求出了所有点对的最短路并存入了dist数组。如果此时继续对该dist数组执行一次完整的Floyd算法过程（无任何提前终止），执行完毕后dist数组内的值（）。

会发生改变，因为 Floyd 又做了一次松弛

不会发生改变

可能变大，因为未针对已有最短路优化

可能在某些负权图中陷入死循环

正确答案B

解析详情

答案 B最短路的三角不等式

思路与推导

既然 dist 已是正确的最短距离，就有 $dist[i][j]≤dist[i][k]+dist[k][j]$ ：经过 k 只是所有可行路线中的一种。
Floyd 只在经 k 更短时更新，因此不会找到可改进值，数组保持不变，选 B。
假设无穷大与数值运算得到正确处理；再次执行仍需完整三重循环的时间。

第 9 题（单选题，2 分）

关于图论中的最短路径算法，下列说法中严格正确的是（）。

Dijkstra 算法能够高效处理包含负权边的有向图。

Floyd 算法可以求出任意两点间的最短路径，且允许图中存在负权边（但不能有负权环）。

单源最短路径算法无法用于无向图，无向图只能通过 BFS 求解。

Dijkstra 算法的每一步必定从当前未访问的节点中，选取距离起始点最远的节点进行松弛操作。

正确答案B

解析详情

答案 BFloyd 的适用范围

思路与推导

Floyd 枚举允许经过的中间顶点，用两段最短路组合更新点对距离，并不依赖所有边非负。
因此可以处理负权边，但若存在影响路径的负权环，便不能得到有限最短路，B 正确。Dijkstra 的一般正确性要求非负权，且选择的是最小距离候选。

第 10 题（单选题，2 分）

有6个人排成一排照相，其中甲、乙两人必须相邻，且丙不能站在排头的不同排法有（）种。

120

144

192

240

正确答案C

解析详情

答案 C捆绑法与补集

思路与推导

把甲乙捆为一个整体，与另外四人共五个单位，先不限制丙的位置，共 $5!×2=240$ 种。
其中丙在排头时，剩下四个单位排列有 $4!×2=48$ 种。
相减得到 $240-48=192$ ，选 C。

第 11 题（单选题，2 分）

下列代码试图实现Floyd算法求所有点对之间的最短路径，横线处应填入（）。

void floyd(int n, int dist[][MAXN]) {
    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (_____) // 在此处填入选项
                    dist[i][j] = dist[i][k] + dist[k][j];
}

dist[i][k] + dist[k][j] < dist[i][j]

dist[i][k] != INF && dist[k][j] != INF

dist[i][k] != INF && dist[k][j] != INF && dist[i][k] + dist[k][j] < dist[i][j]

dist[i][j] == INF

正确答案C

解析详情

答案 C安全的 Floyd 松弛

思路与推导

经 k 的路线只有在 i→k 和 k→j 都可达时才有意义，因此先要求两个距离都不等于 INF。
再比较两段和是否严格小于原 dist[i][j]，只有更短才更新，三个条件合并对应 C。
还应保证有限距离相加不超过整数类型范围。

第 12 题（单选题，2 分）

用数字0、1、2、3、4组成无重复数字的五位偶数，共有（）个。

正确答案B

解析详情

答案 B末位分类计数

思路与推导

偶数的末位只能为 0、2、4。
末位为 0 时，剩下四个非零数字任意排列，有 $4!=24$ 种。末位为 2 或 4 时，首位不能为 0，分别有 3 种首位选择，再排余下三位，各有 $3×3!=18$ 种。
总数为 $24+18+18=60$ ，选 B。

第 13 题（单选题，2 分）

在一个无向带权图中，若使用 Prim 算法从顶点 0 开始构造最小生成树（边权均为正整数，且 graph[u][v] == 0 表示无边），下列代码中横线处应填入（）。

int prim(vector<vector<int>>& graph, int n) {
    vector<bool> inMST(n, false);
    vector<int> minEdge(n, INT_MAX);
    minEdge[0] = 0;
    int result = 0;
    for (int i = 0; i < n; i++) {
        int u = -1;
        for (int j = 0; j < n; j++)
            if (!inMST[j] && (u == -1 || minEdge[j] < minEdge[u]))
                u = j;
        inMST[u] = true;
        result += minEdge[u];
        for (int v = 0; v < n; v++)
            if (_____) // 在此处填入选项
                minEdge[v] = graph[u][v];
    }
    return result;
}

graph[u][v] && !inMST[v] && graph[u][v] < minEdge[v]

!inMST[v] && graph[u][v] < minEdge[v]

graph[u][v] > 0 && !inMST[v]

!inMST[v] && minEdge[v] > 0

正确答案A

解析详情

答案 APrim 候选边更新

思路与推导

minEdge[v] 表示从当前生成树连向尚未加入顶点 v 的最小边权。
更新必须同时满足：u—v 有边、v 尚未入树、新边更便宜。题设 0 表示无边，三个条件正是 graph[u][v]、!inMST[v]、graph[u][v]<minEdge[v]，选 A。
完整程序还应处理图不连通时的不可达候选。

第 14 题（单选题，2 分）

已知三个点 $A(x_{1}, y_{1}), B(x_{2}, y_{2}), C(x_{3}, y_{3})$ 在平面直角坐标系中的坐标。下列 C++ 表达式中，在精度误差范围 1e-8 内能正确计算判断这三个点是三点共线的表达式是（）。

(x2-x1)/(y2-y1) = (x3-x1)/(y3-y1)

(x2-x1)*(y3-y1)-(x3-x1)*(y2-y1) = \theta

fabs((x2-x1)*(y3-y1)-(x3-x1)*(y2-y1)) < 1e-8

fabs((x2-x1)/(y2-y1)-(x3-x1)/(y3-y1)) < 1e-8

正确答案C

解析详情

答案 C叉积判共线

思路与推导

向量 AB 和 AC 共线等价于二维叉积为 0，即 $(x_2-x_1)(y_3-y_1)-(x_3-x_1)(y_2-y_1)=0$ 。
浮点计算用绝对值小于给定容差 1e−8 判断近似为零，选 C。叉积避免了斜率形式的除零问题。

第 15 题（单选题，2 分）

在64位操作系统下（LP64 / LLP64 模型），下面代码的输出结果是（）。

#include <iostream>
using namespace std;

int main() {
    int a[4] = {1, 2, 3, 4};
    int (*p)[4] = &a;
    int *q = a;

    cout << sizeof(a) << " ";
    cout << sizeof(p) << " ";
    cout << sizeof(p + 1) << " ";
    cout << sizeof(q + 1) << " ";
    cout << (p + 1) - p << " ";
    cout << (q + 1) - q << endl;
}

16 8 8 8 1 1

16 8 16 8 1 1

16 8 8 4 4 1

16 8 8 8 4 1

正确答案A

解析详情

答案 A数组与指针大小

思路与推导

题设两种 64 位模型中 int 通常占 4 字节、指针占 8 字节，所以 sizeof(a)=4×4=16，sizeof(p)=8。
p+1 与 q+1 都仍是指针，sizeof 均为 8。p 每次跨过一个四元素数组，q 每次跨过一个 int，但指针相减按各自元素个数计数。
因此两个差值都是 1，完整输出为 16 8 8 8 1 1，选 A。

判断题

第 1 题（判断题，2 分）

在 C++ 中，若结构体中包含一个 static 成员变量，则该变量的存储空间属于结构体对象的一部分。（）

正确答案错误

解析详情

答案错误静态成员存储

思路与推导

static 数据成员属于类级别的共享状态，不是每个对象内部各存一份。
例如创建两个对象，它们访问的是同一个静态成员；sizeof 对象不会为该静态成员逐份计入空间。因此题目错误。

第 2 题（判断题，2 分）

对于任意正整数 n，二项式 $(a + b)^n$ 展开式中各项的二项式系数之和等于 $2^n$ 。（）

正确答案正确

解析详情

答案正确二项式系数和

思路与推导

将 $(a+b)^n$ 展开后，令 a=b=1，每项只剩其二项式系数。
左侧为 $(1+1)^n=2^n$ ，因此全部系数之和为 2ⁿ，正确。

第 3 题（判断题，2 分）

在 C++ 中，若函数参数类型为 const int &，则该参数既可以绑定左值，也可以绑定右值。（）

正确答案正确

解析详情

答案正确常量左值引用

思路与推导

const int& 可以绑定已有 int 左值，也可以绑定整数临时值，例如 f(x) 和 f(3) 都可匹配。
const 限制通过该引用修改对象，允许安全地读取临时值，因此判断正确。

第 4 题（判断题，2 分）

若一个无向图的最小生成树唯一，则图中所有边权必定各不相同。（）

正确答案错误

解析详情

答案错误MST 唯一性的反例

思路与推导

考虑三个顶点构成一条路径，两条边权都为 1。原图本身已是一棵树，生成树只能选这两条边，因此最小生成树唯一。
但两条边权相同，直接否定“唯一则所有边权不同”。

第 5 题（判断题，2 分）

使用快速排序对 n 个元素进行排序时，无论最好、最坏还是平均情况，时间复杂度均为 $O(n \log n)$ 。（）

正确答案错误

解析详情

答案错误快速排序最坏情况

思路与推导

若每次 pivot 都是当前最小值或最大值，分区只排除一个元素，递归工作量为 n+(n−1)+⋯+1。
这个和为平方级，所以最坏 $O(n^2)$ ，而不是所有情况都为 $O(n\log n)$ ，题目错误。

第 6 题（判断题，2 分）

若一个图中所有顶点的度数为偶数，则一定存在欧拉回路。（）

正确答案错误

解析详情

答案错误欧拉回路连通条件

思路与推导

对无向图，度数全偶还需要所有有边的顶点处于同一连通分量，才能用一条闭合路线经过全部边。
两个互不相连的三角形中，每个顶点度数都是 2，却无法从一个三角形走到另一个，故反例成立。

第 7 题（判断题，2 分）

使用倍增法预处理区间最值问题时，预处理的时间复杂度为 $O(n \log n)$ ，查询的时间复杂度为 $O(1)$ 。（）

正确答案正确

解析详情

答案正确稀疏表区间最值

思路与推导

ST 表存储每个起点、每种 $2^k$ 长度的区间最值，约有 n log n 个状态，每个由两半常数时间合并。
查询 [l,r] 时取不超过区间长度的最大 2 的幂，用首尾两个块覆盖，并取二者最大或最小，即 O(1)。
因此预处理 $O(n\log n)$ 、查询 $O(1)$ ，判断正确。

第 8 题（判断题，2 分）

如果将一个连通无向图 $G_1$ 中所有边的权值都统一增加同一个正整数常数 C，形成图 $G_2$ 。则 $G_1$ 的最小生成树中每条边在 $G_2$ 中对应的边组成的树，一定是 $G_2$ 的最小生成树。（）

正确答案正确

解析详情

答案正确生成树边数固定

思路与推导

同一个 n 顶点图的任何生成树都有 n−1 条边。全部边权加 C 后，每棵生成树的总权都恰好增加 $(n-1)C$ 。
所有候选之间的相对大小保持不变，因此原 MST 仍为新图的 MST，题目正确。

第 9 题（判断题，2 分）

在图论算法中，Kruskal算法和Prim算法都可以用来求解最小生成树，且这两者的贪心策略无论在任何连通无向图上求得的最小生成树总边权和必定相同。（）

正确答案正确

解析详情

答案正确最优值唯一

思路与推导

Kruskal 和 Prim 虽使用不同的贪心选边顺序，都能在连通带权无向图上得到最小生成树。
如果它们所得权重和不同，较大的那棵就不是最小，与算法正确性矛盾，因此总权必相同。
相同边权可能使选出的具体边集合不同。

第 10 题（判断题，2 分）

在动态规划问题中，“状态转移方程+递推”和“递归+记忆化搜索”通常是解决同一问题的两种不同实现方式，它们的时间复杂度总是相同的。（）

正确答案错误

解析详情

答案错误记忆化与递推的状态范围

思路与推导

若两种实现处理完全相同的状态和转移，通常具有同阶复杂度。
但记忆化按需求解，可能只访问少量可达状态；直接递推若填满整个表，就会计算更多状态。
因此时间复杂度“总是相同”不成立，题目错误。