单选题

1. 通讯卫星在通信网络系统中主要起到（）的作用。

   {{ select(1) }}

• 信息过滤
• 信号中继
• 避免攻击
• 数据加密

2. 小杨想编写一个判断任意输入的整数N是否为素数的程序，下面哪个方法不合适？（ ）

   {{ select(2) }}

• 埃氏筛法
• 线性筛法
• 二分答案
• 枚举法

3. 内排序有不同的类别，下面哪种排序算法和冒泡排序是同一类？（ ）

   {{ select(3) }}

• 希尔排序
• 快速排序
• 堆排序
• 插入排序

4. 下面Python代码用于求斐波那契数列，该数列第1、2项为1，以后各项均是前两项之和。下面有关说法错误的是（ ）。

   def fiboA(N):
       if N == 1 or N == 2:
           return 1
       return fiboA(N - 1) + fiboA(N - 2)
   
   def fiboB(N):
       if N == 1 or N == 2:
           return 1
       last2, last1 = 1, 1
       for i in range(2, N):
           nowVal = last1 + last2
           last2, last1 = last1, nowVal
       return nowVal
   

   {{ select(4) }}

• fiboA() 用递归方式，fiboB() 循环方式
• fiboA() 更加符合斐波那契数列的数学定义，直观易于理解，而fiboB() 需要将数学定义转换为计算机程序实现
• fiboA() 不仅仅更加符合数学定义，直观易于理解，且因代码量较少执行效率更高
• fiboB() 虽然代码量有所增加，但其执行效率更高

5. 下面Python代码以递归方式实现合并排序，并假设merge(left,right)函数能对有序（同样排序规则）的left和right排序。横线处应填上代码是()。

   def mergeSort(listData):
       if len(listData) <= 1:
           return listData
       Middle = len(listData) // 2
       Left, Right = ______
       return merge(Left, Right)
   

   {{ select(5) }}

• mergeSort(listData[:Middle]), mergeSort(listData[Middle:])
• mergeSort(listData[:Middle-1]), mergeSort(listData[Middle+1:])
• mergeSort(listData[:Middle]), mergeSort(listData[Middle+1:])
• mergeSort(listData[:Middle-1]), mergeSort(listData[Middle:])

6. 阅读下面的Python代码，执行后输出是()。

   stepCount = 0
   def countIt(Fx):
       def wrapper(*args, **kwargs):
           rtn = Fx(*args, **kwargs)
           global stepCount
           stepCount += 1
           print(stepCount, end="->")
           return rtn
       return wrapper
   
   @countIt
   def fracA(N):
       rtn = 1
       for i in range(1, N+1):
           rtn *= i
       return rtn
   
   @countIt
   def fracB(N):
       if N == 1:
           return 1
       return N * fracB(N-1)
   
   print(fracA(5), end="")
   print("<===>", end="")
   print(fracB(5))
   

   {{ select(6) }}

• 1->120<===>2->120
• 1->120<===>1->120
• 1->120<===>1->2->3->4->5->120
• 1->120<===>2->3->4->5->6->120

7. 下面的Python用于对1stA排序，使得偶数在前奇数在后，横线处不应填入（ ）。

   def isEven(N):
       return N % 2 == 0
   
   lstA = list(range(1, 100))
   lstA.sort()
   

   {{ select(7) }}

• key = not isEven
• key = lambda x: isEven(x), reverse = True
• key = isEven, reverse = True
• key = lambda x: not isEven(x)

8. 下面的Python代码用于排序SA字符串中每个字符出现的次数（字频），sA字符串可能很长，此处仅为示例。排序要求是按字频顺序，如果字频相同则按字符的ASCII升序，横线处应填入代码是（ ）。

   sA = "Simple is better than complex"
   charCount = {} #每个字符对应数量
   for c in sA:
       charCount[c] = charCount.get(c, 0) + 1
   print(sorted(___) )
   

   {{ select(8) }}

• charCount, key = lambda x:(~x[1],x[0])
• charCount.items(), key = lambda x:(~x[1],ord(x[0]))
• charCount.items(), key = lambda x:(x[1],-ord(x[0]))
• 触发异常，不能对字典进行排序。

9. 有关下面Python代码正确的是（ ）。

   isEven = lambda x: x % 2 == 0
   def isOdd(N):
       return N % 2 == 1
   print(type(isEven) == type(isOdd), isEven(10), isOdd(10))
   

   {{ select(9) }}

• True True False
• False True False
• False False True
• 触发异常

10. 下面的Python代码实现对list的快速排序，有关说法，错误的是（ ）。

    def qSort(lst):
        if len(lst) < 2:
            return lst
        pivot = lst[0]
        less = [i for i in lst[1:] if i <= pivot]
        greater = [i for i in lst[1:] if i > pivot]
        return ______
    

    {{ select(10) }}

• qSort(less) + qSort(greater) + [pivot]
• [pivot] + qSort(less) + qSort(greater)
• qSort(less) + [pivot] + qSort(greater)
• qSort(less) + pivot + qSort(greater)

11. 下面Python代码中的isPrimeA()和isPrimeB()都用于判断参数N是否素数，有关其时间复杂度的正确说法是（ ）。

    def isPrimeA(N):
        if N < 2: return False
        for i in range(2, N // 2 + 1):
            if N % i == 0: return False
        return True
    
    def isPrimeB(N):
        if N < 2: return False
        for i in range(2, int(N ** 0.5) + 1):
            if N % i == 0: return False
        return True
    

    {{ select(11) }}

• isPrimeA()的最坏时间复杂度是(O(\frac{N}{2}))，isPrimeB()的最坏时间复杂度是(O(\log N))，isPrimeA()优于isPrimeB()
• isPrimeA()的最坏时间复杂度是(O(\frac{N}{2}))，isPrimeB()的最坏时间复杂度是(O(N^{\frac{1}{2}}))，isPrimeB()绝大多数情况下优于isPrimeA()
• isPrimeA()的最坏时间复杂度是(O(N^{\frac{1}{2}}))，isPrimeB()的最坏时间复杂度是(O(N))，isPrimeA()优于isPrimeB()
• isPrimeA()的最坏时间复杂度是(O(\log N))，isPrimeB()的最坏时间复杂度是(O(N))，isPrimeA()优于isPrimeB()

12. 下面Python代码用于有序 list 的二分查找，有关说法错误的是（ ）。

    def bSearch(lst, Val):
        def __binarySearch(lst, Low, High, Target):
            if Low > High:
                return -1
            Mid = (Low + High) // 2
            if Target == lst[Mid]:
                return Mid
            elif Target < lst[Mid]:
                return __binarySearch(lst, Low, Mid - 1, Target)
            else:
                return __binarySearch(lst, Mid + 1, High, Target)
        return __binarySearch(lst, 0, len(lst), Val)
    

    {{ select(12) }}

• 代码采用二分法实现有序list的查找
• 代码采用分治算法实现有序list的查找
• 代码采用递归方式实现有序list的查找
• 代码采用动态规划算法实现有序list的查找

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

    {{ select(13) }}

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

14. 下面的Python代码用于实现每个字符后紧跟随字符及其出现次数，并对紧跟随字符排序。即出现次数最多排在前，形如：{“中”：[('文', 1), ('国', 2), ('华', 2)]}，此处S仅是部分字符，可能很多，横线处应填入代码是（ ）。

    S = """中国华夏中华中华人民共和国中国人中文"""
    dictAfter = {}
    for i, hz in enumerate(S[:-1]):
        tmpDict = dictAfter.get(S[i], {})
        tmpDict[hz] = tmpDict.get(hz, 0) + 1
        dictAfter[S[i]] = tmpDict
    dictAfter = {x[0]: sorted(x[1].items(), key=lambda x: -x[1]) for x in dictAfter.items()}
    print(dictAfter)
    

    {{ select(14) }}

• x[0]:x[1].items().sort(key = lambda x:x[1], reverse = True)
• x[0]:x[1].items().sort(key = lambda x:x[0], reverse = True)
• x[0]:sorted(x[1].items(), key = lambda x:-x[0])
• x[0]:sorted(x[1].items(), key = lambda x:-x[1])

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

    class Node:
        def __init__(self, Val, Prv=None, Nxt=None):
            self.Value = Val
            self.Prev = Prv
            self.Next = Nxt
    
    firstNode = Node(10)
    firstNode.Next = Node(100, firstNode)
    firstNode.Next.Next = Node(111, firstNode.Next)
    

    {{ select(15) }}

• 上述代码构成单向链表
• 上述代码构成双向链表
• 上述代码构成循环链表
• 上述代码构成指针链表

判断题

1. 小杨想写一个程序来算出正整数N有多少个因数，经过思考他写出了一个重复没有超过N/2次的循环就能够算出来了。（ ）

   {{ select(16) }}

• 对
• 错

2. 同样的整数序列分别保存在单链表和双向链中，这两种链表上的简单冒泡排序的复杂度相同。（ ）

   {{ select(17) }}

• 对
• 错

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

   {{ select(18) }}

• 对
• 错

4. 在Python中，当对List类型进行in运算查找元素是否存在时，其查找通常采用二分法。（ ）

   {{ select(19) }}

• 对
• 错

5. 以下Python代码能以递归方式实现斐波那契数列，该数列第1、2项为1，以后各项均是前两项之和。（ ）

   def fibo(N):
       if N == 1 or N == 2:
           return 1
       else:
           m = fibo(N - 1)
           n = fibo(N - 2)
           return m + n
   

   {{ select(20) }}

• 对
• 错

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

   {{ select(21) }}

• 对
• 错

7. 如果自定义Class已经定义了__lt__()魔术方法，则自动支持内置函数sorted()。（ ）

   {{ select(22) }}

• 对
• 错

8. 插入排序有时比快速排序时间复杂度更低。（ ）

   {{ select(23) }}

• 对
• 错

9. 下面的Python代码能实现十进制正整数N转换为八进制并输出。（ ）

   N = int(input())
   rst = "" #保存转换结果
   while N != 0:
       rst += str(N % 8)
       N //= 8
   print(rst)
   

   {{ select(24) }}

• 对
• 错

10. Python代码 print(sorted(list(range(10)), key=lambda x: x % 5)) 执行后将输出 [0, 5, 1, 6, 2, 7, 3, 8, 4, 9]。（ ）

    {{ select(25) }}

• 对
• 错