GESP Python 编程五级 · 2026 年 6 月卷

假设head不为空，下面是实现单向循环链表在头节点后插入新节点的代码，横线处应填入（）。 1 class Node: 2 def __init__(self, val): 3 self.val = val 4 self.next = None 5 def insert_after_head(head, x): 6 new_node = Node(x) 7 ____________________

• A.new_node.next = head.next head.next = new_node
• B.new_node.next = head head.next = new_node
• C.head.next = new_node new_node.next = head
• D.new_node.next = head.next; head = new_node

下面代码遍历并输出一个循环单链表，其中head指向链表的第一个节点，横线处应填入的是（）。 1 class Node: 2 def __init__(self, val): 3 self.val = val 4 self.next = None 5 def printList(head): 6 if head is None: 7 return 8 p = head 9 _______________________ 10 print()

• A.while p is not None: print(p.val, end=" ") p = p.next
• B.while p.next is not None: print(p.val, end=" ") p = p.next
• C.while True: print(p.val, end=" ") p = p.next if p == head: break
• D.while p: print(p.val, end=" ") p = p.next

双链表结点定义如下，若要删除双链表中的中间结点（非首尾节点）p，写法正确的是（）。 1 class Node: 2 def __init__(self, val): 3 self.val = val 4 self.prev = None 5 self.next = None

• A.p.prev.next = p.next p.next.prev = p.prev del p
• B.p.next.prev = p.next p.prev.next = p.prev del p
• C.p.prev = p.next p.next = p.prev del p
• D.p.next.next = p.prev p.prev.prev = p.next del p

使用如下欧几里得算法求gcd(105, 45)时，函数gcd(a, b)的递归调用序列正确的是（）。 1 def gcd(a, b): 2 return a if b == 0 else gcd(b, a % b)

• A.gcd(105, 45) -> gcd(45, 60) -> gcd(60, 15) -> gcd(15, 0)
• B.gcd(105, 45) -> gcd(45, 15) -> gcd(15, 0)
• C.gcd(105, 45) -> gcd(60, 45) -> gcd(15, 45)
• D.gcd(105, 45) -> gcd(15, 45) -> gcd(15, 0)

下面代码实现线性筛（欧拉筛），以筛选出n以内的所有素数。横线处的代码应为（）。 1 def sieve(n): 2 is_prime = [True] * (n + 1) 3 primes = [] 4 if n >= 0: 5 is_prime[0] = False 6 if n >= 1: 7 is_prime[1] = False 8 for i in range(2, n + 1): 9 if is_prime[i]: 10 primes.append(i) 11 j = 0 12 while j < len(primes) and i * primes[j] <= n: 13 is_prime[i * primes[j]] = False 14 if ________________: # 在此处填入代码 15 break 16 j += 1 17 return primes

• A.i % primes[j] == 0
• B.primes[j] % i == 0
• C.i % primes[j] != 0
• D.i == primes[j]

下面关于埃氏筛法的说法正确的是（）。

• A.每个合数只会被筛掉一次
• B.从每个素数出发，把它的倍数标记为合数
• C.只能判断一个数是不是偶数
• D.不能求出素数表

下面代码实现了计算 x^n 的快速幂算法，该算法体现的编程思想是（）。 1 def power(x, n): 2 if n == 0: 3 return 1 4 res = power(x, n // 2) 5 if n % 2 == 0: 6 return res * res 7 else: 8 return res * res * x

• A.枚举
• B.贪心
• C.分治
• D.模拟

下面代码用于统计n中因子2出现了多少次。若n = 40，输出是（）。 1 n = 40 2 cnt = 0 3 while n % 2 == 0: 4 cnt += 1 5 n = n // 2 6 print(cnt)

• A.1
• B.2
• C.3
• D.4

在一个有序数组中查找第一个大于或等于x的元素位置，横线处应填写（）。 1 def lowerBound(a, x): 2 l = 0 3 r = len(a) 4 while l < r: 5 mid = l + (r - l) // 2 6 if a[mid] >= x: 7 ________________ # 在此处填入代码 8 else: 9 l = mid + 1 10 return l

• A.r = mid + 1
• B.r = mid - 1
• C.r = mid
• D.l = mid

有若干根木头，长度存于 wood。每切一刀可以把一段木头分成两段。函数 check(wood, K, x) 返回：用不超过 K 刀，能否使所有木段长度都不超过 x。下面代码使用二分答案查找最小可行的 x，横线处应填（）。 1 def binary_cut(wood, K): 2 l = 1 3 r = 0 4 for length in wood: 5 r = max(r, length) 6 while l < r: 7 mid = l + (r - l) // 2 8 if check(wood, K, mid): 9 ________________ # 在此处填入代码 10 else: 11 l = mid + 1 12 return l

• A.r = mid + 1
• B.r = mid
• C.l = mid
• D.r = mid - 1

下面代码段实现了快速排序的划分操作（以首元素为基准），横线处代码应填入（）。 1 def partition(arr, low, high): 2 pivot = arr[low] 3 i = low 4 j = high 5 while i < j: 6 while i < j and arr[j] >= pivot: 7 j -= 1 8 while i < j and arr[i] <= pivot: 9 i += 1 10 if i < j: 11 arr[i], arr[j] = arr[j], arr[i] 12 ________________ # 在此处填入代码 13 return i

• A.arr[low], arr[high] = arr[high], arr[low]
• B.arr[low], arr[i] = arr[i], arr[low]
• C.arr[i], arr[high] = arr[high], arr[i]
• D.arr[i] = pivot

下面哪句话最符合归并排序的思想？（）

• A.每次选择最小元素放到前面
• B.将数组分成两半分别排序，再合并两个有序部分
• C.相邻元素两两交换
• D.从左到右把元素插入有序区

在对长度为 n(n ≥ 1) 的数组进行归并排序的过程中，mergeArray 函数（合并两个有序子数组的操作）被调用的次数是（）。 1 MAXN = 100005 2 a = [0] * MAXN 3 tempArr = [0] * MAXN 4 def mergeArray(left, mid, right): 5 i = left 6 j = mid + 1 7 k = left 8 while i <= mid and j <= right: 9 if a[i] <= a[j]: 10 tempArr[k] = a[i] 11 i += 1 12 else: 13 tempArr[k] = a[j] 14 j += 1 15 k += 1 16 while i <= mid: 17 tempArr[k] = a[i] 18 i += 1 19 k += 1 20 while j <= right: 21 tempArr[k] = a[j] 22 j += 1 23 k += 1 24 for p in range(left, right + 1): 25 a[p] = tempArr[p] 26 def mergeSort(left, right): 27 if left >= right: 28 return 29 mid = left + (right - left) // 2 30 mergeSort(left, mid) 31 mergeSort(mid + 1, right) 32 mergeArray(left, mid, right)

• A.n − 1
• B.log n
• C.n log n
• D.2n

小杨在学校义卖会上负责打包“零食盲盒”。每个盲盒重量不同，快递盒最多承重 limit 克，每个快递盒最多装两个盲盒。为了尽量少用快递盒，他采用如下策略：（1）每次把最轻的盲盒和最重的盲盒尝试放在一起；（2）如果两者重量之和不超过 limit，就一起装；（3）否则，只能让最重的盲盒单独装一盒。下面代码用于计算最少需要多少个快递盒，则横线处应填入的是（）。 1 def minBoxes(w, limit): 2 w.sort() 3 l = 0 4 r = len(w) - 1 5 boxes = 0 6 while l <= r: 7 if w[l] + w[r] <= limit: 8 __________ # 在此处填入代码 9 else: 10 r -= 1 11 boxes += 1 12 return boxes

• A.l += 1
• B.r -= 1
• C.l += 1 r -= 1
• D.boxes -= 1

高精度减法中，假设两个高精度数按低位在前存储，且已经保证被减数不小于减数。下面处理借位逻辑代码中横线处应填入（）。 1 if a[i] < b[i]: 2 a[i + 1] -= 1 3 ________________ 4 t = a[i] - b[i]

• A.a[i] += 10
• B.a[i] -= 10
• C.b[i] += 10
• D.a[i] = a[i + 1] + 10

数组的存储空间在物理上通常是连续的，而链表的结点可以存储在不连续的内存空间中。

带哨兵头尾节点的双向循环链表，在表头插入节点p，以下四步操作无论什么顺序执行结果都正确。 1 # 1 2 p.next = head.next 3 # 2 4 p.prev = head 5 # 3 6 head.next.prev = p 7 # 4 8 head.next = p

对任意正整数a、b，以下两种写法的gcd函数返回值完全相同。 1 def gcd1(a, b): 2 return gcd1(b, a % b) if b else a 3 def gcd2(a, b): 4 while b: 5 t = b 6 b = a % b 7 a = t 8 return a

在归并排序的合并操作中，如下代码片段可以正确地将两个已排序的子数组L和R合并回原数组arr中。 1 def merge(arr, left, mid, right): 2 n1 = mid - left + 1 3 n2 = right - mid 4 L = [0] * n1 5 R = [0] * n2 6 for i in range(n1): 7 L[i] = arr[left + i] 8 for j in range(n2): 9 R[j] = arr[mid + 1 + j] 10 i = 0 11 j = 0 12 k = left 13 while i < n1 and j < n2: 14 if L[i] <= R[j]: 15 arr[k] = L[i] 16 i += 1 17 else: 18 arr[k] = R[j] 19 j += 1 20 k += 1 21 while i < n1: 22 arr[k] = L[i] 23 i += 1 24 k += 1 25 while j < n2: 26 arr[k] = R[j] 27 j += 1 28 k += 1

分治法通常将一个规模较大的问题拆分为若干个规模较小、结构相似的子问题，分别求解后再合并子问题的结果。

贪心算法只要每一步选择当前最优解，就一定能得到全局最优解。

二分查找不仅可以应用于有序数组，也可以在不增加时间复杂度的情况下应用于有序的单链表，因为链表也支持 O(1) 时间内的随机访问。

以下函数f1的时间复杂度比函数f2的更高。 1 def f1(n): 2 i = 1 3 while i < n: 4 i *= 2 5 def f2(n): 6 if n <= 1: 7 return 8 f2(n - 1) 9 f2(n - 1)

唯一分解定理表明，任何一个大于 1 的自然数都可以唯一地分解为若干个质数的乘积，如果不考虑质因数的顺序，这种分解方式是唯一的。

归并排序和快速排序在平均情况下的时间复杂度均为 O(n log n)。但在稳定性方面，归并排序通常是不稳定的，而快速排序是稳定的。

试题名称：排排坐 时间限制：1.0 s　内存限制：512.0 MB 题目描述：老师正在和小朋友们分糖果。 小朋友们先在自己的手上写一个数字，然后坐成一排。 老师分发糖果的规则是：每个小朋友获得自己以及左侧所有小朋友的手上数字之和个糖果。 现在小朋友们都已经在自己手上写上了数字。 请帮小朋友们安排合适的座位顺序，使得小朋友们分到的糖果总量最大，输出这个最大值。 输入格式：输入 2 行， 第一行为一个正整数 n，表示小朋友的个数； 第二行为 n 个正整数 a_1, a_2, …, a_n，表示小朋友们手上的数字，整数之间以空格分隔。 输出格式：输出一个整数，表示小朋友们可能分到的最大糖果总数量。 输入样例1：5 7 5 8 9 3 输出样例1：111 样例解释1：小朋友安排座位后从左向右每人手上数字依次是：9, 8, 7, 5, 3。 这时可以得到最多的糖果：(9) + (9 + 8) + (9 + 8 + 7) + (9 + 8 + 7 + 5) + (9 + 8 + 7 + 5 + 3) = 111。 数据范围：1 ≤ n ≤ 1000，1 ≤ a_i ≤ 1000。

作答说明：按题目要求完成程序或作品；需要在线运行与自动判分时，可在站内选择「在线考试」。

试题名称：晚宴 时间限制：1.0 s　内存限制：512.0 MB 题目描述：小明去参加晚宴。晚宴中有 n 个菜肴，每个菜肴都有一个美味度，第 i 个菜肴的美味度为 v_i。 晚宴规定小明只能恰好选取两道菜肴，并且这两道菜肴的美味度必须要互质（即最大公约数为 1）。 请帮助小明选取两道菜肴，使得两道菜肴美味度之和最大。 输入格式：输入 2 行， 第一行为一个正整数 n，表示菜肴的个数； 第二行为 n 个整数 v_1, v_2, …, v_n 表示菜肴的美味度，整数之间以空格分隔。 输出格式：输出一个整数，表示两道互质菜肴美味度之和的最大值。 输入样例1：5 3 5 7 35 105 输出样例1：38 样例解释1：最优选择是 3 和 35。 注意到，105 与其他任意菜肴的最大公约数都大于 1，因此无法参与合法选择。 数据范围：2 ≤ n ≤ 1000，1 ≤ v_i ≤ 1000000。 数据保证不存在相同美味度的菜肴。 数据保证至少存在一种选取两道菜肴的方案。

作答说明：按题目要求完成程序或作品；需要在线运行与自动判分时，可在站内选择「在线考试」。