GESP 认证 8级2025-06

2025年6月 GESP C++ 8级

题量

27 题

客观题

25 题

建议时长

60 分钟

卷面总分

100 分

2025年6月 GESP C++ 8级认证考试真题（含编程操作题部分）

开始整卷模拟计时作答 · 交卷即时判分 · 错题自动进错题本（需登录）含 2 道编程大题：在线只判客观题，编程题请自行前往洛谷等 OJ 提交验证

// questions

题目预览

单选题2 分

一间的机房要安排 $6$ 名同学进行上机考试，座位共 $2$ 行 $3$ 列。考虑到在座位上很容易看到同一行的左右两侧的屏幕，安排中间一列的同学做 A 卷，左右两列的同学做 B 卷。请问共有多少种排座位的方案？（）。

$720$

$90$

$48$

$15$

单选题2 分

⼜到了毕业季，学长学姐们都在开心地拍毕业照。现在有 $3$ 位学长、 $3$ 位学姐希望排成一排拍照，要求男生不相邻、⼥生不相邻。请问共有多少种拍照方案？（）。

$720$

$72$

$36$

$2$

单选题2 分

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

通过语句 const int x = 5; 定义了一个对象 $x$ 。

通过语句 std::string t = "12345"; 定义了一个对象 $t$ 。

通过语句 void (*fp)() = NULL; 定义了一个对象 $f p$ 。

通过语句 class MyClass; 定义了一个类 MyClass 。

单选题2 分

关于生成树的说法，错误的是（）。

一个无向连通图，一定有生成树。

$n$ 个顶点的无向图，其生成树要么不存在，要么一定包含 $n - 1$ 条边。

$n$ 个顶点、 $m$ 条边的无向图，不可能有多颗生成树。

$n$ 个顶点、 $n - 1$ 条边的无向图，它本身就是自己的生成树。

单选题2 分

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

单选题2 分

已定义变量 double a, b;，下列哪个表达式可以用来判断一元二次方程是否有实根？（）。

4 * b - a * a < 0

4 * b <= a * a

a * a - 4 * b

b * 4 - a * a

单选题2 分

个结点的二叉树，执行广度优先搜索的平均时间复杂度是（）。

单选题2 分

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

动态规划方法通常能够列出递推公式。

动态规划方法的时间复杂度通常为状态的个数。

动态规划方法有递推和递归两种实现形式。

对很多问题，递推实现和递归实现动态规划方法的时间复杂度相当。

单选题2 分

下面的 sum_digit 函数试图求出从 $1$ 到 $n$ （包含 $1$ 和 $n$ ）的数中，包含数字 $d$ 的个数。该函数的时间复杂度为（）。

#include <string>
int count_digit(int n, char d) {
    int cnt = 0;
    std::string s = std::to_string(n);
    for (int i = 0; i < s.length(); i++)
        if (s[i] == d)
            cnt++;
    return cnt;
}
int sum_digit(int n, char d) {
    int sum = 0;
    for (int i = 1; i <= n; i++)
        sum += count_digit(i, d);
    return sum;
}

单选题2 分

下面程序的输出为（）。

#include <iostream>
const int N = 10;
int ch[N][N][N];
int main() {
    for (int x = 0; x < N; x++)
        for (int y = 0; y < N; y++)
            for (int z = 0; z < N; z++)
                if (x == 0 && y == 0 && z == 0)
                    ch[x][y][z] = 1;
                else {
                    if (x > 0)
                        ch[x][y][z] += ch[x - 1][y][z];
                    if (y > 0)
                        ch[x][y][z] += ch[x][y - 1][z];
                    if (z > 0)
                        ch[x][y][z] += ch[x][y][z - 1];
                }
    std::cout << ch[1][2][3] << std::endl;
    return 0;
}

$60$

$20$

$15$

$10$

单选题2 分

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

int gcd(int a, int b) {
    if (a == 0)
        return b;
    return gcd(b % a, a);
}
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;
}

单选题2 分

下面 quick_sort 函数试图实现快速排序算法，两处横线处分别应该填入的是（）。

void swap(int & a, int & b) {
    int temp = a; a = b; b = temp;
}
int partition(int a[], int l, int r) {
    int pivot = a[l], i = l + 1, j = r;
    while (i <= j) {
        while (i <= j && a[j] >= pivot)
            j--;
        while (i <= j && a[i] <= pivot)
            i++;
        if (i < j)
            swap(a[i], a[j]);
    }
    ________; // 在此处填入选项
    return ________; // 在此处填入选项
}
void quick_sort(int a[], int l, int r) {
    if (l < r) {
        int pivot = partition(a, l, r);
        quick_sort(a, l, pivot - 1);
        quick_sort(a, pivot + 1, r);
    }
}

swap(a[l], a[i])
i

swap(a[l], a[j])
i

swap(a[l], a[i])
j

swap(a[l], a[j])
j

单选题2 分

下面 LIS 函数试图求出最长上升子序列的长度，横线处应该填入的是（）。

int max(int a, int b) {
    return (a > b) ? a : b;
}
int LIS(vector<int> & nums) {
    int n = nums.size();
    if (n == 0)
        return 0;
    vector<int> dp(n, 1);
    int maxLen = 1;
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++)
            if (nums[j] < nums[i])
                ________; // 在此处填入选项
        maxLen = max(maxLen, dp[i]);
    }
    return maxLen;
}

dp[j] = max(dp[j] + 1, dp[i])

dp[j] = max(dp[j], dp[i] + 1)

dp[i] = max(dp[i] + 1, dp[j])

dp[i] = max(dp[i], dp[j] + 1)

单选题2 分

下面 LIS 函数试图求出最长上升子序列的长度，其时间复杂度为（）。

#define INT_MIN (-1000)
int LIS(vector<int> & nums) {
    int n = nums.size();
    vector<int> tail;
    tail.push_back(INT_MIN);
    for (int i = 0; i < n; i++) {
        int x = nums[i], l = 0, r = tail.size();
        while (l < r) {
            int mid = (l + r) / 2;
            if (tail[mid] < x)
                l = mid + 1;
            else
                r = mid;
        }
        if (r == tail.size())
            tail.push_back(x);
        else
            tail[r] = x;
    }
    return tail.size() - 1;
}

单选题2 分

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

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

$9$

$10$

$11$

判断题2 分

C++ 语言中，表达式 9 | 12 的结果类型为 int、值为 $13$ 。

判断题2 分

C++ 语言中，访问数据发生下标越界时，总是会产生运行时错误，从而使程序异常退出。

判断题2 分

对 $n$ 个元素的数组进行归并排序，最差情况的时间复杂度为 $\log n)$ 。

判断题2 分

$5$ 个相同的红球和 $4$ 个相同的蓝球排成一排，要求每个蓝球的两侧都必须至少有一个红球，则一共有 $15$ 种排列方案。

判断题2 分

使用 math.h 或 cmath 头文件中的函数，表达式 log(8) 的结果类型为 double、值约为 $3$ 。

判断题2 分

C++ 是一种面向对象编程语言，C 则不是。继承是面向对象三大特性之一，因此，使用 C 语言无法实现继承。

判断题2 分

$n$ 个顶点的无向完全图，有 $n^{n-2}$ 棵生成树。

判断题2 分

已知三个 double 类型的变量 $a$ 、 $b$ 和 $theta\text{theta}$ 分别表示一个三角形的两条边长及二者的夹角（弧度），则三角形的周长可以通过表达式 $a×a+b×b−2×a×b×cos⁡(theta)\sqrt{a \times a + b \times b - 2 \times a \times b \times \cos(\text{theta})}$ 求得。

判断题2 分

有 $n$ 个顶点、 $m$ 条边的图的深度优先搜索遍历时间复杂度为 $O (n + m)$ 。

判断题2 分

从 $32$ 名学生中选出 $4$ 人分别担任班长、副班长、学习委员和组织委员，老师要求班级综合成绩排名最后的 $4$ 名学生不得参选班长或学习委员（仍可以参选副班长和组织委员），则共有种不同的选法。

GESP 编程操作题

编程题25 分

试题名称：树上旅行

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

题目描述

给定一棵有 $n$ 个结点的 有根树，结点依次以 $1,2,…,n1,2,\dots,n$ 编号，其中根结点的编号为 $1$ 。

小 A 计划在这棵有根树上进行 $q$ 次旅行。在第 $i$ 次旅行中，小 A 首先选定结点 $s_i$ 作为起点，并移动若干次。移动分为以下两种：

移动至当前结点的父结点。特殊地，如果当前位于根结点，则不进行移动。
移动至当前结点的所有子结点中编号最小的结点。特殊地，如果当前位于叶子结点，则不进行移动。

由于移动次数可能很大，对于第 $i$ 次旅行，旅行中的移动以 $k_i$ 个不为零的整数构成的序列 $ai,1,ai,2,…,ai,kia_{i,1}, a_{i,2}, \dots, a_{i,k_i}$ 表示。对 $a_{i,j}$ ，若 $a_{i,j} > 0$ 则代表进行 $a_{i,j}$ 次第一种移动；若 $a_{i,j} < 0$ 则代表进行 $a_{i,j}$ 次第二种移动。根据给出的序列从左至右完成所有移动后，小 A 所在的结点即是旅行的终点。

给定每次旅行的起点与移动序列，请你求出旅行终点的结点编号。

输入格式

第一行，两个正整数 $n, q$ ，分别表示有根树的结点数量，以及旅行次数。

第二行， $n - 1$ 个整数 $p2,p3,…,pnp_2, p_3, \dots, p_n$ ，其中 $p_i$ 表示结点 $i$ 的父结点编号。

接下来 $2 q$ 行中的第 $2 i - 1$ 行（ $\leq i \leq q$ ）包含两个正整数 $s_i, k_i$ ，分别表示第 $i$ 次旅行的起点编号，以及移动序列的长度。第 $2 i$ 行包含 $k_i$ 个整数 $ai,1,ai,2,…,ai,kia_{i,1}, a_{i,2}, \dots, a_{i,k_i}$ ，表示移动序列。

输出格式

输出共 $q$ 行，第 $i$ 行包含一个整数，表示第 $i$ 次旅行终点的结点编号。

样例输入 #1

5 4
1 1 2 2
3 3
1 -1 -1
2 5
1 -1 1 -1 1
5 8
1 1 1 -1 -1 -1 -1 -1
5 3
-1 -1 1

样例输出 #1

样例输入 #2

8 3
5 4 2 1 3 6 6
8 1
8
8 2
8 -8
8 3
8 -8 8

样例输出 #2

1
7
1

说明/提示

子任务编号	测试点占比	$n$	$q$	$∑ki\sum k_i$	特殊性质
$1$	$20%20\%$	$≤100\leq 100$	$≤100\leq 100$	$≤1000\leq 1000$	保证 $a_{i,j}$ 为 $1$ 或 $- 1$
$2$	$20%20\%$	$≤104\leq 10^4$	$≤104\leq 10^4$	$≤4×104\leq 4 \times 10^4$	仅包含第一种移动
$3$	$20%20\%$	$≤104\leq 10^4$	$≤104\leq 10^4$	$≤4×104\leq 4 \times 10^4$	仅包含第二种移动
$4$	$40%40\%$	$≤105\leq 10^5$	$≤2×104\leq 2 \times 10^4$	$≤105\leq 10^5$	-

对于所有测试点，保证：

$\leq n \leq 10^5$
$\leq q \leq 2 \times 10^4$
$\leq p_i \leq n$
$\leq s_i \leq n$
$ki≥1k_i \geq 1$ 且 $∑ki≤105\sum k_i \leq 10^5$
$\leq |a_{i,j}| \leq n$

本题为编程大题：请复制题面到洛谷 / GESP OJ 等平台编写并提交代码（本站不判分）

编程题25 分

试题名称：遍历计数

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

题目描述

给定一棵有 $n$ 个结点的树 $T$ ，结点依次以 $1,2,…,n1,2,\dots,n$ 标号。树 $T$ 的深度优先遍历序可由以下过程得到：

选定深度优先遍历的起点 $s$ （ $\leq s \leq n$ ），当前位置结点即是起点。
若当前结点存在未被遍历的相邻结点 $u$ 则遍历 $u$ ，也即令当前位置结点为 $u$ 并重复这一步；否则回溯。
按照遍历结点的顺序依次写下结点编号，即可得到一组深度优先遍历序。

第一步中起点的选择是任意的，并且第二步中遍历相邻结点的顺序也是任意的，因此对于同一棵树 $T$ 可能有多组不同的深度优先遍历序。请你求出树 $T$ 有多少组不同的深度优先遍历序。由于答案可能很大，你只需要求出答案对 $10^9$ 取模之后的结果。

输入格式

第一行，一个整数 $n$ ，表示树 $T$ 的结点数。

接下来 $n - 1$ 行，每行两个正整数 $u_i, v_i$ ，表示树 $T$ 中的一条连接结点 $u_i, v_i$ 的边。

输出格式

输出一行，一个整数，表示树 $T$ 的不同的深度优先遍历序数量对 $10^9$ 取模的结果。

样例输入 #1

样例输出 #1

样例输入 #2

样例输出 #2

说明/提示

对于 $40%40\%$ 的测试点，保证 $\leq n \leq 8$ 。

对于另外 $20%20\%$ 的测试点，保证给定的树是一条链。

对于所有测试点，保证 $\leq n \leq 10^5$ 。

在洛谷上，只有通过了 Subtask0、Subtask1 和 Subtask2 后，才能获得第三个 Subtask 的分数。

本题为编程大题：请复制题面到洛谷 / GESP OJ 等平台编写并提交代码（本站不判分）