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

CCF编程能力等级认证，英文名Grade Examination of Software Programming（以下简称GESP），由中国计算机学会发起并主办，是为计算机和编程学习者提供学业能力验证的平台。GESP旨在提升青少年计算机编程能力，培训机构编编程教育水平，推广和普及计算机和编程教育。

GESP考察语言为图形化（Scratch）编程、Python编程及C++编程，主要考察学生掌握相关编程知识和操作能力，熟悉编程各项基础知识和理论框架，通过设定不同等级的考试目标，让学生具备编程从简单的程序到复杂程序设计的编程能力，为后期专业化编程学习打下良好基础。

本次为大家带来的是2025年12月Python五级认证真题解析。

Python五级

2025年12月

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

1、对如下定义的循环单链表，横线处填写（ ）。

【答案】C【考纲知识点】单链表、双链表、循环链表【解析】本题考察循环链表的遍历。

1.判空处理：首先需要判断链表是否为空，如果head为None，则直接返回，避免后续访问报错。

2.指针初始化：遍历应该从头节点开始，因此需要将辅助指针p指向head。

3.循环结构：代码中使用while True配合break模拟了do-while循环（先打印后移动，直到回到头节点）。若p初始化为head.next（选项B），则会漏打头节点；若p.next = head（选项A）则是赋值操作而非初始化，且语法错误；选项D的判空条件不完整（单节点链表会被错误拦截）。综上，选项C正确。

2、区块链技术是比特币的基础。在区块链中，每个区块指向前一个区块，构成链式列表，新区块只能接在链尾，不允许在中间插入或删除。下面代码实现插入区块添加函数，则横线处填写（ ）。

A.

B.

C.

D.

【答案】B【考纲知识点】单链表、双链表、循环链表【解析】本题考察链表的尾部插入操作。

1.新节点属性：新区块的索引index应当是前一个区块（当前尾节点）的索引加1，即self.tail.index + 1。

2.前驱指针：新区块的prev指针应当指向当前的尾节点self.tail。

3.更新尾指针：新区块生成后，链表的tail引用需要更新为指向这个新区块。选项B完整实现了上述逻辑。A选项未更新tail且索引错误；C选项data+1逻辑不明；D选项错误地修改了原尾节点的data。

2、下面关于单链表和双链表的描述中，正确的是（ ）。

1. 双链表删除指定节点是O(1) ，单链表是O(1)

2. 双链表删除指定节点是O(n) ，单链表是O(1)

3. 双链表删除指定节点是O(1) ，单链表是O(n)

4. 双链表删除指定节点是O(n) ，单链表是O(n)

【答案】C【考纲知识点】单链表、双链表、循环链表【解析】本题考察链表操作的时间复杂度。

双链表：给定要删除的节点node，可以直接通过node.prev访问前驱节点，修改指针即可完成删除，时间复杂度为 。

单链表：给定要删除的节点node，无法直接获取前驱节点，必须从头遍历链表寻找node的前一个节点，最坏情况需要遍历整个链表，时间复杂度为 。故选C。

4、假设我们有两个数a =38和b = 14，它们对模m同余，即a≡b (mod m)。以下哪个值不可能是m？

A. 3

B.4

C.6

D.9

【答案】D【考纲知识点】初等数论【解析】a≡b (mod m)等价于a-b是m的倍数。38-14=24。m必须是24 的约数。24的约数有：1, 2, 3, 4, 6, 8, 12, 24。9不是 24 的约数，故选D。

5、下面代码实现了欧几里得算法，下面有关说法，错误的是（ ）。

A.gcd1()实现为递归方式。

B.gcd2()实现为迭代方式。

C.当a较大时，gcd1()实现会多次调用自身，需要较多额外的辅助空间。

D.当a较大时，gcd1()的实现比gcd2()执行效率更高。

【答案】D【考纲知识点】辗转相除法（欧几里得算法）【解析】A、B正确：gcd1递归，gcd2迭代。C正确：递归深度大时消耗栈空间。D错误：Python中函数调用开销大且无尾递归优化，递归版效率通常低于或等于迭代版，不会“显著更高”。

6、唯一分解定理描述的内容是（ ）。

A.任何正整数都可以表示为两个素数的和。

B.任何大于1的合数都可以唯一分解为有限个质数的乘积。

C.两个正整数的最大公约数总是等于它们的最小公倍数除以它们的乘积。

D.所有素数都是奇数。

【答案】B【考纲知识点】唯一分解定理【解析】唯一分解定理（算术基本定理）指出：任何大于1 的整数，要么本身是质数，要么可以唯一地分解为有限个质数的乘积。选项B 符合定义。A是哥德巴赫猜想；C是 GCD 与LCM 的关系公式，不是唯一分解定理；D是错误的（2是偶素数）。故选 B。

7、下述代码实现素数表的线性筛法，筛选出所有小于等于n的素数，则横线上应填的代码是( )。

A.is_prime[i * p] = False

B.is_prime[i] = False

C.is_prime[i * p] = True

D.is_prime[i + p] = False

【答案】A【考纲知识点】素数表的埃氏筛法和线性筛法【解析】线性筛法中，当前数i与已找到的素数p相乘得到合数i * p，需要将其标记为非素数。故填is_prime[i * p] = False。

8、下列关于排序的说法，正确的是( )。

A.快速排序是稳定排序

B.归并排序通常是稳定的

C.插入排序是不稳定排序

D.冒泡排序不是原地排序

【答案】B【考纲知识点】算法：排序概念和稳定性（四级）【解析】A错：快速排序不稳定。B对：归并排序在合并时遇到相等元素优先取左侧，保持相对位置，是稳定的。C错：插入排序是稳定的。D错：冒泡排序是原地排序。

9、下面代码实现了归并排序。下述关于归并排序的说法中，不正确的是（ ）。

A.归并排序的的平均复杂度是O(nlogn)。

B.归并排序需要O(n)的额外空间。

C.归并排序在最坏情况的时间复杂度是O(n²)。

D.归并排序适合大规模数据。

【答案】C【考纲知识点】分治算法（归并排序和快速排序）【解析】归并排序的性能稳定，最好、最坏、平均时间复杂度均为O(nlogn)，不会退化为O(n2)。C 说法错误。

10、下述python代码实现了快速排序算法，最差情况时间复杂度是（ ）。

A.O(n)

B.O(logn)

C.O(n²)

D.O(nlogn)

【答案】C【考纲知识点】算法复杂度的估算【解析】快速排序若每次选取的基准值都是当前最大或最小值（如数组已有序且选首元素为基准），递归深度为n，复杂度退化为O(n²)。

10、下面代码尝试在有序数组中查找第一个大于等于x 的元素位置。如果没有大于等于x 的元素，返回arr.size()。以下说法正确的是（ ）。

A.上述代码逻辑正确

B.上述代码逻辑错误，while循环条件应该用l <= r

C.上述代码逻辑错误，mid计算错误

D.上述代码逻辑错误，边界条件不对

【答案】A【考纲知识点】二分查找/二分答案【解析】lower_bound模板：左闭右开区间[0, len)。当arr[mid] >= x时，答案可能是 mid或更左，r = mid；否则l = mid + 1。逻辑完全正确。

12、小杨要把一根长度为L 的木头切成K 段，使得每段长度小于等于x。已知每切一刀只能把一段木头分成两段，他用二分法找到满足条件的最小x（x为正整数），则横线处应填写（ ）。

A.

B.

C.

D.

【答案】A【考纲知识点】二分查找/二分答案【解析】求满足条件的最小值。若check(mid)为真，说明可行，答案可能是mid或更小，收缩右边界r = mid；若不可行，说明太小，l = mid + 1。选A。

13、根据下面代码，以下说法正确的是（ ）。

A.上面两种实现方式的时间复杂度相同，都为O(n)

B.上面两种实现方式空间复杂度相同，都为O(1)

C.函数factorial1()的时间复杂度为O(2ⁿ)，函数factorial2() 的时间复杂度为O(n)

D.上面两种实现方式空间复杂度相同，都为O(n)

【答案】A【考纲知识点】算法复杂度的估算【解析】两种方式都执行n次乘法，时间复杂度均为O(n)。空间上递归为O(n)（栈），迭代为O(1)。A选项描述正确。

14、给定有n个任务，每个任务有截止时间和利润，每个任务耗时1 个时间单位、必须在截止时间前完成，且每个时间槽最多做1 个任务。为了在规定时间内获得最大利润，可以采用贪心策略，即按利润从高到低排序，尽量安排，则横线处应填写（ ）。

A.

B.

C.

D.

【答案】A【考纲知识点】贪心算法【解析】贪心策略：找到符合条件的空闲时间槽后，标记占用slot[t]=True，累加利润，并必须立即停止为该任务寻找槽位break，转而处理下一个任务。

15、下面代码实现了对两个数组表示的正整数的高精度加法（数组低位在前），则横线上应填写（ ）。

A.

B.

C.

D.

【答案】B【考纲知识点】数组模拟高精度加法【解析】高精度加法进位逻辑：当前位保留carry % 10，进位carry更新为carry // 10传入下一轮。

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

1、数组和链表都是线性表。链表的优点是插入删除不需要移动元素，并且能随机查找。

【答案】×【考纲知识点】单链表、双链表、循环链表【解析】链表不支持随机查找，访问第k个元素需要O(n)遍历。

2、假设函数gcd()函数能正确求两个正整数的最大公约数，则下面的 lcm(a，b)函数能正确找到两个正整数a和b 的最小公倍数。

【答案】√【考纲知识点】初等数论【解析】最小公倍数公式lcm(a,b)=|a·b|/gcd(a,b)正确。

3、在Python实现的单链表中，已知引用p指向要删除的节点（该节点不是尾节点），若想在O(1)时间复杂度内删除这个节点，可行的做法是：用p的后继节点p.next的值覆盖p自身的值，再用p的后继节点的next引用覆盖p的next引用，最后断开p的后继节点的引用以辅助垃圾回收（）

【答案】√【考纲知识点】单链表、双链表、循环链表【解析】通过复制后继节点的值和指针覆盖当前节点，可实现O(1)删除非尾节点（逻辑上删除了当前节点数据）。

4、在求解所有不大于n的素数时，线性筛法（欧拉筛）都应当优先于埃氏筛法使用，因为线性筛法的时间复杂度为O(n)，低于埃氏筛法的O(nloglogn)。

【答案】×【考纲知识点】素数表的埃氏筛法和线性筛法【解析】在Python 中，埃氏筛配合切片操作常数极小，对于中等范围数据往往比纯Python 实现的线性筛更快，不能一概而论。

5、二分查找仅适用于有序数据。若输入数据无序，当仅进行一次查找时，为了使用二分而排序通常不划算。

【答案】√【考纲知识点】二分查找/二分答案【解析】单次查找：线性查找O(n)，排序+二分O(nlogn)。只查一次不值得排序。

6、通过在数组的第一个、最中间和最后一个这3个数据中选择中间值作为枢轴（比较基准），快速排序算法可降低落入最坏情况的概率。

【答案】√【考纲知识点】分治算法（归并排序和快速排序）【解析】三数取中法选择基准，可避免有序或逆序输入的O(n²)最坏情况。

7、贪心算法在每一步都做出当前看来最优的局部选择，并且一旦做出选择就不再回溯；而分治算法将问题分解为若干子问题分别求解，再将子问题的解合并得到原问题的解。

【答案】√【考纲知识点】贪心算法【解析】描述正确。贪心是局部最优不回溯，分治是分解子问题合并。

第 8题 以下fib函数计算第n项斐波那契数（fib(0)=0, fib(1)=1），其时间复杂度为O(n)。

【答案】×

【考纲知识点】递归

【解析】该实现是朴素递归版本的斐波那契数计算。每次调用fib(n)会递归计算fib(n-1)和fib(n-2)，而这些子问题又会重复计算大量相同的子结果。递归调用树的规模呈指数增长，时间复杂度O(φn)，其中φ ≈ 1.618（即黄金分割比），而不是O(n)。若要达到O(n)的时间复杂度，需要使用循环或带记忆化的递归。因此题中说法错误，答案为×。

9、递归函数一定要有终止条件，否则可能会造成栈溢出。

【答案】√【考纲知识点】递归【解析】无终止条件的递归会无限进行，导致栈溢出。

10、使用贪心算法解决问题时，通过对每一步求局部最优解，最终一定能找到全局最优解。

【答案】×【考纲知识点】贪心算法【解析】贪心算法仅对满足贪心选择性质和最优子结构的问题有效，并不保证对所有问题都能得到全局最优解（如背包问题）。

三、编程题(每题25分，共50分)

编程题1

• 试题名称：数字移动

• 时间限制：3.0 s

• 内存限制：512.0 MB

题目描述

小A有一个包含N个正整数的序列A={A₁,A₂.....A_N}，序列A恰好包含号N/2对不同的正整数。形式化地，对于任意1≤i≤N，存在唯一一个j满足1≤j≤N,i≠J,A_i=A_j。

小A希望每对相同的数字在序列中相邻，为了实现这一目的，小A每次操作会选择任意i(1≤i≤N)，将当前序列的第i个数字移动到任意位置，并花费对应数字的体力。

例如，假设序列A={1,2,1,3,2,3)，小A可以选择i=2,将A₂=2移动到A₃=1的后面，此时序列变为(1,1,2,3,2,3)，耗费2点体力。小A也可以选择i=3.将A₃=1移动到A₂=2的前面，此时序列变为(1,1,2,3,2,3}，花费1点体力。

小A可以执行任意次操作，但他希望自己每次花费的体力尽可能小。小A希望你能帮他计算出一个最小的x，使得他能够在每次花费的体力均不超过x的情况下令每对相同的数字在序列中相邻。

输入格式

第一行一个正整数N，代表序列长度，保证N为偶数。

第二行包含N个正整数A1,A2.....AN，代表序列A。且对于任意1≤i≤N，存在唯一一个j满足1≤j≤N,i≠J,Ai=Aj。

数据保证小A至少需要执行一次操作。

输出格式

输出一行x，代表满足要求的x的最小值。

样例

输入样例

输出样例

数据范围

对于40%的测试点，保证1≤N,A_i≤100。

对于所有测试点，保证1≤N,A_i≤10⁵。

参考程序

解析

【考纲知识点】二分答案

【解析】

题目大意：给定N/2对正整数组成的序列，保证数对不重复，可以移动任意数到任意位置，最终使得相同的正整数都相邻，希望求出一个最小的移动数上限，在只移动不超过上限的情况下达成目标。

解法：

40%部分分可以采用枚举+验证的方法，枚举上限ans，验证该上限时能否达成目标；时间复杂度为O(N.max(A_i))

验证的逻辑：当力气上限是ans时，所有≤ans的数都可以任意移动，因此这些数必然可以相邻。验证的关键在于＞ans的数，这些数的位置是固定不能移动的。对于初始位置不相邻的>ans的一组数对，其之间所有≤ans的数都可以移走，但是如果有其他>ans的数不能移走，就证明力气上限ans无法达成，需要将ans变大，重新验证。例：(1 3 2 3)，两个3之间存在一个2。假设最大只能挪动1，则不论如何，两个3之间的2不会被挪动，最终无法完成任务。

实现方法为先用列表b按顺序存储所有大于上限的数，遍历列表b，如果相邻两项(b[i], b[i+1])不是相同的数，表明其中间有其他无法移动的数，判断任务失败；遍历完成没有提前终止循环，则证明任务成功。

100%满分做法可以发现，上限ans越大，可以移动的数越大，当上限=ans可以完成任务时，上限>ans一定也可以完成任务；反之，上限=ans不可以完成任务时，上限<ans一定也不可以完成任务，存在单调性，因此可以使用二分枚举上限ans，时间复杂度优化为O(N·log(max(a_i)))。

编程题2

• 试题名称：相等序列

• 时间限制：3.0 s

• 内存限制：512.0 MB

题目描述

小A有一个包含N个正整数的序列A={A1,A2.....AN}。小A每次可以花费1个金币执行以下任意一种操作:

·选择序列中一个正整数Ai(1≤i≤N)，将Ai变为Ai×P，P为任意质数;

·选择序列中一个正整数Ai(1≤i≤N)，将Ai变为Ai/P，P为任意质数，要求Ai能被P整除。

小A想请你帮他计算出令序列中所有整数都相同，最少需要花费多少金币。

输入格式

第一行一个正整数N，含义如题面所示。第二行包含N个正整数A₁,A₂.....A_N，代表序列A。

输出格式

输出一行，代表最少需要花费的金币数量。

样例

输入样例

输出样例

数据范围

参考程序

解析

【考纲知识点】贪心、数论

【解析】

题目大意：给定N个正整数，每次操作可以将任意一个数乘或除以一个质数P（除法要求整除），花费1金币。求使序列中所有数字相等所需的最小花费。

解法：

根据算术基本定理，任何正整数都可以拆成一堆质数的乘积（（比如12=2²×3¹）。题目里的“乘除质数”，其实就是增加或减少某个质因数的个数（指数）。比如把12变成24，就是多乘了一个2，指数从2²变为2³，花费1。而不同质数之间互不干扰，我们可以把每个质数分开单独处理。

关键问题：对于某一个质数（比如2），假设这N个数里分别包含它的个数是：0个、2个、5个（即20,22,25）。我们要把这些个数统一变成同一个数k，使得总的变化步数最少。这个是经典的“货仓选址”问题，答案是选中位数。

实现步骤：

1.分解：把输入的N个数全部进行质因数分解。

2.统计：对于出现的每一个质数（如2, 3, 5...），记下它在每个数字里的指数。注意：如果某个数没有这个质因数，指数就是0，这个0也要算进去！

3.计算：对每种质数的所有指数找中位数，计算所有指数变成这个中位数需要的步数，最后全部加起来就是答案。