GESP 八级 · 2025 真题

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

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

下列关于C++类和对象的说法，错误的是( )

关于生成树的说法，错误的是( )

一对夫妻生两个孩子，实现儿女双全的概率是多少？

已定义变量 double a, b;，下列哪个表达式可判断方程 $x^2 + ax + b = 0$ 是否有实根？

$n$个结点的二叉树，广度优先搜索的平均时间复杂度是？

关于动态规划的说法，错误的是？

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

01#include <string>
02int count_digit(int n, char d) {
03    int cnt = 0; 
04    std::string s = std::to_string(n);
05    for (int i = 0; i < s.length(); i++)
06        if (s[i] == d)
07            cnt++;
08    return cnt;
09}
10int sum_digit(int n, char d) {
11    int sum = 0;
12    for (int i = 1; i <= n; i++)
13        sum += count_digit(i, d);
14    return sum;
15}

下面程序的输出为()

01#include <iostream>
02const int N=10;
03int ch[N][N][N];
04int main(){
05    for(int x=0;x<N;x++)
06        for (int y=0;y<N;y++)
07            for (int z=0;z<N; z++)
08                if(x==0&&y==0&&z==0)
09                    ch[x][y][z]=1;
10                else{
11                    if(x>0) 
12                        ch[x][y][z]+=ch[x-1][y][z];
13                    if(y>0)
14                        ch[x][y][z]+=ch[x][y-1][z];
15                    if(z>0) 
16                        ch[x][y][z]+=ch[x][y][z-1];
17                }
18    std::cout<<ch[1][2][3]<<std::endl;
19    return 0;
20}

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

01int gcd(int a, int b){ 
02    if(a==0)
03        return b;
04    return gcd(b% a,a);
05}
06int 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}

下面quick_sort

01void swap(int & a, int & b) {
02    int temp = a; 
03    a = b; 
04    b = temp;
05}
06int partition(int a[], int l, int r) { 
07    int pivot = a[l], i = l + 1, j = r;
08    while (i <= j) {
09        while (i <= j && a[j] >= pivot)
10            j--;
11        while (i <= j && a[i] <= pivot)
12            i++;
13        if (i < j)
14            swap(a[i], a[j]);
15    }
16    // 在此处填入选项
17    return ________; // 在此处填入选项
18}
19void quick_sort(int a[], int l, int r) { 
20    if (l < r) { 
21        int pivot = partition(a, l, r); 
22        quick_sort(a, l, pivot - 1); 
23        quick_sort(a, pivot + 1, r);
24    }
25}

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

01int max(int a, int b) { 
02    return (a > b) ? a : b;
03}
04int LIS(vector<int> & nums) {
05    int n = nums.size(); 
06    if (n == 0) return 0;
07    vector<int> dp(n, 1);
08    int maxLen = 1;
09    for (int i = 1; i < n; i++) { 
10        for (int j = 0; j < i; j++)
11            if (nums[j] < nums[i])
12                ; // 在此处填入选项
13        maxLen = max(maxLen, dp[i]);
14    }
15    return maxLen;
16}

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

01#define INT_MIN (-1000) 
02int LIS(vector<int> & nums) {
03    int n = nums.size();
04    vector<int> tail;
05    tail.push_back(INT_MIN); 
06    for (int i = 0; i < n; i++) { 
07        int x = nums[i], l = 0, r = tail.size();
08        while (l < r) {
09            int mid = (l + r) / 2;
10            if (tail[mid] < x)
11                l = mid + 1;
12            else
13                r = mid;
14        }
15        if (r == tail.size())
16            tail.push_back(x);
17        else
18            tail[r] = x;
19    } 
20    return tail.size() - 1;
21}

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

01int weight[4][4] = {
02    { 0, 5, 8, 10},
03    { 5, 0, 1, 7},
04    { 8, 1, 0, 3},
05    {10, 7, 3, 0}};

C++语言中,表达式9 | 12 的结果类型为int ､值为13 ｡

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

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

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

第 5 题 使用math.h 或cmath 头文件中的函数,表达式 log(8) 的结果类型为double ､值约为3 ｡

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

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

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

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

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