CCF GESP 2025年12月认证 C++ 7级

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

下面关于 C++ 中形参、实参和定义域的说法中，正确的一项是（ ）。

A

形参是函数定义时所指定的变量，它只在函数内部有效。

B

在函数内部，可以修改传入的形参的值，即使该形参是一个常量引用。

C

实参和形参的类型必须完全一致，否则会导致编译错误。

D

使用指针作为形参时，形参是指向实参的地址，因此对该指针赋值会影响实参。

第 2 题

已知三个序列：s1 = {3, 1, 8, 2, 5, 6, 7, 4}，s2 = {1, 5, 1, 8, 6, 4, 7, 5, 6}，s3 = {1, 8, 3, 5, 7, 6, 2, 4}。以下哪个序列是它们的最长公共子序列（ ）。

A

{1, 8, 5, 6}

B

{1, 5, 6, 7}

C

{1, 8, 6}

D

{1, 5, 7, 4}

第 3 题

现有一个地址区间为 0∼10 的哈希表，当出现冲突情况，会往后找第一个空的地址存储（到 10 冲突了就从 0 开始往后），现在要依次存储 (1,3,5,7,9)，哈希函数为 $h(x) = (x^2 + x) \ mod \ 11$。其中 9 存储在哈希表哪个地址中（ ）。

A

1
B

2
C

3
D

4
第 4 题

在 0/1 背包问题中，给定一组物品，每个物品有一个重量和价值，背包的容量有限。假设背包的最大容量为 $W$，物品的数量为 $n$，其中第 $i$ 个物品的重量为 $w[i]$，价值为 $v[i]$。以下关于 0/1 背包问题的描述，正确的是（ ）。

A

在解决 0/1 背包问题时，使用贪心算法可以保证找到最优解，因为物品只能放入一次。
B

0/1 背包是 $P$ 问题（多项式时间可解问题），它可以在 $O(nW)$ 的时间复杂度内解决。
C

0/1 背包问题中，动态规划解法的空间复杂度为 $O(nW)$，但可以通过滚动数组技巧将空间复杂度优化到 $O(W)$。
D

0/1 背包问题中，每个物品只能选择一次，并且子问题之间是独立的，无法重用计算结果。
第 5 题

一棵深度为 6（根节点深度为 1）的完全二叉树，节点总数最少有（ ）。

A

31
B

32
C

63
D

64
第 6 题

对于如下二叉树，下面关于访问的顺序说法错误的是（ ）。

A

D E B F H J I G C A 是它的后序遍历序列。
B

A B C D E F G H I J 是它的广度优先遍历序列。
C

A B D E C F G H I J 是它的先序遍历序列。
D

D B E A F C H G J I 是它的中序遍历序列。
第 7 题

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

#include <iostream>
 
int query(int n, int *a, int x) {
    int l = 0, r = n;
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (a[mid] >= x) r = mid;
        else l = mid + 1;
    }
 
    if (l == n) return -1;
    return l;
}
 
int main() {
    int n = 10;
    int x = 3;
    int num[] = {1, 2, 2, 3, 3, 4, 5, 5, 6, 7};
 
    std::cout << query(n, num, x) << "\n";
    return 0;
}
A

2
B

3
C

4
D

5
第 8 题

下面程序中，函数 query 的时间复杂度是（ ）。

#include <iostream>
 
int query(int n, int *a, int x) {
    int l = 0, r = n;
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (a[mid] >= x) r = mid;
        else l = mid + 1;
    }
 
    if (l == n) return -1;
    return l;
}
 
int main() {
    int n = 10;
    int x = 3;
    int num[] = {1, 2, 2, 3, 3, 4, 5, 5, 6, 7};
 
    std::cout << query(n, num, x) << "\n";
    return 0;
}
A

$O(1)$
B

$O(log\,n)$
C

$O(n)$
D

$O(n\ log\,n)$
第 9 题

有 5 个字符，它们出现的次数分别为 2 次、2 次、3 次、3 次、5 次。现在要用哈夫曼编码的方式来为这些字符进行编码，最小加权路径长度 WPL（每个字符的出现次数 × 它的编码长度，再把每个字符结果加起来）的值为（ ）。

A

30
B

34
C

43
D

47
第 10 题

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

#include <iostream>
using namespace std;
int f(int n) {
    if (n <= 2) return n * 2;
    return f(n - 1) + f(n - 2);
}
int main() {
    cout << f(5) << endl;
    return 0;
}
A

10
B

16
C

26
D

30
第 11 题

一个简单无向图 G 有 36 条边，且每个顶点的度数都为 4，则图 G 的顶点个数为（ ）。

A

9
B

12
C

18
D

36
第 12 题

下面关于二叉树的说法正确的是（ ）。

A

任意二叉树的中序遍历与后序遍历必定不相同。

B

对任意二叉树，若已知先序遍历与后序遍历，则该二叉树唯一确定。

C

若二叉树有 n 个结点，根节点高度为 1，则其高度满足：$\lceil log⁡_2(n+1) \rceil ≤h≤n$。

D

在二叉树的先序遍历中，根后紧跟的结点一定是根的左孩子。

第 13 题

假设一个算法时间复杂度的递推式是 $T(n)=8T(\frac{n}{4})+n\sqrt{n}$（n 为正整数），和 T(0)=1，那么这个算法的时间复杂度是（ ）。

A

$O(n\sqrt{n})$
B

$O(n\sqrt{n}log\,n)$
C

$O(n^2)$
D

$O(n^2log\,n)$
第 14 题

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

A

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

B

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

C

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

D

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

第 15 题

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

A

3
B

4
C

5
D

6
单选题部分已到底了。