GESP Python 5级 2024.09

在升序数组 nums 中寻找目标值 target，下列程序可以填入的是()

class Search(object):
 def search(self, nums, target):
 left, right = 0, len(nums) - 1
 while left target:
 right = mid - 1
 else:
 left = mid + 1
 return -1

500个病毒样本中，已知有一个是病毒检测呈阳性，用试纸测试阳性病毒以后，试纸在3天以后会变色，用试纸测试时间不计，三天以后要出结果，请问最少用多少个试纸能够找出哪一个病毒样本有毒？

一名收银员，给顾客找零，找零的目标是给出确定金额的同时，使用尽可能少的硬币。有不同面额的硬币：1分，5分，10分，25分.如果需要给顾客准确的零钱77分，同时使用最少的硬币下列程序中横线应该填写（ ）。

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

下列程序是素数筛的程序，横线处应该填上（ ）。

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)

下面程序是埃氏筛的一个实现，横线处应该填写（ ）。

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

下列程序中，使用了二分查找算法，横线处应该填写的是（）。

def search(arr, x):
 low = 0
 high = len(arr) - 1
 while low x:
 high = mid - 1
 else:
 low = mid + 1
 return -1

正整数1024的所有约数的和为多少( )。

下面程序是对n！进行唯一分解，横线处应该填入的是（ ）。

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

假设有一些物品，每个物品都有自己的重量，我们需要将这些物品装入箱子中，每个箱子也有自己的重量限制。贪心算法每次都选择重量最轻的物品放入当前最轻的箱子中，如果箱子可以装下，就放入；如果箱子不能装下，就尝试下一个箱子，直到找到可以放入的箱子。下列贪心算法程序中，横线处应该填入的是（ ）。

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]

下列归并算法程序中，横线处应该填入的是（ ）。

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