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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

二、判断题（每题 2 分，共 20 分）

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

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

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

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

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

第 6 题 在使用 Dijkstra 算法求单源最短路径时，如果发现某条边被选入从源点出发的最短路径生成树中，那么这条边也一定属于该图的某棵最小生成树。

第 7 题 在一个带权无向图中，若所有边的权值都不相同，则该图的最小生成树是唯一的。

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

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

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

三、编程题（每题 25 分，共 50 分）

第 1 题 拆分

题面描述

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

形式化地，$n$ 的拆分是满足 $a_1+ \cdots +a_k=n$ 的若干个正整数 $a_1,\cdots,a_k$，其中 $1 \le k \le n$。你需要求出 $n$ 的所有拆分中 的最大值对 $a_1 \times \cdots \times a_n$ 取模的结果。

输入格式

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

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

输出格式

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

3
5
8
100

6
18
755407364

数据要求

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

对于所有测试点，保证 $1 \le t \le 10^4$，$1 \le n \le 10^6$ 。

第 2 题 物流网络

题面描述

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

- 运输费用 $w_i$

- 景观评分 $b_i$

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

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

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

输入格式

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

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

输出格式

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

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

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

0

数据要求

【样例解释】

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

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

最小费用为 0。

【数据范围】

$1 \le n \le 5000$，$1 \le m \le 5000$，$1 \le w,b \le 10^9$ 。