CCF GESP 2025年6月认证 C++ 8级

一 单选题
共 15 道 每题 2 分 共计 30 分
第 1 题

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

A

$720$
B

$90$
C

$48$
D

$15$
第 2 题

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

A

$720$
B

$72$
C

$36$
D

$2$
第 3 题

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

A

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

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

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

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

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

A

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

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

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

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

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

A

$\frac{2}{3}$
B

$\frac{1}{3}$
C

$\frac{1}{2}$
D

$\frac{1}{4}$
第 6 题

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

A

4 * b - a * a < 0
B

4 * b <= a * a
C

a * a - 4 * b
D

b * 4 - a * a
第 7 题

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

A

$O(\log n)$
B

$O(n \log n)$
C

$O(n)$
D

$O(2^n)$
第 8 题

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

A

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

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

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

对很多问题，递推实现和递归实现动态规划方法的时间复杂度相当。
第 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;
}
A
$O(n \log n)$
B
$O(n)$
C
$O(\log n)$
D
$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 == 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;
}
A

$60$
B

$20$
C

$15$
D

$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;
}
A

$O(n)$
B

$O(n^2)$
C

$O(n \log n)$
D

$O(n^2 \log n)$
第 12 题

下面 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);
    }
}
A 
swap(a[l], a[i])
i
B 
swap(a[l], a[j])
i
C 
swap(a[l], a[i])
j
D 
swap(a[l], a[j])
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;
}
A

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

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

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

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

$O(\log n)$
B

$O(n)$
C

$O(n \log n)$
D

$O(n^2)$
第 15 题

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

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

$9$
B

$10$
C

$11$
D

$12$
单选题部分已到底了。