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

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

下面函数删除单向链表中val==x的节点，横线处应填（ ）。

def eraseAll(head, x):
dummy = Node(0)
dummy.next = head
cur = dummy
while cur.next:
if cur.next.val == x:
______________________
else:
cur = cur.next
return dummy.next

对如下欧几里得算法，调用gcd(48, 18)得到的调用序列为（ ）。

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

下面代码实现了欧拉（线性）筛，横线处应填写（ ）。

def euler_sieve_for(n):
if n < 2:
return []
is_composite = [False] * (n + 1)
primes = []
for i in range(2, n + 1):
if not is_composite[i]:
primes.append(i)
___________________________
p = primes[j]
if i * p > n:
break
is_composite[i * p] = True
if i % p == 0:
break
return primes

埃氏筛中将内层循环从j=i*i开始而不是j=2*i的主要原因是（ ）。

下面程序的运行结果为（ ）。

def solve(n, a, k):
a.sort()
l = 0
r = a[-1] - a[0]
while l < r:
mid = (l + r + 1) // 2
if check(n, a, k, mid):
l = mid
else:
r = mid - 1
return l
a = [1, 2, 8, 4, 9]
print(solve(5, a, 3))

在升序数组中查找第一个大于等于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

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

给定n根木头，切成不少于m段等长木段，求最大可能长度，横线上应填写（ ）。

下面代码用分治求"最大连续子段和"，其时间复杂度为（ ）。

游戏大赛决赛，两组选手分别按得分从小到大排好队，现在要把他们合并成一个有序排行榜。
A组： A = {12, 35, 67, 89} ，B组： B = {20, 45, 55, 78} ，下面是归并合并函数的核心循环，横线处应填入（ ）。

有 位同学的成绩已经从小到大排好序，现在对它执行下面这段以第一个元素为 pivot 的快速排序，请问此次排序的时间复杂度是（ ）。

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

下面代码实现大整数除法，横线处应填写（ ）。

def big_integer_division():
s, b = input().split()
b = int(b)
a = [int(c) for c in s]
c = []
rem = 0
for i in range(len(a)):
rem = rem * 10 + a[i]
q = rem // b
c.append(q)
______________

Python列表随机访问O(1)，单链表在已知结点后插入也是O(1)。（ ）

若数组a已按升序排列，则下面代码可以正确实现"在a中查找第一个大于等于x的元素的位置"。（ ）

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

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

下面代码可以正确统计数组a区间[l,r]内的逆序对总数。（ ）

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

假设数组 的值域范围是D ，下面程序的时间复杂度是<img src="/static/uploads/images/724a9d683f9e.png" style="max-width:35%;border-radius:6px;margin:8px 0;" />

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

线性筛相比埃氏筛的核心改进在于：每个合数只被其最小质因子筛去一次，从而实现O(n)的时间复杂度。（ ）

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

有限不循环小数

时间限制：1.0 s
内存限制：512.0 MB
题面描述
若1/n可化为一个有限的、不循环的小数，则称n为终止数。求出在l到r中终止数的数量。

输入一行，包含两个整数l, r。

输出一行，包含一个整数，表示l到r中终止数的数量。

样例输入
2 11
样例输出
5
数据范围
保证1 ≤ l ≤ r ≤ 10¹²。

找数

时间限制：1.0 s
内存限制：512.0 MB
题面描述
给定一个包含n个互不相同的正整数的数组A与一个包含m个互不相同的正整数的数组B，计算有多少数在数组A与数组B中均出现。

第一行包含两个整数n, m。第二行包含n个正整数表示数组A。第三行包含m个正整数表示数组B。

输出一个整数，表示在数组A与数组B中均出现的数的个数。

样例输入
3 5
4 2 3
3 1 5 4 6
样例输出
2
数据范围
对于100%的数据，保证1 ≤ n, m ≤ 10⁵。