以下哪种情况使用链表比数组更合适？（ ）

下面的Python代码实现删除链表中所有结点值等于val的节点，则横线处填写（ ）。

def removeElements(head, val):
dummy = ListNode(0, head)
cur = dummy
while cur.next:
if cur.next.val == val:
——————————————————————————————————
del del_node
else:
cur = cur.next
return dummy.next

下列Python代码用Floyd判断单链表中是否存在环，横线上应填写（ ）。

def hasCycle(head):
if not head or not head.next:
return False
slow = head
fast = head.next
while fast and fast.next:
if slow == fast:
return True
_________________
return False

下列代码用于判断一个数是否为完全数，哪个选项是正确的实现？（ ）

def isPerfectNumber(n):
if n <= 1:
return False
sum = 1
i = 2
while i * i <= n:
if n % i == 0:
sum += i
_______________
sum += n // i
i += 1
return sum == n

以下代码计算两个数的最大公约数(GCD)，横线上应填写（ ）。

def gcd(a, b):
if a < b:
a, b = b, a
while b != 0:
temp = a % b
a = b
b = temp
return _________

下面的代码实现埃拉托斯特尼筛法，横线处应填入（ ）。

def sieve(n):
is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = False
for i in range(2, n + 1):
if is_prime[i]:
for j in range(______, n + 1, i):
is_prime[j] = False
return is_prime

下面的代码实现线性筛法，横线处应填入（ ）。

def linearSieve(n):
is_prime = [True] * (n + 1)
primes = []
for i in range(2, n + 1):
if is_prime[i]:
primes.append(i)
for p in primes:
if p * i > n:
break
is_prime[p * i] = False
if _____________:
break
return primes

线性筛算法中有语句if p * i > n break; 其目的是（ ）。

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

给定一个n×n的矩阵matrix，返回矩阵中第k小的元素，两处横线上应分别填写（ ）。

def kthSmallest(matrix, k):
n = len(matrix)
lo = matrix[0][0]
hi = matrix[n-1][n-1]
while lo < hi:
mid = lo + (hi - lo) // 2
if countLE(matrix, mid) >= k:
________
else:
________
return lo

下述Python代码实现了快速排序算法，下面说法错误的是（ ）。

下述Python代码实现了归并排序算法，则横线上应填写（ ）。

def merge(nums, left, mid, right):
tmp = []
i, j = left, mid + 1
while i <= mid and j <= right:
if nums[i] <= nums[j]:
tmp.append(nums[i])
i += 1
else:
tmp.append(nums[j])
j += 1
while i <= mid:
tmp.append(nums[i])
i += 1
while ___________:
tmp.append(nums[j])
j += 1

给定电影列表，找出最多能安排多少部不重叠的电影，横线上应填写的代码为（ ）。

def maxMovies(movies):
if not movies:
return 0
movies.sort(key=lambda x: x[1])
count = 1
_____________ = movies[0][1]
for i in range(1, len(movies)):
if movies[i][0] >= lastEnd:
count += 1
lastEnd = movies[i][1]
return count

给定一个整数数组nums，找到一个具有最大和的连续子数组。下面说法错误的是（ ）。

给定一个由非负整数组成的数组digits，对该整数执行+1操作，横线上应填写（ ）。

def plusOne(digits):
for i in range(len(digits)-1, -1, -1):
if digits[i] < 9:
digits[i] += 1
return digits
digits[i] = 0
_______________

基于下面定义的函数，通过判断isDivisibleBy9(n) == isDigitSumDivisibleBy9(n)代码可验算如果一个数能被9整除，则它的各

假设函数gcd()函数能正确求两个正整数的最大公约数，则下面的findMusicalPattern(4, 6)函数返回2。（ ）

下面递归实现的斐波那契数列的时间复杂度为O(n)。（ ）

def fib_memo(n, memo):
if n <= 1:
return n
if memo[n] != -1:
return memo[n]
memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
return memo[n]

链表通过更改指针实现高效的节点插入与删除，但节点访问效率低、占用内存较多。（ ）

二分查找依赖数据的有序性，通过循环逐步缩减一半搜索区间来进行查找。（ ）

线性筛关键是"每个合数只会被最小质因子筛到一次"，因此为O(n)。（ ）

快速排序和归并排序都是稳定的排序算法。（ ）

下面代码采用分治算法求解汉诺塔问题，时间复杂度为O(2^n)。（ ）

def dfs(n, src, buf, tar):
if n == 1:
move(src, tar)
return
dfs(n - 1, src, tar, buf)
move(src, tar)
dfs(n - 1, buf, src, tar)

所有递归算法都可以转换为迭代算法。（ ）

贪心算法总能得到全局最优解。（ ）

数字选取

时间限制：1.0 s
内存限制：512.0 MB
题面描述
给定正整数n，现在有1, 2, ..., n共计n个整数。你需要从这n个整数中选取一些整数，使得所选取的整数中任意两个不同的整数均互质（最大公因数为1）。请你最大化所选取整数的数量。

一行，一个正整数n。

一行，一个正整数，表示所选取整数的最大数量。

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

有趣的数字和

时间限制：1.0 s
内存限制：512.0 MB
题面描述
如果一个正整数的二进制表示包含奇数个1，那么小A就会认为这个正整数是有趣的。给定正整数l, r，请你统计满足l ≤ i ≤ r的有趣的整数i之和。

一行，两个正整数l, r。

一行，一个正整数，表示l到r之间有趣的整数之和。

样例输入
3 8
样例输出
19
数据范围
对于所有测试点，保证1 ≤ l ≤ r ≤ 10¹⁸。