GESP 2024年 9月认证 Python 五级真题

题号 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 答案 B C A C C B C C A D D C D D C Python　五级 2024 年 09 ⽉ 1 单选题（每题 2 分，共 30 分） 第 1 题 在升序数组 nums 中寻找⽬标值 target，下列程序可以填⼊的是（ ） A. mid = (right + left) // 2 + left B. mid = (right - left) // 2 + left C. mid = (right - left) // 2 -right D. mid = (right + left) // 2 - left 第 2 题 500个病毒样本中，已知有⼀个是病毒检测呈阳性，⽤试纸测试阳性病毒以后，试纸在3天以后会变⾊，⽤试 纸测试时间不计，三天以后要出结果，请问最少⽤多少个试纸能够找出哪⼀个病毒样本有毒（） A. 499 B. 250 C. 9 D. 125 第 3 题 ⼀名收银员，给顾客找零，找零的⽬标是给出确定⾦额的同时，使⽤尽可能少的硬币。有不同⾯额的硬币： 1分，5分，10分，25分.如果需要给顾客准确的零钱77分，同时使⽤最少的硬币下列程序中横线应该填写（ ）。 class Search(object): def search(self, nums, target): left, right = 0, len(nums) - 1 while left <= right: ________________________________________ if nums[mid] == target: return mid elif nums[mid] > target: right = mid - 1 else: left = mid + 1 return -1 1 2 3 4 5 6 7 8 9 10 11 12 A. amount -= coin B. amount <= coin C. amount >= coin D. amount += coin 第 4 题 下列程序是素数筛的程序，横线处应该填上（ ）。 A. for j in range(i, n+1, i): B. for j in range(i*i, 1, n): C. for j in range(i*i, n+1, i): D. for j in range(i, n, i): 第 5 题 下⾯程序是埃⽒筛的⼀个实现，横线处应该填写（ ）。 A. for i in range(i*i,n+1,i): B. for j in range(i*i,n,j): def coin_change(amount, coins): result = [] for coin in sorted(coins, reverse=True): while amount >= coin: ___________________ result.append(coin) return result coins = [1, 5, 10, 25] amount = 63 1 2 3 4 5 6 7 8 9 10 def sieve(n): if n < 2: return [] prime = [True] * (n+1) prime[0] = prime[1] = False for i in range(2, int(math.sqrt(n)) + 1): if prime[i]: _______________________ prime[j] = False return [p for p in range(2, n+1) if prime[p]] for prime in sieve_of_eratosthenes(100): print(prime) 1 2 3 4 5 6 7 8 9 10 11 12 n = 10**8 s = [0]*(n+1) k=0 for i in range(2,n+1): if s[i]==0: k+=1 ___________________________ s[j]=1 1 2 3 4 5 6 7 8 C. for j in range(i*i,n+1,i): D. for j in range(j*j,n+1,i): 第 6 题 下列程序中，使⽤了⼆分查找算法，横线处应该填写的是（）。 A. mid = (low - high) // 2 B. mid = (low + high) // 2 C. mid = (low + high) / 2 D. mid = (low - high) / 2 第 7 题 正整数1024的所有约数的和为多少( )。 A. 2050 B. 2059 C. 2047 D. 2044 第 8 题 下⾯程序是对n！进⾏唯⼀分解，横线处应该填⼊的是（ ）。 A. while n % i != 0 and i != n: B. while n % i == 0 and i == n: C. while n % i == 0 and i != n: def search(arr, x): low = 0 high = len(arr) - 1 while low <= high: __________________ if arr[mid] == x: return mid elif arr[mid] > x: high = mid - 1 else: low = mid + 1 return -1 1 2 3 4 5 6 7 8 9 10 11 12 def unique_fac(n): print(n, '=', end='') for i in range(2, n + 1): _____________________________ print(' {}*'.format(i), end='') n //= i if n % i == 0 and i == n: print(' {}'.format(i), end='') break unique_fac(math.factorial(5)) 1 2 3 4 5 6 7 8 9 10 11 D. while n % i != 0 and i == n: 第 9 题 假设有⼀些物品，每个物品都有⾃⼰的重量，我们需要将这些物品装⼊箱⼦中，每个箱⼦也有⾃⼰的重量限 制。贪⼼算法每次都选择重量最轻的物品放⼊当前最轻的箱⼦中，如果箱⼦可以装下，就放⼊；如果箱⼦不能装 下，就尝试下⼀个箱⼦，直到找到可以放⼊的箱⼦。下列贪⼼算法程序中，横线处应该填⼊的是（ ）。 A. boxes[j] = (box[0] - item, boxes[j][1]) B. boxes[i] = (box[0] - item, boxes[j][1]) C. boxes[j] = (box[0] - item, boxes[i][1]) D. boxes[i] = (box[0] - item, boxes[i][1]) 第 10 题 下列归并算法程序中，横线处应该填⼊的是（ ）。 A. while i > len(left) and j < len(right): B. while i < len(left) and j > len(right): def box_packing(items, boxes): boxes.sort(key=lambda x: x[0]) items.sort() taken = [False] * len(items) for i, item in enumerate(items): taken[i] = True for j, box in enumerate(boxes): if box[0] >= item: ______________________________ break return [(box[1], sum(taken)) for box in boxes] 1 2 3 4 5 6 7 8 9 10 11 def merge_sort(arr): if len(arr) <= 1: return arr mid = len(arr) // 2 left = arr[:mid] right = arr[mid:] merge_sort(left) merge_sort(right) return merge(left, right) def merge(left, right): result = [] i, j = 0, 0 ——————————————————————————————— if left[i] < right[j]: result.append(left[i]) i += 1 else: result.append(right[j]) j += 1 result += left[i:] result += right[j:] return result 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 C. while i > len(left) and j > len(right): D. while i < len(left) and j < len(right): 第 11 题 下列快速排序算法中，横线处应该填⼊的是（ ）。 A. p = arr[len() // 2] B. p = arr[len(arr)+1 // 2] C. p = arr[len(arr)-1 // 2] D. p = arr[len(arr) // 2] 第 12 题 下列⼆分枚举算法中，{ }处应该填⼊的程序是（{}不算做程序的⼀部分）（ ）。 A. ```Python mid = (low + high) // 2 if arr[mid] == x: return mid elif arr[mid+1] > x: high = mid - 1 else: low = mid + 1 def quick(arr): if len(arr) <= 1: return arr ____________________ left = [x for x in arr if x < p] middle = [x for x in arr if x == p] right = [x for x in arr if x > p] return quick(left) + middle + quick(right) 1 2 3 4 5 6 7 8 def binary_search(arr, x): low = 0 high = len(arr) - 1 while low <= high: { } return -1 1 2 3 4 5 6 7 8 - [ ] **B.** ```Python mid = (low + high) // 2 if arr[mid] != x: return mid elif arr[mid+1] > x: high = mid - 1 else: low = mid + 1 1 2 3 4 5 6 7 8 9 C. ```Python mid = (low + high) // 2 if arr[mid] == x: return mid elif arr[mid] > x: high = mid - 1 else: low = mid + 1 第 13 题 下⾯代码是寻找⽔仙花数的程序，横线处应该填写的代码是（ ）。【是指⼀个n位数（n≥3），其每位数字 的n次幂之和等于它本⾝】 A. ```Python sum_of_powers = sum(int(digit) ** num_digits for digit in num) C. ```Python sum_of_powers = sum(int(num) ** num_digits for digit in str_num) 第 14 题 对于正整数n，欧拉函数f(n),表⽰⼩于或等于n的正整数中与n互质的数的数⽬，例如f(8)=4。f(100)=（ ）。 A. 50 B. 55 C. 45 - [ ] **D.** ```Python mid = (low + high) // 2 if arr[mid] ！= x: return mid elif arr[mid] > x: high = mid - 1 else: low = mid + 1 1 2 3 4 5 6 7 8 9 def is_narcissistic_num(num): str_num = str(num) num_digits = len(str_num) ———————————————————————————— return num == sum_of_powers for i in range(100, 10000): if is_narcissistic_num(i): print(i, "是水仙花数") 1 2 3 4 5 6 7 8 9 - [ ] **B.** ```Python sum_of_powers = sum(int(digit) ** num for digit in str_num) 1 2 3 - [ ] **D.** ```Python sum_of_powers = sum(int(digit) ** num_digits for digit in str_num) 1 2 3 题号 1 2 3 4 5 6 7 8 9 10 答案 D. 40 第 15 题 下列程序输出的是( )。 A. chen a dai B. dai a chen C. iad a nehc D. chenadai 2 判断题（每题 2 分，共 20 分） 第 1 题 (-1) mod 127和126 mod 127 的结果是一样的 第 2 题 一个数的反码，实际上是这个数对于一个模的同余数 第 3 题 1997和615用欧几里得算法计算最大公约数的过程如下： 第 4 题 欧几里得算法适用于实数 第 5 题 每个大于1的整数可以唯一地写成质数的乘积的形式 第 6 题 贪婪算法的复杂度通常是线性的，即O(n)，其中n是输入的大小 第 7 题 归并排序的时间复杂度为O(n log n) 第 8 题 根据同余计算，可以推导出(a∗b)%m=(a%m∗b%m)%m 第 9 题 二分查找算法的复杂度通常表示为O(log n)，其中n是数组的长度 第 10 题 def(十六进制) = 103231(五进制) def reverse(string): if len(string) == 0: return temp = string[0] reverse(string[1:]) print(temp, end='') string = "chen a dai" reverse(string) 1 2 3 4 5 6 7 8 1997/615=3(余152) 615/152=4(余7) 152/7=21(余5) 7/5=1(余2) 5/2=2(余1) 2/1=2(余0) 得出最大公约是是1 1 2 3 4 5 6 7 子任务编号 数据点占比 1 20% 2 20% 3 60% 3 编程题（每题 25 分，共 50 分） 3.1 编程题 1 试题名称：⼩杨的武器 时间限制：1.0 s 内存限制：512.0 MB 3.1.1 题面描述 ⼩杨有 种不同的武器，他对第 种武器的初始熟练度为 。 ⼩杨会依次参加 场战⽃，每场战⽃⼩杨只能且必须选择⼀种武器使⽤，假设⼩杨使⽤了第 种武器参加了第 场 战⽃，战⽃前该武器的熟练度为 ，则战⽃后⼩杨对该武器的熟练度会变为 。需要注意的是， 可能是正 数， 或负数，这意味着⼩杨参加战⽃后对武器的熟练度可能会提⾼，也可能会不变，还有可能降低。 ⼩杨想请你编写程序帮他计算出如何选择武器才能使得 场战⽃后，⾃⼰对 种武器的熟练度的最⼤值尽可能⼤。 3.1.2 输入格式 第⼀⾏包含两个正整数 ，含义如题⾯所⽰。 第⼆⾏包含 个正整数 ，代表⼩杨对武器的初始熟练度。 第三⾏包含 个正整数 ，代表每场战⽃后武器熟练度的变化值。 3.1.3 输出格式 输出⼀个整数，代表 场战⽃后⼩杨对 种武器的熟练度的最⼤值最⼤是多少。 3.1.4 样例1 ⼀种最优的选择⽅案为，第⼀场战⽃⼩杨选择第⼀种武器，第⼆场战⽃⼩杨选择第⼆种武器。 对于全部数据，保证有 ， 。 3.1.5 参考程序 2 2 9 9 1 -1 1 2 3 101 N = 100010 a = [0] * N c = [0] * N n, m = map(int, input().split()) 1 2 3 4 5 6 3.2 编程题 2 试题名称：挑战怪物 时间限制：1.0 s 内存限制：512.0 MB 3.2.1 题面描述 ⼩杨正在和⼀个怪物战⽃，怪物的⾎量为 ，只有当怪物的⾎量恰好为 时⼩杨才能够成功击败怪物。 ⼩杨有两种攻击怪物的⽅式： 物理攻击。假设当前为⼩杨第 次使⽤物理攻击，则会对怪物造成 点伤害。 魔法攻击。⼩杨选择任意⼀个质数 （ 不能超过怪物当前⾎量），对怪物造成 点伤害。由于⼩杨并不擅长魔 法，他只能使⽤⾄多⼀次魔法攻击。 ⼩杨想知道⾃⼰能否击败怪物，如果能，⼩杨想知道⾃⼰最少需要多少次攻击。 3.2.2 输入格式 第⼀⾏包含⼀个正整数 ，代表测试⽤例组数。 接下来是 组测试⽤例。对于每组测试⽤例，第⼀⾏包含⼀个正整数 ，代表怪物⾎量。 3.2.3 输出格式 对于每组测试⽤例，如果⼩杨能够击败怪物，输出⼀个整数，代表⼩杨需要的最少攻击次数，如果不能击败怪物， 输出 。 3.2.4 样例1 mx = -10000 s = input().split() for i in range(1, n + 1): c[i] = int(s[i-1]) mx = max(mx, c[i]) s = input().split() for i in range(1, m + 1): a[i] = int(s[i-1]) for i in range(1, m + 1): if n == 1 or a[i] > 0: mx += a[i] print(mx) 7 8 9 10 11 12 13 14 15 16 17 18 19 20 3 6 188 9999 1 2 3 4 2 4 -1 1 2 3 子任务编号 数据点占比 1 20% 2 20% 3 60% 对于第⼀组测试⽤例，⼀种可能的最优⽅案为，⼩杨先对怪物使⽤魔法攻击，选择质数 造成 点伤害，之后对怪 物使⽤第 次物理攻击，造成 点伤害，怪物⾎量恰好为 ，⼩杨成功击败怪物。 对于全部数据，保证有 。 3.2.5 参考程序 prime = [] is_prime = [False] * 100010 def Eratosthenes(n): is_prime[0] = is_prime[1] = False for i in range(2, n + 1): is_prime[i] = True for i in range(2, n + 1): if is_prime[i]: prime.append(i) if i * i > n: continue for j in range(i * i, n + 1, i): is_prime[j] = False Eratosthenes(100000) t = int(input()) for _ in range(t): tmp = 1 x = int(input()) ans = 0 while True: if is_prime[x]: ans += 1 break x -= tmp ans += 1 if x <= 0: if x < 0: ans = -1 break tmp *= 2 print(ans) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34