C++ 七级

2026 年 03 月

1 单选题（每题 2 分，共 30 分）

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

{{ select(1) }}

• $O(n)$
• $O(n \ log \ n)$
• $O(n^2)$
• $O(2^n)$

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

{{ select(2) }}

• 如果预处理出 $n$ 以内每个数的最小质因子，那么可以在 $O(log \ n)$时间内完成任意一个不超过 $n$ 的整数的质因数分解。
• 线性筛（欧拉筛）能够保证每个合数只被其最小质因子筛掉一次，这一性质依赖于唯一分解定理。
• 唯一分解定理保证：若一个数未被任何不超过其平方根的质数筛去，则它一定是质数。
• 唯一分解定理是埃氏筛时间复杂度为 $O(n \ log \ log \ n)$ 的根本原因。

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

{{ select(3) }}

• 它们的编辑距离为 5
• 它们至少有 5 个公共字符
• 它们最长公共子串长度为 5
• 它们一定长度相等

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

{{ select(4) }}

• $n - 1$
• $2n - 1$
• $2n$
• $n^2$

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

{{ select(5) }}

• 装载因子越大，发生冲突的概率通常越高
• 开放定址法在删除元素时实现相对复杂
• 链地址法在最坏情况下查找时间复杂度为 $O(n)$
• 查找哈希表的时间复杂度总是 $O(1)$

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

{{ select(6) }}

• 分治
• 贪心
• 动态规划
• 回溯

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

{{ select(7) }}

• 2
• 3
• 4
• 5

第 8 题 下面程序的时间复杂度是（ ），假设数组 $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;
}

{{ select(8) }}

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

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

{{ select(9) }}

• H I D E B J F G C A
• H I D B E J F G C A
• I H D E B J F G C A
• H I D E B F J G C A

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

{{ select(10) }}

• 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

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

{{ select(11) }}

• 3
• 4
• 5
• 6

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

{{ select(12) }}

• 泛洪算法只适用于二维网格中的四连通或八连通问题。
• 泛洪算法必须使用递归方式实现。
• 泛洪算法本质上是对图进行一次从起点出发的搜索。
• 泛洪算法只能用于统计连通块个数，不能用于计算面积或周长。

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

{{ select(13) }}

• 58
• 60
• 62
• 64

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

{{ select(14) }}

• 在单链表中，若已知某结点的指针，则可以在 $O(1)$ 时间内删除该结点。
• 循环链表中一定不存在空指针。
• 在循环双链表中，尾结点的 next 指针一定为 NULL。
• 在带头结点的循环单链表中，判定链表是否为空只需判断头结点的 next 是否指向自身。

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

{{ select(15) }}

• 对任意一棵树进行深度优先遍历，所得序列一定唯一。
• 已知一棵二叉树的先序遍历和后序遍历序列，可以唯一确定这棵二叉树。
• 已知一棵二叉树的先序遍历和中序遍历序列，可以唯一确定这棵二叉树。
• 一棵二叉树的中序遍历序列是单调递增的，则该二叉树一定是二叉平衡树。

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

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

{{ select(16) }}

• 对
• 错

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

{{ select(17) }}

• 对
• 错

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

{{ select(18) }}

• 对
• 错

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

{{ select(19) }}

• 对
• 错

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

{{ select(20) }}

• 对
• 错

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

{{ select(21) }}

• 对
• 错

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

{{ select(22) }}

• 对
• 错

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

{{ select(23) }}

• 对
• 错

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

{{ select(24) }}

• 对
• 错

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

{{ select(25) }}

• 对
• 错