GESP 2025年6月认证 C++ 8级试题

一、选择题

第 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$ 个顶点、$n-1$ 条边的无向图，不可能有多颗生成树。
• $n$ 个顶点、$n-1$ 条边的无向图，它本身就是自己的生成树。

---

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

{{ select(5) }}

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

---

第 6 题 已定义变量 double a, b; ，下列哪个表达式可以用来判断一元二次方程 $ax^2 + bx + c = 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(\log n)$
• $O(n \log n)$
• $O(n)$
• $O(n^2)$

---

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

{{ select(8) }}

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

---

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

{{ select(9) }}

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

---

第 10 题 下面程序的输出为（ ）。

{{ select(10) }}

• 60
• 20
• 15
• 10

---

第 11 题 下面 count_triple 函数的时间复杂度为（ ）。

{{ select(11) }}

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

---

第 12 题 下面 quick_sort 函数试图实现快速排序算法，两处横线处分别应该填入的是（ ）。

{{ select(12) }}

• swap(a[l], a[i]) 和 i
• swap(a[l], a[j]) 和 i
• swap(a[l], a[i]) 和 j
• swap(a[l], a[j]) 和 j

---

第 13 题 下面 LIS 函数试图求出最长上升子序列的长度，横线处应该填入的是（ ）。

{{ 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 函数试图求出最长上升子序列的长度，其时间复杂度为（ ）。

{{ select(14) }}

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

---

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

{{ select(15) }}

• 9
• 10
• 11
• 12

---