试卷解析 · 理解每一步

2026-09-Level-7

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

单选题

第 1 题（单选题，2 分）

下列 C++ 代码的输出结果是（）。

#include <iostream>
using namespace std;
int main() {
    int a = 5, b = 3;
    cout << (a & b) + (a | b) << endl;
    return 0;
}

正确答案C

解析详情

答案 C按位与、按位或

思路与推导

5 的二进制为 101，3 为 011。按位与得到 001，即 1；按位或得到 111，即 7。括号中的两个结果相加为 1+7=8，故选 C。

第 2 题（单选题，2 分）

使用 cmath 或 math.h 中的数学库函数，下列说法中正确的是（）。

pow(2, 3) 的返回值类型为 int

sin(30) 的参数 30 表示

30

度

sqrt(4) 的返回值类型为 int

log(1) 的返回值为 0.0 ，且类型为 double

正确答案D

解析详情

答案 D数学库函数的参数和返回类型

思路与推导

log 表示自然对数，ln(1)=0；整数实参调用数学函数时按相应浮点重载处理，log(1) 的返回类型是 double，故 D 正确。pow(2,3) 和 sqrt(4) 也返回 double；sin 的参数单位是弧度，不是角度。

第 3 题（单选题，2 分）

有 $4$ 个字符，出现次数分别为 $1$ 、 $2$ 、 $3$ 、 $4$ 。构造哈夫曼树后，出现次数为 $1$ 的字符的哈夫曼编码长度为（）。

1

2

3

4

正确答案C

解析详情

答案 C哈夫曼树中叶子的编码长度

思路与推导

先合并最小权值 1、2 得到 3；再把新节点 3 与原叶子 3 合并得到 6；最后合并 4、6 得到根 10。频率为 1 的叶子依次经过这三次合并，距根有 3 条边，因此码长为 3，选 C。

第 4 题（单选题，2 分）

从 $4\times5$ 个点连接成的网格的左上角走到右下角，每次只能向右或向下移动，不同的路径共有（）条。

20

35

70

126

正确答案B

解析详情

答案 B网格路径与组合计数

思路与推导

网格由 4×5 个点组成，所以从左上到右下需要向下 3 次、向右 4 次，共 7 步。任选其中 3 步向下即可唯一确定路径，数量为 C(7,3)=7×6×5÷(3×2×1)=35，选 B。

第 5 题（单选题，2 分）

在含有 $n$ 个结点的二叉排序树中查找一个元素，平均时间复杂度和最坏时间复杂度分别为（）。

O(\log n)

、

O(n)

O(n)

、

O(\log n)

O(\log n)

、

O(\log n)

O(1)

、

O(n)

正确答案A

解析详情

答案 A二叉排序树查找复杂度

思路与推导

查找沿着根到某个节点的一条路径进行，耗时由树高决定。通常随机插入的平均情形下树高为 O(log n)，查找平均为 O(log n)；若按有序顺序插入，树可能退化成长度 n 的链，最坏为 O(n)。因此选 A。

第 6 题（单选题，2 分）

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

17

19

20

23

正确答案B

解析详情

答案 B相邻石子合并的区间动态规划

思路与推导

可先合并 1、2，代价 3，得到 3、3、4；再合并前两堆，代价 6；最后合并 6、4，代价 10，总计 19。为验证最优，枚举最后一次切分：三种切分的此前最小代价分别为 14、10、9，再加总石子数 10，得到 24、20、19，最小为 19，选 B。

第 7 题（单选题，2 分）

在无权图中，使用 BFS 从起点开始遍历，并在访问由结点 u 扩展的相邻结点 v 时记录 dist[v] = dist[u] + 1 ，且起点的 dist 为 0 ，则最终 dist[v] 表示的是（）。

起点到结点 v 的最少边数

结点 v 的度数

从起点到结点 v 的路径上经过的最大边权

包含结点 v 的连通块大小

正确答案A

解析详情

答案 A无权图 BFS 的距离含义

思路与推导

起点 dist=0，每沿一条边首次到达新节点就加 1。BFS 按距离层次扩展，先访问距离小的节点，所以对从起点可达的 v，最终 dist[v] 是最少边数，选 A。它既不是度数，也不是连通块大小。

第 8 题（单选题，2 分）

在二维网格上实现泛洪填充时，为了防止递归层数过深，最适合的非递归实现方式是（）。

使用哈希表记录每个格子被访问的次数

使用快速排序预处理网格

使用二分查找定位边界

使用队列实现 BFS 或使用显式栈模拟 DFS

正确答案D

解析详情

答案 D泛洪填充的非递归实现

思路与推导

泛洪填充需要维护待访问的相邻格子。用队列做 BFS，或用显式栈保存 DFS 的待访问状态，都能完成连通区域遍历，避免递归调用栈过深，因此选 D。哈希表、排序和二分查找都不能单独替代这个遍历过程。

第 9 题（单选题，2 分）

关于哈希表，下列说法正确的是（）。

只要哈希函数选择合适，就可以完全避免冲突

在链地址法中，查找一个元素的时间复杂度一定为

O(1)

开放定址法发生冲突后，会在表内寻找下一个可用位置

哈希表的查找速度与表中元素个数无关

正确答案C

解析详情

答案 C哈希冲突与开放定址法

思路与推导

开放定址法把元素保存在表内；目标槽已占用时，按既定探测规则寻找其他可用槽，因此 C 正确。哈希函数不能普遍保证无冲突；链地址法可能退化成长链；装载因子增加也会影响查找效率。

第 10 题（单选题，2 分）

下列 C++ 代码的输出结果是（）。

#include <iostream>
using namespace std;

void inc(int &x) {
    x++;
}
int main() {
    int a = 3;
    inc(a);
    cout << a;
    return 0;
}

编译错误

正确答案B

解析详情

答案 B引用参数修改实参

思路与推导

inc 的参数 int &x 是 a 的引用，x++ 直接把 a 从 3 改成 4。函数返回后输出 a，结果为 4，选 B。如果参数写成 int x 才是修改副本。

第 11 题（单选题，2 分）

用动态规划求两个序列 $s_1$ 和 $s_2$ 的最长公共子序列长度，若 dp[i][j] 表示 $s_1$ 前 i 个元素与 $s_2$ 前 j 个元素的 LCS 长度。当 $s_1[i-1]=s_2[j-1]$ 时，正确的状态转移是（）。

dp[i][j] = dp[i - 1][j - 1] + 1

dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

dp[i][j] = dp[i - 1][j] + 1

dp[i][j] = dp[i][j - 1]

正确答案A

解析详情

答案 A最长公共子序列的相等末项转移

思路与推导

当 s1[i-1] 与 s2[j-1] 相等时，可把这个共同元素接到两个较短前缀的 LCS 后面。于是 dp[i][j]=dp[i-1][j-1]+1，选 A。末项不等时才使用 max(dp[i-1][j],dp[i][j-1])。

第 12 题（单选题，2 分）

下列代码是一维数组优化 0/1 背包的核心片段，执行后 dp[8] 的输出结果是（）。

#include <iostream>
#include <algorithm>
using namespace std;
int main() {
    int w = 3, v = 5, W = 8;
    int dp[9] = {0};
    for (int c = W; c >= w; c--)
        dp[c] = max(dp[c], dp[c - w] + v);
    cout << dp[8] << endl;
    return 0;
}

正确答案D

解析详情

答案 D0/1 背包逆序更新

思路与推导

只有一件重量 3、价值 5 的物品。容量从 8 递减，计算 dp[8] 时 dp[5] 尚未在本轮更新，仍为 0，所以 dp[8]=max(0,0+5)=5。后面更新较小容量不会再修改 dp[8]，输出 5，选 D。

第 13 题（单选题，2 分）

若要求排序后相等元素的相对顺序保持不变，下列排序算法中最不适宜使用的是（）。

冒泡排序

插入排序

归并排序

快速排序

正确答案D

解析详情

答案 D排序稳定性

思路与推导

稳定排序要求关键字相等的元素保持原先相对顺序。常规快速排序的跨位置交换可能颠倒相等元素，通常不稳定；冒泡、插入和归并排序按标准稳定写法可保持顺序，因此最不适宜的是 D。

第 14 题（单选题，2 分）

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

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

O(n)

O(n\log n)

O(n^2)

O(n\sqrt n)

正确答案B

解析详情

答案 B调和级数型循环复杂度

思路与推导

固定 i 时，j 取 1、1+i、1+2i……，执行次数为 floor((n-1)/i)+1，约为 n/i。对 i=1 到 n 求和，得到 n(1+1/2+…+1/n) 加上 O(n) 级误差，因此紧确增长阶为 O(n log n)，选 B。

第 15 题（单选题，2 分）

已知

int a[6] = {1, 3, 5, 7, 9, 11}; int *p = a + 1;

，则表达式 *(p + 3) 的值是（）。

正确答案C

解析详情

答案 C指针偏移与数组下标

思路与推导

p=a+1 指向 a[1]。再加 3 后指向 a[4]，解引用得到 a[4]=9，因此选 C。指针加 1 前进一个 int 元素，而不是一个字节。

判断题

第 1 题（判断题，2 分）

使用 cmath 或 math.h 中的函数，表达式 exp(0) 的结果值为 1.0 ，且类型为 double 。

正确答案正确

解析详情

答案正确指数函数 exp

思路与推导

exp(x) 计算 e 的 x 次方，e 的 0 次方为 1，因此 exp(0) 的值为 1.0。整数参数对应的数学函数重载返回 double，题目两部分都正确。

第 2 题（判断题，2 分）

采用开放定址法处理冲突的哈希表中，删除一个元素后可以直接将该位置置空，不会影响后续查找。

正确答案错误

解析详情

答案错误开放定址哈希表的删除标记

思路与推导

说法错误。查找通常遇到从未占用的空槽就停止。如果删除后直接置空，探测链中排在后面的冲突元素可能因此找不到。例如两个键哈希到同一位置，删除前一个后会截断查找后一个的路径。通常需使用删除标记，或正确重建受影响的探测链。

第 3 题（判断题，2 分）

在哈夫曼树中，出现次数更多的叶子结点，其深度总是更小。

正确答案错误

解析详情

答案错误哈夫曼树中频率与深度的关系

思路与推导

说法错误。频率更高的叶子深度可以相等，不一定严格更小。例如只有两个字符，频率为 1 和 2，哈夫曼树的两个叶子都在深度 1。高频叶子不会更深，不等于一定更浅。

第 4 题（判断题，2 分）

在一个有向图中，所有顶点的入度之和总是等于所有顶点的出度之和。

正确答案正确

解析详情

答案正确有向图的入度与出度计数

思路与推导

每条有向边在起点贡献 1 个出度，在终点贡献 1 个入度。因此所有出度之和与所有入度之和都等于边数，必然相等，判断正确。自环也各贡献一次，不改变结论。

第 5 题（判断题，2 分）

广度优先搜索通常借助队列实现，深度优先搜索通常借助栈或递归实现。

正确答案正确

解析详情

答案正确BFS 与 DFS 的辅助结构

思路与推导

BFS 按先发现先处理的顺序逐层扩展，通常使用先进先出的队列。DFS 先深入最新发现的分支，通常使用后进先出的显式栈，或利用函数递归调用栈。因此说法正确。

第 6 题（判断题，2 分）

快速排序的平均时间复杂度为 $O(n\log n)$ ，最坏时间复杂度也为 $O(n\log n)$ 。

正确答案错误

解析详情

答案错误快速排序的平均与最坏复杂度

思路与推导

说法错误。快速排序平均为 O(n log n)，但若每次划分极不均衡，只去掉一个基准元素，工作量为 n+(n-1)+…+1，最坏为 O(n²)。因此后半句不成立。

第 7 题（判断题，2 分）

为解决 0/1 背包问题，使用一维数组优化时，内层容量循环应从大到小枚举。

正确答案正确

解析详情

答案正确0/1 背包的一维空间优化

思路与推导

说法正确。容量逆序时，转移用到的较小容量状态尚未使用当前物品，保证每件物品最多使用一次。若改为正序，则可能读到本轮刚更新的状态，重复选择同一件物品。

第 8 题（判断题，2 分）

使用邻接表存储图时，遍历某个顶点的所有邻边所需时间与图中顶点数成正比。

正确答案错误

解析详情

答案错误邻接表遍历代价

思路与推导

说法错误。邻接表只存储实际邻边，遍历顶点 u 的邻接表耗时与其邻边数量成正比，即无向图中的度数或有向图中的出度，并非必然与总顶点数成正比。孤立点的邻接表为空就是简单例子。

第 9 题（判断题，2 分）

在按层序从 $1$ 开始对结点编号的完全二叉树中，编号为 $i$ （ $i>1$ ）的结点的父结点编号为 $\lfloor i/2\rfloor$ 。

正确答案正确

解析详情

答案正确完全二叉树的父节点编号

思路与推导

从 1 开始按层编号时，节点 k 的孩子编号为 2k 和 2k+1。对两者除以 2 并向下取整，均得到 k，因此任意非根节点 i 的父编号为 floor(i/2)，判断正确。

第 10 题（判断题，2 分）

在定义了数组 int arr[10]; 后，表达式 arr 和表达式 &arr[0] 总是等价的。

正确答案错误

解析详情

答案错误数组表达式与数组到指针转换

思路与推导

说法错误。多数普通表达式中 arr 会转换为指向首元素的指针，与 &arr[0] 指向同一位置；但在 sizeof(arr) 中不会发生该转换，结果是 10*sizeof(int)，而 sizeof(&arr[0]) 是一个指针的大小。decltype(arr) 也是数组类型，decltype(&arr[0]) 是指针类型，因此不能说总是等价。