E1110 CCF-GESP编程能力等级认证-Python -2026-06 CCF-GESP Python五级真题-考试

假设 head 不为空，下面是实现单向循环链表在头节点后插入新节点的代码，横线处应填入（ ）。

class Node:
	def __init__(self, val):
		self.val = val
		self.next = None
def insert_after_head(head, x):
	new_node = Node(x)
	____________________

下面代码遍历并输出一个循环单链表，其中 head 指向链表的第一个节点，横线处应填入的是（ ）。

class Node:
	def __init__(self, val):
		self.val = val
		self.next = None
def printList(head):
	if head is None:
		return
	p = head
	_______________________
	print()

双链表结点定义如下，若要删除双链表中的中间结点（非首尾节点） p ，写法正确的是（ ）。

class Node:
	def __init__(self, val):
		self.val = val
		self.prev = None
		self.next = None

使用如下欧几里得算法求 gcd(105, 45) 时，函数 gcd(a, b) 的递归调用序列正确的是（ ）。

def gcd(a, b):
	return a if b == 0 else gcd(b, a % b)

下面代码实现线性筛（欧拉筛），以筛选出 n 以内的所有素数。横线处的代码应为（ ）。

def sieve(n):
  is_prime = [True] * (n + 1)
  primes = []
   
  if n >= 0:
    is_prime[0] = False
  if n >= 1:
    is_prime[1] = False
  for i in range(2, n + 1):
    if is_prime[i]:
      primes.append(i)
    j = 0
    while j < len(primes) and i * primes[j] <= n:
      is_prime[i * primes[j]] = False
      if ________________: # 在此处填入代码
        break
      j += 1
  return primes

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

下面代码实现了计算 的快速幂算法，该算法体现的编程思想是（ ）。

def power(x, n):
	if n == 0:
		return 1
	res = power(x, n // 2)
	if n % 2 == 0:
		return res * res
	else:
		return res * res * x

下面代码用于统计 n 中因子 2 出现了多少次。若 n = 40 ，输出是（ ）。

n = 40
cnt = 0
while n % 2 == 0:
	cnt += 1
	n = n // 2
print(cnt)

在一个有序数组中查找第一个大于或等于 x 的元素位置，横线处应填写（ ）。

def lowerBound(a, x):
	l = 0
	r = len(a)
	while l < r:
		mid = l + (r - l) // 2
		if a[mid] >= x:
			________________ # 在此处填入代码
		else:
			l = mid + 1
	return l

有若干根木头，长度存于 wood 。每切一刀可以把一段木头分成两段。函数 check(wood, K, x) 返回：用不超过 K 刀，能否使所有木段长度都不超过 x 。下面代码使用二分答案查找最小可行的 x ，横线处应填（ ）。

def binary_cut(wood, K):
	l = 1
	r = 0
	for length in wood:
		r = max(r, length)
	while l < r:
		mid = l + (r - l) // 2
		if check(wood, K, mid):
			________________ # 在此处填入代码
		else:
			l = mid + 1
	return l

下面代码段实现了快速排序的划分操作（以首元素为基准），横线处代码应填入（ ）。

def partition(arr, low, high):
	pivot = arr[low]
	i = low
	j = high
	while i < j:
		while i < j and arr[j] >= pivot:
			j -= 1
		while i < j and arr[i] <= pivot:
			i += 1
		if i < j:
			arr[i], arr[j] = arr[j], arr[i]
	________________ # 在此处填入代码
	return i

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

在对长度为 n(n≥1) 的数组进行归并排序的过程中， mergeArray 函数（合并两个有序子数组的操作）被调用的次数是（ ）。

MAXN = 100005
a = [0] * MAXN
tempArr = [0] * MAXN

def mergeArray(left, mid, right):
  i = left
  j = mid + 1
  k = left
  while i <= mid and j <= right:
    if a[i] <= a[j]:
      tempArr[k] = a[i]
      i += 1
    else:
      tempArr[k] = a[j]
      j += 1
    k += 1
  while i <= mid:
    tempArr[k] = a[i]
    i += 1
    k += 1
  while j <= right:
    tempArr[k] = a[j]
    j += 1
    k += 1
  for p in range(left, right + 1):
    a[p] = tempArr[p]

def mergeSort(left, right):
  if left >= right:
    return
  mid = left + (right - left) // 2
  mergeSort(left, mid)
  mergeSort(mid + 1, right)
  mergeArray(left, mid, right)

小杨在学校义卖会上负责打包“零食盲盒”。每个盲盒重量不同，快递盒最多承重 limit 克，每个快递盒最多装两个盲盒。为了尽量少用快递盒，他采用如下策略：

（1）每次把最轻的盲盒和最重的盲盒尝试放在一起；

（2）如果两者重量之和不超过 limit ，就一起装；

（3）否则，只能让最重的盲盒单独装一盒。

下面代码用于计算最少需要多少个快递盒，则横线处应填入的是（ ）。

def minBoxes(w, limit):
	w.sort()
	l = 0
	r = len(w) - 1
	boxes = 0
	while l <= r:
		if w[l] + w[r] <= limit:
			__________ # 在此处填入代码
		else:
			r -= 1
		boxes += 1
	return boxes

高精度减法中，假设两个高精度数按低位在前存储，且已经保证被减数不小于减数。下面处理借位逻辑代码中横线处应填入（ ）。

if a[i] < b[i]:
	a[i + 1] -= 1
	________________
t = a[i] - b[i]

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

带哨兵头尾节点的双向循环链表，在表头插入节点 p ，以下四步操作无论什么顺序执行结果都正确。

# 1
p.next = head.next
# 2
p.prev = head
# 3
head.next.prev = p
# 4
head.next = p

对任意正整数 a 、 b ，以下两种写法的 gcd 函数返回值完全相同。

def gcd1(a, b):
	return gcd1(b, a % b) if b else a
def gcd2(a, b):
	while b:
		t = b
		b = a % b
		a = t
	return a

在归并排序的合并操作中，如下代码片段可以正确地将两个已排序的子数组 L 和 R 合并回原数组 arr中。

def merge(arr, left, mid, right):
  n1 = mid - left + 1
  n2 = right - mid
  L = [0] * n1
  R = [0] * n2
  for i in range(n1):
    L[i] = arr[left + i]
  for j in range(n2):
    R[j] = arr[mid + 1 + j]
   
  i = 0
  j = 0
  k = left
   
  while i < n1 and j < n2:
    if L[i] <= R[j]:
      arr[k] = L[i]
      i += 1
    else:
      arr[k] = R[j]
      j += 1
    k += 1
  while i < n1:
    arr[k] = L[i]
    i += 1
    k += 1
  while j < n2:
    arr[k] = R[j]
    j += 1
    k += 1

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

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

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

以下函数 f1 的时间复杂度比函数 f2 的更高。

def f1(n):
	i = 1
	while i < n:
		i *= 2
def f2(n):
	if n <= 1:
		return
	f2(n - 1)
	f2(n - 1)

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

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