单选题

1. 有关下列 Python 代码的说法，错误的是（ ）。

   def SORTED(for_in_data, fx = None, Reverse = False):
       lst = list(for_in_data)
       if fx == None:
           lst.sort(reverse = Reverse)
       else:
           lst.sort(key = lambda x:fx(x), reverse = Reverse)
       return lst
   

   {{ select(1) }}

• 执行 SORTED([1:1,2:4,3:9]) 不会报错
• 执行 SORTED(range(10)) 不会报错
• 执行 SORTED([1,20,3], Reverse = True)[::-1] 不会报错
• 执行 SORTED([1,None,'123']) 不会报错

2. 下列 Python 代码用于判断一个正整数是否是质数（素数），相关说法中正确的是（ ）。

   def is_prime(N):
       if N <= 1:
           return False
       if N == 2 or N == 3 or N == 5:
           return True
       if N % 2 == 0 or N % 3 == 0 or N % 5 == 0:
           return False
       i = 7
       step = 4
       finish_number = int(N ** 0.5) + 1
       while i <= finish_number:
           if N % i == 0:
               return False
           i += step
           step = 6 - step
       return True
   

   {{ select(2) }}

• 代码存在错误，比如5是质数，但因为5 % 5 余数是0返回了False
• finish_number 的值应该是 N // 2 ，当前写法将导致错误
• 当前while循环正确的前提是：所有大于3的质数都符合 6k±1 形式
• while循环修改如下，其执行效果与执行时间相同。

3. 下列Python代码用于求解两个正整数的最大公约数，相关说法中错误的是（ ）。

   def gcd0(big, small):
       if big < small:
           big, small = small, big
       if big % small == 0:
           return small
       return gcd0(small, big % small)
   
   def gcd1(big,small):
       if big < small:
           big, small = small, big
       for i in range(small, 0, -1):
           if big % i == 0 and small % i == 0:
               return i
   

   {{ select(3) }}

• gcd0()函数的时间复杂度为 O(logN)
• gcd1()函数的时间复杂度为 O(N)
• 一般说来，gcd0() 的效率高于 gcd1()
• gcd1() 中的代码 range(small, 0, -1) 应该修改为 range(small, 1, -1)

4. 在Python中，可以用字典模拟单向或双向链表的实现。下面的代码模拟单向链表，和链表对象相比，有关其缺点的说法，错误的是（ ）。

   node1 = {'data': 1, 'next': None}
   node2 = {'data': 2, 'next': None}
   node1['next'] = node2 #node1的下一个节点是node2
   

   {{ select(4) }}

• 类型安全差，易出错。例如：node1["NEXT"] = node2 不会报错，导致逻辑错误
• 内存开销大。字典需要保存键名称以及哈希表
• 无法封装方法，如 insert() 插入函数较为常用，但其代码需要分散在外部
• 重复存储，难以保证一致性。如在 node1['next'] = node2 代码中，node1['next'] 的值为 node2 ，而 node2 自身也将保存一份

5. 基于上题代码，模拟单向链表实现插入新节点函数insertNode()的代码如下，横线处应填入的代码是（ ）。

   def insertNode(linkNode, newNodeData):
       newNode = ___________________
     ____________________
   

   {{ select(5) }}

• {'data': newNodeData, 'next': linkNode['next']} linkNode['next'] = newNode
• {'data': newNodeData, 'next': None} linkNode['next'] = newNode
• {'data': newNodeData, 'next': newNode} linkNode['next'] = newNode
• {'data': newNodeData, 'next': linkNode['next']} linkNode = newNode

6. 下面的Python代码用于实现双向链表。is_empty()函数用于判断链表是否为空，如为空返回True，否则False。横线处不能填入的代码是（ ）。

   class double_link:
       class Node:
           def __init__(self, data):
               self.data = data
               self.prev = None
               self.next = None
       def __init__(self):
           self.head = None
           self.tail = None
           self._size = 0
       def is_empty(self):
           return _____
   

   {{ select(6) }}

• self.tail is None
• self._size == 0
• self == None
• self.head is None

7. 基于上题代码正确的前提下，填入相应代码完善append()函数，用于在尾部增加新节点（ ）。

   def append(self, data):
       new_node = self.Node(data)
       if self.is_empty():
           self.head = new_node
           self.tail = new_node
       else:
        _____________________
         _______________________
         ________________________
       self._size += 1
       return new_node
   

   {{ select(7) }}

• self.tail.next = new_node
• new_node.prev = self.tail self.tail.next = new_node
• self.tail = new_node new_node.prev = self.tail self.tail.next = new_node
• new_node.prev = self.tail self.tail.next = new_node self.tail = new_node

8. 下面的Python代码，用于求一系列数据中的最大值。有关其算法说法错误的是（ ）。

{{ select(8) }}

• 该算法采用分治算法
• 该算法是递归实现
• 该算法采用贪心算法
• 该算法不是递推算法

9. 基于上题的find_max()实现，下面的说法错误的是（ ）。

   {{ select(9) }}

• find_max()适用于str
• find_max()适用于list
• find_max()适用于tuple
• find_max()适用于dict

10. 下面的Python代码，用于求一系列数据中的最大值。有关其算法说法错误的是（ ）。

{{ select(10) }}

• 本题的find_max()函数采用分治算法
• 和上述的find_max()函数相比，本题find_max()运行效率相对较低，因为需要分配额外的内存空间，用以存储nums的切片结果
• 和上述的find_max()函数相比，本题find_max()的空间复杂度与之相同，不需要额外的存储资源
• 本题的find_max()的时间复杂度为 O(n log n)

11. 下面的Python代码，用于求一系列数据中的最大值。有关其算法说法错误的是（ ）。

{{ select(11) }}

• 本题find_max()函数的实现是递推（迭代）算法
• 本题find_max()函数的时间复杂度为 O(n)
• 和前面的find_max()相比，因为没有递归，所以也就没有栈的创建和销毁开销，因此不会有与递归相关的栈溢出错误
• 本题的find_max()函数支持dict类型，因为dict也支持for-in循环

12. 下面的代码用于列出对N之间的所有质数、错误的说法是（ ）。

{{ select(12) }}

• 换氏筛算法相对于上面的代码效率更高
• 线性筛算法相对于上面的代码效率更高
• 上面的代码，有很多重复计算，因为不是判断单个数是否为质数，故而导致筛选出连续数中质数的效率不高
• 相对而言，换氏筛算法比上面代码以及线性筛算法效率都高

13. 硬币找零，要求找给客户最少的硬币。第一行输入硬币规格且空格间隔，单位为角，规格假设都小于10角，且一定有1角规格。硬币规格不一定是标准的货币系统，可能出现4角、2角等规格。第二行输入找零金额，约定必须为1角的整数倍。输出为每种规格及其数量，按规格从大到小输出，如果某种规格不必要，则输出为0。下面是其实现代码，相关说法正确的是（ ）。

{{ select(13) }}

• 上述代码采用贪心算法实现
• 上述代码能找到本题目要求的最优解
• 上述代码采用枚举算法实现
• 上述代码采用分治算法

14. 下面Python代码用于在升序时（list类型）中查找目标值target最后一次出现的位置。相关说法，正确的是（ ）。

{{ select(14) }}

• 当lst中存在重复的target时，该函数总能返回最后一个target的位置，即便lst全由相同元素组成
• 当target小于lst中所有元素时，该函数会返回0
• 循环条件改为while low <= high程序执行效果相同，且能提高准确性
• 将代码中（low + high + 1）// 2修改为（low + high）// 2效果相同

15. 有关下面Python代码的说法，错误的是（ ）。

    {{ select(15) }}

• "阶段1"的目标是寻找正整数n可能的正完全平方根
• “阶段2”的目标是如果正整数n没有正完全平方根，则在可能产生完全平方根时近寻找带小数点的平方根
• 代码 check_int = int(result + 0.5) 是检查因浮点误差是否为正完全平方根
• 对巨大数求平方根，本算法同样适用

判断题

1. 下面Python代码是用欧几里得算法（辗转相除法）求两个大于0的正整数的最大公约数，a大于b还是小于b都适用。（ ）

   def gcd(a, b):
       while b:
           a, b = b, a % b
       return a
   

   {{ select(16) }}

• 对
• 错

2. 假设函数 gcd() 函数能正确求两个正整数的最大公约数，则下面的 lcm() 函数能求相应两数的最小公倍数。（ ）

   def lcm(a, b):
       return a * b // gcd(a, b)
   

   {{ select(17) }}

• 对
• 错

3. 在下面的Python代码中，for-in每次循环都将执行 n ** 0.5，并取整后加上1。（ ）

   def is_prime(n):
       if n <= 1:
           return False
       for i in range(2, int(n**0.5) + 1):
           if n % i == 0:
               return False
       return True
   

   {{ select(18) }}

• 对
• 错

4. 下面的Python代码用于输出每个数对应的质因数列表，输出形如：{5: [5], 6: [2, 3], 7: [7], 8: [2, 2, 2]}。（ ）

   n, m = map(int, input().split())
   if n > m:
       n, m = m, n
   prime_factor = {}
   for i in range(n, m + 1):
       j, k = 2, i
       while k != 1:
           if k % j == 0:
               prime_factor[i] = prime_factor.get(i,[]) + [j]
               k //= j
               continue
           j += 1
   print(prime_factor)
   

   {{ select(19) }}

• 对
• 错

5. 下面Python代码执行后输出是15。（ ）

   def func(n):
       if n <= 0:
           return 0
       n -= 1
       return n + func(n)
   print(func(5))
   

   {{ select(20) }}

• 对
• 错

6. 求解下图中A点到D点最短路径，其中A到B之间的12可以理解为距离。求解这样的问题，常用Dijkstra算法，其思路是通过逐步选择当前距离起点最近的节点来求解非负权重图（如距离不能为负值）单源最短路径的算法。从该算法的描述可以看出，Dijkstra算法是贪心算法。（ ）

{{ select(21) }}

• 对
• 错

7. 下面的Python代码用于归并排序（merge sort），已测试执行正确。假如整体交换 merge() 和 merge_sort() 两个函数的先后位置，则程序执行将触发异常。（ ）

{{ select(22) }}

• 对
• 错

8. 基于上一题的Python代码。上题代码在执行时，将输出一次 HERE 字符串，因为merge_sort()递归调用在 print("HERE") 之前，因此merge()函数仅被调用一次。（ ）

   {{ select(23) }}

• 对
• 错

9. 基于上题的Python代码。代码片段 left_arr = merge_sort(arr[:mid]) 和 right_arr = merge_sort(arr[mid:]) 因为切片，将产生的新的list，对于大容量list的排序，将需要大量额外存储空间，可以优化为就地（inplace）排序。（ ）

   {{ select(24) }}

• 对
• 错

10. 下面的Python代码实现如果对一维list【形如：[32,12,32,13,42,1],而不是[(1,3),(3,1),(321,321),(32,13)]】进行快速排序，该排序是稳定排序。（ ）

{{ select(25) }}

• 对
• 错