GESP 202506 C++ 八级

一、 单项选择题（共 15 题，每题 2 分，共计 30 分）

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

• 720
• 90
• 48
• 15

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

• 720
• 72
• 36
• 2

3. [2 分] 下列关于 C++ 类和对象的说法，错误的是（ ）。 （ {{ select(3) }} ）

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

4. [2 分] 关于生成树的说法，错误的是（ ）。 （ {{ select(4) }} ）

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

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

• $\frac{1}{4}$
• $\frac{1}{3}$
• $\frac{1}{2}$
• $\frac{3}{4}$

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

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

7. [2 分] $n$ 个结点的二叉树，执行广度优先搜索的平均时间复杂度是（ ）。 （ {{ select(7) }} ）

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

8. [2 分] 以下关于动态规划的说法中，错误的是（ ）。 （ {{ select(8) }} ）

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

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

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. [2 分] 下面程序的输出为（ ）。

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

（ {{ select(10) }} ）

• 60
• 20
• 15
• 10

11. [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 = 2 * u * v;
                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(n^2 \log n)$

12. [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[i] >= pivot) j--; // 注意：这里代码逻辑可能有误，通常是 a[i] <= pivot i++
        // 图片代码较模糊，根据标准快填逻辑推断
        // ...
        if (i < j) swap(a[i], a[j]);
    }
    ________; // 在此处填入选项
    return ________; // 在此处填入选项
}

（ {{ select(12) }} ）

• 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. [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;
}

（ {{ 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. [2 分] 下面 LIS 函数试图求出最长上升子序列的长度，其时间复杂度为（ ）。 （代码使用了 tail 数组和二分查找优化） （ {{ select(14) }} ）

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

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

int weight[4][4] = {
    {0, 5, 3, 10},
    {5, 0, 1, 7}, // 假设值
    {3, 1, 0, 3}, // 假设值
    {10, 7, 3, 0}
};

（ {{ select(15) }} ）

• 9
• 10
• 11
• 12

---

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

16. [2 分] C++ 语言中，表达式 9 | 12 的结果类型为 int，值为 13。 （ {{ select(16) }} ）

• 正确
• 错误

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

• 正确
• 错误

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

• 正确
• 错误

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

• 正确
• 错误

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

• 正确
• 错误

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

• 正确
• 错误

22. [2 分] $n$ 个顶点的无向完全图，有 $n^{n-2}$ 棵生成树。 （ {{ select(22) }} ）

• 正确
• 错误

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

• 正确
• 错误

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

• 正确
• 错误

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

• 正确
• 错误