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

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

• A.在 Python 实现的单链表中，若已知任意结点对象的引用，则可以在 O(1) 时间内删除该结点。
• B.Python 实现的循环链表中一定不存在值为 None 的引用属性。
• C.在 Python 实现的循环双链表中，尾结点对象的 next 属性值一定为 None。
• D.在 Python 实现的带头结点的循环单链表中，判定链表是否为空只需判断头结点对象的 next 属性是否引用头结点自身（即 head.next is head）。

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

• A.s.next=p p.prev=s q.next=s s.prev=q
• B.s.prev=p s.next=p.next p.next.prev=s p.next=s
• C.s.next=p s.prev=p.prev p.prev.next=s p.prev=s
• D.s.next=p s.prev=nullptr p.prev=s

下面函数删除单向链表中val == x的节点，并且使用哑结点统一对头结点和中间节点的删除操作。横线处应填（）。 1 class Node: 2 def __init__(self, val): 3 self.val = val 4 self.next = None 5 def eraseAll(head, x): 6 dummy = Node(0) 7 dummy.next = head 8 cur = dummy 9 while cur.next: 10 if cur.next.val == x: 11 ____________________ # 填空处 12 else: 13 cur = cur.next 14 return dummy.next

• A.cur = cur.next
• B.cur.next = cur.next.next
• C.cur.next = None
• D.cur.next = nullptr

对如下代码实现的欧几里得算法（辗转相除法），调用gcd(48, 18)得到的调用序列为（）。 1 def gcd(a, b): 2 if b == 0: 3 return a 4 else: 5 return gcd(b, a % b)

• 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)

下面代码实现了欧拉（线性）筛，横线处应填写（）。 1 def euler_sieve_for(n): 2 if n < 2: 3 return [] 4 is_composite = [False] * (n + 1) 5 primes = [] 6 for i in range(2, n + 1): 7 if not is_composite[i]: 8 primes.append(i) 9 ___________________________ 10 p = primes[j] 11 if i * p > n: 12 break 13 is_composite[i * p] = True 14 if i % p == 0: 15 break 16 return primes

• 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):

埃氏筛中将内层循环从j = i*i开始而不是j = 2*i的主要原因是（）。 1 def eratosthenes_sieve_for(n): 2 if n < 2: 3 return [] 4 is_composite = [False] * (n + 1) 5 primes = [] 6 for i in range(2, n + 1): 7 if is_composite[i]: 8 continue 9 primes.append(i) 10 # 用for循环模拟C++的 j = i*i; j <=n; j +=i 11 for j in range(i * i, n + 1, i): 12 is_composite[j] = True 13 return primes

• A.因为 2*i 一定不是合数
• B.i*i 一定是质数
• C.小于 i*i 的 i 的倍数已被更小质因子筛过
• D.这样可以把时间复杂度降为 O(n)

下面程序的运行结果为（）。 1 def check(n, a, k, dist): 2 cnt = 1 3 last = a[0] 4 for i in range(1, n): 5 if a[i] - last >= dist: 6 cnt += 1 7 last = a[i] 8 return cnt >= k 9 def solve(n, a, k): 10 a.sort() 11 l = 0 12 r = a[-1] - a[0] 13 while l < r: 14 mid = (l + r + 1) // 2 15 if check(n, a, k, mid): 16 l = mid 17 else: 18 r = mid - 1 19 return l 20 if __name__ == "__main__": 21 a = [1, 2, 8, 4, 9] 22 n = 5 23 k = 3 24 result = solve(n, a, k) 25 print(result)

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

在升序数组中查找第一个大于等于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 11 if __name__ == "__main__": 12 a1 = [1, 3, 5, 7, 9] 13 x1 = 5 14 print(f"数组{a1}中第一个≥{x1}的位置：{lowerBound(a1, x1)}")

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

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

• A.递归调用层次过深时，可能会耗尽栈空间导致栈溢出
• B.尾递归函数可以通过编译器优化来避免栈溢出
• C.所有递归函数都可以通过循环结构来改写，从而避免栈溢出
• D.栈溢出发生时，程序会抛出异常并可以继续执行后续代码

给定n根木头，第i根长度为a[i]。要切成不少于m段等长木段，求最大可能长度，则横线上应填写（）。 1 def check(a, m, x): 2 cnt = 0 3 for length in a: 4 if x == 0: 5 return True 6 cnt += length 7 if cnt >= m: 8 return True 9 return cnt >= m 10 def main(): 11 import sys 12 input = sys.stdin.read().split() 13 idx = 0 14 n = int(input[idx]) 15 idx += 1 16 m = int(input[idx]) 17 idx += 1 18 a = [] 19 mx = 0 20 for _ in range(n): 21 num = int(input[idx]) 22 idx += 1 23 a.append(num) 24 mx = max(mx, num) 25 l = 1 26 r = mx 27 ans = 0 28 while l <= r: 29 mid = l + (r - l) // 2 30 if check(a, m, mid): 31 ans = mid 32 _______________ 33 else: 34 _______________ 35 print(ans) 36 if __name__ == "__main__": 37 main()

• 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

下面代码用分治求“最大连续子段和”，其时间复杂度为（）。 1 import sys 2 def solve(a, l, r): 3 if l == r: 4 return a[l] 5 mid = l + (r - l) // 2 6 left = solve(a, l, mid) 7 right = solve(a, mid + 1, r) 8 sum_val = 0 9 lmax = -sys.maxsize - 1 10 for i in range(mid, l - 1, -1): 11 sum_val += a[i] 12 lmax = max(lmax, sum_val) 13 sum_val = 0 14 rmax = -sys.maxsize - 1 15 for i in range(mid + 1, r + 1): 16 sum_val += a[i] 17 rmax = max(rmax, sum_val) 18 return max(left, right, lmax + rmax) 19 if __name__ == "__main__": 20 a1 = [-2, 1, -3, 4, -1, 2, 1, -5, 4] 21 print(solve(a1, 0, len(a1)-1)) 22 a2 = [-5, -3, -1, -4] 23 print(solve(a2, 0, len(a2)-1)) 24 a3 = [10] 25 print(solve(a3, 0, 0))

• A.O(n²)
• B.O(n log n)
• C.O(log n)
• D.O(n)

游戏大赛决赛，两组选手分别按得分从小到大排好队，现在要把他们合并成一个有序排行榜。 A组：A = {12, 35, 67, 89}，B组：B = {20, 45, 55, 78}，下面是归并合并函数的核心循环，横线处应填入（）。 1 A = [12, 35, 67, 89] 2 B = [20, 45, 55, 78] 3 i = 0 4 j = 0 5 result = [] 6 while i < len(A) and j < len(B): 7 ———————————————————————— 8 result.append(A[i]) 9 i += 1 10 else: 11 result.append(B[j]) 12 j += 1 13 while i < len(A): 14 result.append(A[i]) 15 i += 1 16 while j < len(B): 17 result.append(B[j]) 18 j += 1 19 print("合并后的有序排行榜：", result)

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

有位同学的成绩已经从小到大排好序，现在对它执行下面这段以第一个元素为pivot的快速排序，请问此次排序的时间复杂度是（）。 1 def quicksort(a, l, r): 2 if l >= r: 3 return 4 pivot = a[l] 5 i, j = l, r 6 while i < j: 7 while i < j and a[j] >= pivot: 8 j -= 1 9 while i < j and a[i] <= pivot: 10 i += 1 11 if i < j: 12 a[i], a[j] = a[j], a[i] 13 a[l], a[i] = a[i], a[l] 14 quicksort(a, l, i - 1) 15 quicksort(a, i + 1, r) 16 if __name__ == "__main__": 17 scores = [60, 70, 80, 90, 100] 18 print("排序前：", scores) 19 quicksort(scores, 0, len(scores)-1) 20 print("排序后：", scores) # 输出：[60, 70, 80, 90, 100] 21 def quicksort_with_log(a, l, r, depth=0): 22 if l >= r: 23 return 24 print(f"递归深度{depth}，处理区间[{l},{r}]，数组：{a[l:r+1]}") 25 pivot = a[l] 26 i, j = l, r 27 while i < j: 28 while i < j and a[j] >= pivot: j -= 1 29 while i < j and a[i] <= pivot: i += 1 30 if i < j: a[i], a[j] = a[j], a[i] 31 a[l], a[i] = a[i], a[l] 32 quicksort_with_log(a, l, i-1, depth+1) 33 quicksort_with_log(a, i+1, r, depth+1) 34 scores2 = [60,70,80,90,100] 35 print("\n递归过程：") 36 quicksort_with_log(scores2, 0, 4)

• A.O(n)
• B.O(n log n)
• C.O(n²)
• D.O(log n)

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

• A.冒泡排序和插入排序都是稳定的排序算法
• B.快速排序和归并排序都是不稳定的排序算法
• C.冒泡排序和插入排序最好时间复杂度均为 O(n)
• D.归并排序在最好、最坏和平均三种情况的时间复杂度均为 O(n log n)

下面代码实现两个整数除法，其中被除数为一个“大整数”，用字符串表示，除数是一个小整数，用int表示，则横线处应该填写（）。 1 def big_integer_division(): 2 s, b = input().split() 3 b = int(b) 4 a = [int(c) for c in s] 5 c = [] 6 rem = 0 7 for i in range(len(a)): 8 rem = rem * 10 + a[i] 9 q = rem // b 10 c.append(q) 11 ______________ 12 pos = 0 13 while pos < len(c) - 1 and c[pos] == 0: 14 pos += 1 15 for i in range(pos, len(c)): 16 print(c[i], end='') 17 print() 18 print(rem) 19 if __name__ == "__main__": 20 big_integer_division()

• A.rem =rem / b
• B.rem = rem % b
• C.rem = b
• D.rem = q

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

若数组a已按升序排列，则下面代码可以正确实现 “在 a 中查找第一个大于等于 x 的元素的位置”。 1 def lowerBound(a, x): 2 l = 0 3 r = len(a) 4 while l < r: 5 mid = (l + r) // 2 6 if a[mid] >= x: 7 r = mid 8 else: 9 l = mid + 1 10 return l 11 if __name__ == "__main__": 12 a1 = [1, 3, 5, 7, 9] 13 x1 = 5 14 print(f"数组{a1}中第一个≥{x1}的位置：{lowerBound(a1, x1)}") 15 x2 = 6 16 print(f"数组{a1}中第一个≥{x2}的位置：{lowerBound(a1, x2)}") 17 x3 = 10 18 print(f"数组{a1}中第一个≥{x3}的位置：{lowerBound(a1, x3)}") 19 x4 = 0 20 print(f"数组{a1}中第一个≥{x4}的位置：{lowerBound(a1, x4)}")

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

若某算法满足递推式：T(n) = 2T(n/2) + O(n)，则其时间复杂度为 O(n log n)。

在一个数组中，如果两个元素 a[i] 和 a[j] 满足 i < j 且 a[i] > a[j]，则 a[i] 和 a[j] 是一个逆序对。 下面代码可以正确统计数组 a 区间 [l,r] 内的逆序对总数。 1 cnt = 0 2 def merge_count(a, l, m, r): 3 global cnt 4 i = l 5 j = m + 1 6 while i <= m and j <= r: 7 if a[i] <= a[j]: 8 i += 1 9 else: 10 cnt += (m - i + 1) 11 j += 1 12 if __name__ == "__main__": 13 a = [2, 4, 1, 3] 14 merge_count(a, 0, 1, 3) 15 print(f"跨区间逆序对数量：{cnt}")

唯一分解定理保证：若一个数未被任何不超过其平方根的质数筛去，则它一定是质数。

假设数组 a 的值域范围是 D，以下程序的时间复杂度是 O(n log n + n log D)。 1 def check(n, a, k, dist): 2 cnt = 1 3 last = a[0] 4 for i in range(1, n): 5 if a[i] - last >= dist: 6 cnt += 1 7 last = a[i] 8 return cnt >= k 9 def solve(n, a, k): 10 a_sorted = a.copy() 11 a_sorted.sort() 12 l = 0 13 r = a_sorted[-1] - a_sorted[0] 14 while l < r: 15 mid = (l + r + 1) // 2 16 if check(n, a_sorted, k, mid): 17 l = mid 18 else: 19 r = mid - 1 20 return l 21 if __name__ == "__main__": 22 a = [1, 2, 8, 4, 9] 23 n = 5 24 k = 3 25 result = solve(n, a, k) 26 print(result)

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

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

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

试题名称：有限不循环小数 时间限制：1.0 s　内存限制：512.0 MB 题目描述：若 1/a 可化为一个有限的，不循环的小数，则称 a 为终止数。 请你求出在 L 到 R 中终止数的数量。 输入格式：输入一行，包含两个整数 L, R。 输出格式：输出一行，包含一个整数，表示 L 到 R 中终止数的数量。 输入样例1：2 11 输出样例1：5 样例解释1：在 [2, 11] 终止数有 2、4、5、8、10。 数据范围：保证 1 ≤ L ≤ R ≤ 10^6。

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

试题名称：找数 时间限制：1.0 s　内存限制：512.0 MB 题目描述：给定一个包含 n 个互不相同的正整数的数组 A 与一个包含 m 个互不相同的正整数的数组 B，请你帮忙计算有多少数在数组 A 与数组 B 中均出现。 输入格式：第一行包含两个整数 n, m。 第二行包含 n 个正整数 a_1, a_2, …, a_n 表示数组 A。 第二行包含 m 个正整数 b_1, b_2, …, b_m 表示数组 B。 输出格式：输出一个整数，表示在数组 A 与数组 B 中均出现的数的个数。 输入样例1：3 5 4 2 3 3 1 5 4 6 输出样例1：2 样例解释1：样例 1 中，4、3 在数组 A 与 B 中均出现。 数据范围：对于 40% 的数据，保证 1 ≤ n, m ≤ 1000。 对于 100% 的数据，保证 1 ≤ n, m ≤ 10^5，1 ≤ a_i, b_i ≤ 10^9。

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