GESP C++ 7级 2026.03

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

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

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

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

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

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

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

#include 
#include 

bool check(int n, int a[], int k, int dist) {
 int cnt = 1; 
 int last = a[0];
 for (int i = 1; i = 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;
}

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

#include 
#include 

bool check(int n, int a[], int k, int dist) { 
 int cnt = 1; 
 int last = a[0];
 for (int i = 1; i = 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$，已知它的先序遍历序列为：$ABDHIECFJG$，中序遍历序列为：$H D I B E A F J C G$，则该二叉树的后序遍历序列是（）。

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