E1103 2026-09 CCF-GESP Python五级真题-练习

小杨使用单向链表存放任务序列，同时记录链表的头部结点 head 和尾部结点 tail。链表不为空，已知尾部结点 tail，在链表末尾添加新结点的时间复杂度是 ( )。

class Node:
    def __init__(self, val):
        self.value = val
        self.next = None
head: Node | None
tail: Node | None

在不带哨兵结点的双向链表中，结点 p 既不是头部结点，也不是尾部结点。删除结点 p 的正确代码是 ( )。

class Node:
    def __init__(self, val):
        self.value = val
        self.prev = None # 指向前面结点
        self.next = None # 指向后面结点

下面函数使用快慢变量查找单向链表的中间结点。横线处应填写 ( )

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

def middle(head):
    slow=head
    fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        __________
    return slow

函数 gcd (a,b) 定义如下，则 gcd (105,45) 的结果是 ()。

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

下面函数用于判断正整数 n 是否为质数。横线处的最佳写法是 ()。

def isPrime(n):
    if n<2:
        return False
    i=2
    while __________:
        if n%i==0:
            return False
        i +=1
    return True

下面代码实现线性筛 (欧拉筛)。为保证每个合数只被它的最小质因子筛除一次，横线处应填写 ( )

def linear_sieve (n):
    composite =[False]*(n + 1)
    primes=[]
    for i in range(2, n +1):
        if not composite[i]:
            primes.append(i)
        for p in primes:
            if i*p>n:
                break
            composite[i *p]= True
            if __________:
                break
    return primes

根据唯一分解定理，整数 756 的正确质因数分解是 ( )。

函数 f (n) 定义如下，则 f (4) 的结果是 ()。

def f(n):
    if n==1:
        return 1
    return n +f(n -1)

在升序数组中查找第一个严格大于 x 的元素下标，下面代码横线处应填写 ()。

def upper_bound(a,x):
    l=0
    r=len(a)
    while l < r:
        mid =l+(r -l)//2
        if __________:
            l=mid+1
        else:
            r=mid
    return l

小杨需要把若干箱货物按原有顺序分配到 days 天中，每天运输连续的若干箱，求可以完成任务的最小载重量。函数 check (cap) 判断载重量为 cap 时，是否可以在规定天数运完全部货物。横线处应填写 ()

l =maxWeight
r = totalWeight
while l <r:
    mid = l + (r -l) //2
    if check(mid):
        ________
    else:
        ________
print(l)

下面是归并排序合并两个有序区间 (升序排序) 的片段。想要让排序算法保持稳定，横线处应当填写 ( )

while i <= mid and j<= right:
    if __________:
        temp.append(a[i])
        i+=1
    else:
        temp.append(a[j])
        j+=1

下面快速排序的划分函数以 a [right] 作为枢轴，把不大于枢轴的元素移动到数组左侧。横线处应填写 ( )。

def partition(a, left, right):
    pivot = a[right]
    i =left-1
    for j in range(left,right):
        if __________:
            i+=1
            a[i],a[j]= a[j],a[i]
    a[i + 1],a[right]= a[right],a[i +1]
    return i+1

小杨要在一间教室安排尽可能多场活动，每场活动拥有开始时间 start 和结束时间 end。使用贪心算法，正确的选择策略是 ( )

class Activity:
    def __init__(self, s, e):
        self.start = s
        self.end = e

下面函数用迭代方式求解最大连续子段和。对于数组 [-2, 3, -1, 5, -6, 2] ，函数返回结果是 ( )

def maxSubArray(a):
    best = a[0]
    current = a[0]
    for i in range(1, len(a)):
        current = max(a[i], current + a[i])
        best = max(best, current)
    return best

数组 a 和 b 低位在前存储两个非负大整数，代码实现高精度加法，横线处应填写 ( )

def add(a, b):
    c = []
    carry = 0
    n = max(len(a), len(b))
    for i in range(n):
        sum_val = carry
        if i < len(a):
            sum_val += a[i]
        if i < len(b):
            sum_val += b[i]
        c.append(sum_val % 10)
        __________
    if carry != 0:
        c.append(carry)
    return c

下面代码，在已知结点 p 的前提下，可以用O(1)的时间，在单向链表的 p 结点后面插入新结点 s。

s.next=p.next
p.next=s

下面代码可以安全删除单向链表的头结点，并让 head 指向删除之后的新头结点。

p = head
head=p.next

下面的欧几里得算法，只要 a、b 是正整数，无论 a>b 还是 a<b 都可以正常求出最大公约数。

def gcd(a,b):
    while b!=0:
        r=a%b
        a=b
        b=r
    return a

下面埃氏筛从 i*i 开始标记合数，原因是:i*i 之前 i 的合数倍数，已经被更小的质因子标记完成。

def sieve(n):
    isPrime =[True]*(n +1)
    isPrime[0]= isPrime[1]= False
    i=2
    while i *i<=n:
        if isPrime[i]:
            j=i*i
            while j <= n:
                isPrime[j]= False
                j+=i
        i+=1
    return isPrime

下面程序的时间复杂度为 O(n)。

i=1
while i<=n:
    print(i)
    i*=2

数组 a 已经升序排列，下面函数可以返回数组中最后一个小于等于 x 的元素下标；如果不存在该元素，则返回 - 1。

def findLastLE(a, x):
    l = 0
    r = len(a) - 1
    ans = -1
    while l <= r:
        mid = l + (r - l) // 2
        if a[mid] <= x:
            ans = mid
            l = mid + 1
        else:
            r = mid - 1
    return ans

快速排序中如果选取区间第一个元素作为枢轴。当输入数组已经升序排列时，其最坏时间复杂度仍为O(n log n)。

下面归并排序的递推式对应的时间复杂度为 O(n log n)

T ( n ) = 2 T ( n / 2 ) + O (n)

下面的贪心代码，对于任意硬币面值集合 coins，都一定可以求出凑出 money 所需要的最少硬币数量。

count = 0
# coins 按面值从大到小排序
for coin in coins:
    count += money // coin
    money = money % coin

假设两个非负高精度整数分别存储在数组 a 和 b 中，且 a ≥b。数组采用低位在前的方式存储，即 a [0] 表示个位。下面代码中的 c 可以正确保存 a - b 的各位数字。

borrow = 0
for i in range(len(a)):
    t = a[i] - b[i] + borrow
    if t < 0:
        t += 10
        borrow = 1
    else:
        borrow = 0
    c[i] = t