假设 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

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

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

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

分木头问题：二分查找最小可行的木段长度，横线处应填（ ）。

def binary_cut(wood, K):
    l = 1; r = max(wood)
    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 函数被调用的次数是（ ）。

小杨打包“零食盲盒”，每个快递盒最多装两个盲盒。采用双指针贪心策略，横线处应填入的是（ ）。

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 中。

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

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

二分查找不仅可以应用于有序数组，也可以在不增加时间复杂度的情况下应用于有序的单链表，因为链表也支持 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)。但在稳定性方面，归并排序通常是不稳定的，而快速排序是稳定的。

. 排排坐

小朋友们先在自己的手上写一个数字，然后坐成一排。每个小朋友获得自己以及左侧所有小朋友的手上数字之和个糖果。请帮小朋友们安排合适的座位顺序，使得分到的糖果总量最大。
1≤n≤1000，1≤ai≤1000。

第一行：正整数 n；第二行：n 个正整数。

输出一个整数，表示最大糖果总数量。

5
7 5 8 9 3

111

. 晚宴

晚宴中有 n 个菜肴，每个有一个美味度。小明只能恰好选取两道菜肴，且两道菜肴的美味度必须互质（gcd=1）。求两道菜肴美味度之和的最大值。
2≤n≤1000，1≤美味度≤10^6，保证至少存在一种合法方案。

第一行：正整数 n；第二行：n 个整数表示美味度。

输出最大和。

5
3 5 7 35 105

38