本文收錄于專欄《Python等級認證CCF-GESP真題解析》，專欄總目錄：點這里，訂閱后可閱讀專欄內所有文章。

一、單選題（每題 2 分，共 30 分）

第 1 題

在Python中，print((c for c in “GESP”))的輸出是（ ）。
A. (‘G’, ‘E’, ‘S’, ‘P’)
B. [‘G’, ‘E’, ‘S’, ‘P’]
C. {‘G’, ‘E’, ‘S’, ‘P’}
D. 以上選項均不正確

答案：D

第 2 題

下面有關快速排序的說法，錯誤的是（ ）。
A. 快速排序算法通常采用遞歸實現。
B. 快速排序算法是一種穩定排序算法。
C. 如果被排序數組或者list已排序或逆序，其時間復雜度是 $O(N^2)$。
D. 快速排序是一種原地（in-place）排序算法。

答案：B

第 3 題

內排序有不同的類別，從排序算法的實現思路上考慮，下面哪種排序算法和插入排序是同一類？（ ）
A. 希爾排序
B. 快速排序
C. 堆排序
D. 冒泡排序

答案：A

第 4 題

下面Python代碼用于求斐波那契數列，該數列第1、2項為1，以后各項均是前兩項之和。函數Fibo()屬于()。

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

A. 枚舉算法
B. 貪心算法
C. 迭代算法
D. 遞歸算法

答案：C

第 5 題

下面Python代碼用于將輸入金額換成最少幣種組合方案，其實現算法是( )。

def findCoins(coins, Money):coins_used = []for coin in coins:while Money >= coin:coins_used.append(coin)Money -= coinreturn coins_usedcoins = [100, 50, 20, 10, 5, 2, 1] #貨幣種類，單位相同
M = int(input()) #輸入換算的金額
coins_needed = find_coins(coins, M)result = [(c,coins_needed.count(c)) for c in coins]
result = [x for x in result if x[1] > 0]

A. 枚舉算法
B. 貪心算法
C. 迭代算法
D. 遞歸算法

答案：B

第 6 題

有關下面Python的代碼，錯誤的是( )。

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

A. 執行 print(count_if(range(100))) 將輸出 100
B. 執行 print(count_if(range(-10,10), key = abs)) 將輸出 19
C. 執行 print(count_if(range(-100,10),key = lambda x:x > 5)) 將輸出 4
D. 代碼 Count += bool(key(i)) 存在錯誤

答案：D

第 7 題

在下面的Python代碼中，最后一行用于輸出小于0的list，橫線處不能填入的代碼是( )。

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

A. [x for x in lstData if x < 0 ]
B. list(filter(lambda x: x < 0, lstData))
C. list(filter(LT(x,0), lstData))
D. [x for x in lstData if LT(x, 0)]

答案：C

第 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(________________________________)

A. {x for x in (sSet + hSet) if 0x4E00 <= ord(x) <= 0x9FA5 }
B. {x for x in (sSet | hSet) if 0x4E00 <= x <= 0x9FA5 }
C. {x for x in (sSet + hSet) if 0x4E00 <= x <= 0x9FA5 }
D. {x for x in (sSet | hSet) if 0x4E00 <= ord(x) <= 0x9FA5 }

答案：D

第 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)

A. srcStr[i:j] ， subStr[::-1]
B. srcStr[i:j] ， subStr[j:i:-1]
C. srcStr[i+2:j] ， subStr[j-1:i:-1]
D. srcStr[i:j+2] ， subStr[j-1:i-1:-1]

答案：A

第 10 題

上面代碼的時間復雜度是（ ）。
A.$O(logN)$
B.$O(NlogN)$
C.$O(N)$
D.$O(N^2)$

答案：A

第 11 題

有關下面Python代碼的說法，錯誤的是（ ）。

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

A. 該段代碼是插入排序算法的實現
B. 如果lst完全有序，則時間復雜度為
C. 如果lst完全逆序，則時間復雜度為
D. 由于Sort()函數沒有返回值，沒有最終達到排序效果

答案：D

第 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) + 1return Result

A. len(S)-n ， S[i:n]
B. len(S)-n+1 ， S[i:i+n]
C. len(S) ， S[i:i+n]
D. len(S)-n ， S[i:i+n]

答案：B

第 13 題

上題代碼的時間復雜度是（ ）。
A.$O(logN)$
B.$O(NlogN)$
C.$O(N)$
D.$O(N^2)$

答案：C

第 14 題

下面是埃氏素數篩的Python實現，橫線上應填入的代碼是（ ）。

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

A. i + i, N + 1, 2
B. i * i, N + 1, i
C. i * i, N, i * i
D. i, N + 1, i

答案：B

第 15 題

上題代碼的時間復雜度是（ ）。
A.$O(N^2)$
B.$O(NlogN)$
C.$O(NloglogN)$
D.$O(N)$

答案：C

二、判斷題（每題 2 分，共 20 分）

第 16 題

在程序設計中，i * i的效率通常比i ** 2 更高。（ ）

答案：正確

第 17 題

求解指定正整數范圍內所有質數，采用線性篩算法比埃氏篩效率更高。（ ）

答案：正確

第 18 題

Python沒有指針語法，不能實現C++中涉及指針的算法。（ ）

答案：錯誤

第 19 題

如果將雙向鏈表的最后一個元素指向第一個元素，則構成環狀鏈表。（ ）

答案：正確

第 20 題

鏈表不能采用快速排序或堆排序，但可以采用插入排序。( )

答案：正確

第 21 題

在Python中，set或dict因為存儲時即自動排序，因此可以用二分法查找，時間復雜度為 $O(logN)$。（ ）

答案：錯誤

第 22 題

如果自定義class已經定義了 __lt__() 魔術方法，則包含該類實例的數據結構，則將自動支持內置函數sorted()。（ ）

答案：正確

第 23 題

歸并排序和快速排序都采用遞歸實現，也都是不穩定排序。（ ）

答案：錯誤

第 24 題

下面的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] + rstn //= ds
print(rst)

答案：正確

第 25 題

Python代碼 print(sorted(range(10),key=lambda x:x%5)) 執行時將報錯。（ ）

答案：錯誤

三、編程題（每題 25 分，共 50 分）

第 26 題

試題名稱：黑白格
時間限制：1.0 s
內存限制：512.0 MB
題面描述
小楊有一個 $n$ 行 $m$ 列的網格圖，其中每個格子要么是白色，要么是黑色。
小楊想知道至少包含 $k$ 個黑色格子的最小子矩形包含了多少個格子。
輸入格式
第一行包含三個正整數 $n,m,k$，含義如題面所示。
之后 $n$ 行，每行一個長度為 $m$ 的 $01$ 串，代表網格圖第 $i$ 行格子的顏色，如果為 $0$，則對應格子為白色，否則為黑色。
輸出格式
輸出一個整數，代表至少包含 $k$ 個黑色格子的最小子矩形包含格子的數量，如果不存在則輸出 $0$。
樣例1

4 5 5
00000
01111
00011
00011

6

樣例解釋
對于樣例1，假設 ($i,j$) 代表第 $i$ 行第 $j$ 列，至少包含 $5$ 個黑色格子的最小子矩形的四個頂點為 (2,4)，(2,5)，(4,4)，(4,5)，共包含 $6$ 個格子。
數據范圍

對于全部數據，保證有 $1\le n,m\le 100,1\le k\le n\times m$。
參考程序

N = 110
w = [[0] * N for _ in range(N)]
sum_w = [[0] * N for _ in range(N)]def main():n, m, k = map(int, input().split())for i in range(1, n+1):s = input()for j in range(1, m+1):w[i][j] = int(s[j-1])sum_w[i][j] = sum_w[i][j-1] + w[i][j]ans = 0for i in range(1, m+1):for j in range(i, m+1):num = []now = 0for l in range(1, n+1):tmp = sum_w[l][j] - sum_w[l][i-1]now += tmpnum.append(now)if now >= k:if ans == 0:ans = (j-i+1) * lelse:ans = min(ans, (j-i+1) * l)L, R = 1, lwhile L < R:mid = (L + R + 1) // 2if now - num[mid-1] >= k:L = midelse:R = mid - 1if now - num[L-1] >= k:if ans == 0:ans = (j-i+1) * (l-L)else:ans = min(ans, (j-i+1) * (l-L))print(ans)if __name__ == "__main__":main()

第 27 題

試題名稱：小楊的幸運數字
時間限制：1.0 s
內存限制：512.0 MB
題面描述
小楊認為他的幸運數字應該恰好有兩種不同的質因子，例如，$12=2\times 2\times 3$ 的質因子有 $2,3$，恰好為兩種不同的質因子，因此 $12$是幸運數字，而 $30=2\times 3\times 5$ 的質因子有 $2,3,5$，不符合要求，不為幸運數字。
小楊現在有 $n$ 個正整數，他想知道每個正整數是否是他的幸運數字。
輸入格式
第一行包含一個正整數 $n$，代表正整數個數。
之后 $n$ 行，每行一個正整數。
輸出格式
輸出 $n$ 行，對于每個正整數，如果是幸運數字，輸出 $1$，否則輸出 $0$。
樣例1

3
7
12
30

0
1
0

樣例解釋
$7$的質因子有 $7$，只有一種。
$12$的質因子有$2,3$ ，恰好有兩種。 ，
$30$的質因子有 $2,3,5$，有三種。 ， ，
數據范圍

對于全部數據，保證有 $1\le n\le 10^4$，每個正整數 $a_i$ 滿足 $2\le a_i\le 10^6$。

參考程序

N = 10**5 + 10
a = [0] * Ndef calc(x):i = 2mp = {}while i * i <= x:if x % i == 0:mp[i]=1while x % i == 0:x //= ii += 1if x != 1:mp[x]=1return int(len(mp.items()))def main():n = int(input())for i in range(1, n + 1):a[i] = int(input())x = calc(a[i])if x == 2:print("1")else:print("0")if __name__ == "__main__":
main()