试卷总分：100分
选择题 15题 30分
判断题 10题 20分
编程题 2题 50分
对如下定义的循环单链表，横线处填写（ ）。
class Node: def __init__(self, data): self.data = data self.next = None def create_list(value): head = Node(value) head.next = head return head def insert_tail(head, value): p = head while p.next != head: p = p.next node = Node(value) node.next = head p.next = node def print_list(head): _______________________________ while True: print(p.data, end=" ") p = p.next if p == head: break print()
区块链技术是比特币的基础。在区块链中，每个区块指向前一个区块，构成链式列表，新区块只能接在链尾，不允许在中间插入或删除。下面代码实现插入区块添加函数，则横线处填写（ ）。
class Block: def __init__(self, idx, data, prev_block): self.index = idx self.data = data self.prev = prev_block class Blockchain: def __init__(self): self.tail = None def init(self): genesis_block = Block(0, "Genesis Block", None) self.tail = genesis_block def add_block(self, data): ____________________________________ def clear(self): cur = self.tail while cur is not None: prev_block = cur.prev cur.prev = None cur = prev_block self.tail = None def print_chain(self): cur = self.tail chain = [] while cur is not None: chain.append(f"Block {cur.index}: {cur.data}") cur = cur.prev for block_info in reversed(chain): print(block_info)
下面关于单链表和双链表的描述中，正确的是（ ）。
class DNode: def __init__(self, data): self.data = data self.prev = None self.next = None def delete_dnode(node): if node.prev: node.prev.next = node.next if node.next: node.next.prev = node.prev node.prev = None node.next = None class SNode: def __init__(self, data): self.data = data self.next = None def delete_snode(head, node): if head is None or node is None: return prev = head while prev.next != node: prev = prev.next prev.next = node.next node.next = None
假设我们有两个数 a=38 和 b=14，它们对模 m 同余，即 a==b (mod m)。以下哪个值不可能是 m？
下面代码实现了欧几里得算法，下面有关说法，错误的是（ ）。
def gcd1(a: int, b: int) -> int: return a if b == 0 else gcd1(b, a % b) def gcd2(a: int, b: int) -> int: while b != 0: temp = b b = a % b a = temp return a
唯一分解定理描述的内容是（ ）。
下述代码实现素数表的线性筛法，筛选出所有小于等于 的素数，则横线上应填的代码是( )。
def linear_sieve(n): if n < 2: return [] is_prime = [True] * (n + 1) is_prime[0] = is_prime[1] = False 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
下列关于排序的说法，正确的是( )。
下面代码实现了归并排序。下述关于归并排序的说法中，不正确的是（ ）。
def merge(arr, temp, l, mid, r): i = l j = mid + 1 k = l while i <= mid and j <= r: if arr[i] <= arr[j]: temp[k] = arr[i] i += 1 else: temp[k] = arr[j] j += 1 k += 1 while i <= mid: temp[k] = arr[i] i += 1 k += 1 while j <= r: temp[k] = arr[j] j += 1 k += 1 for p in range(l, r + 1): arr[p] = temp[p] def merge_sort(arr, temp, l, r): if l >= r: return mid = l + (r - l) // 2 merge_sort(arr, temp, l, mid) merge_sort(arr, temp, mid + 1, r) merge(arr, temp, l, mid, r) def merge_sort_wrapper(arr): if not arr: return [] temp = [0] * len(arr) merge_sort(arr, temp, 0, len(arr) - 1) return arr
下述python代码实现了快速排序算法，最差情况时间复杂度是（ ）。
def partition(arr, low, high): i = low j = high pivot = arr[low] while i < j: while i < j and arr[j] >= pivot: j -= 1 while i < j and arr[i] <= pivot: i += 1 if i < j: arr[i], arr[j] = arr[j], arr[i] arr[i], arr[low] = arr[low], arr[i] return i def quick_sort(arr, low, high): if low >= high: return p = partition(arr, low, high) quick_sort(arr, low, p - 1) quick_sort(arr, p + 1, high) def quick_sort_wrapper(arr): if not arr: return [] quick_sort(arr, 0, len(arr) - 1) return arr
下面代码尝试在有序数组中查找第一个大于等于 x 的元素位置。如果没有大于等于 x 的元素，返回arr.size() 。以下说法正确的是（ ）。
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 。已知每切一刀只能把一段木头分成两段，他用二分法找到满足条件的最小 x （ x 为正整数），则横线处应填写（ ）。
def check(L, K, x): cuts = (L - 1) // x return cuts <= K def binary_cut(L, K): l = 1 r = L while l < r: ___________________ return l if __name__ == "__main__": L = 10 K = 2 result = binary_cut(L, K) print(result)
根据下面代码，以下说法正确的是（ ）。
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
给定有 个任务，每个任务有截止时间和利润，每个任务耗时 1 个时间单位、必须在截止时间前完成，且每个时间槽最多做 1 个任务。为了在规定时间内获得最大利润，可以采用贪心策略，即按利润从高到低排序，尽量安排，则横线处应填写（ ）。
class Task: def __init__(self, deadline, profit): self.deadline = deadline self.profit = profit def sort_by_profit(tasks): tasks.sort(key=lambda x: x.profit, reverse=True) def max_profit(tasks): sort_by_profit(tasks) max_time = 0 for task in tasks: if task.deadline > max_time: max_time = task.deadline slot = [False] * (max_time + 1) total_profit = 0 for task in tasks: t = task.deadline while t >= 1: if not slot[t]: __________________ t -= 1 return total_profit
下面代码实现了对两个数组表示的正整数的高精度加法（数组低位在前），则横线上应填写（ ）。
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
数组和链表都是线性表。链表的优点是插入删除不需要移动元素，并且能随机查找。
假设函数 gcd() 函数能正确求两个正整数的最大公约数，则下面的 lcm(a，b) 函数能正确找到两个正整数 a 和 b 的最小公倍数。
import math def lcm(a, b): if a == 0 or b == 0: return 0 return abs(a) // math.gcd(abs(a), abs(b)) * abs(b)
在 Python 实现的单链表中，已知引用 p 指向要删除的节点（该节点不是尾节点），若想在 时间复杂度内删除这个节点，可行的做法是：用 p 的后继节点 p.next 的值覆盖 p 自身的值，再用 p 的后继节点的next 引用覆盖 p 的 next 引用，最后断开 p 的后继节点的引用以辅助垃圾回收。
在求解所有不大于 的素数时，线性筛法（欧拉筛）都应当优先于埃氏筛法使用，因为线性筛法的时间复杂度为 O(n)，低于埃氏筛法的 O(n log log n)。
二分查找仅适用于有序数据。若输入数据无序，当仅进行一次查找时，为了使用二分而排序通常不划算。
通过在数组的第一个、最中间和最后一个这3个数据中选择中间值作为枢轴（比较基准），快速排序算法可降低落入最坏情况的概率。
贪心算法在每一步都做出当前看来最优的局部选择，并且一旦做出选择就不再回溯；而分治算法将问题分解为若干子问题分别求解，再将子问题的解合并得到原问题的解。
以下 fib 函数计算第 n 项斐波那契数（ fib(0)=0 , fib(1)=1 ），其时间复杂度为 O(n)。
def fib(n): if n <= 1: return n return fib(n - 1) + fib(n - 2)
递归函数一定要有终止条件，否则可能会造成栈溢出。
使用贪心算法解决问题时，通过对每一步求局部最优解，最终一定能找到全局最优解。
小 A 有一个包含 N 个正整数的序列 A={A1,A2,...,AN}，序列 A 恰好包含 N/2 对不同的正整数。形式化地，对于任意 1≤i≤N ，存在唯一一个 j 满足 1≤j≤N，i≠j，Ai=Aj。
小 A 希望每对相同的数字在序列中相邻，为了实现这一目的，小 A 每次操作会选择任意 (1≤i≤N)，将当前序列的第 i 个数字移动到任意位置，并花费对应数字的体力。
例如，假设序列 A={1,2,1,3,2,3}，小 A 可以选择 i=2，将 A2=2 移动到 A3=1 的后面，此时序列变为 {1,1,2,3,2,3}，耗费 2 点体力。小 A 也可以选择 i=3，将 A3=1 移动到 A2=2 的前面，此时序列变为{1,1,2,3,2,3}，花费 1 点体力。
小 A 可以执行任意次操作，但他希望自己每次花费的体力尽可能小。小 A 希望你能帮他计算出一个最小的 x，使得他能够在每次花费的体力均不超过 x 的情况下令每对相同的数字在序列中相邻。
第一行一个正整数N，代表序列长度，保证N为偶数。
第二行包含N个正整数A1,A2,...,AN，代表序列A。且对于任意1≤i≤N，存在唯一一个j满足1≤j≤N，i≠j，Ai=Aj。
数据保证小 A 至少需要执行一次操作。
输出一行，代表满足要求的x的最小值。
对于所有测试点，保证 1≤N,Ai≤10^5。
6
1 2 1 3 2 3
2
小 A 有一个包含 N 个正整数的序列 A={A1,A2,...,AN}。小 A 每次可以花费 1 个金币执行以下任意一种操作：
小 A 想请你帮他计算出令序列中所有整数都相同，最少需要花费多少金币。
第一行一个正整数N，含义如题面所示。
第二行包含N个正整数A1,A2,...,AN，代表序列A。
输出一行，代表最少需要花费的金币数量。
5
10 6 35 105 42
8