GESP 八级 · 2025 真题

⼩杨想点⼀杯奶茶外卖，但还差$5$元起送。于是，⼩杨决定点⼀些⼩料。可选的⼩料包括：珍珠$1$元、椰果2
元、奶冻$3$元、奶盖$4$元。每种⼩料最多点1份。请问共有多少种满⾜起送条件的点⼩料⽅案？（ ）。

⼩杨和⼩刘是好朋友，她们在逛商场时发现新设置的⼤头贴⾃拍机，于是决定⼀起拍⼀组照⽚。⼀组照⽚包
括$4$张，这$4$张照⽚没有顺序区分。拍每张照⽚时，可以选择有相框或⽆相框、两⼈可以分别选择有头饰或⽆头饰、还可以从$2$种位置（⼩杨在左，或⼩刘在左）中选出⼀种。她们不希望⼀组照⽚中出现完全相同的相框、头饰、位置的组合。请问⼀组照⽚共有多少种不同的⽅案？（ ）。

下列关于C++类的说法，错误的是（ ）。

下列关于树和图的说法，错误的是（ ）。

⼀对夫妻⽣男⽣⼥的概率相同。这对夫妻希望⼉⼥双全。请问这对夫妻⽣下三个孩⼦时，实现⼉⼥双全的概
率是多少？（ ）。

⼆项式 $(x+y)^6$ 的展开式中 $x^2y^4$ 项的系数是（ ）。

对⼀个包含 $V$ 个顶点、$E$ 条边的图，执⾏⼴度优先搜索，其最优时间复杂度是（ ）。

以下关于贪⼼法和动态规划的说法中，错误的是（ ）。

下⾯程序的输出为（ ）。

01++
02#include <iostream>
03using namespace std;
04int main() {
05    int N = 15, cnt = 0;
06    for (int x = 1; x + x + x <= N; x++)
07        for (int y = x; x + y + y <= N; y++)
08            for (int z = y; x + y + z <= N; z++)
09                cnt++;
10    cout << cnt << endl;
11    return 0;
12}

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

01++
02int primes[MAXP], num = 0;
03bool isPrime[MAXN] = {false};
04void sieve() {
05    for (int n = 2; n <= MAXN; n++) {
06        if (!isPrime[n])
07            primes[num++] = n;
08        for (int i = 0; i < num && n * primes[i] <= MAXN; i++) {
09            isPrime[n * primes[i]] = true;
10            if (n % primes[i] == 0)
11                break;
12        }
13    }
14}

下列 Dijkstra 算法，假设图 $graph$ 中顶点数 $v$ 、边数 $e$，则程序的时间复杂度为（ ）。

01++
02typedef struct Edge {
03    int in, out;    // 从下标in顶点到下标out顶点的边
04    int len;        // 边长度
05    struct Edge * next;
06} Edge;
07// v：顶点个数，graph：出边邻接表，start：起点下标，dis：输出每个顶点的最短距离
08void dijkstra(int v, Edge * graph[], int start, int * dis) {
09    const int MAX_DIS = 0x7fffff;
10    for (int i = 0; i < v; i++)
11        dis[i] = MAX_DIS;
12    dis[start] = 0;
13    int * visited = new int[v];
14    for (int i = 0; i < v; i++)
15        visited[i] = 0;
16    visited[start] = 1;
17    for (int t = 0; ; t++) {
18        int min = MAX_DIS, minv = -1;
19        for (int i = 0; i < v; i++) {
20            if (visited[i] == 0 && min > dis[i]) {
21                min = dis[i];
22                minv = i;
23            }
24        }
25        if (minv < 0)
26            break;
27        visited[minv] = 1;
28        for (Edge * e = graph[minv]; e != NULL; e = e->next)
29            if (dis[e->out] > e->len)
30                dis[e->out] = e->len;
31    }
32    delete[] visited;
33}

下⾯ count_triple 函数的时间复杂度为( )。

01++
02int gcd(int m, int n) {
03    if (m == 0) return n;
04    return gcd(n % m, m);
05 }
06 int count_triple(int n) {
07    int cnt = 0;
08    for (int v = 1; v * v * 4 <= n; v++)
09        for (int u = v + 1; u * (u + v) * 2 <= n; u += 2)
10            if (gcd(u, v) == 1) {
11                int a = u * u - v * v;
12                int b = u * v * 2;
13                int c = u * u + v * v;
14                cnt += n / (a + b + c);
15            }
16    return cnt;
17 }

下⾯ merge_sort 函数试图实现归并排序算法，横线处应该填⼊的是（ ）。

01++
02#include <vector>
03using namespace std;
04void merge_sort(vector<int> & arr, int left, int right) {
05    if (right - left <= 1)
06        return;
07    int mid = (left + right) / 2;
08    merge_sort(________); // 在此处填入选项
09    merge_sort(________); // 在此处填入选项
10    vector<int> temp(right - left);
11    int i = left, j = mid, k = 0;
12    while (i < mid && j < right)
13        if (arr[i] <= arr[j])
14            temp[k++] = arr[i++];
15        else
16            temp[k++] = arr[j++];
17    while (i < mid)
18        temp[k++] = arr[i++];
19    while (j < right)
20        temp[k++] = arr[j++];
21    for (i = left, k = 0; i < right; ++i, ++k)
22        arr[i] = temp[k];
23}

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

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

下⾯的程序使⽤出边邻接表表达的带权⽆向图，则从顶点 $0$ 到顶点 $3$ 的最短距离为（ ）。

01++
02#include <vector>
03using namespace std;
04class Edge {
05public:
06    int dest;
07    int weight;
08    Edge(int d, int w) : dest(d), weight(w) {}
09};
10class Graph {
11private:
12    int num_vertex;
13    vector<vector<Edge>> vve;
14public:
15    Graph(int v) : num_vertex(v), vve(v) {}
16    void addEdge(int s, int d, int w) {
17        vve[s].emplace_back(d, w);
18        vve[d].emplace_back(s, w)
19    }
20};
21int main() {
22    Graph g(4);
23    g.addEdge(0, 1, 8);
24    g.addEdge(0, 2, 5);
25    g.addEdge(1, 2, 1);
26    g.addEdge(1, 3, 3);
27    g.addEdge(2, 3, 7);
28    return 0;
29}

C++语⾔中，表达式 '9' ^ 3 的结果值为 '999' 。

下列C++语⾔代码，能够安全地输出 arr[5] 的值。

01++
02int n = 5;
03int arr[n] = {1, 2, 3}; 
04std::cout << arr[5];

对 $n$ 个元素的数组进⾏排序，最差情况的时间复杂度为 $O(n)$ 。

有 $4$ 个红球、$3$ 个蓝球和 $2$ 个绿球排成⼀排（相同⾊球视为完全相同），则不同的排列⽅案数为 $1260$ 种 。

使⽤ math.h 或 cmath 头⽂件中的函数，对于 int 类型的变量 $x$ ，表达式 fabs(x) 和 sqrt(x * x) 的结果总是近似相等的。

运算符重载是C++语⾔静态多态的⼀种典型体现，⽽使⽤C语⾔则⽆法实现运算符重载。

存在⼀个简单⽆向图满⾜：顶点数为 $6$，边数为 $8$ ，$6$ 个顶点的度数分别为 3、3、3、3、2、2。

已知两个 double 类型的变量 r 和 theta 分别表⽰⼀个扇形的圆半径及圆⼼角（弧度），则扇形的周长可
以通过表达式 (2 + theta) * r 求得。

Dijkstra 算法的时间复杂度为 $O(V^2)$ ，其中 $V$ 为图中顶点的数量。

从 $32$ 名学⽣中选出 $2$ ⼈分别担任男⽣班长和⼥⽣班长（男⽣班长必须是男⽣，⼥⽣班长必须是⼥⽣），则共
有 $C(32,2)/2$ 种不同的选法。