GESP 八级 · 2024 真题

下⾯关于C++类和对象的说法，错误的是（ ）。

对于⼀个具有 $n$ 个顶点的⽆向图，若采⽤邻接矩阵表⽰，则该矩阵的⼤⼩为（ ）。

设有编号为 $A、B、C、D、E$ 的 $5$ 个球和编号为 $A、B、C、D、E$ 的 $5$ 个盒⼦。现将这 $5$ 个球投⼊ $5$ 个盒⼦，要求每个盒⼦放⼀个球，并且恰好有两个球的编号与盒⼦编号相同，问有多少种不同的⽅法？（ ）。

从甲地到⼄地，可以乘⾼铁，也可以乘汽车，还可以乘轮船。⼀天中，⾼铁有 $10$ 班，汽车有 $5$ 班，轮船有 $2$ 班。那么⼀天中乘坐这些交通⼯具从甲地到⼄地共有多少种不同的⾛法？（ ）。

个结点的⼆叉树，执⾏释放全部结点操作的时间复杂度是（ ）。

在⼀个单位圆上，随机分布 $n$ 个点，求这 $n$ 个点能被⼀个单位半圆周全部覆盖的概率（ ）。

下⾯ pailie 函数是⼀个实现排列的程序，横线处可以填⼊的是（ ）。

01#include <iostream>
02using namespace std;
03int sum = 0;
04void swap(int & a, int & b) {
05    int temp = a;
06    a = b;
07    b = temp;
08}
09void pailie(int begin, int end, int a[]) {
10    if (begin == end) {
11        for (int i = 0; i < end; i++)
12            cout << a[i];
13        cout << endl;
14    }
15    for (int i = begin; i < end; i++) {
16        ___________  // 在此处填入选项
17    }
18}

已知 pailie 函数是实现排列的程序（代码如下），主函数为如下的程序，则最后的排列数是多少个？（ ）。

01#include <iostream>
02using namespace std;
03int sum = 0;
04void swap(int & a, int & b) {
05    int temp = a;
06    a = b;
07    b = temp;
08}
09void pailie(int begin, int end, int a[]) {
10    if (begin == end) {
11        for (int i = 0; i < end; i++)
12            cout << a[i];
13        cout << endl;
14    }
15    for (int i = begin; i < end; i++) {
16        swap(a[begin], a[i]);
17        pailie(begin + 1, end, a);
18        swap(a[i], a[begin]);
19    }
20}

主函数如下：

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

下列程序实现了输出杨辉三角形，代码中横线部分应该填⼊的是（ ）。

01#include <iostream>
02using namespace std;
03#define N 35
04int a[N][N];
05int main() {
06    int n;
07    cin >> n;
08    for (int i = 1; i <= n; i++)
09        for (int j = 1; j <= i; j++) {
10            if (j == 1 || j == i)
11                a[i][j] = 1;
12            else
13                __________ // 在此处填入选项
14        }
15    for (int i = 1; i <= n; i++) {
16        for (int j = 1; j <= i; j++)
17            cout << a[i][j];
18        cout<<endl;
19    }
20    return 0;
21}

下⾯最⼩⽣成树的 $Kruskal$ 算法程序中，横线处应该填⼊的是（ ）。

01#include <iostream>
02#include <vector>
03#include <algorithm>
04using namespace std;
05struct Edge {
06    int u, v, weight;
07    bool operator <(const Edge & other) const {
08        return weight < other.weight;
09    }
10};
11int findParent(int vertex, vector<int> & parent) {
12    if (parent[vertex] == -1)
13        return vertex;
14    return parent[vertex] = findParent(parent[vertex], parent);
15}
16int main() {
17    int n, m;
18    cin >> n >> m; // n: 顶点数，m: 边数
19    vector<Edge> edges(m);
20    vector<int> parent(n, -1);
21    int totalWeight = 0;
22    for (int i = 0; i < m; i++)
23        cin >> edges[i].u >> edges[i].v >> edges[i].weight;
24    sort(edges.begin(), edges.end());
25
26    for (const auto & edge : edges) {
27        int uParent = findParent(edge.u, parent);
28        int vParent = findParent(edge.v, parent);
29        if (________) { // 在此处填入选项
30            parent[uParent] = vParent;
31            totalWeight += edge.weight;
32        }
33    }
34}

下⾯ $Prim$ 算法程序中，横线处应该填⼊的是（ ）。

01#include <iostream>
02#include <vector>
03#include <algorithm>
04using namespace std;
05int prim(vector<vector<int>> & graph, int n) {
06    vector<int> key(n, INT_MAX);
07    vector<int> parent(n, -1);
08    key[0] = 0;
09    for (int i = 0; i < n; i++) {
10        int u = min_element(key.begin(), key.end()) - key.begin();
11        if (key[u] == INT_MAX)
12            break;
13        for (int v = 0; v < n; v++) {
14            if (_____________________ ) { // 在此处填入选项
15                key[v] = graph[u][v];
16                parent[v] = u;
17            }
18        }
19    }
20    int sum = 0;
21    for (int i = 0; i < n; i++) {
22        if (parent[i] != -1) {
23            cout << "Edge: " << parent[i] << " - " << i << " Weight: " << key[i] << endl;
24            sum += key[i];
25        }
26    }
27    return sum;
28}
29int main() {
30    int n, m;
31    cin >> n >> m;
32    vector<vector<int>> graph(n, vector<int>(n, 0));
33    for (int i = 0; i < m; i++) {
34        int u, v, w;
35        cin >> u >> v >> w;
36        graph[u][v] = w;
37        graph[v][u] = w;
38    }
39    int result = prim(graph, n);
40    cout << "Total weight of the minimum spanning tree: " << result << endl;
41    return 0;
42}

下列 $Dijkstra$ 算法中，横线处应该填⼊的是（ ）。

01#include <iostream>
02using namespace std;
03
04#define N 100
05int n, e, s;
06const int inf = 0x7ffffff;
07int dis[N + 1];
08int cheak[N + 1];
09int graph[N + 1][N + 1];
10int main() {
11    for (int i = 1; i <= N; i++)
12        dis[i] = inf;
13    cin >> n >> e;
14    for (int i = 1; i <= e; i++) {
15        int a, b, c;
16        cin >> a >> b >> c;
17        graph[a][b] = c;
18    }
19    cin >> s;
20    dis[s] = 0;
21    for (int i = 1; i <= n; i++) {
22        int minn = inf, minx;
23        for (int j = 1; j <= n; j++) {
24            if (_______) { // 在此处填入选项
25                minn = dis[j];
26                minx = j;
27            }
28        }
29        cheak[minx] = 1;
30        for (int j = 1; j <= n; j++) {
31            if (graph[minx][j] > 0) {
32                if (minn + graph[minx][j] < dis[j]) {
33                    dis[j] = minn + graph[minx][j];
34                }
35            }
36        }
37    }
38}

下⾯ $Floyd$ 算法中，横线处应该填⼊的是（ ）。

01#include <iostream>
02using namespace std;
03
04#define N 21
05#define INF 99999999
06int map[N][N];
07int main() {
08    int n, m, t1, t2, t3;
09    cin >> n >> m;
10    for (int i = 1; i <= n; i++) {
11        for (int j = 1; j <= n; j++) {
12            if (i == j)
13                map[i][j] = 0;
14            else
15                map[i][j] = INF;
16        }
17    }
18    for (int i = 1; i <= m; i++) {
19        cin >> t1 >> t2 >> t3;
20        map[t1][t2] = t3;
21    }
22    for (int k = 1; k <= n; k++)
23        for (int i = 1; i <= n; i++)
24            for (int j = 1; j <= n; j++)
25                if (_______) // 在此处填入选项
26                    map[i][j] = map[i][k] + map[k][j];
27    for (int i = 1; i <= n; i++) {
28        for (int j = 1; j <= n; j++) {
29            cout.width(4);
30            cout << map[i][j];
31        }
32        cout << endl;
33    }
34}

下⾯程序的 Merge_Sort 函数时间复杂度为（ ）。

01void Merge(int a[], int left, int mid, int right) {
02    int temp[right - left + 1];
03    int i = left;
04    int j = mid + 1;
05    int k = 0;
06    while (i <= mid && j <= right) {
07        if (a[i] < a[j])
08            temp[k++] = a[i++];
09        else
10            temp[k++] = a[j++];
11    }
12    while (i <= mid)
13        temp[k++] = a[i++];
14    while (j <= right)
15        temp[k++] = a[j++];
16    for (int m = left, n = 0; m <= right; m++, n++)
17        a[m] = temp[n];
18}
19void Merge_Sort(int a[], int left, int right) {
20    if (left == right)
21        return;
22    int mid = (left + right) / 2;
23    Merge_Sort(a, left, mid);
24    Merge_Sort(a, mid + 1, right);
25    Merge(a, left, mid, right);
26}

下⾯ $fibonacci$ 函数的时间复杂度为（ ）。

01int fibonacci(int n) {
02    if (n <= 1)
03        return n;
04    else
05        return fibonacci(n - 1) + fibonacci(n - 2);
06}

表达式 '3' & 1 的结果为 '1' 。

在C++语⾔中，变量定义必须在某⼀个函数定义之内。

冒泡排序⼀般是不稳定的。

⼆叉排序树的查找操作的平均时间复杂度，正⽐于树的⾼度。

使⽤ $math.h$ 或 $cmath$ 头⽂件中的余弦函数，表达式 cos(60) 的结果类型为 double 、值约为 $0.5$ 。

你有三种硬币，分别⾯值 $2$ 元、$5$ 元和 $7$ 元，每种硬币都有⾜够多。买⼀本书需要 $27$ 元，则最少可以⽤ $5$ 个硬币组合起来正好付清，且不需要对⽅找钱。

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

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

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

诚实国公民只说实话，说谎国公民只说谎话。你来到⼀处分岔⼝，⼀条通往诚实国，⼀条通往说谎国，但不知是哪⼀条通往哪⾥。正在为难之际，⾛来两位路⼈，他们都⾃称是诚实国公民，都说对⽅是说谎国公民。你想去说谎国，可以这样问其中⼀位路⼈：“我要去说谎国，如果我去问另⼀个路⼈，他会指向哪⼀条路？”。