下面函数删除单向链表中 val == x 的节点，并且使用哑结点统一对头结点和中间节点的删除操作。横线处应填（ ）。
class Node:
def __init__(self, val):
self.val = val
self.next = None
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
2分
登录后查看选项
04
对如下代码实现的欧几里得算法（辗转相除法），调用 gcd(48, 18) 得到的调用序列为（ ）。
def gcd(a, b):
if b == 0:
return a
else:
return gcd(b, a % b)
2分
登录后查看选项
05
下面代码实现了欧拉（线性）筛，横线处应填写（ ）。
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
2分
登录后查看选项
06
埃氏筛中将内层循环从 j = i*i 开始而不是 j = 2*i 的主要原因是（ ）。
def eratosthenes_sieve_for(n):
if n < 2:
return []
is_composite = [False] * (n + 1)
primes = []
for i in range(2, n + 1):
if is_composite[i]:
continue
primes.append(i)
# 用for循环模拟C++的 j = i*i; j <=n; j +=i
for j in range(i * i, n + 1, i):
is_composite[j] = True
return primes
2分
登录后查看选项
07
下面程序的运行结果为（ ）。
def check(n, a, k, dist):
cnt = 1
last = a[0]
for i in range(1, n):
if a[i] - last >= dist:
cnt += 1
last = a[i]
return cnt >= k
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
if __name__ == "__main__":
a = [1, 2, 8, 4, 9]
n = 5
k = 3
result = solve(n, a, k)
print(result)
2分
登录后查看选项
08
在升序数组中查找第一个大于等于 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
if __name__ == "__main__":
a1 = [1, 3, 5, 7, 9]
x1 = 5
print(f"数组{a1}中第一个≥{x1}的位置：{lowerBound(a1, x1)}")
2分
登录后查看选项
09
关于递归函数调用，下列说法错误的是（ ）。
2分
登录后查看选项
10
给定 n 根木头，第 i 根长度为 a[i] 。要切成不少于 m 段等长木段，求最大可能长度，则横线上应填写（ ）。
def check(a, m, x):
cnt = 0
for length in a:
if x == 0:
return True
cnt += length
if cnt >= m:
return True
return cnt >= m
def main():
import sys
input = sys.stdin.read().split()
idx = 0
n = int(input[idx])
idx += 1
m = int(input[idx])
idx += 1
a = []
mx = 0
for _ in range(n):
num = int(input[idx])
idx += 1
a.append(num)
mx = max(mx, num)
l = 1
r = mx
ans = 0
while l <= r:
mid = l + (r - l) // 2
if check(a, m, mid):
ans = mid
_______________
else:
_______________
print(ans)
if __name__ == "__main__":
main()
2分
登录后查看选项
11
下面代码用分治求“最大连续子段和”，其时间复杂度为（ ）。
import sys
def solve(a, l, r):
if l == r:
return a[l]
mid = l + (r - l) // 2
left = solve(a, l, mid)
right = solve(a, mid + 1, r)
sum_val = 0
lmax = -sys.maxsize - 1
for i in range(mid, l - 1, -1):
sum_val += a[i]
lmax = max(lmax, sum_val)
sum_val = 0
rmax = -sys.maxsize - 1
for i in range(mid + 1, r + 1):
sum_val += a[i]
rmax = max(rmax, sum_val)
return max(left, right, lmax + rmax)
if __name__ == "__main__":
a1 = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(solve(a1, 0, len(a1)-1))
a2 = [-5, -3, -1, -4]
print(solve(a2, 0, len(a2)-1))
a3 = [10]
print(solve(a3, 0, 0))
2分
登录后查看选项
12
游戏大赛决赛，两组选手分别按得分从小到大排好队，现在要把他们合并成一个有序排行榜。
A组： A = {12, 35, 67, 89} ，B组： B = {20, 45, 55, 78} ，下面是归并合并函数的核心循环，横线处应填入（ ）。
A = [12, 35, 67, 89]
B = [20, 45, 55, 78]
i = 0
j = 0
result = []
while i < len(A) and j < len(B):
————————————————————————
result.append(A[i])
i += 1
else:
result.append(B[j])
j += 1
while i < len(A):
result.append(A[i])
i += 1
while j < len(B):
result.append(B[j])
j += 1
print("合并后的有序排行榜：", result)
def quicksort(a, l, r):
if l >= r:
return
pivot = a[l]
i, j = l, r
while i < j:
while i < j and a[j] >= pivot:
j -= 1
while i < j and a[i] <= pivot:
i += 1
if i < j:
a[i], a[j] = a[j], a[i]
a[l], a[i] = a[i], a[l]
quicksort(a, l, i - 1)
quicksort(a, i + 1, r)
if __name__ == "__main__":
scores = [60, 70, 80, 90, 100]
print("排序前：", scores)
quicksort(scores, 0, len(scores)-1)
print("排序后：", scores) # 输出：[60, 70, 80, 90, 100]
def quicksort_with_log(a, l, r, depth=0):
if l >= r:
return
print(f"递归深度{depth}，处理区间[{l},{r}]，数组：{a[l:r+1]}")
pivot = a[l]
i, j = l, r
while i < j:
while i < j and a[j] >= pivot: j -= 1
while i < j and a[i] <= pivot: i += 1
if i < j: a[i], a[j] = a[j], a[i]
a[l], a[i] = a[i], a[l]
quicksort_with_log(a, l, i-1, depth+1)
quicksort_with_log(a, i+1, r, depth+1)
scores2 = [60,70,80,90,100]
print("\n递归过程：")
quicksort_with_log(scores2, 0, 4)
2分
登录后查看选项
14
下面关于排序算法的描述中，不正确的是( )。
2分
登录后查看选项
15
下面代码实现两个整数除法，其中被除数为一个“大整数”，用字符串表示，除数是一个小整数，用 int 表示，则横线处应该填写（ ）。
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)
______________
pos = 0
while pos < len(c) - 1 and c[pos] == 0:
pos += 1
for i in range(pos, len(c)):
print(c[i], end='')
print()
print(rem)
if __name__ == "__main__":
big_integer_division()
2分
登录后查看选项
判断题 共10道
16
有一个存储了 n 个整数的线性表，分别用 Python 列表（数组）和自定义单链表两种方式实现。在已知元素下标（或结点对象引用）的前提下，Python 列表的随机访问操作时间复杂度为 O(1)；而在 Python 实现的单链表中，已知某结点对象的引用时，在该结点之后插入一个新结点的操作时间复杂度也为 O(1)。
2分
登录后查看选项
17
若数组 a 已按升序排列，则下面代码可以正确实现 “在 a 中查找第一个大于等于 x 的元素的位置”。
def lowerBound(a, x):
l = 0
r = len(a)
while l < r:
mid = (l + r) // 2
if a[mid] >= x:
r = mid
else:
l = mid + 1
return l
if __name__ == "__main__":
a1 = [1, 3, 5, 7, 9]
x1 = 5
print(f"数组{a1}中第一个≥{x1}的位置：{lowerBound(a1, x1)}")
x2 = 6
print(f"数组{a1}中第一个≥{x2}的位置：{lowerBound(a1, x2)}")
x3 = 10
print(f"数组{a1}中第一个≥{x3}的位置：{lowerBound(a1, x3)}")
x4 = 0
print(f"数组{a1}中第一个≥{x4}的位置：{lowerBound(a1, x4)}")
cnt = 0
def merge_count(a, l, m, r):
global cnt
i = l
j = m + 1
while i <= m and j <= r:
if a[i] <= a[j]:
i += 1
else:
cnt += (m - i + 1)
j += 1
if __name__ == "__main__":
a = [2, 4, 1, 3]
merge_count(a, 0, 1, 3)
print(f"跨区间逆序对数量：{cnt}")
2分
登录后查看选项
21
唯一分解定理保证：若一个数未被任何不超过其平方根的质数筛去，则它一定是质数。
2分
登录后查看选项
22
假设数组a的值域范围是D，以下程序的时间复杂度是O(n log n + n log D)。
def check(n, a, k, dist):
cnt = 1
last = a[0]
for i in range(1, n):
if a[i] - last >= dist:
cnt += 1
last = a[i]
return cnt >= k
def solve(n, a, k):
a_sorted = a.copy()
a_sorted.sort()
l = 0
r = a_sorted[-1] - a_sorted[0]
while l < r:
mid = (l + r + 1) // 2
if check(n, a_sorted, k, mid):
l = mid
else:
r = mid - 1
return l
if __name__ == "__main__":
a = [1, 2, 8, 4, 9]
n = 5
k = 3
result = solve(n, a, k)
print(result)