GESP2025年03月Python五级试卷
从PDF导入：GESP2025年03月Python五级试卷
试卷题目预览
链表不具备的特点是（ ）。
双向链表中每个结点有两个指针域 prev 和 next ，分别指向该结点的前驱及后继结点。设 p 指向链表中的一个结点，它的前驱结点和后继结点均非空。现要求删除结点 p ，则下述语句中正确的是（ ）。
假设双向循环链表包含头尾哨兵结点，分别为head和tail，下面代码实现了一个空的双向循环链表，横线上应填的最佳代码是（ ）。
class ListNode:
def __init__(self, val=None):
self.data = val
self.prev = None
self.next = None
class LinkedList:
def __init__(self):
self.head = ListNode()
self.tail = ListNode()
_______________________
用以下辗转相除法求gcd(84, 60)的步骤中，第二次调用gcd()函数计算的数是（ ）。
def gcd(a, b):
big = max(a, b)
small = min(a, b)
if big % small == 0:
return small
return gcd(small, big % small)
根据唯一分解定理，下面整数的唯一分解是正确的（ ）。
下述代码实现素数表的线性筛法，横线上应填的最佳代码是（ ）。
def sieve_linear(n):
is_prime = [True] * (n + 1)
primes = []
if n < 2:
return primes
is_prime[0] = is_prime[1] = False
for i in range(2, n // 2 + 1):
if is_prime[i]:
primes.append(i)
j = 0
_____________________________________
is_prime[i * primes[j]] = False
if i % primes[j] == 0:
break
j += 1
return primes
在程序运行过程中，如果递归调用的层数过多，会因为（ ）引发错误。
对下面两个函数，说法错误的是（ ）。
def factorialA(n):
if n <= 1:
return 1
return n * factorialA(n - 1)
def factorialB(n):
if n <= 1:
return 1
res = 1
for i in range(2, n + 1):
res *= i
return res
下算法中，（ ）是不稳定的排序。
考虑以下快速排序算法，将数据从小到大排序，则横线上应填的最佳代码是（ ）。
def partition(arr, low, high):
pivot = arr[high]
i = low - 1
for j in range(low, high):
_________________________________
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1
def quick_sort(arr, low, high):
if low < high:
pi = partition(arr, low, high)
quick_sort(arr, low, pi - 1)
quick_sort(arr, pi + 1, high)
若用二分法在[1, 100]内猜数，最多需要猜（ ）次。
下面的python代码实现了二分查找算法，则横线上能填写的最佳代码是（ ）。
def binary_search(arr, left, right, target):
while left <= right:
_________________________
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
贪心算法的核心特征是（ ）。
函数def find_max(arr, low, high)计算数组中最大元素，（ ）正确实现了分治逻辑。
小杨编写了一个高精度乘法函数，则横线上应填写的代码为（ ）。
def multiply(a, b):
m, n = len(a), len(b)
c = [0] * (m + n)
for i in range(m):
for j in range(n):
c[i + j] += a[i] * b[j]
carry = 0
for k in range(len(c)):
————————————————————
c[k] = temp % 10
carry = temp // 10
while len(c) > 1 and c[-1] == 0:
c.pop()
return c
单链表中删除某个结点p(非尾结点)，但不知道头结点，可行的操作是将p的值设为p.next的值，然后删除p.next。（ ）
链表存储线性表时要求内存中可用存储单元地址是连续的。（ ）
线性筛相对于埃拉托斯特尼筛法，每个合数只会被它的最小质因数筛去一次，因此效率更高。（ ）
贪心算法通过每一步选择当前最优解，从而一定能获得全局最优解。（ ）
递归函数必须具有一个终止条件，以防止无限递归。（ ）
快速排序算法的时间复杂度与输入是否有序无关，始终稳定为O(n log n)。（ ）
归并排序算法的时间复杂度与输入是否有序无关，始终稳定为O(n log n)。（ ）
二分查找适用于对无序数组和有序数组的查找。（ ）
小杨有10元去超市买东西，每次挑价格最低的商品买，这体现了分治思想。（ ）
归并排序算法体现了分治算法，每次将大的待排序数组分成大小大致相等的两个小数组。（ ）
平均分配
时间限制：3.0 s
内存限制：512.0 MB
题面描述
小A有2n件物品，小B和小C想从小A手上买走这些物品。对于第i件物品，小B会以bi的价格购买，而小C会以ci的价格购买。为了平均分配这2n件物品，小A决定小B和小C各自只能买走恰好n件物品。你能帮小A求出他卖出这2n件物品所能获得的最大收入吗？
第一行，一个正整数n。第二行，2n个整数bi。第三行，2n个整数ci。
一行，一个整数，表示答案。
样例输入 3 1 3 5 6 8 10 2 4 6 7 9 11 样例输出 36 数据范围 对于所有测试点，保证1 ≤ n ≤ 10⁵，1 ≤ bi, ci ≤ 10⁹。
原根判断
时间限制：3.0 s
内存限制：512.0 MB
题面描述
小A知道，对于质数p而言，p的原根a是满足以下条件的正整数：1 ≤ a < p；a^phi(p) % p = 1；对于任意1 ≤ k < phi(p)均有a^k % p ≠ 1。其中x % y表示x除以y的余数。小A现在有一个整数a，请你帮他判断a是不是p的原根。
第一行，一个正整数T，表示测试数据组数。每组测试数据包含一行，两个正整数a, p。
对于每组测试数据，输出一行，如果a是p的原根则输出Yes，否则输出No。
样例输入 3 3 998244353 5 998244353 7 998244353 样例输出 Yes Yes No 数据范围 对于所有测试点，保证1 ≤ T ≤ 10，1 ≤ a < p ≤ 10¹²，p为质数。