2025年6月 GESP C++ 8级

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

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

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

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

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

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

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

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

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

下面程序的输出为（ ）。

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

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

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

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

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

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

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

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

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

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

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

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

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

个顶点的无向完全图，有 棵生成树。

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

有 个顶点、 条边的图的深度优先搜索遍历时间复杂度为 。

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