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

一、单选题(每题2分,共30分)

第1题 链表不具备的特点是( )。

A.可随机访问任何一个元素

B.插入、删除操作不需要移动元素   

C.无需事先估计存储空间大小

D.所需存储空间与存储元素个数成正比

【答案】A

【解析】链表是非线性存储，顺序访问的存储结构，动态分配内存，需要从头节点遍历，不支持随机访问

第2题 双向链表中每个结点有两个指针域 prev和next，分别指向该结点的前驱及后继结点 。设 p指向链表中的 一个结点 ，它的前驱结点和后继结点均⾮空 。现要求删除结点p，则下述语句中正确的是（）  。

A.

B.

C.

D.

【答案】A

【解析】

A选项，让p后继的prev指向p前驱，让p前驱的next指向p后继，操作正确；

B选项，修改了p后继的next指针，而非prev指针，错误；

C选项，将p前驱的next指向自身，错误；

D选项，将p后继的prev指向自身，错误。

第3题 假设双向循环链表包含头尾哨兵结点(不存储实际内容)，分别为head和tail，链表中每个结点有两个指    针域 prev和next，分别指向该结点的前驱及后继结点 。下⾯代码实现了一个空的双向循环链表 ，横线上应填的最 佳代码是( )。

A.

B.

C.

D.

【答案】A

【解析】

A选项，head.next指向tail，tail.prev指向head，形成了头尾的连接，但还没有构成循环，因此是最接近正确的选择。

B选项，head.next和tail.prev都指向了自己，头尾哨兵未连接，错误。

C选项，head.next指向tail，tail.next指向head，没有设置prev，导致链表为单向，错误。

D选项，head.prev指向tail，tail.next指向head，形成了头尾的连接，但还没有构成循环，且连接方向相反，错误。

第4题用以下辗转相除法（欧⼏⾥得算法）求gcd(84, 60)的步骤中 ，第⼆次调用gcd()函数计算的数是（  ）。

A. 84和60

B. 60和24

C. 24和12

D. 12和0

【答案】B

【解析】第一次调用执行gcd(84, 60)：big = 84，small = 60，big % small = 24；第二次递归调用gcd(60, 24)。因此选择B选项。

第5题 根据唯一分解定理 ，下⾯整数的唯一分解是正确的（  ）。

A. 18 = 3 × 6

B. 28 = 4 × 7

C. 36 = 2 × 3 × 6

D. 30 = 2 × 3 × 5

【答案】D

【解析】唯一分解定理（Unique Factorization Theorem），又称算术基本定理（Fundamental Theorem of Arithmetic），它表明：每个大于1的自然数，要么本身是素数，要么可以唯一地分解为有限个素数的乘积（不考虑素因子的排列顺序）。选项A、B、C的因子都包含合数（6、4、6），可以继续分解。正确答案是D选项。

第6题 下述代码实现素数表的线性筛法筛选出所有小于等于n的素数  ,横线上应填的最佳代码是( )

A.  while j < len(primes) and j * primes[j] <= n:

B.  while j < len(primes) and i * primes[j] <= n:

C.  while j < len(primes) and j * primes[i] <= n:

D.  while i < len(primes) and i * primes[j] < n:

【答案】B

【解析】线性筛法是一种在O(n)时间复杂度内生成素数表的高效算法，其核心在于每个合数仅被其最小质因数标记一次。内层循环的作用是：使用当前遍历的整数i与已知的素数列表primes中的素数相乘来标记合数，同时要保证合数在小于等于n的范围内。先检查j是否小于len(primes)可以防止越界错误。

第7题 在程序运⾏过程中 ，如果递归调用的层数过多 ，会因为（  ）引发错误。 

A.系统分配的栈空间溢出

B.系统分配的堆空间溢出

C.系统分配的队列空间溢出

D.系统分配的链表空间溢出

【答案】A

【解析】栈（Stack）是系统为程序分配的内存区域，专门用于存储函数调用时的临时数据。栈空间容量有限，当递归调用层数太多，会超出容量导致栈溢出错误。

第8题 对下面两个函数 ，说法错误的是（  ）。

A.两个函数的实现的功能相同。

B.两个函数的时间复杂度均为O(n)。

C. factorialA采用递归方式。

D. factorialB采用递归方式。

【答案】D

【解析】两个函数的作用都是计算阶乘，factorialB的函数体没有调用自己，故不是递归。

第9题 下算法中，（  ）是不稳定的排序。

A.选择排序

B.插入排序

C.归并排序

D.冒泡排序

【答案】A

【解析】一个排序算法是否稳定，就是看相等的元素在排序前后的相对位置是否发生变化。选择排序可能将后面位置的相等元素移动到前面，因此是不稳定的。

第10题 考虑以下python代码实现的快速排序算法 ，将数据从小到大排序 ，则横线上应填的最佳代码是( )。

【答案】D

【解析】快速排序会从待排序的元素中选择一个基准值，然后将所有小于基准值的元素放在基准值左侧，大于基准值的元素放在基准值右侧，基准值固定，并递归的对两侧的元素排序。

横线处的代码需要将所有小于基准值的元素移动到数组左侧，具体来说：

1.if arr[j] < pivot：筛选出小于基准值的元素

2.i += 1：维护一个"较小元素区间"的右边界指针

3.交换操作：把符合条件的元素交换到"较小元素区间"的末尾

这个分区过程完成后：所有在i指针左侧的元素都<基准值，所有在i指针右侧的元素都>=基准值。

第11题 若用⼆分法在[1, 100]内猜数 ，最多需要猜（  ）次。

A. 100

B. 10

C. 7

D. 5

【答案】C

【解析】二分查找的最多次数为log2n，[1, 100]中，n = 100，log2(100)约等于6.65，向上取整为7。

第12题  下面的python代码实现了二分查找算法，在数组arr找到目标元素target的位置 ，则横线上能填写的 最佳代码是（  ）。

A.

B.

C.

D.

【答案】A

【解析】为了避免left+right溢出，一般使用left + (right - left) // 2。

第13题  贪心算法的核心特征是（  ）。

A.总是选择当前最优解

B.回溯尝试所有可能

C.分阶段解决子问题

D.总能找到最优解

【答案】A

【解析】贪心算法的核心在于每一步都选择当前最优，不回溯、不全局规划。B是回溯算法，C是分治算法，D选项贪心算法不一定总能找到最优解，只有满足贪心选择和最优子结构时才能找到最优解。

第14题  函数 def find_max(arr, low, high): 计算数组中最大元素 ，其中数组 arr从索引low到high，( )  正确实现了分治逻辑。

【答案】D

【解析】使用分治法计算最大值，首先将区间[low, high]，划分为[low, mid] 和[mid + 1, high]两个子区间，然后递归求解子区间的最大值，最后用两个最大值比较大小，返回最大的一个。A、B、C选项区间划分错误，且A选项出现语法错误，正确答案是D选项。

第15题小杨编写了一个如下的⾼精度乘法函数 ，则横线上应填写的代码为（  ）。

【答案】B

【解析】当前位c[k]的值需要加上前一位的进位carry，才能计算当前位的temp，正确答案是B。

二、判断题 (每题2分, 共20分)

第1题 单链表中删除某个结点 p (非尾结点)，但不知道头结点 ，可⾏的操作是将 p的值设为p.next的值 ，然后删除 p.next。

【答案】正确

【解析】此方法通过覆盖p的值为p.next的值，再删除p.next，逻辑等价于删除p结点。

第2题 链表存储线性表时要求内存中可用存储单元地址是连续的。

【答案】错误

【解析】链表的核心特点：结点通过指针链接，存储单元地址不要求连续。

第3题 线性筛相对于埃拉托斯特尼筛法 ，每个合数只会被它的最小质因数筛去一次， 因此效率更高 。

【答案】正确

【解析】线性筛：时间复杂度O(n)，每个合数仅被标记一次。

埃氏筛：时间复杂度O(nloglogn)，存在重复标记（如12会被2和3重复标记）。

第4题 贪心算法通过每一步选择当前最优解 ，从而一定能获得全局最优解。

【答案】错误

【解析】贪心算法的局限性：仅当问题满足贪心选择性质和最优子结构时才能得到全局最优解。

第5题 递归函数必须具有一个终止条件， 以防止无限递归。

【答案】正确

【解析】递归必须有终止条件，否则导致栈溢出。

第6题 快速排序算法的时间复杂度与输入是否有序无关 ，始终稳定为O(nlogn)。

【答案】错误

【解析】当输入已有序且基准选择不当（如固定选第一个元素），时间复杂度退化为O(n^2)。

第7题 归并排序算法的时间复杂度与输入是否有序无关 ，始终稳定为O(nlog n) 。

【答案】正确

【解析】无论输入是否有序，均需完整执行分解和合并操作，时间复杂度恒为O(nlogn)。

第8题 ⼆分查找适用于对无序数组和有序数组的查找。

【答案】错误

【解析】数组必须有序，否则无法通过与比较中间值缩小搜索范围。

第9题小杨有10元去超市买东西 ，每个商品有各自的价格 ，每种商品只能买1个 ，小杨的目标是买到最多数量的商品 。小杨采用的策略是每次挑价格最低的商品买 ，这体现了分治思想。

【答案】错误

【解析】小杨的策略属于贪心算法。

第10题  归并排序算法体现了分治算法 ，每次将大的待排序数组分成大小大致相等的两个小数组 ，然后分别对两个小数组进行排序，最后对排好序的两个小数组合并成有序数组。

【答案】正确

【解析】归并的步骤：将数组分为两半，递归排序子数组，合并有序子数组，体现了分治。

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

3.1    编程题1

. 时间限制：1.0 s

. 内存限制：512.0 MB

3.1.1  平均分配

3.1.2   题目描述

小A有2n件物品 ，小B和小C想从小A⼿上买走这些物品 。对于第 i件物品 ，小B会以b_i的价格购买 ，而小C会 以 c_i的价格购买 。为了平均分配这 2n件物品 ，小A决定小B和小C各自只能买走恰好n件物品 。你能帮小A求出 他卖出这 2n件物品所能获得的最大收入吗？

3.1.3    输入格式

第一行，一个正整数 n。

第⼆行，2n个整数b₁, b₂,....,b_2n。

第三行，2n个整数c1 , c₂,....,c_2n。

3.1.4    输出格式

一行，一个整数 ，表示答案。

3.1.5    样例

3.1.5.1    输入样例1

3.1.5.2    输出样例1

3.1.5.3    输入样例2

3.1.5.4    输出样例2

3.1.6    数据范围

对于20%的测试点 ，保证 1 ≤ n ≤ 8。

对于另外20%的测试点 ，保证 0 ≤ b_i≤ 1 ，0 ≤ c_i≤ 1 。

对于所有测试点 ，保证 1 ≤ n ≤ 10⁵，0 ≤ b_i≤ 10⁹，o ≤ c_i≤ 10⁹。

【题目大意】

小A有2n件物品，需分配给小B和小C各n件。第i件物品卖给小B的收入为b_i，卖给小C的收入为c_i。求如何分配使总收入最大。

【考纲知识点】

模拟、排序

【思路分析】

假设所有物品默认卖给C，总收入为sum(c)。此时需从中选择n件改卖给B，使得总收益增加最多。计算每件物品 “卖给B比卖给C多赚的差价”，即d_i = b_i - c_i。选择差价最大的n件物品卖给B，其余卖给C。

【参考程序】

3.2    编程题2

. 时间限制：1.0 s

. 内存限制：512.0 MB

3.2.8    原根判断

3.2.9    题目描述

小A知道 ，对于质数 p而⾔，p的原根g是满⾜以下条件的正整数：

.   1 < g < p；

.  g^p-1mod p = 1 ；

对于任意1 ≤ i < P-1均有gⁱmod p≠1。

其中a modp表示a除以p的余数。

小A现在有一个整数a，请你帮他判断a是不是p的原根。

3.2.10    输入格式

第一行，一个正整数 T，表示测试数据组数。

每组测试数据包含一行，两个正整数 a,p。

3.2.11    输出格式

对于每组测试数据 ，输出一行，如果a是p的原根则输出Yes，否则输出 No 。

3.2.12    样例

3.2.12.5    输入样例1

3.2.12.6    输出样例1

3.2.13    数据范围

对于40%的测试点 ，保证 3 ≤ p≤ 10³。

对于所有测试点 ，保证 1 ≤ T ≤ 20 ，3 ≤ p ≤ 10⁹，1 < a < P，P为质数。

【题目大意】

给定整数a和质数p，判断a是不是p的原根。

【考纲知识点】

素数

【思路分析】

初始化变量：phi和v都初始化为p - 1。在数论中，对于质数p，其欧拉函数值phi(p) = p - 1 ，这里phi用于后续计算。

分解p - 1：通过循环从2到sqrt(phi) + 2遍历，检查v是否能被i整除。如果能整除，进入内层循环，不断将v除以i；同时检查fpw(a, phi // i, p)是否等于1，若等于1，说明存在小于p - 1的指数i使得a^i mod p = 1 ，a不是原根，输出No并返回。

特殊情况处理：如果循环结束后v大于1，说明p - 1存在大于sqrt(phi)的质因数，再检查a的phi // v次幂对p取模是否等于1。若等于1，同样输出No并返回。

原根判定：如果上述所有检查都通过，说明a满足原根的条件，输出Yes。

【参考程序】

策划：GESP技术委员会副主席 刘晓庆

技术支持：付琪元