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

一 单选题
共 15 道 每题 2 分 共计 30 分
第 1 题
已知小写字母 b 的 ASCII 码为 98，下列 C++ 代码的输出结果是（ ）。
#include <iostream>
using namespace std;
int main() {
    char a = 'b';
    cout << a + 1;
    return 0;
}
A
b
B
c
C
98
D
99
第 2 题
已知 a 为 int 类型变量，p 为 int * 类型变量，下列赋值语句不符合语法的是（ ）。
A
+a = *p;
B
*p = +a;
C
a = *(p + a);
D
*(p + a) = a;
第 3 题
已知数组 a 的定义 int a[10] = {0};，下列说法不正确的是（ ）。
A
语句 a[-1] = 0; 会产生编译错误。
B
数组 a 的所有元素均被初始化为 0。
C
数组 a 至少占用 10 个 int 大小的内存，一般为 40 个字节。
D
语句 a[13] = 0; 不会产生编译错误，但会导致难以预测的运行结果。
第 4 题
下列关于 C++ 类的说法，错误的是（ ）。
A
构造函数不能声明为虚函数，但析构函数可以。
B
函数参数如声明为类的引用类型，调用时不会调用该类的复制构造函数。
C
静态方法属于类、不属于对象，因此不能使用 对象.方法(...) 的形式调用静态方法。
D
析构派生类的对象时，一定会调用基类的析构函数。
第 5 题

下列关于有向图的说法，错误的是（ ）。

A

$n$ 个顶点的弱连通有向图，最少有 $n - 1$ 条边。
B

$n$ 个顶点的强连通有向图，最少有 $n$ 条边。
C

$n$ 个顶点的有向图，最多有 $n \times (n - 1)$ 条边。
D

$n$ 个顶点的有向完全图，有 $n \times (n - 1)$ 条边。
第 6 题
一棵二叉树的每个结点均满足：结点的左子树和右子树，要么同时存在，要么同时不存在。该树有 197 个结点。则其叶结点有多少个？（ ）
A
$98$
B
$99$
C
不存在这样的树。
D
无法确定叶结点数量。
第 7 题
下列关于二叉树的说法，错误的是（ ）。
A
二叉排序树的中序遍历顺序与元素排序的顺序是相同的。
B
$n$ 个元素的二叉排序树，其高一定为 $\lfloor \log_2 n \rfloor$。
C
自平衡二叉查找树（AVL 树）是一种二叉排序树。
D
任意的森林，都可以映射为一颗二叉树进行表达和存储。
第 8 题
一个简单无向图有 10 个结点、6 条边。在最差情况，至少增加多少条边可以使其连通？（ ）
A
$3$
B
$4$
C
$6$
D
$9$
第 9 题
一个哈希表，包括 $n$ 个位置（分别编号 $0 \sim (n-1)$），每个位置最多仅能存储一个元素。该哈希表只有插入元素和查询两种操作，没有删除或修改元素的操作。以下说法错误的是（ ）。
A
如果哈希函数取值范围为 $0 \sim (n-1)$，且当发生哈希函数碰撞时循环向后寻找空位，则查询操作的最差时间复杂度为 $O(n)$。（“循环向后”指：0 向后一位为 1，1 向后一位为 2，……，$(n-2)$ 向后一位为 $(n-1)$，$(n-1)$ 向后一位为 0）
B
如果哈希函数取值范围为 $0 \sim (n-1)$，且当发生哈希函数碰撞时仅循环向后一个位置寻找空位，则查询操作的最差时间复杂度为 $O(1)$。
C
如果哈希函数取值范围为 $0 \sim (m-1)$（$m < n$），且当发生哈希函数碰撞时仅在 $m \sim (n-1)$ 的范围内寻找空位，则查询操作的最差时间复杂度为 $O(n - m)$。
D
查询操作时，如果发现查询元素经哈希函数对应的位置为空位，该查询元素仍可能出现在哈希表内。
第 10 题
以下关于动态规划的说法中，错误的是（ ）。
A
动态规划方法将原问题分解为一个或多个相似的子问题。
B
动态规划方法通常能够列出递推公式。
C
动态规划方法有递推和递归两种实现形式。
D
递推实现动态规划方法的时间复杂度总是不低于递归实现。
第 11 题
下面程序的输出为（ ）。
#include <iostream>
#include <cmath>
using namespace std;
int main() {
    cout << (int)exp(2) << endl;
    return 0;
}
A
$4$
B
$7$
C
$100$
D
无法通过编译。
第 12 题

下面程序的输出为（ ）。

#include <iostream>
#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;
}
A

$132$
B

$1430$
C

$16796$
D

结果是随机的。
第 13 题
上题中程序的时间复杂度为（ ）。
A
$O(N)$
B
$O(N \log N)$
C
$O(N^{3/2})$
D
$O(N^2)$
第 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]--;
}
A
$O(n)$
B
$O(n \log n)$
C
$O(n^2)$
D
无法正常结束。
第 15 题

下列选项中，哪个不可能是下图的深度优先遍历序列（ ）。

A

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

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

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

1, 2, 3, 6, 9, 8, 5, 7, 4
单选题部分已到底了。