试卷解析 · 理解每一步

2026-03-Level-7

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

单选题

第 1 题（单选题，2 分）

假设一个算法时间复杂度的递推式是 $T(n) = 2T(n-1) + 1$ （ $n$ 为正整数），且 $T(0) = 1$ ，那么这个算法的时间复杂度是（）。

O(n)

O(n \log n)

O(n^2)

O(2^n)

正确答案D

解析详情

答案 D时间复杂度、递推方程

思路与推导

由 $T(n) = 2T(n-1) + 1$ 且 $T(0) = 1$ 可推得： $T(n)+1 = 2(T(n-1)+1)$ 。这是一个公比为 2 的等比数列，通项为 $T(n)+1 = (T(0)+1) \cdot 2^n = 2 \cdot 2^n = 2^{n+1}$ ，故 $T(n) = 2^{n+1}-1$ ，时间复杂度为 $O(2^n)$ 。

第 2 题（单选题，2 分）

下面关于“唯一分解定理”和“素数筛法”的说法中，错误的是（）。

如果预处理出

n

以内每个数的最小质因子，那么可以在

O(\log n)

时间内完成任意一个不超过

n

的整数的原因数分解。

线性筛（欧拉筛）能够保证每个合数只被其最小质因子筛掉一次，这一性质依赖于唯一分解定理。

唯一分解定理保证：若一个数未被任何不超过其平方根的质数筛去，则它一定是质数。

唯一分解定理是埃氏筛时间复杂度为

O(n \log \log n)

的根本原因。

正确答案D

解析详情

答案 D唯一分解定理、素数筛法、算法复杂度分析

思路与推导

埃氏筛的时间复杂度 $O(n \log \log n)$ 是由素数倒数之和的渐进性质（Mertens' Theorem）决定的，即 $\sum_{p \le n} 1/p \approx \ln \ln n$ 。这与唯一分解定理没有直接的逻辑因果关系。其他选项均表述正确。

第 3 题（单选题，2 分）

若字符串A与字符串B的最长公共子序列（LCS）长度为5，则（）。

它们的编辑距离为 5

它们至少有 5 个公共字符

它们最长公共子串长度为 5

它们一定长度相等

正确答案B

解析详情

答案 B字符串、最长公共子序列（LCS）

思路与推导

最长公共子序列（LCS）是指在两个序列中都出现的、且相对顺序相同的最长子序列。LCS 长度为 5 意味着 A 和 B 至少有 5 个字符是相同的且顺序一致。编辑距离、最长公共子串（连续）以及字符串总长度与 LCS 长度没有固定的等量关系。

第 4 题（单选题，2 分）

对于一棵包含 $n$ 个顶点（ $n \geq 2$ ）的树，其所有顶点的度数之和必定等于（）。

n - 1

2n - 2

2n

n^2

正确答案B

解析详情

答案 B树的性质、图论基本定理

思路与推导

根据图论中的握手定理，所有顶点的度数之和等于边数的 2 倍。在包含 $n$ 个顶点的树中，边数固定为 $n-1$ 。因此，度数之和为 $2(n-1) = 2n-2$ 。

第 5 题（单选题，2 分）

关于哈希表（Hash Table）在不考虑扩容且采用简单均匀哈希函数的前提下，下列说法中错误的是（）。

装载因子越大，发生冲突的概率通常越高

开放定址法在删除元素时实现相对复杂

链地址法在最坏情况下查找时间复杂度为

O(n)

查找哈希表的时间复杂度总是

O(1)

正确答案D

解析详情

答案 D哈希表、复杂度分析

思路与推导

哈希表在平均情况下的查找时间复杂度为 $O(1)$ ，但在最坏情况下（所有元素都哈希到同一个桶中），时间复杂度会退化到 $O(n)$ 。因此，说法“总是 $O(1)$ ”是错误的。

第 6 题（单选题，2 分）

在 Kruskal 算法中，会将边排序后按顺序扫描选取边加入最小生成树中，算法的本质思想是（）。

分治

贪心

动态规划

回溯

正确答案B

解析详情

答案 B最小生成树、Kruskal 算法、贪心算法

思路与推导

Kruskal 算法的核心思想是每次选择权值最小且不与已选边构成环的边，这是一种局部最优选择从而达到全局最优的策略，属于典型的贪心思想。

第 7 题（单选题，2 分）

下面程序的运行结果为（）。

#include <iostream>
#include <algorithm>

bool check(int n, int a[], int k, int dist) {
    int cnt = 1;
    int last = a[0];

    for (int i = 1; i < n; i++) {
        if (a[i] - last >= dist) {
            cnt++;
            last = a[i];
        }
    }
    return cnt >= k;
}

int solve(int n, int a[], int k) {
    std::sort(a, a + n);
    int l = 0;
    int r = a[n - 1] - a[0];

    while (l < r) {
        int mid = (l + r + 1) / 2;

        if (check(n, a, k, mid)) {
            l = mid;
        } else {
            r = mid - 1;
        }
    }

    return l;
}

int main() {
    int a[] = {1, 2, 8, 4, 9};
    int n = 5;
    int k = 3;

    std::cout << solve(n, a, k) << std::endl;

    return 0;
}

正确答案B

解析详情

答案 B二分答案、贪心

思路与推导

程序实现了“最大化最小距离”的逻辑。数组排序后为 {1, 2, 4, 8, 9}，要在其中选 3 个数使其最小间距最大。当 $dist=3$ 时，可选 {1, 4, 8}，满足条件；当 $dist=4$ 时，选 1 后下一个只能选 8，选不到 3 个。故最大最小间距为 3。

第 8 题（单选题，2 分）

下面程序的时间复杂度是（），假设数组a的值域范围是D。

#include <iostream>
#include <algorithm>

bool check(int n, int a[], int k, int dist) {
    int cnt = 1;
    int last = a[0];

    for (int i = 1; i < n; i++) {
        if (a[i] - last >= dist) {
            cnt++;
            last = a[i];
        }
    }

    return cnt >= k;
}

int solve(int n, int a[], int k) {
    std::sort(a, a + n);
    int l = 0;
    int r = a[n - 1] - a[0];

    while (l < r) {
        int mid = (l + r + 1) / 2;

        if (check(n, a, k, mid)) {
            l = mid;
        } else {
            r = mid - 1;
        }
    }

    return l;
}

int main() {
    int a[] = {1, 2, 8, 4, 9};
    int n = 5;
    int k = 3;

    std::cout << solve(n, a, k) << std::endl;

    return 0;
}

O(n \log n + n \log D)

O(n \log n \log D)

O(n \log n)

O(n \log D)

正确答案A

解析详情

答案 A复杂度分析、二分查找、排序

思路与推导

1. `std::sort` 复杂度为 $O(n \log n)$ 。
2. 二分查找范围是数组最大差值 $D$ ，循环次数为 $O(\log D)$ 。
3. 每次二分调用一次 `check` 函数，其复杂度为 $O(n)$ 。二分部分总复杂度为 $O(n \log D)$ 。
综合得到 $O(n \log n + n \log D)$ 。

第 9 题（单选题，2 分）

某二叉树共有10个结点，记为A~J，已知它的先序遍历序列为：ABDHIECFJG，中序遍历序列为：HDIBEAFJCG，则该二叉树的后序遍历序列是（）。

HIDEBJFGCA

HIDBEJFGCA

IHDEBJFGCA

HIDEBFJGCA

正确答案A

解析详情

答案 A二叉树遍历、根据前序中序求后序

思路与推导

1. 前序首位 A 是根。中序中 A 划分为左子树 {HDIBE} 和右子树 {FJCG}。
2. 左子树前序首位 B 为根，中序中 B 划分为左 {HDI} 和右 {E}。以此类推，得到左子树后序：HIDEB。
3. 右子树前序首位 C 为根，中序中 C 划分为左 {FJ} 和右 {G}。得到右子树后序：JFGC。
4. 组合：左+右+根 = HIDEB JFGCA。

第 10 题（单选题，2 分）

下面哪一个可能是下图的深度优先遍历序列（）。

1, 5, 4, 8, 7, 9, 6, 3, 2

1, 5, 8, 4, 7, 9, 6, 3, 2

2, 5, 8, 7, 9, 6, 3, 4, 1

8, 9, 6, 3, 2, 5, 1, 4, 7

正确答案B

解析详情

答案 B图的深度优先遍历（DFS）

思路与推导

根据图的连接关系，从 1 出发：
1 可到 5 或 4。选 B 路径：1 -> 5 -> 8 -> 4 -> 7 -> 9 -> 6 -> 3 -> 2。在每个结点处，下一步都是该结点的未访问邻居。B 序列完全符合 DFS 的回溯前深度探测规则。A 选项中 5 到 4 虽是邻居，但后续路径 8 无法由 4 直接连接到达（需回溯）。

第 11 题（单选题，2 分）

下面这个有向图的强连通分量的个数是（）。

正确答案B

解析详情

答案 B强连通分量（SCC）

思路与推导

图中存在以下循环路径：
1. {1, 2, 5} 构成一个环，是一个强连通分量。
2. {3, 4} 相互可达，构成一个强连通分量。
3. {6} 是孤立的或单向的，是一个强连通分量。
4. {7} 是孤立的或单向的，是一个强连通分量。
总计 4 个强连通分量。

第 12 题（单选题，2 分）

关于泛洪算法（Flood Fill）的说法，正确的是（）。

泛洪算法只适用于二维网格中的四连通或八连通问题。

泛洪算法必须使用递归方式实现。

泛洪算法本质上是对图进行一次从起点出发的搜索。

泛洪算法只能用于统计连通块个数，不能用于计算面积或周长。

正确答案C

解析详情

答案 C泛洪算法、图的遍历

思路与推导

泛洪算法的核心是从一个种子点开始，寻找所有连通的、具有相同属性的区域。这本质上就是在图（网格可以看作图）上进行 BFS 或 DFS 遍历。A 错误，可用于任何连通性定义；B 错误，可用队列/栈实现非递归；D 错误，可同步计算面积（点数）等信息。

第 13 题（单选题，2 分）

有 6 个字符，它们出现的次数分别为：{2, 3, 3, 4, 6, 8}，现在用哈夫曼编码为这些字符编码，最小加权路径长度WPL（每个字符的出现次数×它的编码长度，再把每个字符结果加起来）的值为（）。

正确答案D

解析详情

答案 D哈夫曼树、带权路径长度（WPL）

思路与推导

构造过程：
1. {2, 3} -> 5；集合变为 {3, 4, 5, 6, 8}
2. {3, 4} -> 7；集合变为 {5, 6, 7, 8}
3. {5, 6} -> 11；集合变为 {7, 8, 11}
4. {7, 8} -> 15；集合变为 {11, 15}
5. {11, 15} -> 26
WPL 等于所有非叶结点的权值之和：5 + 7 + 11 + 15 + 26 = 64。

第 14 题（单选题，2 分）

关于单链表、双链表和循环链表，下列说法正确的是（）。

在单链表中，若已知某结点的指针，则可以在O(1)时间内删除该结点。

循环链表中一定不存在空指针。

在循环双链表中，尾结点的 next 指针一定为 NULL。

在带头结点的循环单链表中，判定链表是否为空只需判断头结点的 next 是否指向自身。

正确答案D

解析详情

答案 D链表、循环链表、双链表

思路与推导

A 错误：单链表删除结点需要前驱指针，通常需 $O(n)$ 寻找；B 错误：循环链表尾部指向头部，标准结构中不设 NULL，但实现中可能存在例外；C 错误：循环双链表尾部 next 指向头结点；D 正确：带头结点的循环链表，空表即头结点 next 指向自己。

第 15 题（单选题，2 分）

下列关于树的遍历的说法中，正确的一项是（）。

对任意一棵树进行深度优先遍历，所得序列一定唯一。

已知一棵二叉树的先序遍历和后序遍历序列，可以唯一确定这棵二叉树。

已知一棵二叉树的先序遍历和中序遍历序列，可以唯一确定这棵二叉树。

一棵二叉树的中序遍历序列是单调递增的，则该二叉树一定是二叉平衡树。

正确答案C

解析详情

答案 C二叉树遍历、确定二叉树

思路与推导

二叉树中，“先序+中序”或“后序+中序”或“层序+中序”可以唯一确定。只有先序和后序不能确定（如无法区分左子树还是右子树）。D 选项：中序递增是二叉搜索树（BST）的特征，不代表其“平衡”。

连通图的定义即任意两点间均有路径。DFS 从任一点出发，都会探测所有可达点。因此连通图的一次 DFS 遍历必然访问所有顶点。