CCF GESP C++ 七级 (2026 年 03 月)

一、单选题（每题 2 分，共 30 分）

1. 假设⼀个算法时间复杂度的递推式是 （ 为正整数），且 ，那么这个算法的 时间复杂度是（ ）。 A. B. C. D.

{{ select(1) }}

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

2. 下⾯关于“唯⼀分解定理”和“素数筛法”的说法中，错误的是（ ）

{{ select(2) }}

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

3. 若字符串 与字符串 的最长公共⼦序列（LCS）长度为 5，则（ ）

{{ select(3) }}

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

4. 对于⼀棵包含 个顶点（ ）的树，其所有顶点的度数之和必定等于（ ） A. B. C. D.

{{ select(4) }}

• n-1
• 2n-2
• 2n
• $O(2^n)$

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

{{ select(5) }}

• 装载因⼦越⼤，发⽣冲突的概率通常越⾼
• 开放定址法在删除元素时实现相对复杂
• 链地址法在最坏情况下查找时间复杂度为
• 查找哈希表的时间复杂度总是

6. 在 Kruskal 算法中，会将边排序后按顺序扫描选取边加⼊最⼩⽣成树中，算法的本质思想是（ ）

{{ select(6) }}

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

7. 下⾯程序的运⾏结果为（ ） 3 7 14 17 20 23 26 32 35 40 42

#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（每个字符的出现次数 它的编码长度，再把每个字符结果加起来）的值为（ ）。

{{ select(13) }}

• 58
• 60
• 62
• 64

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

{{ select(14) }}

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

15. 下列关于树的遍历的说法中，正确的⼀项是（ ）

{{ select(15) }}

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

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

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

{{ select(16) }}

• 对
• 错

2. C++ 中引⽤可以重新绑定

{{ select(17) }}

• 对
• 错

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

{{ select(18) }}

• 对
• 错

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

{{ select(19) }}

• 对
• 错

5. 使⽤归并排序对 个元素进⾏排序时，⽆论最好、最坏还是平均情况，时间复杂度均为 O(nlogn)####

{{ 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) }}

• 对
• 错