GESP2026年9月认证C++五级( 第一部分选择题（1~7题）精讲

第一部分 选择题 1～7

第1题：单链表尾部插入，究竟有多快？

题目：

小杨用单链表保存任务序列，并同时维护头指针head和尾指针tail。在链表非空且已知tail

的情况下，在表尾插入新结点的时间复杂度是（ ）。

答案：A

一、先想象一个“排队的小火车”

单链表可以想象成一列小火车：

head ↓ [任务1] → [任务2] → [任务3] → nullptr ↑ tail

每个结点里面有两个东西：

struct Node { int value; Node *next; };

一个存数据：

value

一个负责指向下一个结点：

next

二、如果没有 tail，会发生什么？

假设我们只有：

head

现在想在最后面添加：

[1] → [2] → [3] → [4]

我们不知道谁是最后一个。

只能从头开始找：

1 → 2 → 3 → 4 ↑ 从这里开始找

如果有n个结点，就可能需要走n

步。

所以：

时间复杂度：O(n)

三、可是题目说：我有 tail！

现在：

head ↓ [1] → [2] → [3] ↑ tail

要加入：

[4]

直接：

tail->next = newNode; tail = newNode;

只做两三件固定的事情。

不管链表里面有：

10个 100个 10000个 1000000个

都差不多这么几步。

所以：

O(1)

⭐ 小学生记忆法

有尾指针 tail，找队伍最后一个人就不用从头找。

已知 tail → 尾部插入 O(1)

第2题：双向链表删除结点

题目说：

在不带哨兵结点的双向链表中，结点p既不是头结点也不是尾结点。删除p

的正确代码是（ ）。

答案：C

。

一、先认识“双向链表”

单链表：

A → B → C

B 只知道：

后面是谁？

双向链表则是：

A ⇄ B ⇄ C

B 不但知道 C：

B.next = C

还知道 A：

B.prev = A

所以：

prev next ← → [A] ⇄ [B] ⇄ [C]

二、现在要删除 B

原来：

A ⇄ B ⇄ C

删除 B 后，我们希望变成：

A ⇄ C

那么要修改哪两个“指针”？

第一步

让 A 跳过 B，直接指向 C：

p->prev->next = p->next;

图：

A.next = C

第二步

让 C 反过来指向 A：

p->next->prev = p->prev;

图：

C.prev = A

最后：

delete p;

所以完整代码：

p->prev->next = p->next; p->next->prev = p->prev; delete p;

答案：

C

⭐ 为什么其他思路容易错？

比如：

p->prev = p->next;

这只是修改了p 自己的 prev

。

但是我们真正需要修理的是：

A.next C.prev

也就是说：

删除一个结点，不是只修改“自己”，而是要把前后两个邻居重新牵手。

🧠 记忆口诀

删除双向链表中的p

：

前面的 next 跳过 p 后面的 prev 跳过 p 最后 delete p

即：

p->prev->next = p->next; p->next->prev = p->prev; delete p;

第3题：快慢指针寻找链表中点

题目给出了：

Node *middle(Node *head) { Node *slow = head; Node *fast = head; while (fast != nullptr && fast->next != nullptr) { slow = slow->next; ______________________ } return slow; }

答案：B：

fast = fast->next->next;

原题程序结构见试卷。

一、什么叫“快慢指针”？

想象学校运动会上有两位同学：

  • 小慢：一次走1格

  • 小快：一次走2格

例如：

1 → 2 → 3 → 4 → 5

一开始：

slow ↓ 1 fast ↓ 1

每轮：

slow走1步 fast走2步

二、跑一跑

第一轮：

1 → 2 → 3 → 4 → 5 ↑ slow ↑ fast

第二轮：

1 → 2 → 3 → 4 → 5 ↑ slow ↑ fast

此时：

slow = 3

刚好来到中间！

三、为什么这么神奇？

因为：

fast速度 = slow速度 × 2

当 fast 走完整条链表时：

fast走了 n slow只走了 n/2

所以 slow 就停在中间附近。

四、横线应该写什么？

slow：

slow = slow->next;

一次走一步。

那么 fast 就必须：

fast = fast->next->next;

一次走两步。

答案：

B

⭐ 记忆口诀

慢指针一步走，快指针两步走。

看到：

slow fast

脑袋里立刻出现：

🐢 一步 🐇 两步

第4题：欧几里得算法求最大公约数

题目：

int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }

求：

gcd(105,45)

答案：C：15

。

一、什么是最大公约数？

105 和 45 的公约数：

1 3 5 15

最大的：

15

所以：

gcd(105,45)=15

不过考试不会让我们一个一个试。

这里使用的是非常经典的：

欧几里得算法，也叫辗转相除法。

二、看看代码到底在干什么

核心：

gcd(a,b)

会变成：

gcd(b,a%b)

我们一步一步算。

第一次

105 ÷ 45

余数：

15

所以：

gcd(105,45) = gcd(45,15)

第二次

45 ÷ 15

余数：

0

所以：

gcd(45,15) = gcd(15,0)

第三次

因为：

b == 0

于是：

return a;

返回：

15

⭐ 记忆口诀

欧几里得算法就像：

大石头不断用小石头去除，最后剩下的那个“最后的非零余数”，就是最大公约数。

口诀：

gcd(a,b) ↓ gcd(b,a%b) ↓ 直到 b=0 ↓ 答案就是 a

第5题：怎么判断一个数是不是质数？

题目：

bool isPrime(int n) { if (n < 2) return false; for (int i = 2; __________________; i++) { if (n % i == 0) return false; } return true; }

选项：

A. i < n B. i <= n / 2 C. i * i < n D. (long long)i * i <= n

答案：D

。

一、什么是质数？

质数就是：

大于1，并且只能被1和自己整除的数。

例如：

2、3、5、7、11、13……

不是质数：

4、6、8、9、10……

二、最笨的方法

判断：

97

是不是质数。

最笨：

2、3、4、5、6、7、……96

全部试。

太慢了！

三、其实只需要检查到 √n

为什么？

假设：

n = a × b

如果：

a > √n

那么：

b < √n

也就是说，如果一个数是合数，那么它一定至少有一个因数：

≤ √n

所以我们只需要检查：

i × i <= n

四、为什么选 D？

D：

(long long)i * i <= n

它表示：

i² ≤ n

也就是：

i ≤ √n

这正是最经典的质数判断范围。

五、为什么还要(long long)

？

这个细节非常重要！

如果：

i

是int

，那么：

i * i

可能发生整数溢出

。

例如 i 很大的时候：

i × i

超过int

能表示的范围，就可能出问题。

所以写：

(long long)i * i

更加安全。

⭐ 记忆口诀

判断质数，不必试到 n，只试到 √n。

代码模板：

for (int i = 2; (long long)i * i <= n; i++)

看到它，就应该马上想到：

质数判断！

第6题：线性筛为什么能做到“一合数只筛一次”？

这一题开始稍微有点难度了。

题目给出的核心代码：

for (int p : primes) { if ((long long)i * p > n) break; composite[i * p] = true; if (__________________) break; }

选项：

A. p % i == 0 B. i % p == 0 C. i == p D. i * p == n

答案：B：

i % p == 0

原题线性筛代码见试卷。

一、先理解“筛子”

我们想找：

2、3、5、7、11……

这些质数。

而：

4、6、8、9、10……

都是合数。

线性筛的目标非常牛：

每一个合数，只让它被自己的最小质因子筛掉一次。

二、什么叫最小质因子？

例如：

12 = 2 × 2 × 3

最小质因子是：

2
15 = 3 × 5

最小质因子：

3
35 = 5 × 7

最小质因子：

5

三、关键问题来了

代码：

composite[i * p] = true;

说明：

i × p

被筛掉。

但是什么时候应该停止？

答案：

if (i % p == 0) break;

四、举个例子：i = 12

12 = 2 × 2 × 3

质数从小到大：

2、3、5、7……

首先：

p = 2

筛：

12 × 2 = 24

然后：

12 % 2 == 0

成立！

说明：

2 是 12 的最小质因子

这时候：

break;

停止。

五、为什么必须停止？

因为如果继续：

12 × 3 = 36

以后又可能通过其他方式把：

36

筛掉。

线性筛就是想做到：

一个合数只认一个“最小质因子”，不重复处理。

所以：

if (i % p == 0) break;

答案：

B

🧠 一句话记住

线性筛遇到“p 能整除 i”，说明 p 已经是 i 的最小质因子，该停了。

第7题：唯一分解定理——质因数分解

题目：

根据唯一分解定理，整数……的正确质因数分解是（ ）。

本题在 PDF 的文字解析中，题目的具体被分解整数和选项公式出现了排版丢失，因此仅凭当前提取文本无法可靠还原第7题的具体数字和四个选项

。原卷目录位置明确显示第7题紧接在线性筛之后。

但这道题考察的知识点可以确定是：

唯一分解定理 + 质因数分解

第7题答案是：

A

。

一、什么叫“唯一分解定理”？

一个大于 1 的整数，都可以写成：

若干个质数相乘的形式，而且这种分解方式是唯一的（除了质因子的排列顺序不同）。

例如：

12

可以分解：

12 = 2 × 2 × 3

也可以写：

12 = 3 × 2 × 2

虽然顺序不同，但是本质完全一样：

2² × 3

二、再看一个例子

比如：

60

不断拆：

60 ↓ ÷2 30 ↓ ÷2 15 ↓ ÷3 5 ↓ ÷5 1

所以：

60 = 2 × 2 × 3 × 5

也就是：

60 = 2² × 3 × 5

这就是质因数分解。

三、为什么叫“唯一”？

比如：

60

你无论怎么拆：

60 = 2 × 30 = 2 × 2 × 15 = 2 × 2 × 3 × 5

最终都会得到：

2、2、3、5

不会出现另外一套完全不同的质因数。

所以：

大整数就像一座城堡，质数是它最基本的砖块。

城堡可以有不同的拆墙顺序，但是最后使用的“砖块种类和数量”是固定的。

🌟 1～7题串起来看

这一组题其实不是七个完全孤立的知识点。

我们把它们串起来：

第1题 单链表 ↓ 第2题 双向链表 ↓ 第3题 快慢指针 ↓ 第4题 最大公约数 ↓ 第5题 质数判断 ↓ 第6题 线性筛 ↓ 第7题 质因数分解

可以把它看成一场“算法升级冒险”

：

🏰 第一关：链表村

学会：

head tail next prev

核心思想：

指针就是“告诉你下一个人在哪里”。

🐢 第二关：快慢赛跑

学会：

slow：一步 fast：两步

用来寻找链表中点。

🧙 第三关：数学魔法

欧几里得算法：

gcd(a,b) → gcd(b,a%b)

不断缩小问题。

🔍 第四关：质数侦探

不要傻傻检查：

2～n-1

只检查：

2～√n

⚡ 第五关：线性筛

普通筛法：

一个合数可能被标记很多次。

线性筛：

一个合数只让最小质因子负责。

🧱 第六关：质因数分解

最终发现：

所有大于1的整数，都可以拆成唯一的一组质数“积木”。

📌 考试最后一分钟速记表

题目核心知识记忆口诀
1单链表尾插有tail，尾插O(1)
2双向链表删除前next跳过，后prev跳过
3快慢指针slow一步，fast两步
4gcdgcd(a,b)=gcd(b,a%b)
5质数判断只检查到√n
6线性筛i%p==0就停止
7唯一分解每个数都有唯一的质因数“积木”

如果把这 7 道题压缩成7 句话

，同学们可以这样记：

① 有 tail，尾插 O(1)。

② 删 p，前后邻居重新牵手。

③ 慢一快二找中点。

④ gcd 不断换成(b, a%b)。

⑤ 质数只查到 √n。

⑥ 线性筛遇到i%p==0就停。

⑦ 每个整数都有唯一的质因数积木。