单选题

1. 链表不具备的特点是( )。

   {{ select(1) }}

• 可随机访问任何一个元素
• 插入、删除操作不需要移动元素
• 无需事先估计存储空间大小
• 所需存储空间与存储元素个数成正比

2. 双向链表中每个结点有两个指针域 prev 和 next ，分别指向该结点的前驱及后继结点。设 p 指向链表中的一个结点，它的前驱结点和后继结点均非空。现要求删除结点 p ，则下述语句中正确的是（ ）。

   class Node:
       def __init__(self, value):
           self.value = value
           self.prev = None
           self.next = None
   
   if p.next:
       p.next.prev = p.prev
   if p.prev:
       p.prev.next = p.next
   p = None
   

   {{ select(2) }}

• class Node: def init(self, value): self.value = value self.prev = None self.next = None if p.next: p.next.prev = p.prev if p.prev: p.prev.next = p.next p = None
• class Node: def init(self, value): self.value = value self.prev = None self.next = None if p.next: p.next.next = p.prev if p.prev: p.prev.next = p.next p = None
• class Node: def init(self, value): self.value = value self.prev = None self.next = None if p.next: p.next.prev = p.prev if p.prev: p.prev.next = p.prev p = None
• class Node: def init(self, value): self.value = value self.prev = None self.next = None if p.next: p.next.prev = p.next if p.prev: p.prev.next = p.next p = None

3. 假设双向循环链表包含头尾哨兵结点(不存储实际内容)，分别为 head 和 tail，链表中每个结点有两个指针域 prev 和 next，分别指向该结点的前驱及后继结点。下面代码实现了一个空的双向循环链表，横线上应填的最佳代码是()。

{{ select(3) }}

• self.head.next = self.tail self.tail.prev = self.head
• self.head.next = self.head self.tail.prev = self.tail
• self.head.next = self.tail self.tail.next = self.head
• self.head.prev = self.tail self.tail.next = self.head

4. 用以下辗转相除法（欧几里得算法）求gcd(84,60)的步骤中，第二次调用gcd()函数计算的是（ ）。

   def gcd(a, b):
       big = max(a, b)
       small = min(a, b)
       if big % small == 0:
           return small
       return gcd(small, big % small)
   

   {{ select(4) }}

• 84和60
• 60和24
• 24和12
• 12和0

5. 根据唯一分解定理，下面整数的唯一分解是正确的（ ）。

   {{ select(5) }}

• 18 = 3 × 6
• 28 = 4 × 7
• 36 = 2 × 3 × 6
• 30 = 2 × 3 × 5

6. 下述代码实现数学结构的线性解法。解法由所有小于等于n的素数、横线上应填的最佳代码是（）。

   def sieve_linear(n):
       is_prime = [True] * (n + 1)
       primes = []
       if n < 2:
           return primes
       is_prime[0] = is_prime[1] = False
       for i in range(2, n // 2 + 1):
           if is_prime[i]:
               primes.append(i)
               j = 0
               while j < len(primes) and i * primes[j] <= n:
                   is_prime[i * primes[j]] = False
                   if i % primes[j] == 0:
                       break
                   j += 1
       for i in range(n // 2 + 1, n + 1):
           if is_prime[i]:
               primes.append(i)
       return primes
   

   {{ select(6) }}

• while j < len(primes) and j * primes[j] <= n;
• while j < len(primes) and i * primes[j] <= n;
• while j < len(primes) and j * primes[i] <= n;
• while i < len(primes) and i * primes[j] < n;

7. 在程序运行过程中，如果递归调用的层数过多，会因为（ ）引发错误。

   {{ select(7) }}

• 系统分配的栈空间溢出
• 系统分配的堆空间溢出
• 系统分配的队列空间溢出
• 系统分配的链表空间溢出

8. 对下面两个函数，说法错误的是（ ）。

   def factorialA(n):
       if n <= 1:
           return 1
       return n * factorialA(n - 1)
   
   def factorialB(n):
       if n <= 1:
           return 1
       res = 1
       for i in range(2, n + 1):
           res *= i
       return res
   

   {{ select(8) }}

• 两个函数的实现的功能相同。
• 两个函数的时间复杂度均为 ( O(n) )。
• factorialA采用递归方式。
• factorialB采用递归方式。

9. 下算法中，（ ）是不稳定的排序。

   {{ select(9) }}

• 选择排序
• 插入排序
• 归并排序
• 冒泡排序

10. 考虑以下python代码实现的快速排序算法，将数据从小到大排序，则横线上应填的最佳代码是（）。

    def partition(arr, low, high):
        pivot = arr[high]
        i = low - 1
        for j in range(low, high):
            if arr[j] < pivot:
                i += 1
                arr[i], arr[j] = arr[j], arr[i]
        arr[i + 1], arr[high] = arr[high], arr[i + 1]
        return i + 1
    
    def quick_sort(arr, low, high):
        if low < high:
            pi = partition(arr, low, high)
            quick_sort(arr, low, pi - 1)
            quick_sort(arr, pi + 1, high)
    

    {{ select(10) }}

• if arr[i] < pivot: i += 1 arr[i], arr[j] = arr[j], arr[i]
• if arr[j] < pivot: j += 1
• if arr[i] < pivot: j += 1 arr[i], arr[i] = arr[j], arr[i]
• if arr[j] < pivot: i += 1 arr[i], arr[j] = arr[j], arr[i]

11. 若用二分法在[1,100]内猜数，最多需要猜（ ）次。

    {{ select(11) }}

• 100
• 10
• 7
• 5

12. 下面的python代码实现了二分查找算法，在数组 arr 找到目标元素 target 的位置，则横线上能填写的最佳代码是（ ）。

    def binary_search(arr, left, right, target):
        while left <= right:
            mid = left + (right - left) // 2
            if arr[mid] == target:
                return mid
            elif arr[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return -1
    

    {{ select(12) }}

• mid = left + (right - left) // 2
• mid = left;
• mid = (left + right) // 2 + 1;
• mid = right;

13. 贪心算法的核心特征是（ ）。

    {{ select(13) }}

• 总是选择当前最优解
• 回溯尝试所有可能
• 分阶段解决子问题
• 总能找到最优解

14. 函数def find_max(arr, low, high): 计算数组中最大元素，其中数组arr 从索引low 到high ，（ ）正确实现了分治逻辑。

    {{ select(14) }}

• def find_max(arr, low, high): if low == high: return arr[low] mid = low + (high - low) // 2 left_max = find_max(arr, low, mid) right_max = find_max(arr, mid + 1, high) return left_max if left_max > right_max else right_max
• def find_max(arr, low, high): if low == high: return arr[low] mid = low + (high - low) // 2 left_max = find_max(arr, low, mid) right_max = find_max(arr, mid, high) return left_max if left_max > right_max else right_max
• def find_max(arr, low, high): if low == high: return arr[low] mid = low + (high - low) // 2 left_max = find_max(arr, low, mid) right_max = find_max(arr, mid - 1, high) return left_max if left_max > right_max else right_max
• def find_max(arr, low, high): if low == high: return arr[low] mid = low + (high - low) // 2 left_max = find_max(arr, low, mid) right_max = find_max(arr, mid + 1, high) return left_max if left_max > right_max else right_max

15. 小杨编写了一个如下的高精度乘法函数，则横线上应填写的代码为（ ）。

    def multiply(a, b):
        m, n = len(a), len(b)
        c = [0] * (m + n)
        for i in range(m):
            for j in range(n):
                c[i + j] += a[i] * b[j]
        carry = 0
        for k in range(len(c)):
            temp = c[k] + carry
            c[k] = temp % 10
            carry = temp // 10
        while len(c) > 1 and c[-1] == 0:
            c.pop()
        return c
    

    {{ select(15) }}

• temp = c[k]
• temp = c[k] + carry
• temp = c[k] - carry
• temp = c[k] * carry

判断题

1. 单链表中删除某个结点p(非尾结点)，但不知道头结点，可行的操作是将p的值设为p.next的值，然后删除p.next。

   {{ select(16) }}

• 对
• 错

2. 链表存储线性表时要求内存中可用存储单元地址是连续的。

   {{ select(17) }}

• 对
• 错

3. 线性筛相对于块拉杆将标记筛选，每个含数只会被它的最小原因数筛去一次，因此效率更高。

   {{ select(18) }}

• 对
• 错

4. 贪心算法通过一步选择当前最优解，从而一定能获得全局最优解。

   {{ select(19) }}

• 对
• 错

5. 递归函数必须具有一个终止条件，以防止无限递归。

   {{ select(20) }}

• 对
• 错

6. 快速排序算法的时间复杂度与输入是否有序无关，始终稳定为O(n log n)。

   {{ select(21) }}

• 对
• 错

7. 归并排序算法的时间复杂度与输入是否有序无关，始终稳定为O(n log n)。

   {{ select(22) }}

• 对
• 错

8. 二分查找适用于对无序数组和有序数组的查找。

   {{ select(23) }}

• 对
• 错

9. 小杨有10元去超市买东西，每个商品有各自的价格，每种商品只能买1个，小杨的目标是买到最多数量的商品。小杨采用的策略是每次挑价格最低的商品买，这体现了分治思想。

   {{ select(24) }}

• 对
• 错

10. 归并排序算法体现了分治算法，每次将大的待排序数组分成大小大致相等的两个小数组，然后分别对两个小数组进行排序，最后对排好序的两个小数组合并成有序数组。

    {{ select(25) }}

• 对
• 错