对如下定义的循环单链表，横线处填写（ ）。

def print_list(head):
_______________________________
while True:
print(p.data, end=" ")
p = p.next
if p == head:
break
print()

区块链技术中，下面代码实现插入区块添加函数，横线处填写（ ）。

下面关于单链表和双链表的描述中，正确的是（ ）。

假设我们有两个数x和y，它们对模m同余。如果x=7，m=3，以下哪个值不可能是y？（ ）

下面代码实现了欧几里得算法，下面有关说法，错误的是（ ）。

def gcd1(a, b):
return a if b == 0 else gcd1(b, a % b)
def gcd2(a, b):
while b != 0:
temp = b
b = a % b
a = temp
return a

唯一分解定理描述的内容是（ ）。

下述代码实现素数表的线性筛法，横线上应填的代码是（ ）。

def linear_sieve(n):
is_prime = [True] * (n + 1)
primes = []
for i in range(2, n + 1):
if is_prime[i]:
primes.append(i)
for j in range(len(primes)):
p = primes[j]
if i * p > n:
break
——————————————————————————
if i % p == 0:
break
return primes

下列关于排序的说法，正确的是（ ）。

下面代码实现了归并排序。下述说法中，不正确的是（ ）。

下述Python代码实现了快速排序算法，最差情况时间复杂度是（ ）。

下面代码在有序数组中查找第一个大于等于x的元素位置，以下说法正确的是（ ）。

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

小杨要把长度为L的木头切成K段，用二分法找到满足条件的最小x，横线处应填写（ ）。

根据下面代码，以下说法正确的是（ ）。

def factorial1(n):
if n <= 1:
return 1
return n * factorial1(n - 1)
def factorial2(n):
result = 1
while n > 1:
result *= n
n -= 1
return result

给定n个任务，每个任务有截止时间和利润，为了获得最大利润，横线处应填写（ ）。

下面代码实现了高精度加法，横线上应填写（ ）。

def add(a, b):
c = []
carry = 0
i = 0
while i < len(a) or i < len(b):
if i < len(a):
carry += a[i]
if i < len(b):
carry += b[i]
____________________
i += 1
if carry:
c.append(carry)
return c

数组和链表都是线性表。链表的优点是插入删除不需要移动元素，并且能随机查找。（ ）

下面的lcm(a, b)函数能正确找到两个正整数的最小公倍数。（ ）

在单链表中，若想在O(1)时间复杂度内删除节点p（非尾节点），可用后继节点的值覆盖p。（ ）

线性筛法的时间复杂度为O(n)，低于埃氏筛法的O(n log log n)。（ ）

二分查找仅适用于有序数据。（ ）

快速排序通过三数取中选择枢轴，可降低落入最坏情况的概率。（ ）

贪心算法每步做出局部最优选择不再回溯；分治算法将问题分解为子问题求解。（ ）

以下fib函数计算第n项斐波那契数，其时间复杂度为O(n)。（ ）

def fib(n):
if n <= 1:
return n
return fib(n - 1) + fib(n - 2)

递归函数一定要有终止条件，否则可能会造成栈溢出。（ ）

使用贪心算法解决问题时，最终一定能找到全局最优解。（ ）

数字移动

时间限制：3.0 s
内存限制：512.0 MB
题面描述
小A有一个包含n个正整数的序列a，序列a恰好包含n/2对不同的正整数。小A希望每对相同的数字在序列中相邻，每次操作选择任意i，将当前序列的第i个数字移动到任意位置，并花费对应数字的体力。小A希望计算一个最小的x，使得他能在每次花费体力均不超过x的情况下令每对相同数字相邻。

第一行一个正整数n。第二行包含n个正整数ai。

输出一行，代表满足要求的x的最小值。

样例输入
6
1 2 1 3 2 3
样例输出
2
数据范围
对于所有测试点，保证2 ≤ n ≤ 2×10⁵。

相等序列

时间限制：3.0 s
内存限制：512.0 MB
题面描述
小A有一个包含n个正整数的序列a。小A每次可以花费1个金币执行操作：选择一个正整数ai，将ai变为ai*p或ai/p（p为任意质数）。小A想计算出令序列中所有整数都相同，最少需要花费多少金币。

第一行一个正整数n。第二行包含n个正整数ai。

输出一行，代表最少需要花费的金币数量。

样例输入
5
10 6 35 105 42
样例输出
8
数据范围
对于所有测试点，保证2 ≤ n ≤ 10⁵。