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

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

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

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

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

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

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

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 main() {
int a[] = {1, 2, 4, 8, 9};
cout << check(5, a, 3, 3) << endl;
return 0;
}

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

void process(int n, int a[]) {
sort(a, a + n);
for (int i = 0; i < n; i++) {
// 二分查找
int l = 0, r = D;
while (l < r) {
int mid = (l + r) / 2;
if (check(mid)) r = mid;
else l = mid + 1;
}
}
}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

拆分

时间限制：1.0s 内存限制：512.0MB
小A想将正整数n拆分成若干个正整数之和，并最大化拆分后的正整数之积。
小A希望你帮他计算出拆分后正整数之积的最大值。由于答案可能很大，你只需要求出答案对10^9取模的结果。
形式化地，n的拆分是满足a₁+...+aₖ=n的若干个正整数a₁,...,aₖ，其中1≤k≤n。
你需要求出n的所有拆分中a₁×...×aₙ的最大值对10^9取模的结果。

第一行，一个正整数t，表示数据组数。对于每组数据：一行，一个整数n。

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

【样例输入】
3
1
2
10
【样例输出】
1
1
36
对于所有测试点，保证1≤t≤10⁴，1≤n≤10⁸。

物流网络

时间限制：1.0s 内存限制：512.0MB
一个物流网络由n个城市和m条双向公路组成。每条公路都有两个属性：运输费用wᵢ、景观评分bᵢ。
当一辆运输车从城市1运送货物到城市n时，需要支付经过道路的运输费用之和。
为了推广旅游线路，物流公司推出了一项优惠政策：在运输路径上，可以免除景观评分最高的那条公路的运输费用。
如果有多条公路的景观评分同为最大值，则只免除其中一条的费用。
请你计算，从城市1到城市n的最小运输费用。

【数据范围】
对于所有测试点，保证1≤n≤5000，1≤m≤5000，1≤w,b≤10⁹。

第一行两个整数n,m。接下来m行，每行四个整数u,v,w,b，表示一条双向公路。

输出一个整数，表示从城市1到城市n的最小费用。
对于所有测试点，保证1≤n≤5000，1≤m≤5000，1≤w,b≤10⁹。