GESP2024年12月Python五级试卷
从PDF导入：GESP2024年12月Python五级试卷
试卷题目预览
下面的程序中，x,y都是正整数，完成的算法是（ ）
def chenadai(x, y):
while y:
x, y = y, x % y
return x
下列程序中实现的是（ ）
def chenadai(x, y):
return x * y // (x,y的最大公约数)
欧几里得算法又称作辗转相除算法，下面程序中是这种算法的是（ ）
下列程序是二分法的程序，横线处应该填上（ ）
def binary_search(arr, target):
left = 0
right = len(arr) - 1
while left <= right:
mid = (left + right) // 2
_________________________
return -1
下面折半查找程序的时间复杂度为（ ）
下列程序中，使用了埃氏筛法，横线处应该填写的是（ ）
def aishishai(n):
if n < 2:
return []
prime = [True] * (n + 1)
prime[0] = prime[1] = False
————————————————————————————————
if prime[p]:
for i in range(p * p, n + 1, p):
prime[i] = False
return [p for p in range(n + 1) if prime[p]]
18到100之间的所有素数的和为多少？（ ）
下面程序是对2024进行唯一分解，最后的结果应该是（ ）。
def weiyi(n):
factors = {}
for i in range(2, n+1):
while n % i == 0:
if i in factors:
factors[i] += 1
else:
factors[i] = 1
n //= i
return factors
下面关于循环链表的说法正确的是（ ）。
下列归并算法程序中，横线处应该填入的是（ ）
def merge_sort(array):
if len(array) == 1:
return array
_________________________
return merge(left, right)
def merge(left, right):
left_index, right_index, merge_array = 0, 0, list()
while left_index < len(left) and right_index < len(right):
if left[left_index] <= right[right_index]:
merge_array.append(left[left_index])
left_index += 1
else:
merge_array.append(right[right_index])
right_index += 1
merge_array = merge_array + left[left_index:] + right[right_index:]
return merge_array
关于算法复杂度，下列说法不正确的是（ ）
下列程序中，实现了16进制转到8进制。横线处应该填入的是（ ）
def dec_conversion_n(n, base):
str_list = "0123456789ABCDEF"
if n < base:
return str_list[n]
else:
___________________________
水仙花数是指一个3位数，它的每个数位上的数字的3次幂之和等于它本身。下面代码是计算100到n之间有多少个水仙花数的程序，横线处应该填写的是（ ）
n = int(input("输入一个正整数N:"))
sum = 0
for i in range(100,n+1):
_______________________
print(sum)
下面程序输出的是（ ）
def func(x):
if x%2 == 1:
return x+1
else:
return func(x-1)
print(func(9))
print(func(6))
旋转数组是一种常见的数据结构问题，通常是指一个有序数组经过旋转后，使得所有元素逆序排列。整数数组 nums 按升序排列，数组中的值互不相同。在预先未知的某个下标 k（0 <= k < nums.length）上进行了旋转，使数组变为 [nums[k], nums[k + 1],..., nums[n - 1], nums[0], nums[1],..., nums[k - 1]]（下标从 0 开始计数）。现在给定旋转后的数组 nums 和一个整数 target，如果 nums 中存在这个目标值 target，则返回它的下标，否则返回-1。下面程序中（）处应填入的程序是：例如，给定一个数组 [4,5,6,7,0,1,2]，它可能经过旋转变为 [0,1,2,4,5,6,7]。二分查找算法搜索旋转排序数组的程序，下面横线中，应填入的一行或多行代码是（ ）
def search(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return True
if nums[mid] > nums[right]:
if nums[mid] > target or nums[left] <= target:
right = mid - 1
else:
left = mid + 1
elif nums[mid] < nums[right]:
___________________________
else:
right -= 1
return False
两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数。（ ）
任何一个大于1的自然数都可以分解成若干个不同的质数的乘积，且分解方式是唯一的。（ ）
要得到不大于某个自然数N的所有素数，只要在2至N中将不大于√N的素数的倍数全部划去即可。（ ）
任何一个大于1的自然数，要么所有质因子都小于等于√n，要么只有一个质因子大于√n，其余质因子都小于√n。（ ）
贪心算法的空间复杂度通常是O(1)。（ ）
归并排序的空间复杂度为O(n)。（ ）
时间复杂度对比：O(1) < O(log n) < O(n) < O(n log n) < O(n²)。（ ）
对于任意整数a, b, m，(a+b)%m = ((a%m)+(b%m))%m。（ ）
下列程序输出的是21。（ ）
def digui(n):
if n <= 1:
return n
else:
return digui(n-1) + digui(n-2)
print(digui(8))
CCF(十六进制) = 1653(十三进制)。（ ）
奇妙数字
时间限制：1.0 s
内存限制：512.0 MB
题面描述
小杨认为一个数字x是奇妙数字当且仅当x=p^k，其中p为任意质数且k为正整数。对于一个正整数n，小杨想要构建一个包含若干个奇妙数字的集合S，使其满足：集合中不包含相同的数字；S中所有数字的乘积是n的因子。小杨希望集合包含的奇妙数字尽可能多，请你帮他计算出满足条件的集合最多包含多少个奇妙数字。
第一行包含一个正整数n，含义如题面所示。
输出一个正整数，代表满足条件的集合最多包含多少个奇妙数字。
样例输入 128 样例输出 3 数据范围 对于全部数据，保证有1 ≤ n ≤ 10¹²。
武器强化
时间限制：2.0 s
内存限制：512.0 MB
题面描述
小杨有n种武器和m种强化材料。第i种强化材料会适配第pi种武器，小杨可以花费ci金币将该材料对应的适配武器修改为任意武器。小杨最喜欢第1种武器，因此他希望适配该武器的强化材料种类数严格大于其他的武器，请你帮小杨计算为了满足该条件最少需要花费多少金币。
第一行包含两个正整数n, m。之后m行，每行包含两个正整数pi, ci，代表第i种强化材料的适配武器和修改花费。
输出一个整数，代表最少花费的金币。
样例输入 4 4 1 1 2 1 3 1 3 2 样例输出 1 数据范围 对于全部数据，保证有2 ≤ n ≤ 10⁵，n ≤ m ≤ 10⁵，1 ≤ pi ≤ n，1 ≤ ci ≤ 10⁹。