GESP-Python五级 题库
共 27 道题
,第 2 / 2 页
· 按题型筛选,点「查看答案」核对解析
21
判断题
适中
唯一分解定理保证:若一个数未被任何不超过其平方根的质数筛去,则它一定是质数。
A
正确
B
错误
答案与解析
正确答案:对
唯一分解定理表明每个大于1的整数均可唯一表示为质因数的乘积。若一个数不能被任何不超过其平方根的质数整除,则不存在小于等于该数平方根的质因数,进而无法被分解为更小质数的乘积。此时该数不能写成两个大于1的整数之积,因此只能是质数。判断依据在于:所有合数必有质因数不超过其平方根,反之未被筛去则说明无此类质因数。
22
判断题
适中
假设数组a的值域范围是D,以下程序的时间复杂度是O(nlogn+nlogD)。
def check(n , a , k , dist): cnt = 1 last = a [0] for i in range(1 , n): if a [i] - last >= dist : cnt += 1 last = a [i] return cnt >= k def solve(n , a , k): a_sorted = a .copy() a_sorted .sort() l = 0 r = a_sorted [-1] - a_sorted [0] while l < r: mid = (l + r + 1) // 2 if check(n , a_sorted , k , mid): l = mid else: r = mid - 1 return l if __name__ == "__main__": a = [1 , 2 , 8 , 4 , 9] n = 5 k = 3 result = solve(n , a , k) print(result)
A
正确
B
错误
答案与解析
正确答案:对
这道题暂未补解析。
23
判断题
适中
若一个问题满足最优子结构性质,则一定可以用贪心算法得到最优解。()
A
正确
B
错误
答案与解析
正确答案:错
分析问题是否具备最优子结构性质,即原问题的最优解是否包含其子问题的最优解。考察贪心算法适用条件,需验证该问题是否同时满足贪心选择性质和最优子结构。贪心选择性质要求局部最优选择能导向全局最优解,可通过构造法或交换论证判断每次贪心决策能否保持最优性。若仅满足最优子结构而不满足贪心选择性质,则无法保证贪心算法得到最优解。动态规划适用于具有最优子结构的问题,而贪心算法是更特殊的情形,需额外满足贪心选择性质。
24
判断题
适中
线性筛相比埃氏筛的核心改进在于:埃氏筛中一个合数可能被多个质数重复标记,线性筛通过"每个合数只被其最大质因子筛去"的策略,保证每个合数恰好被标记一次,从而实现O(n)的时间复杂度。
A
正确
B
错误
答案与解析
正确答案:错
这道题暂未补解析。
25
判断题
适中
任何递归程序都可以改写为等价的非递归程序,但改写后的非递归程序一定需要显式地使用栈来模拟递归调用过程。
A
正确
B
错误
答案与解析
正确答案:错
分析递归程序转化为非递归程序时控制流的管理方式;考察是否必须引入显式栈结构来保存调用上下文;考虑原递归调用的深度和分支结构对状态存储的需求;对比隐式调用栈与显式数据结构在状态保存上的等价性;探讨是否存在不依赖栈结构的转化方法,如通过循环变量重构或尾调用优化实现状态迭代。
26
简答题
适中
有限不循环小数
时间限制:1.0 s
内存限制:512.0 MB
题目描述
若1/a可化为一个有限的,不循环的小数,则称a为终止数。
请你求出在L到R中终止数的数量。
输入格式
输入一行,包含两个整数L,R。
输出格式
输出一行,包含一个整数,表示L到R中终止数的数量。
输入样例
2 11
输出样例
5
样例解释
在[2,11]终止数有2、4、5、8、10。
数据范围
保证1≤L≤R≤106。
答案与解析
参考答案
# L,R输入 l, r = map(int, input().split()) # 最终的答案,初始化为0 ans = 0 for i in range(l, r + 1): t = i # 不断除以2 while t > 0 and t % 2 == 0: t //= 2 # 不断除以5 while t > 0 and t % 5 == 0: t //= 5 # 如果不含其他因子,则这个数能够表示为不循环的小数 if t == 1: ans += 1 print(ans)
27
简答题
适中
找数
时间限制:1.0 s
内存限制:512.0 MB
题目描述
给定一个包含n个互不相同的正整数的数组A与一个包含m个互不相同的正整数的数组B,请你帮忙计算有多少数在数组A与 数组B中均出现。
输入格式
第一行包含两个整数n,m。
第二行包含n个正整数a1,a2,...,an表示数组A。
第二行包含m个正整数b1,b2,...,bn表示数组B。
输出格式
输出一个整数,表示在数组A与 数组B中均出现的数的个数。
输入样例
3 5 4 2 3 3 1 5 4 6
输出样例
2
样例解释
样例 1 中,4、3在数组 与 中均出现。
数据范围
对于40%的数据,保证1≤n,m≤1000。
对于100%的数据,保证1≤n,m≤105,1≤ai,bi≤109。
答案与解析
参考答案
# 接收a,b数组的大小以及数组内容 n, m = map(int, input().split()) a = list(map(int, input().split())) b = list(map(int, input().split())) a.sort() ans = 0 # 遍历b中的每一个数 for x in b: l, r = 0, n - 1 # 二分查找a中是否包含x while l < r: mid = (l + r) // 2 # 如果a[mid]<x,则x一定在mid+1之后 if a[mid] < x: l = mid + 1 else: r = mid if a[l] == x: ans += 1 print(ans)