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

下面代码尝试在有序数组中查找第一个大于等于 x 的元素位置。如果没有大于等于 x 的元素，返回数组长度。以下说法正确的是（ ）。

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

下面代码实现了对两个数组表示的正整数的高精度加法（数组低位在前），则横线上应填写（）。

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]
        # 填空位置
        c.append(carry % 10)
        carry = carry // 10
        i += 1
    if carry:
        c.append(carry)
    return c

下面代码实现了欧几里得算法，下面有关说法，错误的是（）。

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

对如下定义的循环单链表，`print_list` 函数横线处填写（）。

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()

下述代码实现素数表的线性筛法，筛选出所有小于等于 n 的素数，则横线上应填的代码是( )。

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

下述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

根据下面代码，以下说法正确的是（）。

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

给定有 n 个任务，每个任务有截止时间和利润，每个任务耗时 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]:
                # 填空处完整代码
                slot[t] = True
                total_profit += task.profit
                break
            t -= 1
    return total_profit

小杨要把一根长度为 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 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

假设我们有两个数 a = 38 和 b = 14 ，它们对模 m 同余， 即a ≡ b (mod m)。以下哪个值不可能是 m？

下列关于排序的说法，正确的是( )。

区块链技术是比特币的基础。在区块链中，每个区块指向前一个区块，构成链式列表，新区块只能接在链尾，不允许在中间插入或删除。下面代码实现插入区块添加函数，则横线处填写（）。

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

二分查找仅适用于有序数据。若输入数据无序，当仅进行一次查找时，为了使用二分而排序通常不划算。（）

使用贪心算法解决问题时，通过对每一步求局部最优解，最终一定能找到全局最优解。（）

以下 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)

通过在数组的第一个、最中间和最后一个这3个数据中选择中间值作为枢轴（比较基准），快速排序算法可降低落入最坏情况的概率。（）

递归函数一定要有终止条件，否则可能会造成栈溢出。（）

数组和链表都是线性表。链表的优点是插入删除不需要移动元素，并且能随机查找。（）

4. 在求解所有不大于 n 的素数时，线性筛法（欧拉筛）都应当优先于埃氏筛法使用，因为线性筛法的时间复杂度为 O(n)，低于埃氏筛法的O(n loglogn)。（）

贪心算法在每一步都做出当前看来最优的局部选择，并且一旦做出选择就不再回溯；而分治算法将问题分解为若干子问题分别求解，再将子问题的解合并得到原问题的解。（）

在 Python 实现的单链表中，已知引用 p 指向要删除的节点（该节点不是尾节点），若想在 O(1) 时间复杂度内删除这个节点，可行的做法是：用 p 的后继节点 p.next 的值覆盖 p 自身的值，再用 p 的后继节点的 next 引用覆盖 p 的 next 引用，最后断开 p 的后继节点的引用以辅助垃圾回收。（）

假设函数 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)

相等序列
时间限制：3.0 s
内存限制：512.0 MB
题目描述

小 A 有一个包含 N 个正整数的序列A = {A₁ , A₂ , · · ,A_N}。小 A 每次可以花费 1 个金币执行以下任意一种操作：

1. 选择序列中一个正整数 A_i（ 1 ≤ i ≤ N），将 A_i 变为 A_i × P，P 为任意质数；
2. 选择序列中一个正整数 A_i（ 1 ≤ i ≤ N），将 A_i 变为 A_i ÷ P，P 为任意质数，要求 A_i 能整除 P。
小 A 想请你帮他计算出令序列中所有整数都相同，最少需要花费多少金币。
输入格式
第一行一个正整数 N，含义如题面所示。
第二行包含 N 个正整数 A₁ , A₂ , · · ,A_N，代表序列 A。
输出格式
输出一行，代表最少需要花费的金币数量。
样例
输入样例

5
10  6  35  105  42

输出样例

8

数据范围
对于60%的测试点，保证 1 ≤ N, A_i ≤ 100。
对于所有测试点，保证 1 ≤ N, A_i ≤ 10⁵。

数字移动
时间限制：3.0 s
内存限制：512.0 MB
题目描述
小 A 有一个包含 N 个正整数的序列 A = A₁ , A₂, … …A_N，序列 A 恰好包含成对不同的正整数。形式化地，对于任意 1 ≤ i ≤ N ，存在唯一一个 j 满足 1 ≤j≤ N, i≠ j, A_i = A_j。
小 A 希望每对相同的数字在序列中相邻，为了实现这一目的，小 A 每次操作会选择任意 i (1 ≤ i ≤ N)，将当前序列的第 i 个数字移动到任意位置，并花费对应数字的体力。

例如，假设序列 A = {1 , 2, 1 , 3, 2, 3}，小 A 可以选择 i = 2，将 A₂ = 2 移动到 A₃=1 的后面，此时序列变为{1 , 1 , 2, 3, 2, 3}，耗费 2 点体力。小 A 也可以选择 i = 3，将 A₃=1 移动到A₂ = 2 的前面，此时序列变为{1 , 1 , 2, 3, 2, 3}，花费 1 点体力

小 A 可以执行任意次操作，但他希望自己每次花费的体力尽可能小。小 A 希望你能帮他计算出一个最小的 X，使得他能够在每次花费的体力均不超过 X 的情况下令每对相同的数字在序列中相邻。
输入格式
第一行一个正整数 N，代表序列长度，保证 N 为偶数。
第二行包含 N 个正整数 A₁ , A₂ , · · . , A_N，代表序列 A。且对于任意 1 ≤ i ≤ N，存在唯一一个j 满足1 ≤ j ≤ N, i≠ j, A_i= A_j。
数据保证小 A 至少需要执行一次操作。
输出格式
输出一行，代表满足要求的 X 的最小值。
样例
输入样例

6
1  2  1  3  2  3

输出样例

1

仅移动数值1即可完成全部配对，所有操作体力≤1，最小X=1。 数据范围 对于40%的测试点，保证 1 ≤ N, A_i ≤ 100。 对于所有测试点，保证 1 ≤ N, A_i ≤ 10⁵。