2024年6月CCF—GESP（Python五级）编程能力等级认证试卷

单选题共 15 题

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

快速排序算法通常采用递归实现。

快速排序算法是一种稳定排序算法。

如果被排序数组或者list已排序或逆序，其时间复杂度是 O(N^2)

快速排序是一种原地（in-place）排序算法。

下面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

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]

下面是埃氏素数筛的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]

i + i, N + 1, 2

i * i, N + 1, i

i * i, N, i * i

i, N + 1, i

有关下面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)

该段代码是插入排序算法的实现

如果lst完全有序，则时间复杂度为

如果lst完全逆序，则时间复杂度为

由于Sort()函数没有返回值，没有最终达到排序效果

下面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]

枚举算法

贪心算法

迭代算法

递归算法

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

O(logN)

O(NlogN)

O(N)

O(N^2)

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

def findCoins(coins, Money):
	coins_used = []
	for coin in coins:
		while Money >= coin:
			coins_used.append(coin)
			Money -= coin
	return coins_used
	
coins = [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]

枚举算法

贪心算法

迭代算法

递归算法

汉字的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(________________________________)

{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 }

在Python中，print((c for c in “GESP”))的输出是（）。

(‘G’, ‘E’, ‘S’, ‘P’)

[‘G’, ‘E’, ‘S’, ‘P’]

{‘G’, ‘E’, ‘S’, ‘P’}

以上选项均不正确

10.

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

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

[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)]

11.

求回文子字符串，如：在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)

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]

12.

有关下面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

执行 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)) 存在错误

13.

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

O(logN)

O(NlogN)

O(N)

O(N^2)

14.

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

希尔排序

快速排序

堆排序

冒泡排序

15.

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

O(N^2)

O(NlogN)

O(NloglogN)

O(N)

判断题共 10 题

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

A 正确 B 错误

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

A 正确 B 错误

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

A 正确 B 错误

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

A 正确 B 错误

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

A 正确 B 错误

下面的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)

A 正确 B 错误

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

A 正确 B 错误

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

A 正确 B 错误

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

A 正确 B 错误

10.

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

A 正确 B 错误

编程题共 2 题

小杨的幸运数字

时间限制：1.0 s

内存限制：512.0 MB

题面描述

小杨认为他的幸运数字应该恰好有两种不同的质因子，例如，12=2×2×3 的质因子有2,3，恰好为两种不同的质因子，因此12是幸运数字，而30=2×3×5 的质因子有2,3,5，不符合要求，不为幸运数字。

小杨现在有n个正整数，他想知道每个正整数是否是他的幸运数字。

输入格式

第一行包含一个正整数n，代表正整数个数。

之后n行，每行一个正整数。

输出格式

输出n行，对于每个正整数，如果是幸运数字，输出1，否则输出0。

输入样例

输出样例

0
1
0

样例解释

7的质因子有7，只有一种。

12的质因子有2,3 ，恰好有两种。

30的质因子有2,3,5，有三种。

数据范围

对于全部数据，保证有1≤n≤104，每个正整数ai满足 2≤ai≤106。

黑白格

时间限制：1.0 s

内存限制：512.0 MB

题面描述

小杨有一个n行m列的网格图，其中每个格子要么是白色，要么是黑色。

小杨想知道至少包含k个黑色格子的最小子矩形包含了多少个格子。

输入格式

第一行包含三个正整数n,m,k，含义如题面所示。

之后n行，每行一个长度为m的01串，代表网格图第i行格子的颜色，如果为0，则对应格子为白色，否则为黑色。

输出格式

输出一个整数，代表至少包含k个黑色格子的最小子矩形包含格子的数量，如果不存在则输出0。

输入样例

输出样例

样例解释

对于样例1，假设 (i,j) 代表第i行第j列，至少包含5个黑色格子的最小子矩形的四个顶点为 (2,4)，(2,5)，(4,4)，(4,5)，共包含6个格子。

数据范围

对于全部数据，保证有 1 ≤ n , m ≤ 100 , 1 ≤ k ≤ n × m

提交试卷

退出练习

正在提交