2024年3月GESP 7级C++真题_含答案与解析

一单选题

共 15 道每题 2 分共计 30 分

第 1 题

下列关于排序的说法，正确的是（）。

A

冒泡排序是最快的排序算法之一。

B

快速排序通常是不稳定的。

C

最差情况，$N$ 个元素做归并排序的时间复杂度为 $O(N)$。

D

以上均不正确。

第 2 题

下面的程序属于哪种算法（）。

int pos[8];
void queen(int n) {
    for (int i = 0; i < 8; i++) {
        pos[n] = i;
        bool attacked = false;
        for (int j = 0; j < n; j++)
            if (pos[n] == pos[j] || pos[n] + n == pos[j] + j || pos[n] - n == pos[j] - j) {
                attacked = true;
                break;
            }
        if (attacked)
            continue;
        if (n == 7) {
            return;
        } else {
            queen(n + 1);
        }
    }
}

A

贪心算法

B

动态规划

C

深度优先搜索

D

广度优先搜索

第 3 题

下面有关 C++ 类的说法，错误的是（）。

A

C++ 类对象销毁时，会执行析构函数。

B

C++ 类可以通过定义构造函数实现自动类型转换。

C

C++ 类可以通过重载 [ ] 运算符实现通过给定下标访问数组成员的元素。

D

C++ 类可以包含任意类型的成员变量。

第 4 题

一个连通的简单无向图，共有 $28$ 条边，则该图至少有（）个顶点。

A

$6$

B

$7$

C

$8$

D

$9$

第 5 题

以下哪个方案不能合理解决或缓解哈希表冲突（）。

A

在每个哈希表项处，使用单链表管理该表项的冲突元素。

B

建立额外的单链表，用来管理所有发生冲突的元素。

C

使用不同的哈希函数再建立一个哈希表，用来管理所有发生冲突的元素。

D

用新元素覆盖发生冲突的哈希表项。

第 6 题

已知一颗二叉树的中序遍历序列为：$\{C\ F\ B\ A\ E\ D\ G\}$，后序遍历序列为：$\{F\ C\ B\ E\ G\ D\ A\}$，则下列说法中正确的是（）。

A

该树是平衡二叉树。

B

该树的高为 $4$。

C

该树有 $4$ 个叶节点。

D

以上说法都不对。

第 7 题

以下关于二叉排序树的说法，正确的是（）。

A

二叉排序树的中序遍历序列一定是有序的。

B

在含 $n$ 个节点的二叉排序树中查找元素，最差情况的时间复杂度为 $O(\log(n))$。

C

二叉排序树一定是二叉平衡树。

D

以上说法都不对。

第 8 题

已知 $x$ 为 double 类型的变量，且值大于 $0$，则下列表达式的值一定大于 $0$ 的是（）。

A

$\sin(x) / x$

B

$\exp(x) - x$

C

$\log(x) - x$

D

$x \times x - x$

第 9 题

一个简单有向图有 $10$ 个结点、$30$ 条边。再增加多少条边可以成为完全图。（）

A

$60$

B

$70$

C

$15$

D

$20$

第 10 题

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

A

$8, 6, 1, 5, 3, 4, 2, 10, 7, 12, 11, 9$

B

$7, 8, 6, 4, 2, 1, 5, 3, 12, 9, 11, 10$

C

$8, 10, 12, 9, 11, 4, 5, 3, 2, 1, 6, 7$

D

$7, 8, 10, 9, 11, 12, 4, 5, 1, 2, 3, 6$

第 11 题

下面 schedule 函数的时间复杂度为（）。

#include <algorithm>
using namespace std;
struct activity {
    int id, start, end;
};
bool compare(activity a, activity b) {
    return a.end < b.end;
}
int schedule(int n, activity * p) {
    sort(p, p + n, compare);
    int cnt = 0, end = 0;
    for (int i = 0; i < n; i++) {
        if (p[i].start >= end) {
            end = p[i].end;
            cnt++;
        }
    }
    return cnt;
}

A

$O(n)$

B

$O(\log(n))$

C

$O(n \log(n))$

D

$O(n^2)$

第 12 题

下面 search 函数的平均时间复杂度为（）。

int search(int n, int * p, int target) {
    int low = 0, high = n;
    while (low <= high) {
        int middle = (low + high) / 2;
        if (target == p[middle]) {
            return middle;
        } else if (target > p[middle]) {
            low = middle + 1;
        } else {
            high = middle - 1;
        }
    }
    return -1;
}

A

$O(n)$

B

$O(\log(n))$

C

$O(1)$

D

可能无法返回

第 13 题

下面 count_triple 函数的时间复杂度为（）。

int count_triple(int n) {
    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++;
    return cnt;
}

A

$O(N)$

B

$O(N^2)$

C

$O(N^3)$

D

$O(N^4)$

第 14 题

下面程序的输出为（）。

#include <iostream>
using namespace std;
int down(int n) {
    if (n <= 1)
        return n;
    return down(n - 1) + down(n - 2) + down(n - 3);
}
int main() {
    cout << down(6) << endl;
    return 0;
}

A

$6$

B

$13$

C

$20$

D

无法正常结束。

第 15 题

下面的程序使用邻接矩阵表达的带权无向图，则从顶点 0 到顶点 3 的最短距离为（）。

int weight[4][4] = {
    {0, 2, 5, 8},
    {2, 0, 1, 7},
    {5, 1, 0, 4},
    {8, 7, 4, 0}
};

A

$6$

B

$7$

C

$8$

D

$9$

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