单选题

1. 在Python中，print((c for c in "GESP"))的输出是（ ）。

   {{ select(1) }}

• ('G', 'E', 'S', 'P')
• ['G', 'E', 'S', 'P']
• {'G', 'E', 'S', 'P'}
• 以上选项均不正确

2. 下面有关快速排序的说法，错误的是（ ）。

   {{ select(2) }}

• 快速排序算法通常采用递归实现。
• 快速排序算法是一种稳定排序算法。
• 如果被排序数组或者list已排序或逆序，其时间复杂度是 (O(n^2))。
• 快速排序是一种原地（in-place）排序算法。

3. 内排序有不同的类别，从排序算法的实现思路上考虑，下面哪种排序算法和插入排序是同一类？（ ）

   {{ select(3) }}

• 希尔排序
• 快速排序
• 堆排序
• 冒泡排序

4. 下面Python代码用于求斐波那契数列，该数列第1、2项为1，以后各项均是前两项之和。函数Fibo()属于（ ）。

   def Fibo(N):
       if N == 1 or N == 2:
           return 1
       fiboList = [1, 1]
       for i in range(2, N):
           fiboList.append(fiboList[i - 1] + fiboList[i - 2])
       return fiboList[N-1]
   

   {{ select(4) }}

• 枚举算法
• 贪心算法
• 迭代算法
• 递归算法

5. 下面Python代码用于将输入金额换成最少币种组合方案，其实现算法是（ ）。

   def findCoins(coins, Money):
       coins_used = []
       for coin in coins:
           while Money >= coin:
               coins_used.append(coin)
               Money -= coin
       return coins_used
   

   {{ select(5) }}

• 枚举算法
• 贪心算法
• 迭代算法
• 递归算法

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

   def count_if(iterData, *, key=None):
       if key == None:
           return len(iterData)
       Count = 0
       for i in iterData:
           Count += bool(key(i))
       return Count
   

   {{ select(6) }}

• 执行print(count_if(range(100))) 将输出100
• 执行print(count_if(range(-10,10), key = abs)) 将输出19
• 执行print(count_if(range(-100,10), key = lambda x:x > 5)) 将输出4
• 代码Count += bool(key(i)) 存在错误

7. 在下面的Python代码中，最后一行用于输出小于0的list，横线处不能填入的代码是（ ）。

   def LT(a, b):
       return a < b
   lstData = list(range(-100,100))
   print(___________________________)
   

   {{ select(7) }}

• [x for x in lstData if x < 0]
• list(filter(lambda x: x < 0, lstData))
• list(filter(LT(x,0), lstData))
• [x for x in lstData if LT(x, 0)]

8. 汉字的unicode编码界于0x4E00和0x9FA5之间。下面Python的代码用于读取红楼们和水浒传文本。如果要能完整阅读这两本小说，求出需要认识的汉字集合，横线处应填入代码是（ ）。

   shzFile = open("水浒传.txt", "r", encoding = "utf-8")
   hlmFile = open("红楼梦.txt", "r", encoding = "utf-8")
   sSet = set(shzFile.read())
   hSet = set(hlmFile.read())
   shzFile.close()
   hlmFile.close()
   print(________________________________)
   

   {{ select(8) }}

• {x for x in (sSet + hSet) if 0x4E00 <= ord(x) <= 0x9FA5}
• {x for x in (sSet | hSet) if 0x4E00 <= x <= 0x9FA5}
• {x for x in (sSet + hSet) if 0x4E00 <= x <= 0x9FA5}
• {x for x in (sSet | hSet) if 0x4E00 <= ord(x) <= 0x9FA5}

9. 求回文子字符串，如：在ABCDDCBAXz中，DD、CDDC、BCDDCB、ABCDDCBA均为回文子字符串。下面Python代码是其实现，横线处应填入的代码是（ ）。

   srcStr = input()
   symList = [] #保存回文子字符串
   for i in range(len(srcStr)):
       for j in range(i + 2, len(srcStr) + 1):
           subStr = ___________
           if subStr == _____________:
               symList.append(subStr)
   for i in sorted(symList, key = lambda x: len(x)):
       print(i)
   

   {{ select(9) }}

• srcStr[i:j], subStr[::-1]
• srcStr[i:j], subStr[j:i:-1]
• srcStr[i+2:j], subStr[j-1:i:-1]
• srcStr[i:j+2], subStr[j-1:i-1:-1]

10. 上面代码的时间复杂度是（ ）。

    {{ select(10) }}

• (O(n))
• (O(n^2))
• (O(n^3))
• (O(n \log n))

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

    def Sort(lst):
        for i in range(1, len(lst)):
            key = lst[i]
            j = i - 1
            while j >= 0 and key < lst[j]:
                lst[j + 1] = lst[j]
                j -= 1
            lst[j + 1] = key
    lst = [4,5,13,2,7,10,1,3,8,11,6,9,12]
    lst = Sort(lst)
    print("sorted list:", lst)
    

    {{ select(11) }}

• 该段代码是插入排序算法的实现
• 如果lst完全有序，则时间复杂度为 (O(n))
• 如果lst完全逆序，则时间复杂度为 (O(n^2))
• 由于Sort()函数没有返回值，没有最终达到排序效果

12. 下面Python函数nGram()用于逐一从字符串中截取n个字符，如：nGram("ABCDEF",2)将逐一截取为AB、BC、CD、DE、EF，如：nGram("ABCDEF",3)将逐一截取为ABC、BCD、CDE、DEF，并统计每种截取的数量，横线处应填入代码是（ ）。

    def nGram(S,n):
        Result = {} #保存截取字符串及其数量
        for i in range(________________):
            nChar = ________________
            Result[nChar] = Result.get(nChar,0) + 1
        return Result
    

    {{ select(12) }}

• len(S)-n, S[i:n]
• len(S)-n+1, S[i:i+n]
• len(S), S[i:i+n]
• len(S)-n, S[i:i+n]

13. 上题代码的时间复杂度是（ ）。

    {{ select(13) }}

• (O(n))
• (O(n^2))
• (O(n \log n))
• (O(n^3))

14. 下面是埃氏素数筛的Python实现，横线上应填入的代码是（ ）。

    def listPrime(N):
        primeList = list(range(N+1))
        primeList[0] = primeList[1] = False
        for i in range(2, int(N ** 0.5) + 1):
            if primeList[i] != False:
                for j in range(_____________):
                    primeList[j] = False
        return [x for x in primeList if x != False]
    

    {{ select(14) }}

• i + i, N + 1, 2
• i * i, N + 1, i
• i * i, N, i * i
• i, N + 1, i

15. 上题代码的时间复杂度是（ ）。

    {{ select(15) }}

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

判断题

1. 在程序设计中，i * i的效率通常比i ** 2 更高。（ ）

   {{ select(16) }}

• 对
• 错

2. 求解指定正整数范围内所有质数，采用线性筛算法比埃氏筛效率更高。（ ）

   {{ select(17) }}

• 对
• 错

3. Python没有指针语法，不能实现C++中涉及指针的算法。（ ）

   {{ select(18) }}

• 对
• 错

4. 如果将双向链表的最后一个元素指向第一个元素，则构成环状链表。（ ）

   {{ select(19) }}

• 对
• 错

5. 链表不能采用快速排序或堆排序，但可以采用插入排序。（ ）

   {{ select(20) }}

• 对
• 错

6. 在Python中，set或dict因为存储时即自动排序，因此可以用二分法查找，时间复杂度为 (O(\log n))。（ ）

   {{ select(21) }}

• 对
• 错

7. 如果自定义class已经定义了__lt__() 魔术方法，则包含该类实例的数据结构，则将自动支持内置函数sorted()。（ ）

   {{ select(22) }}

• 对
• 错

8. 归并排序和快速排序都采用递归实现，也都是不稳定排序。（ ）

   {{ select(23) }}

• 对
• 错

9. 下面的Python代码能实现十进制正整数N转换为2、8、10、16，可适用于16进制以内进制。其中n和ds分别表示将转换的数以及目标进制。（ ）

   n, ds = map(int, input().split())
   rst = "" #保存转换结果
   digDict = {i:c for i,c in enumerate("0123456789ABCDEF")}
   while n != 0:
       rst = digDict[n % ds] + rst
       n //= ds
   print(rst)
   

   {{ select(24) }}

• 对
• 错

10. Python代码 print(sorted(range(10),key=lambda x:x%5)) 执行时将报错。（ ）

    {{ select(25) }}

• 对
• 错