CCF GESP C++ 八级 (2023 年 12 月)

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

第 1 题小杨要从 A 城到 B 城，又想顺路游览一番。他有两个选项：1、坐高铁路到 C 城游览，再坐高铁或飞机到 B 城；2、坐船到 D 城游览，再坐船、高铁或飞机到 B 城。请问小杨从 A 城到 B 城共有几种交通方案可以选择？( )

{{ select(1) }}

• 2
• 3
• 5
• 6

第 2 题以下哪个函数声明是符合语法的，且在调用时可以将二维数组的名字作为实际参数传递给形式参数 a？( )

{{ select(2) }}

• void QuickSort(int a[][10], int n);
• void QuickSort(int a[5][], int m);
• void QuickSort(int a[][], int n, int m);
• void QuickSort(int **a, int n, int m);

第 3 题下面有关 C++ 类和对象的说法，错误的是 ( )。

{{ select(3) }}

• 对象的生命周期开始时，会执行构造函数。
• 对象的生命周期结束时，会执行析构函数。
• 类的析构函数可以为虚函数。
• 类的构造函数可以为虚函数。

第 4 题使用邻接矩阵表达 n 个顶点的有向图，则该矩阵的大小为 ( )。

{{ select(4) }}

• $n \times (n+1)$
• $n × n$
• $n \times (n-1)$
• $n \times (n-1)/2$

第 5 题5 位同学排队，其中一位同学不能排在第一，则共有多少种可能的排队方式？( )

{{ select(5) }}

• 5
• 24
• 96
• 120

第 6 题一个无向图包含 n 个顶点，则其最小生成树包含多少条边？( )

{{ select(6) }}

• $(n-1)$
• $(n)$
• $(n+1)$
• 最小生成树可能不存在。

第 7 题已知三个double类型的变量a、b和theta分别表示一个三角形的两条边长及二者的夹角（弧度），则下列哪个表达式可以计算这个三角形的面积？( )

{{ select(7) }}

• a * b * sin(theta) / 2
• (a + b) * sin(theta) / 2
• a * b * cos(theta) / 2
• sqrt(a * a + b * b - 2 * a * b * cos(theta))

第 8 题对有 n 个元素的二叉排序树进行中序遍历，其时间复杂度是 ( )。

{{ select(8) }}

• $O(1)$
• $O(logn)$
• $O(n)$
• $O(n^2)$

第 9 题假设输入参数m和n满足 (m ≤n)，则下面程序的最差情况的时间复杂度为 ( )。

int gcd(int m, int n) {
    while (m > 0) {
        int t = m;
        m = n % m;
        n = t;
    }
    return n;
}

{{ select(9) }}

• $O(logn)$
• $O(n)$
• $O(n*m)$
• $O(mlogn)$

第 10 题下面程序的时间复杂度为 ( )。

long long power_mod(long long a, long long n, long long mod) {
    if (n == 0)
        return 1;
    if (n == 1) {
        a = a % mod;
        return a;
    }
    long long pw = power_mod(a, n / 2, mod);
    long long pw2 = pw * pw % mod;
    if (n % 2 == 0)
        return pw2;
    return pw2 * a % mod;
}

{{ select(10) }}

• $O(n)$
• $O(a^n)$
• $O(\log(n))$
• $O(\log(n) \times a)$

第 11 题下面程序的时间复杂度为 ( )。

int record_choose[MAXN][MAXM];
int choose(int n, int m) {
    if (m == 0 || m == n)
        return 1;
    if (record_choose[n][m] == 0)
        record_choose[n][m] = choose(n - 1, m - 1) + choose(n - 1, m);
    return record_choose[n][m];
}

{{ select(11) }}

• $O(2^n)$
• $O(2^m*(n-m))$
• $O(C(n,m))$
• $O(m*(n-m))$

第 12 题下面的程序使用出边的邻接表表达有向图，则下列选项中哪个是它表达的图？( )

#include <iostream>
struct Edge {
    int e;
    Edge* next;
};
struct Node {
    Edge* first;
};
int main() {
    Edge e[5] = {{1, nullptr}, {2, &e[2]}, {3, nullptr}, {3, nullptr}, {0, nullptr}};
    Node n[4] = {&e[0], &e[1], &e[3], &e[4]};
    // 其他处理
    return 0;
}

1. 2. 3. 4. {{ select(12) }}

• 1
• 2
• 3
• 4

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

#include <iostream>
using namespace std;
int main() {
    int cnt = 0;
    for (int a = 1; a <= 10; a++)
        for (int b = 1; b <= 10; b++)
            for (int h = 1; h <= 10; h++)
                if ((a + b) * h == 20)
                    cnt++;
    cout << cnt << endl;
    return 0;
}

{{ select(13) }}

• 12
• 18
• 36
• 42

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

#include <iostream>
using namespace std;
int main() {
    const int N = 30;
    int cnt = 0;
    for (int a = 1; a <= N; a++)
        for (int b = a; a + b <= N; b++)
            for (int c = b; a + b + c <= N; c++)
                if (a * a + b * b == c * c)
                    cnt++;
    cout << cnt << endl;
    return 0;
}

{{ select(14) }}

• 3
• 6
• 11
• 22

第 15 题下面的程序中，二维数组h和v分别代表如下图所示的网格中的水平边的时间消耗和垂直边的时间消耗。程序使用动态规划计算从左下角到右上角的最小时间消耗，则横线处应该填写下列哪个选项的代码？( )

int dis[MAXY][MAXX];
int shortest_path(int x, int y) {
    dis[0][0] = 0;
    for (int i = 0; i < y; i++)
        dis[i + 1][0] = dis[i][0] + v[i][0];
    for (int j = 0; j < x; j++)
        dis[0][j + 1] = dis[0][j] + h[0][j];
    for (int i = 0; i < y; i++)
        for (int j = 0; j < x; j++)
            // 在此处填写代码
            ;
    return dis[y][x];
}

{{ select(15) }}

• dis[i][j] = min(dis[i - 1][j] + v[i - 1][j], dis[i][j - 1] + h[i][j - 1]);
• dis[i][j] = min(dis[i - 1][j] + h[i - 1][j], dis[i][j - 1] + v[i][j - 1]);
• dis[i + 1][j + 1] = min(dis[i][j + 1] + v[i][j + 1], dis[i + 1][j] + h[i + 1][j]);
• dis[i + 1][j + 1] = min(dis[i][j + 1] + h[i][j + 1], dis[i + 1][j] + v[i + 1][j]);

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

第 1 题C++ 语言非常强大，可以用来求解方程的解。例如，如果变量x为double类型的变量，则执行语句x * 2 - 4 = 0;后，变量x的值会变为 2.0。

{{ select(16) }}

• 对
• 错

第 2 题一个袋子中有 3 个完全相同的红色小球、2 个完全相同的蓝色小球。每次从中取出 1 个，且不放回袋子，这样进行 3 次后，将取出的小球依次排列，则可能的颜色顺序有 7 种。

{{ select(17) }}

• 对
• 错

第 3 题杨辉三角，是二项式系数的一种三角形排列，在中国南宋数学家杨辉 1261 年所著的《详解九章算法》一书中出现，是中国数学史上的一项伟大成就。

{{ select(18) }}

• 对
• 错

第 4 题N 个顶点的有向完全图（不带自环）有 (N × (N - 1)/2) 条边。

{{ select(19) }}

• 对
• 错

第 5 题如果待查找的元素确定，只要哈希表的大小不小于查找元素的个数，就一定存在不会产生冲突的哈希函数。

{{ select(20) }}

• 对
• 错

第 6 题动态规划算法的时间复杂度一般为：必要状态的数量，乘以计算一次状态转移方程的时间复杂度。

{{ select(21) }}

• 对
• 错

第 7 题已知int类型的变量a、b和h中分别存储着一个梯形的顶边长、底边长和高，则这个梯形的面积可以通过表达式(a + b) * h / 2求得。

{{ select(22) }}

• 对
• 错

第 8 题判断图是否连通只能用广度优先搜索算法实现。

{{ select(23) }}

• 对
• 错

第 9 题在 N 个元素的二叉排序树中查找一个元素，最好情况的时间复杂度是 (O(log N))。

{{ select(24) }}

• 对
• 错

第 10 题给定double类型的变量x，且其值大于等于0，我们可以通过二分法求出 ($\sqrt{x}$) 的近似值。

{{ select(25) }}

• 对
• 错