试卷总分：100分
选择题 15题 30分
判断题 10题 20分
编程题 2题 50分
关于 Python 实现的单链表、双链表和循环链表，下列说法正确的是（ ）。
双向循环链表中要在结点 p 之前插入新结点 s （均非空），以下操作正确的是（ ）。
下面函数删除单向链表中 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
对如下代码实现的欧几里得算法（辗转相除法），调用 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 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
下面程序的运行结果为（ ）。
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)
在升序数组中查找第一个大于等于 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)}")
关于递归函数调用，下列说法错误的是（ ）。
给定 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()
下面代码用分治求“最大连续子段和”，其时间复杂度为（ ）。
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))
游戏大赛决赛，两组选手分别按得分从小到大排好队，现在要把他们合并成一个有序排行榜。
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)
有n位同学的成绩已经从小到大排好序，现在对它执行下面这段以第一个元素为 pivot 的快速排序，请问此次排序的时间复杂度是（ ）。
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)
下面关于排序算法的描述中，不正确的是( )。
下面代码实现两个整数除法，其中被除数为一个“大整数”，用字符串表示，除数是一个小整数，用 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()
有一个存储了 n 个整数的线性表，分别用 Python 列表（数组）和自定义单链表两种方式实现。在已知元素下标（或结点对象引用）的前提下，Python 列表的随机访问操作时间复杂度为 O(1)；而在 Python 实现的单链表中，已知某结点对象的引用时，在该结点之后插入一个新结点的操作时间复杂度也为 O(1)。
若数组 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)}")
快速排序只要每次都选取中间元素作为枢轴，就一定是稳定排序。
若某算法满足递推式：T(n) = 2T(n/2) + O(n)，则其时间复杂度为 O(n log n)。
在一个数组中，如果两个元素 a[i] 和 a[j] 满足 i < j 且 a[i] > a[j] ，则 a[i] 和 a[j] 是一个逆序对。
下面代码可以正确统计数组 a 区间 [l,r] 内的逆序对总数。
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}")
唯一分解定理保证：若一个数未被任何不超过其平方根的质数筛去，则它一定是质数。
假设数组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)
若一个问题满足最优子结构性质，则一定可以用贪心算法得到最优解。
线性筛相比埃氏筛的核心改进在于：埃氏筛中一个合数可能被多个质数重复标记，线性筛通过"每个合数只被其最大质因子筛去"的策略，保证每个合数恰好被标记一次，从而实现O(n)的时间复杂度。
任何递归程序都可以改写为等价的非递归程序，但改写后的非递归程序一定需要显式地使用栈来模拟递归调用过程。
若 1/a 可化为一个有限的，不循环的小数，则称 a 为终止数。
请你求出在 L 到 R 中终止数的数量。
输入一行，包含两个整数 L,R。
输出一行，包含一个整数，表示L到R中终止数的数量。
1≤L≤R≤10^6
2 11
复制
5
给定一个包含 n 个互不相同的正整数的数组 A 与一个包含 m 个互不相同的正整数的数组 B，请你帮忙计算有多少数在数组 A 与数组 B 中均出现。
第一行包含两个整数 n,m。
第二行包含 n 个正整数 a1,a2,...,an 表示数组 A。
第二行包含 m 个正整数 b1,b2,...,bm 表示数组 B。
输出一个整数，表示在数组 A 与数组 B 中均出现的数的个数。
对于100%的数据，保证 1≤n,m≤10^5，1≤ai,bi≤10^9。
3 5
4 2 3
3 1 5 4 6
2