GESP第13次认证真题解析|Python五级真题回顾

一、单选题（每题2分，共30分）

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

A. 在Python实现的单链表中，若已知任意结点对象的引用，则可以在O(1)时间内删除该结点。

B. Python 实现的循环链表中一定不存在值为None的引用属性。

C. 在Python实现的循环双链表中，尾结点对象的next属性值一定为None。

D. 在Python实现的带头结点的循环单链表中，判定链表是否为空只需判断头结点对象的next属性是否引用头结点自身（即head.next is head）。

【答案】D

【考纲知识点】单链表、双链表、循环链表

【解析】

A选项：单链表中若已知任意结点对象的引用，要删除该结点通常需要知道其前驱结点，找前驱需要从头遍历，时间复杂度为O(n)，错误。

B选项：如果是不带头结点的循环单链表且为空表，其头引用即为None，错误。

C选项：循环双链表的尾结点的next引用指向头结点，而不是None，错误。

D选项：带头结点的循环单链表中，当为空链表时，头结点的next恰好引用自己（即head.next is head），判断正确。

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

A.  

B.  

C.  

D.  

【答案】C

【考纲知识点】单链表、双链表、循环链表

【解析】在双向链表中结点p之前插入结点s，需要修改四个引用且不能丢失原有的前驱结点引用。首先处理新结点s的两端：s.next = p 以及s.prev = p.prev。接着修改原链表中的引用，必须先修改p的原前驱结点的后继：p.prev.next = s，最后修改p的前驱指向新结点：p.prev = s。只有C选项符合此逻辑过程。

第3题 下面函数删除单向链表中val == x 的节点，并且使用哑结点统一对头结点和中间节点的删除操作。横线处应填（ ）。

A. cur = cur.next

B. cur.next = cur.next.next

C.cur.next = None

D.cur.next = nullptr

【答案】B

【考纲知识点】单链表、双链表、循环链表

【解析】代码中通过建立哨兵结点dummy，并用变量cur遍历链表。当满足条件cur.next.val == x 时，表示cur的下一个结点即为需要被删除的结点。在单链表中删除该结点，应当将cur结点的next引用越过被删除的结点，直接指向被删结点的后继节点，即cur.next.next。因此横线处应填入cur.next = cur.next.next，选项B正确。

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

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

B.gcd(48,18) -> gcd(30,18) -> gcd(12,18)

C.gcd(48,18) -> gcd(18,30) -> gcd(30,6)

D.gcd(48,18) -> gcd(12,18) -> gcd(6,12)

【答案】A

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

【解析】根据所给的递归代码逻辑，若b != 0，则递归调用gcd(b, a % b)。对于初始调用gcd(48, 18)，因为18非0，会执行48 % 18 = 12，接着进入gcd(18, 12)；同理下一步为18 % 12 = 6，进入gcd(12, 6)；接着12 % 6 = 0，进入gcd(6, 0)。当参数b变为0时，达到递归终点并返回6。所以完整过程如A选项所示。

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

A.for j in range(len(primes+1)):

B.for j in range(len(primes)+1):

C.for j in range(len(primes)):

D.for j in range(len(primes)-1):

【答案】C

【考纲知识点】素数表的埃氏筛法和线性筛法

【解析】线性筛的核心原理是利用每个合数最小的质因子将其筛除。算法中内层循环用于遍历目前已经被发现并收集到primes列表中的质数。列表下标j从0开始，为了防止越界，j的范围必须对应质数列表当前的元素个数。Python的range函数左闭右开，因此使用for j in range(len(primes)): 能够恰好遍历当前所有质数，保证程序安全访问primes[j]。所以选C。

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

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

B. i*i 一定是质数

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

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

【答案】C

【考纲知识点】素数表的埃氏筛法和线性筛法

【解析】在埃氏筛法中，当我们遇到一个素数i时，需要将i的所有倍数标记为合数。对于形如k * i（其中k<i）的倍数，因为k小于i，那么这个数必然存在一个更小的素数因子。在算法之前的遍历过程中，这个数肯定已经被那个更小的素数筛去了，所以内层循环直接从i * i 开始即可避免重复标记。

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

A. 2

B. 3

C. 4

D. 5

【答案】B

【考纲知识点】二分答案（也称二分枚举法）

【解析】本题考察经典的“二分答案”模型（最大化最小值）。列表排序后为[1, 2, 4, 8, 9]，在其中选择k=3个元素使得相邻差值最大。当假定最小距离为3时，可以选择1、4、8（4−1≥3且8−4≥3），满足条件；假定距离为4时，选了1之后只能选8，选不够3个，不满足条件。因此最大满足要求的距离是3，选B。

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

A.r = mid

B.r = mid - 1

C.l = mid

D.l = mid + 1

【答案】A

【考纲知识点】二分查找

【解析】题目要求在升序列表中查找第一个大于等于x的元素位置（即lower_bound的逻辑）。在二分过程中，如果满足条件a[mid] >= x，说明当前的mid可能是目标位置，或者目标位置在mid的左侧。为了不漏掉这个可能的答案，右边界应该更新为mid，即r = mid。填r = mid - 1 会漏掉解，填左边界更新逻辑错误，这种写法也不会导致死循环。

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

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

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

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

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

【答案】D

【考纲知识点】递归

【解析】

A选项：每次递归都会消耗系统栈内存，层数过深确实会溢出。

B选项：尾递归优化可以让编译器或解释器重用当前栈帧，避免溢出，原理上可以，但Python并不支持尾递归优化，相较之下，D选项明显错误。

C选项：依据理论，所有递归问题都可用显式栈配合循环来转换为非递归实现。

D选项：栈溢出发生时（如Python引发RecursionError异常），往往意味着执行上下文的栈空间已耗尽，即便可以强行捕获，程序的原有控制流状态通常已经受损，不应视为一种正常的异常来继续执行核心代码，说法错误。

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

A.l = mid + 1 和r = mid - 1

B.r = mid - 1 和l = mid + 1

C.l = mid + 1 和r = mid

D.l = mid - 1 和r = mid + 1

【答案】A

【考纲知识点】二分答案（也称二分枚举法）

【解析】本题依然采用二分答案求最大可能长度。当check(a, m, mid) 为真时，说明长度为mid是可行的，我们要继续寻找有没有更大的长度。此时记录了最优解ans = mid，因此接下来的搜索范围可以安全地避开mid，转到[mid + 1, r]，故第一个空应填l = mid + 1。反之若不可行，则说明切得太长了，转到[l, mid - 1] 寻找，第二个空填r = mid - 1。选A。

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

A. O(n²)

B. O(nlogn)

C. O(logn)

D. O(n)

【答案】B

【考纲知识点】分治算法

【解析】该算法采用典型的分治思想，将规模为n的问题划分为两个规模为n2的子问题进行递归处理。而合并步骤中，为了计算跨越中点的最大子段和，代码向左和向右分别遍历了一遍当前区间的元素，合并操作的时间开销为O(n)。因此其递归时间复杂度表达式为T(n)=2T(n/2)+O(n)，根据主定理得出该算法的时间复杂度为O(nlogn)。

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

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

A. if A[i+1] <= B[j]:

B. if A[i] <= B[j+1]:

C. if A[i] <= B[j]:

D. if i < j:

【答案】C

【考纲知识点】分治算法（归并排序和快速排序）

【解析】这是归并排序中合并两个有序列表的经典过程。题目要求最终合并为从小到大的有序排行榜。因此当遍历时，应当比较A组和B组当前的元素大小，谁小就优先将谁放入结果列表中。为了保证相同元素时原有顺序不改变（稳定性），在A[i] <= B[j] 时选取前面列表的元素A[i]并将其对应的索引i后移。选项C符合逻辑。

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

A. O(n)

B. O(nlogn)

C. O(n²)

D. O(logn)

【答案】C

【考纲知识点】分治算法（归并排序和快速排序）

【解析】在快速排序中，若总是选取第一个元素作为枢轴（pivot），且给定列表已经是有序状态，那么在每次划分子列表时，pivot右边没有比它小的元素。这会导致划分产生的两个子列表长度极度不平衡，一个是0，另一个是n−1。此时递归树退化成了一条链式结构，递归深度达到n，每层的时间开销依然是O(n)，导致总时间复杂度退化为最坏情况O(n2)。

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

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

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

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

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

【答案】B

【考纲知识点】算法：排序概念和稳定性

【解析】A选项正确，冒泡和插入排序只在相邻元素间操作，不会改变相等元素的相对位置，所以稳定。

B选项错误，快速排序中枢轴交换的过程会导致不稳定，但归并排序在合并子列表时严格控制了相等元素的插入顺序，是典型的稳定排序算法。

C选项正确，插入排序在已有序时为O(n)；冒泡排序若采用“本轮无交换则提前结束”的优化，最好情况为O(n)。在常见教材语境下，冒泡排序最好复杂度通常指优化版，因此C可视为正确。

D选项正确，归并排序恒定对半分，时间复杂度固定。

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

A.rem = rem / b

B.rem = rem % b

C.rem = b

D.rem = q

【答案】B

【考纲知识点】数组模拟高精度除法

【解析】这道题使用列表模拟高精度被除数除以单精度除数的过程（此题旨在考察竖式除法原理）。在模拟竖式除法的每一位计算中，需要将“上一位的余数乘10再加上当前位数字”构成本次计算的新被除数rem。将新被除数整除除数b得到当前位的商q，而参与下一位运算的则是本次计算剩下的余数，因此通过rem = rem % b 获取新余数，B选项正确。

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

第1题 有一个存储了 n个整数的线性表，分别用Python列表（数组）和自定义单链表两种方式实现。在已知元素下标（或结点对象引用）的前提下，Python列表的随机访问操作时间复杂度为O(1)；而在Python实现的单链表中，已知某结点对象的引用时，在该结点之后插入一个新结点的操作时间复杂度也为O(1)。

【答案】√

【考纲知识点】单链表、双链表、循环链表

【解析】Python列表的底层通常由连续内存（如动态数组）实现，支持通过下标直接进行偏移计算获取元素，因此随机访问的时间复杂度是O(1)。在单链表中，如果不考虑查找前驱的时间，仅仅是在已知当前节点cur引用的基础上插入新结点s，只需执行s.next = cur.next; cur.next = s，操作与链表总长度无关，因此复杂度同样也是O(1)。描述正确。

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

【答案】√

【考纲知识点】二分查找

【解析】这是一个典型的求解下界（lowerBound）的二分查找算法实现。当a[mid] >= x 成立时，说明目标位置一定不会大于mid，所以应当把右边界收缩至当前位置即r = mid；当a[mid] < x 成立时，说明目标一定严格在mid的右边，因此左边界更新为l = mid + 1。该逻辑能正确处理并跳出循环。描述正确。

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

【答案】×

【考纲知识点】算法：排序概念和稳定性

【解析】排序算法稳定性的定义是指相等大小的元素在排序后能够保持原有相对顺序不变。快速排序的工作机制决定了它会把元素按照和枢轴的大小关系交换到两侧。不论选取哪个元素（包括中间元素）作为枢轴，这种远距离位置跳跃式的交换都有可能会打乱原本数值相等的两个元素的先后次序。所以快速排序本质上是不稳定的算法。

第4题 若某算法满足递推式：

T(n) = 2T(n/2) + O(n)

则其时间复杂度为O(nlogn)。

【答案】√

【考纲知识点】算法复杂度的估算（含多项式、指数、对数复杂度）

【解析】该递推关系式表明，算法将规模为n的大问题划分为了2个规模为n2的子问题进行求解，且在合并或拆分过程花费了额外的O(n)时间。根据时间复杂度分析的主定理（Master Theorem）或通过绘制递归树可推导：树的高度为logn，且每一层的操作代价总和均为O(n)。因此最终的时间复杂度为O(nlogn)。描述正确。

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

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

【答案】×

【考纲知识点】归并排序

【解析】该代码只有在[l,m]和[m+1,r]两个区间已经分别有序时，才能正确统计“跨越左右区间”的逆序对数量；但题目说的是统计数组区间[l,r]内的逆序对总数，代码既没有递归统计左右区间内部逆序对，也没有将左右区间合并成有序状态，因此不能正确统计总逆序对。

第6题 根据唯一分解定理，如果大于1的整数不能被任何不超其平方根的质数整除，那么n必定是质数。

【答案】√

【考纲知识点】唯一分解定理

【解析】根据数论中的唯⼀分解定理及素因数分解原理，如果一个大于1的整数n是合数，那么它一定可以分解为至少两个质因子的乘积，且这两个因子中必然至少存在一个较小因子是不大于n的。逆反地推论，如果n没有发现任何小于等于n的质因数来整除它，那就说明n没有除自身外的质因子，因此n一定是素数。描述正确。

第7题 假设数组 a的值域范围是D，以下程序的时间复杂度是

【答案】√

【考纲知识点】二分答案（也称二分枚举法）

【解析】程序先对数组排序，复杂度为O(nlogn)。随后在距离范围[0, a_sorted[-1] - a_sorted[0]]上进行二分。若值域范围为D，则二分次数为O(logD)。每次调用check都需要线性扫描数组，复杂度为O(n)。因此总复杂度为O(nlogn+nlogD)。

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

【答案】×

【考纲知识点】贪心算法

【解析】满足“最优子结构”仅仅是使得问题具备可以使用动态规划或贪心算法进行求解的前提条件。要保证贪心算法真正可以得出全局最优解，该问题还必须满足更严格的“贪心选择性质”，也就是在当前步骤做的每一步局部最优选择，未来一定能导向最终的全局最优。缺乏贪心选择性质时，只有使用动态规划去全局推导才是安全的。描述错误。

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

【答案】×

【考纲知识点】素数表的埃氏筛法和线性筛法

【解析】题目描述前半部分解释埃氏筛法的重复标记缺陷是正确的，并且线性筛（欧拉筛）的初衷也是为了保证每个数只被筛选一次进而实现严格的O(n)时间复杂度。但线性筛的正确实现策略是确保“每个合数只被其最小质因子筛除”而不是“最大质因子”。概念表述错误，判定为错。

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

【答案】×

【考纲知识点】递归

【解析】递归程序都可以改写为非递归程序，但不一定必须显式使用“栈”。对于简单的尾递归或某些具备特定数学递推规律的递归（例如求阶乘），完全可以直接利用简单的循环迭代（for或while）以及常数个中间变量来实现，根本不需要使用栈结构来模拟调用过程。描述过于绝对，判定为错。

三、编程题（每题25分，共50分）

1.3.1 编程题1

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

时间限制：1.0 s

内存限制：512.0 MB

1.3.1.1 题目描述

若1a可化为一个有限的，不循环的小数，则称a为终止数。

请你求出在L到R中终止数的数量。

1.3.1.2 输入格式

输入一行，包含两个整数L,R。

1.3.1.3 输出格式

输出一行，包含一个整数，表示L到R中终止数的数量。

1.3.1.4 样例

1.3.1.4.1 输入样例

2 11

1.3.1.4.2 输出样例

5

1.3.1.5 样例解释

在[2,11]终止数有2、4、5、8、10。

1.3.1.6 数据范围

保证1≤L≤R≤10⁶。

1.3.1.7 参考程序

【考纲知识点】初等数论

【解析】这道题的考点在于识别分数能够化为有限小数的充要数学规律。由于十进制的基数是10，根据数论原理，一个最简分数的分母如果仅仅包含素因子2和5，它就可以化为不循环的有限小数。代码遍历L到R之间的每一个数，利用不断除以2和5将这两个因子全部剔除，最后判断如果剩下的值等于1，就说明这是个终止数并累加答案。

1.3.2 编程题2

 试题名称：找数

 时间限制：1.0 s

内存限制：512.0 MB

1.3.2.1 题目描述

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

1.3.2.2 输入格式

第一行包含两个整数n,m。

第二行包含n个正整数a₁,a₂,⋯,a_n表示数组A。

第三行包含m个正整数b₁,b₂,⋯,b_m表示数组B。

1.3.2.3 输出格式

输出一个整数，表示在数组A与 数组 B中均出现的数的个数。

1.3.2.4 样例

1.3.2.4.1 输入样例

3 5

4 2 3

3 1 5 4 6

1.3.2.4.2 输出样例

2

1.3.2.5 样例解释

样例1中，4、3在数组A与B中均出现。

1.3.2.6 数据范围

对于40%的数据，保证1≤n,m≤1000。

对于100%的数据，保证1≤n,m≤10⁵，1≤a_i,b_i≤10⁹。

1.3.2.7 参考程序

【考纲知识点】二分查找/二分答案（也称二分枚举法）

【解析】本题需要在庞大数据量的列表A中寻找列表B里的元素。暴力遍历查询的时间复杂度为O(n×m)，会造成超时。正确且高效的做法是将其中一个列表（如列表A）预先通过sort()排序，其开销为O(nlogn)。然后在遍历列表B的过程中，采用二分查找的思想去查询列表A中是否存在相同的值，将单次查询时间降至O(logn)，整体时间复杂度降为O((n+m)logn)，满足百万级数据的限时要求。