GESP C++ 八级 2025年06月考试试卷

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

第 1 题

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

• 720
• 90
• 48
• 15

第 2 题

又到了毕业季，学长学姐们都在开心地拍毕业照。现在有3位学长、3位学姐希望排成一排拍照，要求男生不相邻、女生不相邻。请问共有多少种拍照方案？( ) {{ select(2) }}

• 720
• 72
• 36
• 2

第 3 题

下列关于C++类和对象的说法，错误的是( )。 {{ select(3) }}

• 通过语句const int x = 5;定义了一个对象x。
• 通过语句std::string t = "12345";定义了一个对象t。
• 通过语句void (*fp)() = NULL;定义了一个对象fp。
• 通过语句class MyClass;定义了一个类MyClass。

第 4 题

关于生成树的说法，错误的是( )。 {{ select(4) }}

• 一个无向连通图，一定有生成树。
• n个顶点的无向图，其生成树要么不存在，要么一定包含n-1条边。
• n个顶点、m条边的无向图，不可能有多颗生成树。
• n个顶点、n-1条边的无向图，它本身就是自己的生成树。

第 5 题

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

• (\frac{1}{4})
• (\frac{1}{2})
• (\frac{3}{4})
• (\frac{1}{3})

第 6 题

已定义变量double a, b;，下列哪个表达式可以用来判断一元二次方程(x^2 + a x + b = 0)是否有实根？( ) {{ select(6) }}

• (4 * b - a * a < 0)
• (4 * b <= a * a)
• (a * a - 4 * b)
• (b * 4 - a * a)

第 7 题

n个结点的二叉树，执行广度优先搜索的平均时间复杂度是( )。 {{ select(7) }}

• (O(1))
• (O(n))
• (O(\log n))
• (O(n\log n))

第 8 题

以下关于动态规划的说法中，错误的是( )。 {{ select(8) }}

• 动态规划方法通常能够列出递推公式。
• 动态规划方法的时间复杂度通常为状态的个数。
• 动态规划方法有递推和递归两种实现形式。
• 对很多问题，递推实现和递归实现动态规划方法的时间复杂度相当。

第 9 题

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

{{ select(9) }}

• (O(n \log n))
• (O(n))
• (O(\log n))
• (O(n^2))

第 10 题

下面程序的输出为( )。

#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 == 6 && z == 8)
                    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;
}

{{ select(10) }}

• 60
• 20
• 15
• 10

第 11 题

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

{{ select(11) }}

• (O(n))
• (O(n^2))
• (O(n\log n))
• (O(\sqrt{n}\log n))

第 12 题

下面quick_sort函数中，partition函数的横线处应该依次填入( )。

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]);
    }
    ________; // 横线1：交换基准值与正确位置
    return ________; // 横线2：返回基准值最终位置
}

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

{{ select(12) }}

• 横线1：swap(a[l], a[i])；横线2：i
• 横线1：swap(a[l], a[j])；横线2：i
• 横线1：swap(a[l], a[i])；横线2：j
• 横线1：swap(a[l], a[j])；横线2：j

第 13 题

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

{{ select(13) }}

• 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)

第 14 题

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

{{ select(14) }}

• (O(n))
• (O(n\log n))
• (O(n^2))
• (O(n\sqrt{n}))

第 15 题

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

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

{{ select(15) }}

• 9
• 10
• 11
• 12

2 判断题（每题 2 分，共 20 分）

第 16 题

C++语言中，表达式9 | 12的结果类型为int、值为13。( ) {{ select(16) }}

• 正确
• 错误

第 17 题

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

• 正确
• 错误

第 18 题

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

• 正确
• 错误

第 19 题

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

• 正确
• 错误

第 20 题

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

• 正确
• 错误

第 21 题

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

• 正确
• 错误

第 22 题

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

• 正确
• 错误

第 23 题

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

• 正确
• 错误

第 24 题

有V个顶点、E条边的图的深度优先搜索遍历时间复杂度为 (O(V+E))。( ) {{ select(24) }}

• 正确
• 错误

第 25 题

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

• 正确
• 错误