第 1 题 关于单链表、双链表和循环链表，下列说法正确的是（ ）。

A. 在单链表中，若已知任意结点的指针，则可以在 O(1)时间内删除该节点。

B. 循环链表中一定不存在空指针。

C. 在循环双链表中，尾结点的 next 指针一定为 nullptr 。

D. 在带头结点的循环单链表中，判定链表是否为空只需判断头结点的 next 是否指向自身。

【答案】D

【考纲知识点】链表基础结构特性

1、单链表：每个结点只有next指针，删除某结点需要找到其前驱结点，无法 O (1) 删除

2、循环链表：尾结点的next指向头结点（或首元结点），形成闭环，但头结点的prev（双链表）仍可能为空

3、循环双链表：首尾相连，尾结点next指向头结点，头结点prev指向尾结点，无空指针

4、带头结点的循环单链表：空链表时，头结点next指向自己；非空时指向首元结点

【解析】

A 选项：❌ 错误。单链表删除结点需要前驱结点，仅知当前结点指针，无法 O (1) 删除（除非用「后继结点覆盖」的特殊方法，但不是通用 O (1) 删除，且会丢失数据）

B 选项：❌ 错误。循环链表的头指针 / 头结点的prev（双链表）仍可能为空，并非完全无空指针

C 选项：❌ 错误。循环双链表尾结点next指向头结点，不是nullptr

D 选项：✅ 正确。带头结点的循环单链表，空链表时头结点next指向自身；非空时指向首元结点，因此可通过该条件判空

第 2 题 双向循环链表中要在结点 p 之前插入新结点 s （均非空），以下指针操作正确的是（ ）。

【答案】C

【考纲知识点】双向循环链表的插入操作

双向链表每个结点有next（后继）和prev（前驱）两个指针，插入p前的步骤：

1、s->next = p：新节点s的后继指向p

2、s->prev = p->prev：新结点s的前驱指向p原来的前驱q

3、p->prev->next = s：p原来的前驱q的后继指向s

4、p->prev = s：p的前驱指向s

四个步骤缺一不可，保证链表闭环不断裂

【解析】

A 选项：❌ 错误。代码中出现未定义的q，逻辑混乱，无法正确插入

B 选项：❌ 错误。这是 ** 在p之后插入s** 的操作，不是在p之前插入

C 选项：✅ 正确。完全符合双向链表前插的四步标准操作，指针关系完整闭环

D 选项：❌ 错误。s->prev = nullptr破坏了循环链表的闭环，导致链表断裂

单链表删除：必须找前驱，无法 O (1) 删除

循环链表判空：带头结点的循环单链表，空链表头结点next指向自己

双向链表前插：四步标准操作：s->next=p → s->prev=p->prev → p->prev->next=s → p->prev=s

循环双链表：首尾相连，无空指针，尾结点next指向头结点

第 3 题 下面函数用“哑结点”统一处理删除单向链表中的头结点与中间结点。横线处应填（ ）。

【答案】B

【考纲知识点】

1. 哑结点（哨兵结点）的作用

（1）单链表删除头结点和中间结点的逻辑原本是不同的：

删除中间结点：需要找到前驱结点，修改前驱的next指向被删结点的后继

删除头结点：没有前驱，需要单独修改头指针

（2）哑结点（dummy）是一个额外的头结点，它的next指向原链表的头结点。这样一来，原链表的所有结点（包括原头结点）都变成了中间结点，可以用统一的逻辑删除，无需区分头结点和中间结点。

2. 单链表删除结点的核心逻辑

要删除结点del，必须修改其  前驱结点cur 的next指针，让cur->next直接指向del->next，从而跳过del，完成删除。

（1）公式：cur->next = del->next

（2）之后再释放del的内存，避免内存泄漏。

【解析】

代码逐行分析

1、Node dummy(0);：创建哑结点，值为 0，next初始为nullptr

2、dummy.next = head;：哑结点的next指向原链表头结点，原链表头结点成为哑结点的后继

3、Node* cur = &dummy;：cur初始指向哑结点，作为遍历的前驱指针

4、while(cur->next)：遍历链表，只要cur的后继不为空，就继续

5、if(cur->next->val == x)：如果cur的后继结点值等于x，说明需要删除这个后继结点

Node* del = cur->next;：用del保存要删除的结点

横线处：需要修改cur的next，跳过del，指向del的后继

delete del;：释放del的内存

6、else cur = cur->next;：如果不需要删除，cur向后移动

7、return dummy.next;：返回哑结点的next，即新的链表头结点（原头结点被删除时也能正确返回）

逐项分析

• A 选项：cur = cur->next;❌ 错误。只是让cur向后移动，没有修改cur->next，del结点仍然在链表中，没有被删除，还会导致死循环。

• B 选项：cur->next = del->next;✅ 正确。这是单链表删除结点的标准操作：让前驱cur的next直接指向del的后继，跳过del，完成删除。

• C 选项：del->next = cur->next;❌ 错误。del->next本来就等于cur->next，这行代码是无意义的赋值，没有修改cur->next，del结点仍然在链表中，没有被删除。

• D 选项：cur->next = nullptr;❌ 错误。会把cur的后继直接置空，截断链表，导致del之后的所有结点都丢失，不是正确的删除操作。

【补充说明】

1、哑结点的优势

• 统一了头结点和中间结点的删除逻辑，代码更简洁，避免了分情况讨论的错误。
• 即使原链表头结点被删除，dummy.next也会正确指向新的头结点，无需额外处理。

2、易错点

• 必须先修改cur->next，再delete del，否则会丢失del->next的指针，导致链表断裂。
• 不能直接cur = del->next，因为cur是前驱指针，修改cur本身不会改变链表结构，必须修改cur->next。

第 4 题 对如下代码实现的欧几里得算法（辗转相除法），执行 gcd(48, 18) 得到的调用序列为（ ）。

【答案】A

【考纲知识点】欧几里得算法（辗转相除法）

核心公式：gcd(a,b)=gcd(b,a%b)，当 b=0 时，gcd(a,0)=a

作用：求两个正整数的最大公约数（Greatest Common Divisor, GCD）

【解析】

1、初始调用：gcd(48, 18)

b = 18 ≠ 0，计算 a % b = 48 % 18 = 12

递归调用：gcd(18, 12)

2、第二次调用：gcd(18, 12)

b = 12 ≠ 0，计算 a % b = 18 % 12 = 6

递归调用：gcd(12, 6)

3、第三次调用：gcd(12, 6)

b = 6 ≠ 0，计算 a % b = 12 % 6 = 0

递归调用：gcd(6, 0)

4、第四次调用：gcd(6, 0)

b = 0，递归终止，返回 a = 6（48 和 18 的最大公约数为 6）

最终完整调用序列：

gcd(48,18) -> gcd(18,12) -> gcd(12,6) -> gcd(6,0)

易错点

1、混淆减法和取模：辗转相除法用的是 a % b（余数），不是 a - b（差），因此 B 选项的减法逻辑错误

2、颠倒参数顺序：递归调用必须是 gcd(b, a%b)，不能写成 gcd(a%b, b)，否则会导致参数顺序错误（如 D 选项）

3、忽略取模结果小于除数：a % b 的结果一定小于 b，因此 C 选项中第二个参数 30>18，直接排除

第 5 题 下面代码实现了欧拉（线性）筛，横线处应填写（ ）。

【答案】C

【考纲知识点】欧拉筛（线性筛）原理

1、目标：线性时间复杂度 O(n) 筛出 [2,n] 内的所有质数，保证每个合数只被其最小质因子筛一次。

核心逻辑：

（1）遍历 i 从 2 到 n，若 i 未被标记为合数，则 i 是质数，加入 primes 数组。

（2）用当前 i 乘以已筛出的所有质数 primes[j]，标记乘积为合数。

当 i % primes[j] == 0 时，说明 primes[j] 是 i 的最小质因子，此时必须 break，避免重复筛。

内层循环的边界：j 必须不超过 primes 数组的长度，否则会访问越界（primes[j] 不存在）。

【解析】

A 选项 j <= n：❌ 错误。primes 数组长度远小于 n，j 超过 primes.size() 会访问越界，导致程序崩溃。

B 选项 j < sqrt(n)：❌ 错误。无意义的限制，会导致部分质数无法参与筛除，漏筛合数。

C 选项 j < primes.size()：✅ 正确。j 遍历 primes 数组的所有元素，保证不越界，符合欧拉筛的逻辑。

D 选项 j < i：❌ 错误。primes 数组长度可能大于 i，会导致越界；且无此限制的必要。

第 6 题 埃氏筛中将内层循环从 j = i*i 开始而不是 j = 2*i 的主要原因是（ ）。

A. 因为 2*i 一定不是合数

B. i*i 一定是质数

C. 小于 i*i 的 i 的倍数已被更小质因子筛过

D. 这样可以把时间复杂度降为O(n)

【答案】C

【考纲知识点】埃拉托斯特尼筛法（埃氏筛）优化原理

1、埃氏筛的核心：遍历每个质数 i，标记其所有倍数（2i,3i,4i,…）为合数。

2、优化逻辑：

（1）对于小于 i^2 的 i 的倍数（如 2i,3i,…,(i−1)i），已经被更小的质数筛过了。

例如：i=5 时，2×5=10 已被质数 2 筛过，3×5=15 已被质数 3 筛过，4×5=20 已被质数 2 筛过，因此只需从 5×5=25 开始筛。

（2）从 i^2 开始筛，不影响筛除结果，但大幅减少了重复操作，提升效率。

3、时间复杂度：埃氏筛优化后仍为 O(nloglogn)，不是线性的 O(n)（线性筛是欧拉筛）。

【解析】

A 选项：❌ 错误。2*i 是合数（i≥2），只是已经被更小的质数筛过了。

B 选项：❌ 错误。i*i 是合数（i≥2），不是质数。

C 选项：✅ 正确。小于 i^2 的 i 的倍数，都被更小的质因子筛过了，无需重复筛。

D 选项：❌ 错误。埃氏筛优化后时间复杂度仍为 O(nloglogn)，无法降到 O(n)（只有欧拉筛是线性的）。

【补充:欧拉筛 埃氏筛】

欧拉筛（线性筛）

（1）内层循环条件：j < primes.size()，保证不越界

（2）核心：每个合数只被最小质因子筛一次，时间复杂度 O(n)

（3）关键：if (i % primes[j] == 0) break，避免重复筛

埃氏筛优化

（1）内层循环从 i*i 开始，因为小于 i^2 的倍数已被更小质数筛过

（2）时间复杂度：O(nloglogn)，不是线性

（3）对比：欧拉筛是线性的，埃氏筛是近似线性，欧拉筛效率更高

第 7 题 下面程序的运行结果为（ ）。

A. 2

B. 3

C. 4

D. 5

【答案】B

【考纲知识点】

算法本质：二分答案 + 贪心验证（经典「最大化最小距离」问题）

1、问题模型：在数组中选k个元素，要求任意两个选中元素的距离 ≥ dist，求最大的 dist。

2、二分答案：对dist的值进行二分，判断「是否能选出至少k个元素，两两距离≥dist」。

3、贪心验证：check函数用贪心策略，从左到右遍历，只要当前元素与上一个选中元素的距离≥dist，就选中它，统计最多能选多少个。

4、二分边界：l=0（最小可能距离），r=数组最大值-最小值（最大可能距离），最终l=r即为最大的 dist。

【解析】

解题步骤

步骤 1：数组排序

原数组a = {1,2,8,4,9}，排序后为：a = {1,2,4,8,9}，n=5，k=3。

步骤 2：初始化二分边界

l = 0

r = a[4] - a[0] = 9 - 1 = 8

步骤 3：二分迭代过程

第 1 轮：l=0, r=8

mid = (0 + 8 + 1) / 2 = 4（整数除法，(9)/2=4）

调用check(5, a, 3, 4)：

（1）cnt=1，last=1

（2）i=1：a[1]=2，2-1=1 <4 → 不选

（3）i=2：a[2]=4，4-1=3 <4 → 不选

（4）i=3：a[3]=8，8-1=7 ≥4 → cnt=2，last=8

（5）i=4：a[4]=9，9-8=1 <4 → 不选

最终cnt=2 <3 → check返回false

因此r = mid -1 = 4-1=3，现在l=0, r=3

第 2 轮：l=0, r=3

mid = (0 + 3 +1)/2 = 2

调用check(5, a, 3, 2)：

（1）cnt=1，last=1

（2）i=1：2-1=1 <2 → 不选

（3）i=2：4-1=3 ≥2 → cnt=2，last=4

（4）i=3：8-4=4 ≥2 → cnt=3，last=8

（5）i=4：9-8=1 <2 → 不选

最终cnt=3 ≥3 → check返回true

因此l = mid =2，现在l=2, r=3

第 3 轮：l=2, r=3

mid = (2 +3 +1)/2 = 3

调用check(5, a, 3, 3)：

cnt=1，last=1

i=1：2-1=1 <3 → 不选

i=2：4-1=3 ≥3 → cnt=2，last=4

i=3：8-4=4 ≥3 → cnt=3，last=8

i=4：9-8=1 <3 → 不选

最终cnt=3 ≥3 → check返回true

因此l = mid =3，现在l=3, r=3，循环结束。

步骤 4：返回结果

return l =3，最终输出为3。

【核心知识点补充】

1. 二分答案的关键

向上取整：mid = (l + r +1)/2，避免死循环（当l=r-1时，mid=r，若可行则l=r，否则r=l）。

贪心验证的正确性：从左到右选，每次选第一个满足距离的元素，能保证选中的元素数量最多，是最优的贪心策略。

2. 问题本质

这是经典的 「最大化最小距离」 问题，常见场景如：

安排座位，最大化相邻座位的最小距离

放置卫星，最大化相邻卫星的最小距离

放牛问题（经典 POJ / 洛谷题目）

===== 开始二分 =====排序后数组：1 2 4 8 9初始 l = 0, r = 8当前 l = 0, r = 8计算 mid = 4检查距离 = 4，结果 = 不可行不可行 → r = 3当前 l = 0, r = 3计算 mid = 2检查距离 = 2，结果 = 可行可行 → l = 2当前 l = 2, r = 3计算 mid = 3检查距离 = 3，结果 = 可行可行 → l = 3===== 二分结束 =====最终答案 l = r = 3

本题核心知识点（必背）

1. 算法名字

二分答案 + 贪心验证也叫 “最大化最小距离” 经典模板（放牛题、选址题）

2. 思路

• 我们要找：能选出 k 个点，两两距离 ≥ dist 的最大 dist
• 对 dist 二分
• check 函数：贪心从左往右选，能选就选，统计最多能选几个
• 选够 k 个 → dist 可行，尝试更大
• 不够 → dist 太大，尝试更小

一、先搞懂：这道题到底在问什么？

场景还原

假设你有一排位置，坐标分别是：1, 2, 4, 8, 9（对应排序后的数组）现在要求你选 3 个位置，让任意两个选中位置之间的距离，都尽可能大，同时保证：

• 所有选中位置的最小距离（最近的两个的距离）越大越好
• 必须选够 3 个位置

举个例子：

• 选1,4,8：最近的两个是1和4（距离 3）、4和8（距离 4），最小距离是 3
• 选1,2,9：最近的两个是1和2（距离 1），最小距离是 1
• 选1,8,9：最近的两个是8和9（距离 1），最小距离是 1

我们的目标：找到最大的那个「最小距离」，也就是让选出来的 3 个点，最近的两个也尽量远。

二、代码的两个核心部分，分别干什么？

1. check函数：「给定一个距离dist，我能不能选出至少 3 个点，两两距离都≥dist？」

这是一个贪心验证函数，逻辑超级简单：

• 从第一个位置1开始选（last = a[0]，计数器cnt=1）
• 往后遍历每个位置：
• 如果当前位置和上一个选中位置的距离 ≥ dist，就选它，计数器 + 1，更新last为当前位置
• 否则跳过
• 最后看计数器cnt是否≥k（这里 k=3），能选够 3 个就返回true，否则false

举个例子：dist=4，能不能选 3 个？

选1（cnt=1，last=1）

2：2-1=1 <4 → 不选

4：4-1=3 <4 → 不选

8：8-1=7 ≥4 → 选（cnt=2，last=8）

9：9-8=1 <4 → 不选

最终只选了 2 个，不够 3 个 → check(4)=false，说明4这个距离太大了，做不到

再试dist=3，能不能选 3 个？

选1（cnt=1，last=1）

2：2-1=1 <3 → 不选

4：4-1=3 ≥3 → 选（cnt=2，last=4）

8：8-4=4 ≥3 → 选（cnt=3，last=8）

9：9-8=1 <3 → 不选

选够了 3 个 → check(3)=true，说明3这个距离是可行的

• 2. solve函数：「用二分法，找到最大的那个可行dist」

  我们已经知道：

  二分法的作用：快速缩小范围，不用一个个试0~8

  二分的核心逻辑（大白话）

• 每次取中间值mid，问check(mid)行不行
• 行：说明mid是可行的，我们可以尝试更大的，把左边界l拉到mid
• 不行：说明mid太大了，把右边界r缩到mid-1
• 直到l==r，这个值就是最大的可行dist
• dist
  的可能范围：最小是0（所有点都挤在一起），最大是9-1=8（选 1 和 9 两个点）
• 我们要找最大的、能让check返回true的dist

• 三、一步步跟着代码走，每一步都讲透

  步骤 1：排序数组

  原数组{1,2,8,4,9} → 排序后{1,2,4,8,9}（贪心必须在有序数组上才能生效，不然没法从左到右选）

  步骤 2：初始化二分边界

  l=0（最小可能距离）

  r=9-1=8（最大可能距离）

  第一轮二分：l=0, r=8

  第二轮二分：l=0, r=3

• 选1（cnt=1）

  2：2-1=1 <2 → 不选

  4：4-1=3 ≥2 → 选（cnt=2）

  8：8-4=4 ≥2 → 选（cnt=3）

  9：9-8=1 <2 → 不选

  选够 3 个 → true

• 取中间值：mid=(0+3+1)/2=2
• 调用check(2)：
• 取中间值：mid=(0+8+1)/2=4（+1 是为了向上取整，避免死循环）
• 调用check(4)：刚才算过，只能选 2 个，不够 3 个 → false
• 结论：4太大了，右边界缩到r=4-1=3
• 现在范围：[0,3]

• 结论：2是可行的，尝试更大的，左边界拉到l=2

  第三轮二分：l=2, r=3

• 取中间值：mid=(2+3+1)/2=3
• 调用check(3)：刚才算过，能选 3 个 → true
• 结论：3是可行的，尝试更大的，左边界拉到l=3
• 现在l==r=3，循环结束，返回3
• 现在范围：[2,3]

四、为什么用二分法？不用一个个试？

• 一个个试0,1,2,3,4,5,6,7,8，也能算出结果，但效率低
• 二分法只需要 3 次就找到答案，时间复杂度从O(n)变成O(logn)，数据大的时候优势巨大
• 这是 「最大化最小值」/「最小化最大值」 问题的标准解法，几乎所有这类题都用二分答案 + 贪心

五、关键细节：为什么mid要(l+r+1)/2？

这是二分法的防死循环技巧：

• 当l=r-1时（比如l=2, r=3），如果用普通的(l+r)/2，会得到mid=2
• 如果check(2)=true，l=2，永远l<r，死循环
• 加1向上取整，mid=(2+3+1)/2=3，check(3)=true，l=3，直接跳出循环

六、最终结论

• 最大的可行dist是3，对应选项B
• 选出来的 3 个点是1,4,8，最近的两个距离是 3，是所有选法里最大的最小距离

一句话总结

这道题的本质：用二分法找最大的「最小距离」，用贪心验证这个距离能不能选够 k 个点

第 8 题 在升序数组中查找第一个大于等于 x 的位置，下面循环中横线应填（ ）。

【答案】A

【考纲知识点】算法本质：左闭右开区间的二分查找（lower_bound 标准实现）

在升序数组中查找第一个大于等于 x 的位置（即 C++ 标准库std::lower_bound的实现）

1、目标：在升序数组中，找到第一个≥x 的元素的下标，若所有元素都 < x，返回数组长度a.size()。

2、区间定义：[l, r) 左闭右开，即l是搜索区间的左端点（包含），r是搜索区间的右端点（不包含），初始l=0, r=a.size()覆盖整个数组。

3、核心逻辑：

（1）若a[mid] >= x：说明第一个≥x 的位置在[l, mid]区间内（mid 本身可能是目标位置），因此将右边界r收缩到mid。

（2）若a[mid] < x：说明目标位置在[mid+1, r)区间内，因此将左边界l更新为mid+1。

（3）循环终止条件l == r，此时l就是第一个≥x 的位置。

【解析】

A 选项 r = mid;：✅ 正确。完全符合左闭右开区间的收缩逻辑：当a[mid] >= x时，右边界收缩到mid，保留 mid 作为候选位置。

B 选项 r = mid - 1;：❌ 错误。会导致mid位置被排除在搜索区间外，可能漏掉第一个≥x 的元素（比如 mid 本身就是目标位置）。

C 选项 l = mid;：❌ 错误。左边界右移会扩大搜索区间，导致死循环（l永远小于r），逻辑完全错误。

D 选项 l = mid + 1;：❌ 错误。这是a[mid] < x时的操作，用在这里会把目标位置排除，导致结果错误。

【实例验证（用具体数组走一遍流程）】

假设数组a = [1, 3, 5, 7, 9]，x=5，目标是找第一个≥5 的位置（下标2）。

1、初始：l=0, r=5

mid = 0 + (5-0)/2 = 2，a[2]=5 ≥5 → r=2

2、现在l=0, r=2

mid = 0 + (2-0)/2 =1，a[1]=3 <5 → l=2

3、现在l=2, r=2，循环结束，返回2，正确。

再验证x=6（第一个≥6 的位置是下标3，元素7）：

1、初始：l=0, r=5

mid=2，a[2]=5 <6 → l=3

2、现在l=3, r=5

mid=3 + (5-3)/2=4，a[4]=9 ≥6 → r=4

3、现在l=3, r=4

mid=3 + (4-3)/2=3，a[3]=7 ≥6 → r=3

4、现在l=3, r=3，返回3，正确。

【关键细节补充】

1. 为什么用l + (r-l)/2而不是(l+r)/2？

避免整数溢出：当l和r都很大时，l+r可能超过int的最大值，l + (r-l)/2可以安全计算中间值。

结果等价：l + (r-l)/2 = (l+r)/2（整数除法）。

2. 左闭右开 vs 左闭右闭

本题是左闭右开[l, r)的标准lower_bound实现，因此a[mid] >=x时r=mid。

若用左闭右闭[l, r]实现，a[mid] >=x时应写r=mid-1，但本题区间是左闭右开，因此 B 错误。

3. 与upper_bound的区别

lower_bound：找第一个≥x 的位置，条件a[mid] >=x时r=mid。

upper_bound：找第一个 > x 的位置，条件a[mid] >x时r=mid，其余逻辑一致。

【总结】

• 这是 C++ 标准库std::lower_bound的标准实现，核心是左闭右开区间的二分收缩。
• 记住口诀：a[mid] >=x，右边界缩到mid；a[mid] <x，左边界跳到mid+1。

第 9 题 关于递归函数调用，下列说法错误的是（ ）。

A. 递归调用层次过深时，可能会耗尽栈空间导致栈溢出

B. 尾递归函数可以通过编译器优化来避免栈溢出

C. 所有递归函数都可以通过循环结构来改写，从而避免栈溢出

D. 栈溢出发生时，程序会抛出异常并可以继续执行后续代码

【答案】D

【考纲知识点】

递归与栈溢出基础

• 1、递归调用会在调用栈中为每一层函数分配栈帧，层次过深会耗尽栈空间，引发栈溢出（Stack Overflow）。
• 2、尾递归：递归调用是函数的最后一步操作，编译器可优化为循环，避免栈帧累积，防止栈溢出。
• 3、递归与循环的等价性：所有递归算法都可以用循环 + 栈模拟实现，彻底避免栈溢出。
• 4、栈溢出的后果：属于严重运行时错误，程序会直接崩溃，无法继续执行后续代码。

【解析】

A：✅ 正确。递归层次过深会耗尽栈空间，导致栈溢出。

B：✅ 正确。尾递归可被编译器优化为循环，不累积栈帧，避免栈溢出。

C：✅ 正确。所有递归都可通过循环 + 栈模拟改写，消除递归，避免栈溢出。

D：❌ 错误。栈溢出是致命错误，程序会直接崩溃，无法继续执行后续代码。

递归过深会栈溢出，尾递归可优化，递归可改循环，栈溢出会崩溃。

【尾递归】

递归调用是函数最后一步操作的递归，就叫尾递归。

1、先看普通递归（不是尾递归）

intfact(int n) {    if (n == 0) return 1;    return n * fact(n - 1);  // 👈 最后一步是乘法，不是递归}

递归调用 fact(n-1) 之后，还要做乘法

所以递归不是最后一步

这种会一层层压栈，容易栈溢出

2、再看尾递归

intfact(int n, int res) {    if (n == 0) return res;    return fact(n - 1, n * res);  // 👈 最后一步只有递归}

• 函数最后一步就是调用自己
• 没有任何额外计算
• 所有结果都通过参数传递下去

这就叫 尾递归。

尾递归的关键点（考试必背）

1. 1、递归调用必须是函数的最后一条语句
2. 2、递归调用之后不能再有任何运算（加减乘除都不行）
3. 3、结果通过参数累积传递
4. 4、编译器可以优化成循环，不会栈溢出！

为什么尾递归不会栈溢出？

因为编译器发现是尾递归时，会：

• 1、不新建栈帧
• 2、直接覆盖当前栈帧
• 3、相当于变成了循环

所以深度再大也不会爆栈。

【最简单对比】

• 普通递归：要回头计算 → 占栈空间
• 尾递归：不用回头 → 可优化成循环

【考试常考结论】

• 尾递归是最后一步只有递归调用
• 尾递归可以被编译器优化，避免栈溢出
• 不是所有递归都天然是尾递归，需要改写

第 10 题 给定 n 根木头，第 i 根长度为 a[i] 。要切成不少于 m 段等长木段，求最大可能长度，则横线上应填写（ ）。

【答案】A

【考纲知识点】

二分答案（最大化可行值）- 左闭右闭区间模板

• 1、问题本质：求最大的长度x，使得所有木头按x切分，总段数≥m。
• 2、check(x)：验证长度x是否能切出≥m 段。
• 3、二分逻辑（左闭右闭[l, r]，求最大值）：
• （1）若check(mid)=true：mid可行，尝试更大值 → l = mid + 1，同时记录ans=mid。
• （2）若check(mid)=false：mid太大，尝试更小值 → r = mid - 1。
• 4、循环终止条件l > r，最终ans即为最大可行长度。

【解析】

A：✅ 正确。check(mid)为真时l=mid+1，为假时r=mid-1，完全符合左闭右闭二分模板。

B：❌ 错误。逻辑完全颠倒，会导致二分死循环或结果错误。

C：❌ 错误。else分支r=mid会导致死循环（l=r时永远无法跳出）。

D：❌ 错误。逻辑完全错误，二分区间无法正确收缩。

（二分答案）

• 最大化可行值：check(mid)为真l=mid+1，为假r=mid-1，左闭右闭模板。

输入数据

木头数量 n = 4，目标段数 m = 5

木头长度 a = [5, 8, 10, 15]

最大木头长度 mx = 15，二分初始区间 l = 1, r = 15

完整二分迭代过程

第 1 轮：l = 1, r = 15

• （1）mid = 1 + (15-1)/2 = 8
• （2）调用 check(8)：
• 5/8 = 0，8/8 = 1，10/8 = 1，15/8 = 1

• 总段数 = 0+1+1+1 = 3 < 5 → check(8) = false

• （3）结论：8 太大，右边界收缩 → r = 8 - 1 = 7
• （4）现在区间：[1, 7]

  第 2 轮：l = 1, r = 7

• 5/4 = 1，8/4 = 2，10/4 = 2，15/4 = 3
• （1）mid = 1 + (7-1)/2 = 4
• （2）调用 check(4)：

• 总段数 = 1+2+2+3 = 8 ≥ 5 → check(4) = true

• （3）结论：4 可行，记录 ans = 4，尝试更大 → l = 4 + 1 = 5
• （4）现在区间：[5, 7]

• 第 3 轮：l = 5, r = 7

  （1）mid = 5 + (7-5)/2 = 6

  （2）调用 check(6)：

  5/6 = 0，8/6 = 1，10/6 = 1，15/6 = 2

  总段数 = 0+1+1+2 = 4 < 5 → check(6) = false

  （3）结论：6 太大，右边界收缩 → r = 6 - 1 = 5

  （4）现在区间：[5, 5]

  第 4 轮：l = 5, r = 5

  （1）mid = 5 + (5-5)/2 = 5

  （2）调用 check(5)：

  5/5 = 1，8/5 = 1，10/5 = 2，15/5 = 3

  总段数 = 1+1+2+3 = 7 ≥ 5 → check(5) = true

  （3）结论：5 可行，记录 ans = 5，尝试更大 → l = 5 + 1 = 6

  （4）现在 l = 6 > r = 5，循环结束

  最终结果

  【关键细节补充】

  1. 为什么用 l + (r-l)/2 而不是 (l+r)/2？

  2. 为什么 check 里要判断 x == 0？

• 防止除零错误：x=0 时 a[i]/x 会触发运行时错误，因此直接返回 true（实际二分中 l 从 1 开始，x 不会为 0，是防御性代码）。
• 避免整数溢出：当 l 和 r 很大时，l+r 可能超过 long long 范围，l + (r-l)/2 安全无溢出。
• 结果等价：l + (r-l)/2 = (l+r)/2（整数除法）。
• （1）最大可行长度 ans = 5
• （2）验证：按 5 切分，总段数 7 ≥ 5，满足要求；按 6 切分，总段数 4 < 5，不满足，因此 5 是最大值。

第 11 题 下面代码用分治求“最大连续子段和”，其时间复杂度为（ ）。

【答案】B

【考纲知识点】分治算法时间复杂度分析（主定理）

• 分治步骤：
  1、递归分解：将数组分成左右两半，递归求解左右子数组的最大子段和 →         2 次递归调用，每次规模n/2。
  2、跨中点计算：遍历左半部分求最大后缀和，遍历右半部分求最大前缀和         → 总遍历长度O(n)。
  3、合并结果：取左右子数组、跨中点子段的最大值 → O(1)。
• 主定理应用：递推式T(n)=2T(n/2)+O(n)，对应时间复杂度T(n)=O(nlogn)。
• 直观理解：二分共logn层，每层总遍历长度为n，总操作数nlogn。

【解析】

A：❌ 错误。O(n2)是暴力枚举的时间复杂度，分治效率更高。

B：✅ 正确。符合分治的时间复杂度O(nlogn)。

C：❌ 错误。logn是递归层数，总操作数远大于此。

D：❌ 错误。O(n)是 Kadane 算法（动态规划）的时间复杂度，分治无法达到线性。

（分治时间复杂度）

• 分治求最大子段和：T(n)=2T(n/2)+O(n) → O(nlogn)。

第 12 题 游戏大赛决赛，两组选手分别按得分从小到大排好队，现在要把他们合并成一个有序排行榜。

A组： A = {12, 35, 67, 89} ，B组： B = {20, 45, 55, 78} ，下面是归并合并函数的核心循环，横线处应填入（ ）。

A. A[i] >= B[j]

B. A[i] <= B[j]

C. i >= j

D. i <= j

【答案】B

【考纲知识点】

归并排序（Merge Sort）合并逻辑

• 1、前提：两个数组 均为升序。
• 2、策略：双指针 i, j 分别指向 A, B 的起始位置，每次取较小的元素 加入结果数组，保证整体有序。
• 3、题目要求合并成有序排行榜（从小到大），因此优先取 A[i] <= B[j] 的元素。

【解析】

A. A[i] >= B[j]：❌ 错误。这是取较大元素，会导致结果数组降序，与题目要求不符。

B. A[i] <= B[j]：✅ 正确。取较小元素，维持升序合并，符合题目要求。

C. i >= j / D. i <= j：❌ 错误。这是比较下标，不是比较元素大小，逻辑完全错误。

第 13 题 有n 位同学的成绩已经从小到大排好序，现在对它执行下面这段以第一个元素为 pivot 的快速排序，请问此次排序的时间复杂度是（ ）。

【答案】C

【考纲知识点】快速排序（Quick Sort）时间复杂度分析

1、最优 / 平均情况：每次划分将数组均分成两部分，递归树高度为 O(logn)，每层划分耗时 O(n)，总复杂度 O(nlogn)。

2、最坏情况：数组已有序（或逆序），pivot 是极值，划分出 0 和 n−1 两个区间，递归树退化为链表，高度 O(n)，总复杂度 O(n²)。

3、本题关键点：题目描述是 “执行下面这段以第一个元素为 pivot 的快速排序”，没有说明数组是否有序。

在算法考试中，若未特别说明 “已排序” 或 “随机化”，且代码逻辑是固定首元素做 pivot，最坏情况 O(n²) 是标准考点。

虽然平均是 O(nlogn)，但选项中 C 是 O(n²)，对应最坏情况。

【解析】

A. O(n)：❌ 错误。遍历不是排序。

B. O(nlogn)：❌ 这是平均 / 最优情况，不是题目指向的核心考点。

C. O(n²)：✅ 正确。固定首元做 pivot，有序数组下会达到 O(n²)。

D. O(logn)：❌ 这是递归深度，不是总操作数。

快排复杂度：固定首元 pivot，最坏 O(n²)，平均 O(nlogn)。

第 14 题 下面关于排序算法的描述中，不正确的是( )。

A. 冒泡排序和插入排序都是稳定的排序算法

B. 快速排序和归并排序都是不稳定的排序算法

C. 冒泡排序和插入排序最好时间复杂度均为O(n)

D. 归并排序在最好、最坏和平均三种情况的时间复杂度均为O(nlogn)

【答案】B

【考纲知识点】排序算法稳定性（Stability）

1、稳定排序：相等元素的相对顺序不变。

代表：冒泡排序、插入排序、归并排序。

2、不稳定排序：相等元素的相对顺序改变。

代表：快速排序、选择排序、希尔排序、堆排序。

3、时间复杂度：

冒泡 / 插入排序：最好 O(n)（已有序），最坏 O(n²)。

归并排序：O(nlogn)（所有情况均为）。

【解析】

A. 冒泡排序和插入排序都是稳定的：✅ 正确。

B. 快速排序和归并排序都是不稳定的：❌ 错误。快速排序是不稳定的，但归并排序是稳定的（合并时优先取左数组即可保持稳定）。此选项将两者归为 “不稳定”，因此错误。

C. 冒泡排序和插入排序最好时间复杂度均为 O(n)：✅ 正确。遍历一次即有序。

D. 归并排序在最好、最坏和平均三种情况的时间复杂度均为 O(nlogn)：✅ 正确。归并排序无最坏情况，效率稳定。

稳定性：冒泡 / 插入 / 归并 稳定；快排 / 堆排 / 选排 不稳定。

【2025 年 12 月 GESP C++ 五级真题解析    有口诀】2025 年 12 月 GESP C++ 五级真题解析（单双链表删除时间复杂度、排序算法空间时间稳定原地口诀）

第 15 题 下面代码实现两个整数除法，其中被除数为一个“大整数”，用字符串表示，除数是一个小整数，用 int 表示，则横线处应该填写（ ）。

【答案】B

【考纲知识点】大数除法（竖式计算）原理

1、每一步计算：(上一步余数 * 10 + 当前位数字) / 除数。

2、计算完当前位后，新的余数 是 rem % b（即 rem 除以 b 的余数），只有余数带入下一轮计算。

3、若直接用 rem / b 作为新的 rem，数值会溢出且逻辑错误。

【解析】题目描述

long long rem = 0;for(int i = 0; i < a.size(); i++){    rem = rem * 10 + a[i];  // 累积余数和当前位    int q = rem / b;        // 计算当前位的商    c.push_back(q);    ____________________;  // 👈 填空}

A. rem /= b;：❌ 错误。rem /= b 等于 rem = rem / b，存的是商，不是余数。

B. rem %= b;：✅ 正确。取模运算得到新的余数，为下一轮计算做准备。

C. rem = b; / D. rem = q;：❌ 错误。逻辑完全错误，会导致后续计算结果全错。

大数除法：算完商后，rem 要留余数（rem %= b）。

第 1 题 有一个存储了 n个整数的线性表，分别用数组和单链表两种方式实现。在已知下标（或结点指针）的前提下，数组的随机访问是 O(1)， 而在链表中已知某结点的指针时，在该结点之后插入一个新结点的操作也是 O(1)。

【答案】√

【考纲知识点】

数组随机访问：数组是连续内存，通过下标直接计算地址，时间复杂度为 O(1)。

单链表后插操作：已知当前结点p，插入新结点s的操作为：

s->next = p->next;p->next = s;

仅需修改 2 个指针，无需遍历，时间复杂度为 O(1)。

数组 O (1) 随机访问，单链表已知结点后插 O (1)

第 2 题 若数组 a 已按升序排列，则下面代码可以正确实现 “在 a 中查找第一个大于等于 x 的元素的位置”。

【答案】√

【考纲知识点】lower_bound标准实现（左闭右开区间）

【解析】

1、区间定义：[l, r)，初始l=0, r=a.size()覆盖整个数组。

2、逻辑：

若a[mid] >= x：目标位置在[l, mid]，因此r = mid。

若a[mid] < x：目标位置在[mid+1, r)，因此l = mid + 1。

3、循环终止时l == r，返回的l就是第一个≥x的位置，完全符合std::lower_bound的标准实现。

lower_bound标准实现：左闭右开，a[mid]>=x则r=mid，否则l=mid+1

第 3 题 快速排序只要每次都选取中间元素作为枢轴，就一定是稳定排序。

【答案】×

【考纲知识点】排序稳定性：相等元素的相对顺序在排序后保持不变。

【解析】

第 4 题 若某算法满足递推式：T(n)=2T(n/2) + O(n)，则其时间复杂度为 O(nlogn)。

【答案】√

【考纲知识点】主定理（Master Theorem）

【解析】

对于递推式 T(n) = aT(n/b) + f(n)：

• 1、本题中：a=2, b=2, f(n)=O(n)
• 2、计算：n^{log_b a} = n^{log_2 2} = n^1 = n，与f(n)同阶
• 3、根据主定理，时间复杂度为 O(n log n)
• 4、对应经典算法：归并排序、分治求最大子段和等，时间复杂度均为O(n log n)。
• 【总结】递推式T(n)=2T(n/2)+O(n) → 时间复杂度O(n log n)

第 5 题 在一个数组中，如果两个元素 a[i] 和 a[j] 满足 i < j 且 a[i] > a[j] ，则 a[i] 和 a[j] 是一个逆序对。

下面代码可以正确统计数组 a 区间 [l,r] 内的逆序对总数。

【答案】×

【考纲知识点】归并排序统计逆序对

1. 正确原理

要使用归并排序统计逆序对，必须遵循分治三步走：

1. (1)分解：将数组拆分为左右两部分。
2. (2)治理：递归排序左右两部分，并递归统计左右内部的逆序对。
3. (3)合并：合并两个有序数组，并统计跨左右区间的逆序对。

2. 合并时的统计逻辑

当左数组 [l,m] 和右数组 [m+1,r] 均为升序时：

• 若 a[i]>a[j]，则左数组中从 i 到 m 的所有元素都大于 a[j]。
• 贡献的逆序对数量为：m−i+1。
• 代码逻辑：cnt += (m - i + 1); 这部分是完全正确的。

【解析】

• 这是本题的唯一考点，也是最容易踩的坑：

  ❌ 缺少递归排序步骤！

  题目给出的代码片段只是 merge_count 函数（合并逻辑），但它没有包含递归排序的部分。

• (1)代码中缺少了 merge_count(a, l, m) 和 merge_count(a, m+1, r)。
• (2)没有递归排序，就意味着左右区间 [l,m] 和 [m+1,r] 是无序的。

• (3)既然数组无序，那么 a[i] <= a[j] 的比较逻辑就无法保证双指针的有序移动，统计出来的逆序对数量完全是错误的。

✅ 正确代码（完整分治流程）

long long cnt = 0;// 1. 先写递归分解（排序）voidmerge_sort(vector<int>& a, int l, int r){    if (l >= r) return;    int m = (l + r) / 2;    merge_sort(a, l, m);     // 排序左区间    merge_sort(a, m+1, r);   // 排序右区间    merge_count(a, l, m, r);  // 2. 再合并并统计逆序对}// 3. 题目中的代码是这里的一部分，它是正确的，但不能单独存在voidmerge_count(vector<int>& a, int l, int m, int r){    int i = l, j = m + 1;    // ... 临时数组 tmp 逻辑需要补充 ...    while(i <= m && j <= r) {        if(a[i] <= a[j]) i++;        else {            cnt += (m - i + 1); // 这行逻辑本身正确            j++;        }    }    // ... 回填剩余元素 ...}

【总结（考试必背）】

1. 统计逆序对
   1、必须使用归并排序（分治法）。     
2. 2、代码结构必须包含：递归分解 + 合并统计。
3. 3、只有合并代码（题目片段），没有递归排序，不能正确统计。

原代码混淆了计数与合并的逻辑，且尾部累加错误。掌握归并排序统计逆序对的关键在于：

1、在合并过程中，只有当左半元素大于右半元素时才计数。

2、必须同时完成排序，以保证子数组有序，从而正确应用计数公式。

3、使用辅助数组暂存合并结果，最后拷贝回原数组。

第 6 题 唯一分解定理保证：若一个数未被任何不超过其平方根的质数筛去，则它一定是质数。

【答案】√

【考纲知识点】核心知识点：唯一分解定理 & 质数判断

【解析】定理内容：任何一个大于 1 的自然数 N，都可以唯一分解成有限个质数的乘积。

第 7 题 假设数组a 的值域范围是 D，以下程序的时间复杂度是 O(nlogn+nlogD)。

【答案】√

【考纲知识点】二分答案 + 排序 + 贪心

【解析】

算法步骤：

1、排序：O(nlogn)。

2、二分：二分次数为 O(logD)（值域范围 D）。

3、check 验证：每次遍历数组，O(n)。

第 8 题 若一个问题满足最优子结构性质，则一定可以用贪心算法得到最优解。

【答案】×

【考纲知识点】

贪心算法与动态规划

• 最优子结构：问题的最优解包含子问题的最优解。这是贪心和 DP 的共同前提。
• 贪心算法的条件：除了最优子结构，还必须满足 贪心选择性质

【解析】

反例：

（1）带权图的最短路径：满足最优子结构，但不能用贪心（负权边会失效）。

（2）0-1 背包：满足最优子结构，但不能用贪心（拿物品 1/2 无法凑最优）。

结论：只有最优子结构 不一定 能用贪心。

第 9 题 线性筛相比埃氏筛的核心改进在于：埃氏筛中一个合数可能被多个质数重复标记，线性筛通过"每个合数只被其最大质因子筛去"的策略，保证每个合数恰好被标记一次，从而实现 O(n)的时间复杂度。

【答案】×

【考纲知识点】

1、埃氏筛：每个合数可能被多个质数筛去（如 12 会被 2,3 筛），复杂度 O(nloglogn)。

2、线性筛：保证每个合数只被筛一次。

（1）核心策略：每个合数只被其 最小质因子 筛去。

（2）实现方式：if (i % primes[j] == 0) break; 保证 primes[j] 不超过 i 的最小质因子，从而让 i×primes[j] 的最小质因子为 i。

3、结论：代码逻辑描述 错误，应该是 “最小质因子”（或 “最大质因子” 说法需对应具体实现，但考试常考最小质因子优化）。通常这类判断题认为此描述 错误。

【解析】（注：部分教材认为是维护最小质因子，这里按常规考试逻辑判错）

第 10 题 任何递归程序都可以改写为等价的非递归程序，但改写后的非递归程序一定需要显式地使用栈来模拟递归调用过程。

【答案】×

【考纲知识点】

1、正确性：任何递归算法都可以转化为非递归（利用 栈 模拟函数调用栈帧）。

【解析】题目说 “一定需要显式使用栈” 是错误的，因为尾递归可优化为循环。

3.1 编程题 1

试题名称：有限不循环小数

时间限制：1.0 s

内存限制：512.0 MB

【考纲知识点】

终止数的数学定义

题目定义：若 1/a 是有限不循环小数（有限小数），则称 a 为终止数。

根据分数化小数的数学定理：

本题中 1/a  本身就是最简分数，因此 a 是终止数的充要条件是：a 的质因数仅由 2 和 5 组成 。

输入区间[2,11]，符合条件的数：

共 5 个，与样例输出一致。

【解题思路】

方法 1：暴力枚举（适合 10^6 规模）

遍历区间 [L,R] 内的每个数 a，判断其是否仅含质因数 2 和 5：

• (1)对 a 反复除以 2，直到无法整除；
• (2)再反复除以 5，直到无法整除；
• (3)若最终结果为 1，则 a 是终止数，否则不是。时间复杂度：O(R−L+1⋅loga)，对于 R=10^6 完全可接受。

方法 2：预处理打表（更高效）

提前预处理 1∼10^6 内所有数，标记是否为终止数，再用前缀和数组快速查询区间 [L,R] 的数量。时间复杂度：预处理 O(n)，查询 O(1)，适合多次查询。

【参考程序】版本 1：暴力枚举（代码简洁，适合单次查询）

#include<iostream>using namespace std;// 判断x是否为终止数：质因数仅含2和5boolisTerminating(int x){    // 先除尽可能多的2    while (x % 2 == 0) {        x /= 2;    }    // 再除尽可能多的5    while (x % 5 == 0) {        x /= 5;    }    // 剩余为1，说明仅含2和5的质因数    return x == 1;}intmain(){    ios::sync_with_stdio(false);    cin.tie(nullptr);    int L, R;    cin >> L >> R;    int ans = 0;    for (int a = L; a <= R; ++a) {        if (isTerminating(a)) {            ans++;        }    }    cout << ans << endl;    return 0;}

#include<iostream>#include<vector>using namespace std;const int MAXN = 1e6 + 5;vector<bool> is_term(MAXN, false);vector<int> pre_sum(MAXN, 0);// 预处理1~MAXN的终止数标记voidpreprocess(){    // 生成所有仅含2和5质因数的数，并标记    for (long long x = 1; x < MAXN; x *= 2) {        for (long long y = x; y < MAXN; y *= 5) {            is_term[y] = true;        }    }    // 计算前缀和：pre_sum[i] = 1~i中终止数的数量    for (int i = 1; i < MAXN; ++i) {        pre_sum[i] = pre_sum[i-1] + (is_term[i] ? 1 : 0);    }}intmain(){    ios::sync_with_stdio(false);    cin.tie(nullptr);    preprocess(); // 预处理    int L, R;    cin >> L >> R;    // 区间[L,R]的数量 = pre_sum[R] - pre_sum[L-1]    cout << pre_sum[R] - pre_sum[L-1] << endl;    return 0;}

【代码说明】

版本 1（暴力）

• （1）核心函数 isTerminating：通过反复除以 2、5，判断剩余是否为 1，逻辑直观易懂。
• （2）时间复杂度：对于 R=10^6，总运算量约 10^6×20（log210^6≈20），运行极快。

版本 2（打表）

• （1）预处理逻辑：直接生成所有 2^x⋅5^y 形式的数（仅含 2、5 质因数），标记为终止数，避免了重复判断。
• （2）前缀和数组：pre_sum[i] 存储 1∼i 的终止数总数，查询区间 [L,R] 时直接做差，时间复杂度 O(1)。
• （3）优势：预处理仅需执行一次，适合多次查询场景，时间复杂度更低。

3.2 编程题 2

试题名称：找数

时间限制：1.0 s

内存限制：512.0 MB

3.2.1 题目描述

给定一个包含 n个互不相同的正整数的数组 A与一个包含m 个互不相同的正整数的数组 B，请你帮忙计算有多少数在数组A 与 数组 B中均出现。

【考纲知识点】

本题最优选择

数据范围 n,m≤10^5，暴力枚举 O(nm) 会超时，因此选择哈希表法（时间复杂度最优，实现简单）或排序 + 双指针法（空间复杂度最优）。

【解题思路】

解题思路1（哈希表法，最常用）

(1)将数组 A 的元素存入哈希集合：利用unordered_set的O(1)查找特性，快速判断元素是否存在。

(2)遍历数组 B：逐个检查 B 中的元素是否在哈希集合中，若存在则计数 + 1。

(3)输出计数结果：最终计数即为两个数组交集元素的个数。

解题思路2（排序 + 双指针法，空间最优）

1、分别排序数组 A 和数组 B：时间复杂度O(nlogn+mlogm)。

2、双指针遍历：用i遍历 A，j遍历 B：

（1）若A[i] == B[j]：计数 + 1，i++，j++（元素互不相同，无需处理重复）。

（2）若A[i] < B[j]：i++（找更大的 A 元素匹配 B）。

（3）若A[i] > B[j]：j++（找更大的 B 元素匹配 A）。

3、输出计数结果。

【参考程序】

#include<iostream>#include<vector>#include<unordered_set>using namespace std;intmain(){    ios::sync_with_stdio(false);    cin.tie(nullptr); // 加速输入，避免大数据量超时    int n, m;    cin >> n >> m;    unordered_set<int> s;    // 读取数组A，存入哈希集合    for (int i = 0; i < n; ++i) {        int a;        cin >> a;        s.insert(a);    }    int ans = 0;    // 读取数组B，检查是否在集合中    for (int i = 0; i < m; ++i) {        int b;        cin >> b;        if (s.count(b)) {            ans++;        }    }    cout << ans << endl;    return 0;}

#include<iostream>#include<vector>#include<algorithm>using namespace std;intmain(){    ios::sync_with_stdio(false);    cin.tie(nullptr);    int n, m;    cin >> n >> m;    vector<int> A(n), B(m);    for (int i = 0; i < n; ++i) {        cin >> A[i];    }    for (int i = 0; i < m; ++i) {        cin >> B[i];    }    // 排序两个数组    sort(A.begin(), A.end());    sort(B.begin(), B.end());    int i = 0, j = 0, ans = 0;    // 双指针遍历    while (i < n && j < m) {        if (A[i] == B[j]) {            ans++;            i++;            j++;        } else if (A[i] < B[j]) {            i++;        } else {            j++;        }    }    cout << ans << endl;    return 0;}

版本 1（哈希表法）

1、核心优势：时间复杂度O(n+m)，是理论最优，适合105级别的大数据量，运行速度极快。

2、注意事项：

必须加ios::sync_with_stdio(false); cin.tie(nullptr);加速输入，否则大数据量会超时。

unordered_set的count()函数时间复杂度为O(1)，是判断元素存在的最优方式。

3、适用场景：空间充足、追求最快速度的场景。

版本 2（排序 + 双指针法）

1、核心优势：空间复杂度O(1)（仅需排序数组，无需额外存储），适合空间受限的场景。

2、注意事项：

排序时间复杂度O(nlogn+mlogm)，对于105数据量完全可接受。

双指针遍历时间复杂度O(n+m)，整体效率接近哈希表法。

3、适用场景：空间受限、不允许使用哈希表的场景。

数据范围适配：两种版本均支持ai,bi≤10^9，无需担心数值溢出（int在 C++ 中通常为 4 字节，可存储2×10^9以内的数，若需更大范围可改为long long）。

去重处理：题目保证数组内元素互不相同，因此无需额外去重；若数组存在重复元素，哈希表法会自动去重，双指针法需修改逻辑跳过重复元素。