2026年3月 GESP C++ 7级

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

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

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

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

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

深度优先搜索（DFS）在遍历图时，每当访问到某个顶点后，选择一个相邻的未访问顶点继续搜索，直到某个顶点的所有相邻顶点均已被访问，则退回到前一顶点继续搜索。该算法主要运用了（ ）。

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

#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;
}

下面程序的时间复杂度是（ ），假设数组的值域范围是 $[0,M]$。

#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;
}

某二叉树共有 $10$ 个结点，记为 $A$~$J$，已知它的先序遍历序列为：$A$ $B$ $D$ $H$ $I$ $E$ $C$ $F$ $J$ $G$，中序遍历序列为：$H$ $D$ $I$ $B$ $E$ $A$ $F$ $J$ $C$ $G$，则该二叉树的后序遍历序列是（ ）。

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

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

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

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

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

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

C++ 语言中，表达式 4 ^ 2 的结果类型为 int，值为 $6$。

C++ 中引用可以重新绑定。

在 C++ 中，若函数形参为引用类型，则在函数内部对该形参的修改会影响对应的实参。

如果一个最值问题可以用动态规划在多项式时间内求解，那么也一定存在一种贪心策略，可以在多项式时间内求得最优解。

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

在无向连通图中删除一条边，该图就一定变成非连通图。

在一个无向图中，每个顶点有不同的编号，在执行深度优先遍历过程中选择下一个顶点时总是优先选择编号更小的相邻顶点，则从指定顶点开始的遍历序列是唯一的。

若所有字符出现频率相同，则哈夫曼编码一定会得到完全二叉树。

使用 math.h 或 cmath 头文件中的函数，表达式 sin(90) 的结果为 $1$。

在一个无向连通图中，从任意顶点开始进行深度优先遍历，最终得到的 DFS 生成树一定包含图中的所有顶点。

试题名称：拆分

时间限制：1.0 s | 内存限制：512.0 MB

题目描述

小 A 想将正整数 $n$ 拆分成若干个正整数之和，并最大化拆分后的正整数之积。小 A 希望你帮他计算出拆分后正整数之积的最大值。由于答案可能很大，你只需要求出答案对 10910^9109 取模的结果。

形式化地，$n$ 的拆分是满足 a1+⋯+ak=na_1+\cdots+a_k=na1​+⋯+ak​=n 的若干个正整数 a1,…,aka_1,\dots,a_ka1​,…,ak​，其中 $1\le k\le n$。你需要求出 $n$ 的所有拆分中 a1×⋯×aka_1\times \cdots\times a_ka1​×⋯×ak​ 的最大值对 10910^9109 取模的结果。

输入格式

第一行，一个正整数 $t$，表示数据组数。

对于每组数据：一行，一个整数 $n$，表示给定的正整数。

输出格式

对于每组数据：输出一行，一个整数，表示 $n$ 拆分后正整数之积的最大值对 10910^9109 取模的结果。

样例输入 #1

3
5
8
100

样例输出 #1

6
18
755407364

说明/提示

对于 $40\%$ 的测试点，保证 $n\le 50$。

对于所有测试点，保证 1≤t≤1041\leq t\leq 10^41≤t≤104，1≤n≤1061\leq n\leq 10^61≤n≤106。

试题名称：物流网络

时间限制：1.0 s | 内存限制：512.0 MB

题目描述

一个物流网络由 $n$ 个城市和 $m$ 条双向公路组成。每条公路都有两个属性：

• 运输费用 wiw_iwi​
• 景观评分 bib_ibi​

当一辆运输车从城市 $1$ 运送货物到城市 $n$ 时，需要支付经过道路的运输费用之和。

为了推广旅游线路，物流公司推出了一项优惠政策：在运输路径上，可以免除景观评分最高的那条公路的运输费用。如果有多条公路的景观评分同为最大值，则只免除其中 一条 的费用。

请你计算，从城市 $1$ 到城市 $n$ 的最小运输费用。

输入格式

第一行两个整数 $n,m$，分别表示城市数量和公路数量。

接下来 $m$ 行，每行四个整数 $u,v,w,b$，表示存在一条连接城市 $u$ 和城市 $v$ 的双向公路，其中 $w$ 为运输费用，$b$ 为景观评分。

输出格式

输出一个整数，表示从城市 $1$ 到城市 $n$ 的最小费用。

如果无法到达，输出 -1。

样例输入 #1

3 3
1 2 10 5
2 3 20 6
1 3 100 1

样例输出 #1

0

说明/提示

样例解释

路径 $1\to 2\to 3$：费用 $10+20$，最大美丽值 $6$（边 $2-3$）。免除 $20$，总花费 $10$。

路径 $1\to 3$：费用 $100$，最大美丽值 $1$（边 $1-3$）。免除 $100$，总花费 $0$。

数据范围

$1\le n\le 5000$，$1\le m\le 5000$，1≤w,b≤1091\leq w,b\leq 10^91≤w,b≤109。