GESP 七级 · 2024 真题

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

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

01int pos[8];
02void queen(int n) {
03    for (int i = 0; i < 8; i++) {
04        pos[n] = i;
05        bool attacked = false;
06        for (int j = 0; j < n; j++)
07            if (pos[n] == pos[j] || pos[n] + n == pos[j] + j || pos[n] - n == pos[j] - j) {
08                attacked = true;
09                break;
10            }
11        if (attacked)
12            continue;
13        if (n == 7) {
14            return;
15        } else {
16            queen(n + 1);
17        }
18    }
19}

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

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

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

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

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

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

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

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

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

01#include <algorithm>
02using namespace std;
03struct activity {
04    int id, start, end;
05};
06bool compare(activity a, activity b) {
07    return a.end < b.end;
08}
09int schedule(int n, activity * p) {
10    sort(p, p + n, compare);
11    int cnt = 0, end = 0;
12    for (int i = 0; i < n; i++) {
13        if (p[i].start >= end) {
14            end = p[i].end;
15            cnt++;
16        }
17    }
18    return cnt;
19}

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

01int search(int n, int * p, int target) {
02    int low = 0, high = n;
03    while (low <= high) {
04        int middle = (low + high) / 2;
05        if (target == p[middle]) {
06            return middle;
07        } else if (target > p[middle]) {
08            low = middle + 1;
09        } else {
10            high = middle - 1;
11        }
12    }
13    return -1;
14}

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

01int count_triple(int n) {
02    int cnt = 0;
03    for (int a = 1; a <= n; a++)
04        for (int b = a; a + b <= n; b++)
05            for (int c = b; a + b + c <= n; c++)
06                if (a * a + b * b == c * c)
07                    cnt++;
08    return cnt;
09}

下面程序的输出为（ ）。

01#include <iostream>
02using namespace std;
03int down(int n) {
04    if (n <= 1)
05        return n;
06    return down(n - 1) + down(n - 2) + down(n - 3);
07}
08int main() {
09    cout << down(6) << endl;
10    return 0;
11}

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

01int weight[4][4] = {
02    {0, 2, 5, 8},
03    {2, 0, 1, 7},
04    {5, 1, 0, 4},
05    {8, 7, 4, 0}};

祖冲之是南北朝时期杰出的数学家、天文学家，其主要贡献在数学、天文历法和机械制造三方面。他首次将“圆周率”精算到小数第七位，即在 $3.1415926$ 和 $3.1415927$ 之间。（ ）

C++ 语言中，表达式 2 ^ 3 的结果类型为 int，值为 $8$。（ ）

一棵有 N 个节点的完全二叉树，则树的深度为 $\lfloor\log_2(N)\rfloor+1$。（ ）

能用动态规划解决的问题，一般也可以用贪心法解决，但动态规划的效率更高。（ ）

使用 math.h 或 cmath 头文件中的正弦函数，表达式 sin(30) 的结果类型为 double、值约为 $0.5$。（ ）

要求出简单有向图中从顶点 A 到顶点 B 的最短路径，在深度优先搜索和广度优先搜索中选择，广度优先更适合。（ ）

某 N 个表项的哈希表，在发生哈希函数冲突时采用向后寻找空位的方法解决冲突。其查找操作的平均时间复杂度为 $O(1)$，即使当该哈希表的每个表项都有元素时，查找操作的平均时间复杂度仍为 $O(1)$。（ ）

动态规划有递推实现和递归实现，有时两种实现的时间复杂度不同。（ ）

围棋游戏中，判断落下一枚棋子后是否会提掉对方的子，可以使用泛洪算法来实现。（ ）

类 B 继承了抽象类 A，但未实现类 A 中的纯虚函数 f，则类 B 不能直接实例化。（ ）