CCF GESP C++ 八级 (2024 年 09 月)

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

第1题 下面关于C++类和对象的说法,错误的是( )｡

{{ select(1) }}

• 类的析构函数可以为虚函数｡
• 类的构造函数不可以为虚函数｡
• class中成员的默认访问权限为private｡
• struct中成员的默认访问权限为private｡

第2题 对于一个具有n个顶点的无向图,若采用邻接矩阵表示,则该矩阵的大小为( )｡

{{ select(2) }}

• $n \times \frac{n}{2}$
• $n \times n$
• $(n - 1) \times (n - 1)$
• $(n + 1) \times (n + 1)$

第3题 设有编号为A､B､C､D､E的5个球和编号为A､B､C､D､E的5个盒子｡现将这5个球投入5个盒子,要求每个盒子放一个球,并且恰好有两个球的编号与盒子编号相同,问有多少种不同的方法?( )｡

{{ select(3) }}

• 5
• 120
• 20
• 60

第4题 从甲地到乙地,可以乘高铁,也可以乘汽车,还可以乘轮船｡一天中,高铁有10班,汽车有5班,轮船有2班｡那么一天中乘坐这些交通工具从甲地到乙地共有多少种不同的走法?( )｡

{{ select(4) }}

• 100
• 60
• 30
• 17

第5题 n个结点的二叉树,执行释放全部结点操作的时间复杂度是( )｡

{{ select(5) }}

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

第6题 在一个单位圆上,随机分布n个点,求这个点能被一个单位半圆周全部覆盖的概率( )｡

{{ select(6) }}

• $\frac{n}{2^{n-1}}$
• $\frac{1}{n^2}$
• $\frac{1}{n}$
• $\frac{1}{2^n}$

第7题 下面pailie函数是一个实现排列的程序,横线处可以填入的是( )｡

#include <iostream>
using namespace std; 
int sum = 0;
void swap(int & a, int & b) {
    int temp = a;
    a = b;
    b = temp;
}
void pailie(int begin, int end, int a[]) {
    if (begin == end) {
        for (int i = 0; i < end; i++)
            cout << a[i];
        cout << endl;
       
    }
    for (int i = begin; i < end; i++) {
        ___________________// 在此处填入选项
        
    }
   
}

{{ select(7) }}

• 1. swap(a[begin + 1], a[i]); 2. pailie(begin + 1, end, a); 3. swap(a[i], a[begin]);
• 1. swap(a[begin], a[i]); 2. pailie(begin, end, a); 3. swap(a[i], a[begin]);
• 1. swap(a[begin], a[i]); 2. pailie(begin + 1, end, a); 3. swap(a[i], a[begin]);
• 1. swap(a[begin] + 1, a[i]); 2. pailie(begin + 1, end, a); 3. swap(a[i], a[begin + 1]);

第 8 题上一题中，如果主函数为如下的程序，则最后的排列数是多少个？( )｡

int main() {
    int a[5] = {1, 2, 3, 4, 5}; 
    pailie(0, 5, a);
    return 0;
}

{{ select(8) }}

• 120
• 60
• 240
• 180

第 9 题下列程序实现了输出杨辉三角形，代码中横线部分应该填入的是 ( )｡

#include <iostream>
using namespace std;
#define N 35
int a[N][N];
int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= i; j++) {
            if (j == 1 || j == i) 
                a[i][j] = 1;
            else
                _____________// 在此处填入选项
        }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) 
            cout << a[i][j];
        cout << endl;
    }
    return 0;
}

{{ select(9) }}

• a[i][j] = a[i - 1][j - 1] + a[i - 1][j];
• a[i][j] = a[i][j - 1] + a[i - 1][j];
• a[i][j] = a[i - 1][j] + a[i - 1][j];
• a[i][j] = a[i - 1][j - 1] + a[i][j];

第 10 题下面最小生成树的 Kruskal 算法程序中，横线处应该填入的是 ( )｡

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Edge {
    int u, v, weight;
    bool operator <(const Edge & other) const {
        return weight < other.weight;
    }
};
int findParent(int vertex, vector<int> & parent) {
    if (parent[vertex] == -1)
        return vertex;
    return parent[vertex] = findParent(parent[vertex], parent);
}
int main() {
    int n, m;
    cin >> n >> m; // n: 顶点数, m: 边数
    vector<Edge> edges(m);
    vector<int> parent(n, -1); 
    int totalWeight = 0;
    for (int i = 0; i < m; i++) 
        cin >> edges[i].u >> edges[i].v >> edges[i].weight;
    sort(edges.begin(), edges.end());
    for (const auto & edge : edges) { 
        int uParent = findParent(edge.u, parent); 
        int vParent = findParent(edge.v, parent); 
        if (__________) { // 在此处填入选项
            parent[uParent] = vParent; 
            totalWeight += edge.weight;
        }
    }
  
    return 0;
}

{{ select(10) }}

• uParent == vParent
• uParent >= vParent
• uParent != vParent
• uParent <= vParent

第 11 题下面 Prim 算法程序中，横线处应该填入的是 ( )｡

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
int prim(vector<vector<int>> & graph, int n) { 
    vector<int> key(n, INT_MAX);
    vector<int> parent(n, -1);
    key[0] = 0;
    for (int i = 0; i < n; i++) { 
        int u = min_element(key.begin(), key.end()) - key.begin(); 
        if (key[u] == INT_MAX)
            break;
        key[u] = INT_MAX; // 标记已选中
        for (int v = 0; v < n; v++) {
            if (__________) { // 在此处填入选项
                key[v] = graph[u][v];
                parent[v] = u;
            }
        }
    }
    int sum = 0;
    for (int i = 0; i < n; i++) {
        if (parent[i] != -1) {
            cout << "Edge: " << parent[i] << " - " << i << " Weight: " << key[i] << endl;
            sum += key[i];
        }
    }
    return sum;
}
int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> graph(n, vector<int>(n, INT_MAX));
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        graph[u][v] = w;
        graph[v][u] = w;
    }
    int result = prim(graph, n);
    cout << "Total weight of the minimum spanning tree: " << result << endl;
    return 0;
}

{{ select(11) }}

• graph[u][v] >= 0 && key[v] > graph[u][v]
• graph[u][v] <= 0 && key[v] > graph[u][v]
• graph[u][v] == 0 && key[v] > graph[u][v]
• graph[u][v] != 0 && key[v] > graph[u][v]

第 12 题下列 Dijkstra 算法中，横线处应该填入的是 ( )｡

#include <iostream>
using namespace std;
#define N 100
int n, e, s; 
const int inf = 0x7fffff;
int dis[N + 1];
int cheak[N + 1];
int graph[N + 1][N + 1];
int main() {
    // 初始化邻接矩阵
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)
            graph[i][j] = inf;
    for (int i = 1; i <= N; i++)
        dis[i] = inf;
    cin >> n >> e; 
    for (int i = 1; i <= e; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        graph[a][b] = c;
    }
    cin >> s; 
    dis[s] = 0;
    for (int i = 1; i <= n; i++) {
        int minn = inf, minx;
        for (int j = 1; j <= n; j++) {
            if (__________) { // 在此处填入选项
                minn = dis[j];
                minx = j;
            }
        }
        cheak[minx] = 1;
        for (int j = 1; j <= n; j++) {
            if (graph[minx][j] < inf) {
                if (minn + graph[minx][j] < dis[j]) {
                    dis[j] = minn + graph[minx][j];
                }
            }
        }
    }
   
    return 0;
}

{{ select(12) }}

• dis[j] > minn && cheak[j] == 0
• dis[j] < minn && cheak[j] == 0
• dis[j] >= minn && cheak[j] == 0
• dis[j] < minn && cheak[j] != 0

第 13 题下面 Floyd 算法中，横线处应该填入的是 ( )｡

#include <iostream>
using namespace std;
#define N 21
#define INF 99999999
int main() { 
    int map[N][N];
    int n, m, t1, t2, t3;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) { 
        for (int j = 1; j <= n; j++) {
            if (i == j) 
                map[i][j] = 0;
            else
                map[i][j] = INF;
        }
    }
    for (int i = 1; i <= m; i++) { 
        cin >> t1 >> t2 >> t3;
        map[t1][t2] = t3;
    }
    // Floyd核心三重循环
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (__________) // 在此处填入选项
                    map[i][j] = map[i][k] + map[k][j];
    // 输出结果
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cout.width(4);
            cout << map[i][j];
        }
        cout << endl;
    }
    return 0;
}

{{ select(13) }}

• map[i][j] < map[i][k] + map[k][j]
• map[i][j] > map[i][k] + map[k][j]
• map[i][j] > map[i][k] - map[k][j]
• map[i][j] < map[i][k] - map[k][j]

第 14 题下面程序的 Merge_Sort 函数时间复杂度为 ( )｡

void Merge(int a[], int left, int mid, int right) { 
    int temp[right - left + 1]; 
    int i = left;
    int j = mid + 1;
    int k = 0;
    while (i <= mid && j <= right) { 
        if (a[i] < a[j]) 
            temp[k++] = a[i++];
        else
            temp[k++] = a[j++];
    }
    while (i <= mid)
        temp[k++] = a[i++];
    while (j <= right) 
        temp[k++] = a[j++];
    for (int m = left, n = 0; m <= right; m++, n++)
        a[m] = temp[n];
}
void Merge_Sort(int a[], int left, int right) { 
    if (left == right)
        return;
    int mid = (left + right) / 2;
    Merge_Sort(a, left, mid);
    Merge_Sort(a, mid + 1, right);
    Merge(a, left, mid, right);
}

{{ select(14) }}

• $O(nlog n)$
• $O(n^2)$
• $O(2^n)$
• $O(log n)$

第 15 题下面 fibonacci 函数的时间复杂度为 ( )｡

int fibonacci(int n) { 
    if (n <= 1)
        return n;
    else
        return fibonacci(n - 1) + fibonacci(n - 2);
}

{{ select(15) }}

• $O(1)$
• $O(\phi^n), \text{其中 } \phi = \frac{\sqrt{5} - 1}{2}$
• $O(n)$
• $O(nlogn)$

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

第 1 题表达式 '3' & 1 的结果为 '1' ｡

{{ select(16) }}

• 对
• 错

第 2 题在 C++ 语言中，变量定义必须在某一个函数定义之内｡

{{ select(17) }}

• 对
• 错

第 3 题冒泡排序一般是不稳定的｡

{{ select(18) }}

• 对
• 错

第 4 题二叉排序树的查找操作的平均时间复杂度，正比于树的高度｡

{{ select(19) }}

• 对
• 错

第 5 题使用 math.h 或 cmath 头文件中的余弦函数，表达式 cos (60) 的结果类型为 double ､值约为 0.5 ｡

{{ select(20) }}

• 对
• 错

第 6 题你有三种硬币，分别面值 2 元、5 元和 7 元，每种硬币都有足够多。买一本书需要 27 元，则最少可以用 5 个硬币组合起来正好付清，且不需要对方找钱。

{{ select(21) }}

• 对
• 错

第 7 题现有n个完全相同的元素，要将其分为k组，允许每组可以有 0 个元素，则一共有(C(n - 1, k - 1))种分组方案。

{{ select(22) }}

• 对
• 错

第 8 题已知int类型的变量a和b中分别存储着一个直角三角形的两条直角边的长度，则该三角形的面积可以通过表达式a / 2.0 * b求得。

{{ select(23) }}

• 对
• 错

第 9 题已知等差数列的通项公式(a_n = a_1 + (n - 1) \cdot d)，则前n项和的求和公式为(S_n = n \cdot (a_1 + a_n) / 2)。使用这一公式计算(S_n)的时间复杂度是(O(1))。

{{ select(24) }}

• 对
• 错

第 10 题诚实国公民只说实话，说谎国公民只说谎话。你来到一处分岔口，一条通往诚实国，一条通往说谎国，但不知是哪一条通往哪里。正在为难之际，走来两位路人，他们都自称是诚实国公民，都说对方是说谎国公民。你想去说谎国，可以这样问其中一位路人：“我要去说谎国，如果我去问另一个路人，他会指向哪一条路？”。

{{ select(25) }}

• 对
• 错