CCF GESP C++ 七级 (2025 年 12 月)

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

1. 下⾯关于C++中形参、实参和定义域的说法中，正确的⼀项是（ ）

{{ select(1) }}

• 形参是函数定义时所指定的变量，它只在函数内部有效。
• 在函数内部，可以修改传⼊的形参的值，即使该形参是⼀个常量引⽤。
• 实参和形参的类型必须完全⼀致，否则会导致编译错误。
• 使⽤指针作为形参时，形参是指向实参的地址，因此对该指针赋值会影响实参。

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} 。以下哪个序列是它们的最长公共⼦序列（ ）。

{{ select(2) }}

• {1, 8, 5, 6}
• {1, 5, 6, 7}
• {1, 8, 6}
• {1, 5, 7, 4}

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

{{ select(3) }}

• 1
• 2
• 3
• 4

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

{{ select(4) }}

• 在解决0/1背包问题时，使⽤贪⼼算法可以保证找到最优解，因为物品只能放⼊⼀次。
• 0/1背包是P问题（多项式时间可解问题），它可以在 $O(nW)$ 的时间复杂度内解决。
• 0/1背包问题中，动态规划解法的空间复杂度为 $O(nW)$，但可以通过滚动数组技巧将空间复杂度优化到 $O(W)$。
• 0/1背包问题中，每个物品只能选择⼀次，并且⼦问题之间是独⽴的，⽆法重⽤计算结果。

5. ⼀棵深度为6（根节点深度为1）的完全⼆叉树，节点总数最少有（ ）

{{ select(5) }}

• 31
• 32
• 63
• 64

6. 对于如下⼆叉树，下⾯关于访问的顺序说法错误的是（ ）

{{ select(6) }}

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

7. 下⾯程序的运⾏结果为（ ） 2 10 14 19

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

{{ select(7) }}

• 2
• 3
• 4
• 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;
}
}

{{ select(8) }}

• $O(1)$
• $O(\log n)$
• $O(n)$
• $O(n \log n)$

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

{{ select(9) }}

• 30
• 34
• 43
• 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;
}

{{ select(10) }}

• 10
• 16
• 26
• 30

11. ⼀个简单⽆向图 有36条边，且每个顶点的度数都为4，则图 的顶点个数为（ ）

{{ select(11) }}

• 9
• 12
• 18
• 36

12. 下⾯关于⼆叉树的说法正确的是（ ）

{{ select(12) }}

• 任意⼆叉树的中序遍历与后序遍历必定不相同。
• 对任意⼆叉树，若已知先序遍历与后序遍历，则该⼆叉树唯⼀确定。
• 若⼆叉树有 个结点，根节点⾼度为 ，则其⾼度满⾜： 。
• 在⼆叉树的先序遍历中，根后紧跟的结点⼀定是根的左孩⼦。

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

{{ select(13) }}

• $O(n\sqrt{n})$
• $O(n\sqrt{n} \log n)$
• $O(n^2)$
• $O(n^2 \log n)$

14. 下⾯哪⼀个可能是下图的深度优先遍历序列（ ）

{{ select(14) }}

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

15. 下⾯这个有向图的强连通分量的个数是（ ）

{{ select(15) }}

• 3
• 4
• 5
• 6

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

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

{{ select(16) }}

• 对
• 错

2. 使⽤ cmath 头⽂件中的正弦函数，表达式 sin(90) 的结果类型为 double ，值约为 1.0

{{ select(17) }}

• 对
• 错

3. 使⽤ strcmp("10", "9") ⽐较两个字符串，返回值⼤于0，说明 "10" ⽐ "9" ⼤

{{ select(18) }}

• 对
• 错

4. 选择排序是⼀种不稳定的排序算法，⽽冒泡排序是⼀种稳定的排序算法

{{ select(19) }}

• 对
• 错

5. 求两个长度为 序列的最长公共⼦序列（LCS）长度时，可以使⽤滚动数组将空间复杂度从 优化到 。

{{ select(20) }}

• 对
• 错

6. 在⽆向图中，所有顶点的度数之和等于边数的两倍

{{ select(21) }}

• 对
• 错

7. 使⽤邻接矩阵存储⼀个有 个顶点、 条边的图，对该图进⾏⼀次完整的BFS遍历，时间复杂度为 。

{{ select(22) }}

• 对
• 错

8. 在图像处理或游戏开发中，泛洪（flood fill）算法既可以⽤BFS实现，也可以⽤DFS实现

{{ select(23) }}

• 对
• 错

9. 使⽤链地址法处理冲突的哈希表，当所有元素都映射到同⼀个槽位时，查找操作的最坏时间复杂度为 ， 其中 为元素个数。

{{ select(24) }}

• 对
• 错

10. ⼀个包含 个顶点的连通⽆向图，其任何⼀棵⽣成树都恰好包含 条边

{{ select(25) }}

• 对
• 错