单选题

1. 下面流程图在输入2024时，可以判定y代表闰年，并输出 2月是29天，则图中菱形框中应该填入（ ）。

   {{ select(1) }}

• (yr % 400 == 0) or (yr % 4 == 0)
• ( yr % 400 == 0) or (yr % 4 == 0 and yr %100 != 0)
• ( yr % 400 == 0) and ( yr % 4 == 0)
• (yr % 400 == 0) and (yr % 4 == 0 and yr % 100 != 0)

2. 在TCP协议中，完成连接建立需要通过（ ）握手。

   {{ select(2) }}

• 一次
• 二次
• 三次
• 四次

3. 下面有关排序算法的说法，正确的是（ ）

   {{ select(3) }}

• 快速排序是稳定排序
• Python中list类型的sort()是稳定排序
• 冒泡排序是不稳定排序
• 归并排序是不稳定排序

4. 不同的排序算法，其空间复杂度也不同。与冒泡法排序空间复杂度相同的是（ ）

   {{ select(4) }}

• 归并排序
• 快速排序
• 计数排序
• 插入排序

5. 下面Python代码中，aFactorial()和bFactorial()用于求正整数的阶乘。有关说法，错误的是（ ）。

   def aFactorial(N):
       rst = 1
       for i in range(1, N + 1):
           rst *= 1
       return rst
   
   def bFactorial(N):
       if N == 1 or N == 0:
           return 1
       return N * bFactorial(N - 1)
   
   print(aFactorial(10), bFactorial(10))
   

   {{ select(5) }}

• aFactorial()用循环方式，bFactorial()递归方式
• bFactorial()更加符合数学定义，直观易于理解，而aFactorial()需要将数学定义转换为计算机程序实现
• 当N值较大时，aFactorial()执行效率更高，而bFactorial()因为有多次函数调用，效率将降低，且N如果较大，将可能导致不能使用
• bFactorial()因为代码量较少，没有循环，因此其执行效率更高

6. 有关下面Python代码的说法，正确的是（ ）。

   def qSort(lst):
       if len(lst) <= 1:
           return lst
       else:
           Pivot = lst[0]
           less = [x for x in lst[1:] if x <= Pivot]
           Greater = [x for x in lst[1:] if x > Pivot]
           return qSort(less) + [Pivot] + qSort(Greater)
   
   lstA = [1, 2, 11, 12, 21, 21, 2, 3, 41, 4, 3]
   lstB = qSort(lstA)
   print(lstA, lstB)
   

   {{ select(6) }}

• 代码中qSort()函数不是稳定排序
• 代码中qSort()函数空间复杂度为O(1)
• 代码中qSort()函数是就地排序
• 代码中qSort()函数是外排序，因为排序后的结果保存在新的内存空间即外空间

7. 上题不能支持其他常见类型的排序，如实现该支持，横线处分别应填写代码是（ ）。

   def qSort(iterData):
       if ______:
       else:
           lst = iterData
           if len(lst) <= 1:
               return lst
           else:
               pivot = lst[0]
               less = [x for x in lst[1:] if x <= pivot]
               Greater = [x for x in lst[1:] if x > pivot]
               return qSort(less) + [Pivot] + qSort(Greater)
   
   tpla = (1, 2, 11, 12, 21, 21, 2, 3, 41, 4, 3)
   lstB = qSort(tpla)
   print(tpla, lstB)
   

   {{ select(7) }}

• isinstance(iterData, list) == False, st == [x for x in iterData]
• type(iterData) == list, lst = [x for x in iterData]
• isinstance(iterData, list), lst = list(iterData)
• type(iterData) != list, lst = list(iterData)

8. 上题qSort()函数不支持排序规则函数，形如sorted()函数的key参数，为实现类似目标，横线处分别应填入代码是（ ）。

   def qSort(lst, fx=None):
       if len(lst) <= 1:
           return lst
       else:
           pivot = lst[0]
           if ______:
               less = [x for x in lst[1:] if ______]
               Greater = [x for x in lst[1:] if ______]
               return qSort(less, fx) + [Pivot] + qSort(Greater, fx)
           else:
               less = [x for x in lst[1:] if x <= pivot]
               Greater = [x for x in lst[1:] if x > pivot]
               return qSort(less, fx) + [Pivot] + qSort(Greater, fx)
   
   lsta = [1, 2, 11, 12, 21, 21, 2, 3, 41, 4, 3]
   lstB = qSort(lsta, lambda x: x % 10)
   print(lsta, lstB)
   

   {{ select(8) }}

• fx == None, fx(x) >= fx(Pivot), fx(x) < fx(Pivot)
• fx == None, fx(x) >= Pivot, fx(x) < Pivot
• fx != None, fx(x) >= fx(Pivot), fx(x) < fx(Pivot)
• fx != None, fx(x) >= Pivot, fx(x) < Pivot

9. 下面的Python代码中merge()函数的两个参数均为list类型，且是已按相同规则排序的数据。下面有关说法中，正确的是（ ）。

   def merge(arr1, arr2):
       result = []
       while arr1 and arr2:
           if arr1[0] < arr2[0]:
               result.append(arr1.pop(0))
           else:
               result.append(arr2.pop(0))
       if arr1:
           result += arr1
       if arr2:
           result += arr2
       return result
   

   {{ select(9) }}

• 第3-7行代码将导致死循环，因为没有循环变量及其改变
• 第5行和第7行代码执行后，result的成员值为None
• 第9行和第11行是否被执行，与arr1和arr2的成员值有关，如果值转换为False，将不会被执行
• merge()函数的代码没有错误，执行后参数arr1和arr2将合并成新的list保存到result之中，且有序

10. 阅读下面Python代码，横线处应填入（ ）。

    def Check(N, Fx):
        return Fx(N)
    def isOdd(N):
        return "偶数" if N % 2 == 0 else "奇数"
    isEven = lambda N: "偶数" if N % 2 == 0 else "奇数"
    print(Check(10, ______), Check(11, ______))
    

    {{ select(10) }}

• isOdd, isEven
• isOdd, isEven(10)
• isOdd(10), isEven
• isOdd(10), isEven(10)

11. 下面Python代码的平均时间复杂度是（ ）。

    def gcd(N, M):
        return N if M == 0 else gcd(M, N % M)
    

    {{ select(11) }}

• O(N)
• O(log N)
• O(N log N)
• O(N^2)

12. 有关下面Python代码的说法，正确的是（ ）。

    def bSearch(lst, val):
        def __bSearch(lst, Low, High, queryVal):
            if Low > High:
                return -1
            midIdx = (Low + High) // 2
            midVal = lst[midIdx]
            if queryVal == midVal:
                return midIdx
            elif queryVal < midVal:
                return __bSearch(lst, Low, midIdx - 1, queryVal)
            else:
                return __bSearch(lst, midIdx + 1, High, queryVal)
        return __bSearch(lst, 0, len(lst), val)
    let = list(range(10))
    print(bSearch(lst, 3))
    

    {{ select(12) }}

• 代码采用二分法查找，仅对有序list有效，不适用于set、dict等
• 在函数内定义函数，存在多次调用多次定义，因此存在错误
• 第16行代码__bSearch()最后一个参数val应为queryVal
• 第16行代码应为return__bSearch

13. 在上题的算法中，其时间复杂度是（ ）。

    {{ select(13) }}

• (O(N))
• (O(\log N))
• (O(N \log N))
• (O(N^2))

14. 下面的Python代码中，idList变量为list类型，保存有大量身份编码，倒数第二位如为偶数，则为女性，奇数为男性。从第7位开始连续8位为出生年月日，年为4位数月和日均为两位数。编码统计每天有几位男生生日女生生日。横线处应填入代码是（ ）。

    dictGender_Birthday = {} #性别，出生月日的字典
    for everyID in idList:
        gender, key = int(everyID[-2]) % 2, everyID[10:14]
        male, female = ______
        lastData = dictGender_Birthday.get(key, ______)
        dictGender_Birthday[key] = (lastData[0] + male, lastData[1] + female)
    listGender_Birthday = sorted(dictGender_Birthday.items())
    print(listGender_Birthday)
    

    {{ select(14) }}

• (1, 0) if gender == 1 else (1, 0), (0, 1)
• (0, 1) if gender == 1 else (1, 0), (0, 0)
• 0, 1 if gender == 1 else 1, 0, 0, 0
• (0, 1) if gender == 1 else (1, 0), 0, 0

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

    class Node:
        def __init__(self, Val, Prv=None, Nxt=None):
            self.Value = Val
            self.Previous, self.Next = Prv, Nxt
        def setPrevious(self, Prv=None):
            self.Previous = Prv
        def setNext(self, Nxt=None):
            self.Next = Nxt
    
    firstNode = Node(1)
    firstNode.Next = Node(2, firstNode)
    firstNode.Next.Next = Node(3, firstNode.Next)
    firstNode.Next.setPrevious(firstNode)
    firstNode.Next.Next.setPrevious(firstNode.Next)
    
    secondNode = firstNode.Next
    firstNode.Next = secondNode.Next
    secondNode.Next.Previous = firstNode
    

    {{ select(15) }}

• 代码中第17行执行后，firstNode(第一个节点的下一个节点指向第3个节点，即secondNode(第2个节点的下一个
• 代码中第18行执行后，第3个节点的Previous(前向)指向第1个节点（firstNode）
• 仅仅通过firstNode节点，不能访问第2个节点，第2个节点已不在内存中存在，自动释放所占内存
• 在第18行后，执行del secondNode后，第2个节点所占内存才会被释放。仅仅执行先有第16-18行，第2个节点内存不会被释放。

判断题

1. 一个算法设计合理的话是可以没有输出的，比如冒泡排序就不输出任何信息（ ）。

   {{ select(16) }}

• 对
• 错

2. 流程图描述算法的能力是有限的，比如它无法对能够提前终止的循环给出等价描述（ ）。

   {{ select(17) }}

• 对
• 错

3. 归并排序的空间复杂度是O(N)。（ ）

   {{ select(18) }}

• 对
• 错

4. 在Python中，当对dict类型进行in运算查找元素是否存在时，其时间复杂度为O(1)，set类型也如此。（ ）

   {{ select(19) }}

• 对
• 错

5. 在以下Python代码中，执行后输出是5=>4=>3=>2=>1=>2=>3=>2=>1=>5。（ ）

   def Fibo(N):
       print(N, end="=>")
       if N == 1 or N == 2:
           return 1
       else:
           return Fibo(N - 1) + Fibo(N - 2)
   
   print(fibo(5))
   

   {{ select(20) }}

• 对
• 错

6. 贪心算法虽然可能不是局部最优，但可达到全局最优。（ ）

   {{ select(21) }}

• 对
• 错

7. Python内置函数sorted()可支持for-in循环的数据类型排序。（ ）

   {{ select(22) }}

• 对
• 错

8. 冒泡排序是就地排序，空间复杂度为O(1)。（ ）

   {{ select(23) }}

• 对
• 错

9. 下面的Python代码能实现N的质因数分解，类似埃氏筛法。（ ）

   def Factorization(N):
       rst = f"{N}="
       i = 2
       while N != 1:
           if N % i == 0:
               rst += f"{i}"
               N //= i
           else:
               i += 1
       return rst[i:-1]
   
   print(Factorization(45))
   

   {{ select(24) }}

• 对
• 错

10. Python代码print(sorted(list(range(10,20)), key = hex))执行后将输出[10, 11, 12, 13, 14, 15, 16, 17, 18, 19]。 ( )

    {{ select(25) }}

• 对
• 错