2024年3月 GESP C++ 7级

下列关于排序的说法，正确的是( )。

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

下面的程序属于哪种算法( )。

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);
        }
    }
}

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

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

一棵有 $n$ 个节点的完全二叉树，则树的深度为 ⌊log⁡2n⌋+1\lfloor \log_2 n \rfloor + 1⌊log2​n⌋+1。( )

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

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

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

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

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

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

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

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

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

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

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

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

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

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

下面 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;
}

下面 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;
}

下面 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;
}

下面程序的输出为（ ）。

#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;
}

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

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

试题名称：交流问题

时间限制：1.0 s | 内存限制：512.0 MB

题目描述

来自两所学校 $A$、$B$ 的 $n$ 名同学聚在一起相互交流。为了方便起见，我们把这些同学从 $1$ 至 $n$ 编号。他们共进行了 $m$ 次交流，第 $i$ 次交流中，编号为 ui,viu_i, v_iui​,vi​ 的同学相互探讨了他们感兴趣的话题，并结交成为了新的朋友。

由于这次交流会的目的是促进两校友谊，因此只有不同学校的同学之间会交流。同校同学并不会互相交流。

作为 $A$ 校顾问，你对 $B$ 校的规模非常感兴趣，你希望求出 $B$ 校至少有几名同学、至多有几名同学。

输入格式

第一行两个正整数，表示同学的人数 $n$、交流的次数 $m$。
接下来 $m$ 行，每行两个整数 ui,viu_i, v_iui​,vi​，表示一次交流。

输出格式

输出一行两个整数，用单个空格隔开，分别表示 $B$ 校至少有几名同学、至多有几名同学。

样例输入 #1

4 3
1 2
2 3
4 2

样例输出 #1

1 3

样例输入 #2

7 5
1 2
2 3
4 2
5 6
6 7

样例输出 #2

2 5

说明/提示

数据规模与约定

• 对 $30\%$ 的数据，保证 $n\le 17$，$m\le 50$。
• 对 $60\%$ 的数据，保证 $n\le 500$，$m\le 2000$。
• 对全部的测试数据，保证 1≤ui,vi≤n≤1051 \leq u_i, v_i \leq n \leq 10^51≤ui​,vi​≤n≤105，1≤m≤2×1051 \leq m \leq 2\times 10^51≤m≤2×105，输入是合法的，即交流一定是跨校开展的。

试题名称：俄罗斯方块

时间限制：1.0 s | 内存限制：512.0 MB

题目描述

小杨同学用不同种类的俄罗斯方块填满了一个大小为 $n\times m$ 的网格图。

网格图由 $n\times m$ 个带颜色方块构成。小杨同学现在将这个网格图交给了你，请你计算出网格图中俄罗斯方块的种类数。
如果两个同色方块是四连通（即上下左右四个相邻的位置）的，则称两个同色方块直接连通；若两个同色方块同时与另一个同色方块直接或间接连通，则称两个同色方块间接连通。一个俄罗斯方块由一个方块和所有与其直接或间接连接的同色方块组成。定义两个俄罗斯方块的种类相同当且仅当通过平移其中一个俄罗斯方块可以和另一个俄罗斯方块重合；如果两个俄罗斯方块颜色不同，仍然视为同一种俄罗斯方块。

例如，在如下情况中，方块 $1$ 和方块 $2$ 是同一种俄罗斯方块，而方块 $1$ 和方块 $3$ 不是同一种俄罗斯方块。

输入格式

第一行包含两个正整数 $n$ 和 $m$，表示网格图的大小。
对于之后的 $n$ 行，第 $i$ 行包含 $m$ 个正整数 ai1,ai2,…aima_{i1}, a_{i2}, \dots a_{im}ai1​,ai2​,…aim​，表示该行 $m$ 个方块的颜色。

输出格式

输出一行一个整数表示答案。

样例输入 #1

5 6
1 2 3 4 4 5
1 2 3 3 4 5
1 2 2 3 4 5
1 6 6 7 7 8
6 6 7 7 8 8

样例输出 #1

7

说明/提示

对全部的测试数据，保证 $1\le n,m\le 500$，1≤ai,j≤n×m1 \leq a_{i,j} \leq n \times m1≤ai,j​≤n×m。