CCF GESP 2026年3月认证 C++ 7级

一 单选题
共 15 道 每题 2 分 共计 30 分
第 1 题

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

A

$O(n)$
B

$O(n\ log\,n)$
C

$O(n^2)$
D

$O(2^n)$
第 2 题

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

A

如果预处理出 n 以内每个数的最小质因子，那么可以在 $O(log\,n)$ 时间内完成任意⼀个不超过 n 的整数的质因数分解。
B

线性筛（欧拉筛）能够保证每个合数只被其最小质因子筛掉一次，这一性质依赖于唯一分解定理。
C

唯一分解定理保证：若一个数未被任何不超过其平方根的质数筛去，则它一定是质数。
D

唯一分解定理是埃氏筛时间复杂度为 $O(n\ log\,log\,n)$ 的根本原因。
第 3 题

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

A

它们的编辑距离为 5

B

它们至少有 5 个公共字符

C

它们最长公共子串长度为 5

D

它们⼀定长度相等

第 4 题

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

A

$n-1$
B

$2n-2$
C

$2n$
D

$n^2$
第 5 题

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

A

装载因子越大，发生冲突的概率通常越高

B

开放定址法在删除元素时实现相对复杂

C

链地址法在最坏情况下查找时间复杂度为 $O(n)$
D

查找哈希表的时间复杂度总是 $O(1)$
第 6 题

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

A

分治
B

贪心
C

动态规划
D

回溯
第 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;
}
A

2
B

3
C

4
D

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

$O(n\ log\,n+n\ log\,D)$
B

$O(n\ log\,n\,log\,D)$
C

$O(n\ log\,n)$
D

$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，则该二叉树的后序遍历序列是（ ）。

A

H I D E B J F G C A
B

H I D B E J F G C A
C

I H D E B J F G C A
D

H I D E B F J G C A
第 10 题

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

A

1, 5, 4, 8, 7, 9, 6, 3, 2
B

1, 5, 8, 4, 7, 9, 6, 3, 2
C

2, 5, 8, 7, 9, 6, 3, 4, 1
D

8, 9, 6, 3, 2, 5, 1, 4, 7
第 11 题

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

A

3
B

4
C

5
D

6
第 12 题

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

A

泛洪算法只适用于二维网格中的四连通或八连通问题。

B

泛洪算法必须使用递归方式实现。

C

泛洪算法本质上是对图进行一次从起点出发的搜索。

D

泛洪算法只能用于统计连通块个数，不能用于计算面积或周长。

第 13 题

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

A

58
B

60
C

62
D

64
第 14 题

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

A

在单链表中，若已知某结点的指针，则可以在 $O(1)$ 时间内删除该结点。

B

循环链表中一定不存在空指针。

C

在循环双链表中，尾结点的 next 指针一定为 NULL。

D

在带头结点的循环单链表中，判定链表是否为空只需判断头结点的 next 是否指向自身。

第 15 题

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

A

对任意一棵树进行深度优先遍历，所得序列一定唯一。

B

已知一棵二叉树的先序遍历和后序遍历序列，可以唯一确定这棵二叉树。

C

已知一棵二叉树的先序遍历和中序遍历序列，可以唯一确定这棵二叉树。

D

一棵二叉树的中序遍历序列是单调递增的，则该二叉树一定是二叉平衡树。

单选题部分已到底了。