GESP C++ 八 级 2025年9月真题（180 分钟，总分 100 分）

单选题（共 15 题，每题 2 分，共 30 分）

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

{{ select(1) }}

• 16
• 10
• 9
• 7

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

{{ select(2) }}

• 1820
• 70
• 24
• 16

3. 下列关于C++类的说法，错误的是？

{{ select(3) }}

• 派生类对象占用的内存总是不小于基类对象。
• 派生类可以不实现基类的虚函数。
• 如果一个类包含纯虚函数，则它不能包含成员变量。
• 如果一个类包含纯虚函数，则不能用它定义对象。

4. 下列关于树和图的说法，错误的是？

{{ select(4) }}

• 每个连通图都存在生成树。
• 每个存在生成树的有向图，都一定是强连通的。
• 保留树的所有节点，并把树的每个节点指向其父节点，则可以将树转换为一个有向弱连通图。
• 保留树的所有节点，并把树的每个节点指向其子节点，则可以将树转换为一个有向无环图。

5. 一对夫妻生男生女的概率相同。这对夫妻希望儿女双全。请问这对夫妻生下三个孩子时，实现儿女双全的概率是多少？

{{ select(5) }}

• $\frac{1}{4}$
• $\frac{1}{2}$
• $\frac{3}{4}$
• $\frac{7}{8}$

6. 二项式 (x+y)⁶ 的展开式中 x²y⁴ 项的系数是？

{{ select(6) }}

• 720
• 120
• 20
• 15

7. 对一个包含 V 个顶点、E 条边的图，执行广度优先搜索，其最优时间复杂度是？

{{ select(7) }}

• O(V)
• O(V+E)
• O(V²)
• O(E)

8. 以下关于贪心法和动态规划的说法中，错误的是？

{{ select(8) }}

• 动态规划能解决大部分多阶段决策问题。
• 对特定的问题，贪心法不一定适用。
• 当特定的问题适用贪心法时，通常比动态规划的时间复杂度更低。
• 对很多问题，递推实现和递归实现动态规划方法的时间复杂度相当。

9. 下面程序的输出为？

#include <iostream>
using namespace std;
int main()
{
    int N = 15, cnt = 0;
    for (int x = 1; x + x + x <= N; x++)
        for (int y = x; x + y + y <= N; y++)
            for (int z = y; x + y + z <= N; z++)
                cnt++;
    cout << cnt << endl;
    return 0;
}

{{ select(9) }}

• 45
• 102
• 174
• 3375

10. 下面程序的时间复杂度为？

int primes[MAXP], num = 0;
bool isPrime[MAXN] = {false};
void sieve()
{
    for (int n = 2; n <= MAXN; n++)
    {
        if (!isPrime[n])
            primes[num++] = n;
        for (int i = 0; i < num && n * primes[i] <= MAXN; i++)
        {
            isPrime[n * primes[i]] = true;
            if (n % primes[i] == 0)
                break;
        }
    }
}

{{ select(10) }}

• O( n log n)
• O( n log log n)
• O( n )
• O( log n )

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

typedef struct Edge
{
    int in, out;
    // 从下标in顶点到下标out顶点的边
    int len;
    // 边长度
    struct Edge *next;
} Edge;
// v：顶点个数，graph：出边邻接表，start：起点下标，dis：输出每个顶点的最短距离
void dijkstra(int v, Edge *graph[], int start, int *dis)
{
    const int MAX_DIS = 0x7fffff;
    for (int i = 0; i < v; i++)
        dis[i] = MAX_DIS;
    dis[start] = 0;
    int *visited = new int[v];
    for (int i = 0; i < v; i++)
        visited[i] = 0;
    visited[start] = 1;
    for (int t = 0;; t++)
    {
        int min = MAX_DIS, minv = -1;
        for (int i = 0; i < v; i++)
        {
            if (visited[i] == 0 && min > dis[i])
            {
                min = dis[i];
                minv = i;
            }
        }
        if (minv < 0)
            break;
        visited[minv] = 1;
        for (Edge *e = graph[minv]; e != NULL; e = e->next)
            if (dis[e->out] > e->len)
                dis[e->out] = e->len;
    }
    delete[] visited;
}

{{ select(11) }}

• O( v² )
• O( v log v + e )
• O( (v+e) log v )
• O( v+e )

12. 下面count_triple函数的时间复杂度为?

int gcd(int m, int n)
{
    if (m == 0)
        return n;
    return gcd(n % m, m);
}
int count_triple(int n)
{
    int cnt = 0;
    for (int v = 1; v * v * 4 <= n; v++)
        for (int u = v + 1; u * (u + v) * 2 <= n; u += 2)
            if (gcd(u, v) == 1)
            {
                int a = u * u - v * v;
                int b = u * v * 2;
                int c = u * u + v * v;
                cnt += n / (a + b + c);
            }
    return cnt;
}

{{ select(12) }}

• O( n² )
• O( n² log n )
• O( n )
• O( n log n )

13. 下面merge_sort函数试图实现归并排序算法，横线处应该填入的是？

#include <vector>
using namespace std;
void merge_sort(vector<int> &arr, int left, int right)
{
    if (right - left <= 1)
        return;
    int mid = (left + right) / 2;
    merge_sort(________); // 在此处填入选项
    merge_sort(________); // 在此处填入选项
    vector<int> temp(right - left);
    int i = left, j = mid, k = 0;
    while (i < mid && j < right)
        if (arr[i] <= arr[j])
            temp[k++] = arr[i++];
        else
            temp[k++] = arr[j++];
    while (i < mid)
        temp[k++] = arr[i++];
    while (j < right)
        temp[k++] = arr[j++];
    for (i = left, k = 0; i < right; ++i, ++k)
        arr[i] = temp[k];
}

{{ select(13) }}

• arr, left, mid
arr, mid, right
• arr, left, mid + 1
arr, mid + 1, right
• arr, left, mid
arr, mid + 1, right
• arr, left, mid + 1
arr, mid + 1, right + 1

14. 下面Prim算法程序中，横线处应该填入的是？

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int prim(vector<vector<int>> &graph, int n)
{
    vector<int> key(n, INT_MAX);
    vector<int> parent(n, -1);
    key[0] = 0;
    for (int i = 0; i < n; i++)
    {
        int u = min_element(key.begin(), key.end()) - key.begin();
        if (key[u] == INT_MAX)
            break;
        for (int v = 0; v < n; v++)
        {
            if (__________)
            { // 在此处填入选项
                key[v] = graph[u][v];
                parent[v] = u;
            }
        }
    }
    int sum = 0;
    for (int i = 0; i < n; i++)
    {
        if (parent[i] != -1)
        {
            cout << "Edge: " << parent[i] << " - " << i << " Weight: " << key[i] << endl;
            sum += key[i];
        }
    }
    return sum;
}
int main()
{
    int n, m;
    cin >> n >> m;
    vector<vector<int>> graph(n, vector<int>(n, 0));
    for (int i = 0; i < m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        graph[u][v] = w;
        graph[v][u] = w;
    }
    int result = prim(graph, n);
    cout << "Total weight of the minimum spanning tree: " << result << endl;
    return 0;
}

{{ select(14) }}

• graph[u][v] >= 0 && key[v] > graph[u][v]
• graph[u][v] <= 0 && key[v] > graph[u][v]
• graph[u][v] == 0 && key[v] > graph[u][v]
• graph[u][v] != 0 && key[v] > graph[u][v]

15. 下面的程序使用出边邻接表表达的带权无向图，则从顶点0到顶点3的最短距离为？

#include <vector>
using namespace std;
class Edge
{
public:
    int dest;
    int weight;
    Edge(int d, int w) : dest(d), weight(w) {}
};
class Graph
{
private:
    int num_vertex;
    vector<vector<Edge>> vve;

public:
    Graph(int v) : num_vertex(v), vve(v) {}
    void addEdge(int s, int d, int w)
    {
        vve[s].emplace_back(d, w);
        vve[d].emplace_back(s, w)
    }
};
int main()
{
    Graph g(4);
    g.addEdge(0, 1, 8);
    g.addEdge(0, 2, 5);
    g.addEdge(1, 2, 1);
    g.addEdge(1, 3, 3);
    g.addEdge(2, 3, 7);
    return 0;
}

{{ select(15) }}

• 12
• 11
• 10
• 9