GESP2025年12月认证C++八级真题与解析（判断题8-10）

🧠 判断题第 8 题

1、📌 题目原文

快速排序在最坏情况下的时间复杂度为O(n²)，
可以通过随机化选择基准值（pivot）的方法完全避免退化。

❌ 判断结果：错误（×）

⚠️这是一个非常经典、非常容易被“骗”的题！

2、📖 故事讲解：

🏃‍♂️ 快速排序小子的一天

快速排序（Quick Sort）是一个：

• 🏃‍♂️ 跑得很快

• 😎 很受欢迎

• 📈 平均表现非常好

但他有也有致命弱点……

3、🧠 第一部分：为什么最坏是 O(n²)？

（1）🧩 快速排序的核心动作

1️⃣ 选一个基准值 pivot
2️⃣ 比 pivot 小的放左边
3️⃣ 比 pivot 大的放右边

（2）❌ 最倒霉的情况来了

假设数组已经是：

1 2 3 4 5 6

你每次都选：

pivot = 第一个数

结果会怎样？

左边：空 右边：n-1 个

（3）👉 每一层只少一个数
👉 一共要分 n 层

📉 时间复杂度就变成：

O(n²)

4、🧠 第二部分：随机 pivot 能“完全避免”吗？

（1）🎲 随机选 pivot 是什么？

不是总选第一个，而是：

• 随机挑一个

• 让“倒霉情况”不常发生

（2）⚠️ 关键点来了

随机 ≠ 不可能

随机只是：

• ✅降低概率

• ❌不能保证 100% 不退化

（3）📌 所以题目里说：

“完全避免退化”

这是错的！

5、🧠 记忆口诀

快排会退化，随机可以降概率，但不是百分百

🧠 判断题第 9 题

1、📌 题目原文

在 C++ 语言中，一个类可以拥有多个构造函数，也可以拥有多个析构函数。

❌ 判断结果：错误（×）

2、📖 故事讲解：

🏠 类 = 房子

在 C++ 王国里：

• 类就像一栋房子

• 构造函数= 进门方式

• 析构函数= 离开时清理房子

3、🧠 第一部分：构造函数（可以多个）

(1)🚪 为什么可以有多个构造函数？

因为进门方式可以不同：

class Cat { public: Cat() {} // 空手进门 Cat(int age) {} // 带年龄进门 Cat(int age, int w) {}// 带年龄和体重 };

(2)👉 这叫函数重载

✅完全合法

4、🧠 第二部分：析构函数（只能一个）

（1）🚪🚫 为什么不能多个？

析构函数的名字是固定的：

~Cat()

• 名字不能改

• 没参数

• 没返回值

(2)👉无法区分多个

所以：

📌 一个类只能有一个析构函数

5、🧠 记忆口诀

构造函数能重载，

所以可以有多个，

析构函数是固定，

一个类只能有一个。

🧠 判断题第 10 题

1、📌 题目原文

求两个序列的最长公共子序列（LCS）时，
使用滚动数组优化空间后，仍然可以还原出具体的 LCS 序列。

❌ 判断结果：错误（×）

⚠️ 这是算法理解题，很重要！

2、📖 故事讲解：

🧬 找“共同的秘密密码”

两个字符串：

A = ABCBDAB B = BDCABA

LCS 是：

BCBA 或 BDAB

3、🧠 普通 LCS（能还原）

我们用一个二维表：

dp[i][j]

每一步都记录：

• 从哪来

• 是上？左？还是左上？

📌路径在，答案就能回溯

4、🧠 第二部分：滚动数组做了什么？

（1）🧩 滚动数组的目的

省内存！

原来是：

n × m

现在只保留：

2 行

（2）❌ 问题来了

• 旧的行被覆盖了

• “走过的路”被擦掉了

👉 你只知道长度
👉 不知道具体选了哪些字符

5、🧠 结论

6、🧠 记忆口诀

普通LCS,

路径可还原，

滚动省空间，

路径全不见。