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

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

第1 题已知小写字母 b 的 ASCII 码为 98，下列 C++ 代码的输出结果是 ( )。

using namespace std;
int main() {
    char a = 'b';
    cout << a + 1;
    return 0;
}

{{ select(1) }}

• b
• c
• 98
• 99

第2 题已知 a 为 int 类型变量，p 为 int * 类型变量，下列赋值语句不符合语法的是 ( )。

{{ select(2) }}

• +a=*p;
• *p=+a;
• a=*(p+a);
• *(p+a)=a;

第3 题已知数组 a 的定义int a[10] = {0};，下列说法不正确的是 ( )。

{{ select(3) }}

• 语句a[-1]=0会产生编译错误。
• 数组 a 的所有元素均被初始化为 0。
• 数组 a 至少占用 10 个 int 大小的内存，一般为 40 个字节。
• 语句a[13] = 0;不会产生编译错误，但会导致难以预测的运行结果。

第4 题下列关于 C++ 类的说法，错误的是 ( )。

{{ select(4) }}

• 构造函数不能声明为虚函数，但析构函数可以。
• 函数参数如声明为类的引用类型，调用时不会调用该类的复制构造函数。
• 静态方法属于类、不属于对象，因此不能使用对象.方法(...)的形式调用静态方法。
• 析构派生类的对象时，一定会调用基类的析构函数。

第5 题下列关于有向图的说法，错误的是 ( )。

{{ select(5) }}

• n 个顶点的弱连通有向图，最少有 (n - 1) 条边。
• n 个顶点的强连通有向图，最少有 n 条边。
• n 个顶点的有向图，最多有 (n×(n - 1)) 条边。
• n 个顶点的有向完全图，有 (n×(n - 1)) 条边。

第6 题一棵二叉树的每个结点均满足：结点的左子树和右子树，要么同时存在，要么同时不存在。该树有 197 个结点，则其叶结点有多少个？( )

{{ select(6) }}

• 98
• 99
• 不存在这样的树。
• 无法确定叶结点数量。

第7 题下列关于二叉树的说法，错误的是 ( )。

{{ select(7) }}

• 二叉排序树的中序遍历顺序与元素排序的顺序是相同的。
• n 个元素的二叉排序树，其高一定为 (\lfloor\log _{2}n\rfloor) 。
• 自平衡二叉查找树 (AVL 树) 是一种二叉排序树。
• 任意的森林，都可以映射为一颗二叉树进行表达和存储。

第8 题一个简单无向图有 10 个结点、6 条边。在最差情况，至少增加多少条边可以使其连通？( )

{{ select(8) }}

• 3
• 4
• 6
• 9

第9 题一个哈希表，包括 n 个位置 (分别编号 0~(n - 1))，每个位置最多仅能存储一个元素。该哈希表只有插入元素和查询两种操作，没有删除或修改元素的操作。以下说法错误的是 ( )。

{{ select(9) }}

• 如果哈希函数取值范围为 (0 ~(n - 1)) ，且当发生哈希函数碰撞时循环向后寻找空位，则查询操作的最差时间复杂度为 (O(n)) 。(“循环向后” 指：0 向后一位为 1，1 向后一位为 2，……，(n - 2) 向后一位为 (n - 1)，(n - 1) 向后一位为 0)
• 如果哈希函数取值范围为 0 ~ (n - 1)，且当发生哈希函数碰撞时仅循环向后一个位置寻找空位，则查询操作的最差时间复杂度为 (O(1)) 。
• 如果哈希函数取值范围为 (0 ~(m - 1) (m < n)) )，且当发生哈希函数碰撞时仅在 (m ~(n - 1)) 的范围内寻找空位，则查询操作的最差时间复杂度为 (O(n - m)) 。
• 查询操作时，如果发现查询元素经哈希函数对应的位置为空位，该查询元素仍可能出现在哈希表内。

第10 题以下关于动态规划的说法中，错误的是 ( )。

{{ select(10) }}

• 动态规划方法将原问题分解为一个或多个相似的子问题。
• 动态规划方法通常能够列出递推公式。
• 动态规划方法有递推和递归两种实现形式。
• 递推实现动态规划方法的时间复杂度总是不低于递归实现。

第11 题下面程序的输出为 ( )。

#include <cmath>
using namespace std;
int main() {
    cout << (int)exp(2) << endl;
    return 0;
}

{{ select(11) }}

• 4
• 7
• 100
• 无法通过编译。

第12 题下面程序的输出为 ( )。

#define N 10
using namespace std;
int h[N];
int main() {
    h[0] = h[1] = 1;
    for (int n = 2; n < N; n++)
        for (int j = 0; j < n; j++)
            h[n] += h[j] * h[n - j - 1];
    cout << h[6] << endl;
    return 0;
}

{{ select(12) }}

• 132
• 1430
• 16796
• 结果是随机的。

第13 题上题中程序的时间复杂度为 ( )。

{{ select(13) }}

• （文档未明确 A 选项内容，无法列出）
• （文档未明确 B 选项内容，无法列出）
• (O(N^{3/2}))
• （文档未明确 D 选项内容，无法列出）

第14 题下面init_sieve函数的时间复杂度为 ( )。

int sieve[MAX_N];
void init_sieve(int n) {
    for (int i = 1; i <= n; i++)
        sieve[i] = i;
    for (int i = 2; i <= n; i++)
        for (int j = i; j <= n; j += i)
            sieve[j]--;
}

{{ select(14) }}

• （文档未明确 A 选项内容，无法列出）
• （文档未明确 B 选项内容，无法列出）
• （文档未明确 C 选项内容，无法列出）
• 无法正常结束。

第15 题下列选项中，哪个不可能是下图的深度优先遍历序列 ( )。（文档未提供图，无法针对图进行分析）

{{ select(15) }}

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

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

第1 题表达式 5 ^ 3 的结果为 125。

{{ select(16) }}

• 对
• 错

第2 题在 C++ 语言中，函数定义和函数调用可以不在同一个文件内。

{{ select(17) }}

• 对
• 错

第3 题在 n 个元素中进行二分查找，平均时间复杂度是（文档未明确，无法准确描述），但须要事先进行排序。

{{ select(18) }}

• 对
• 错

第4 题unsigned long long类型是 C++ 语言中表达范围最大的非负整数类型之一，其表达范围是 ([0,2^{64}-1]) 。超出该范围的非负整数运算，将无法使用 C++ 语言进行计算。

{{ select(19) }}

• 对
• 错

第5 题使用math.h或cmath头文件中的函数，表达式log2(32)的结果为 5、类型为 int。

{{ select(20) }}

• 对
• 错

第6 题C++ 是一种面向对象编程语言，C 则不是。继承是面向对象三大特性之一。因此，使用 C 语言无法实现继承。

{{ select(21) }}

• 对
• 错

第7 题邻接表和邻接矩阵都是图的存储形式。邻接表在遍历单个顶点的所有边时，时间复杂度更低；邻接矩阵在判断两个顶点之间是否有边时，时间复杂度更低。

{{ select(22) }}

• 对
• 错

第8 题MD5 是一种常见的哈希函数，可以由任意长度的数据生成 128 位的哈希值，曾广泛应用于数据完整性校验。中国科学家的系列工作首次发现了可实用的 MD5 破解方法。之后，MD5 逐渐被其他哈希函数所取代。

{{ select(23) }}

• 对
• 错

第9 题递归调用在运行时会由于层数过多导致程序崩溃，可以通过循环配合栈缓解这一问题。

{{ select(24) }}

• 对
• 错

第10 题一个图中，每个顶点表达一个城市，连接两个顶点的边表达从一个城市到达另一个城市的一种交通方式。这个图可以用来表达交通网络，且是简单有向图。

{{ select(25) }}

• 对
• 错