GESP-Python五级 题库

共 27 道题 ,第 2 / 2 页 · 按题型筛选,点「查看答案」核对解析
21 判断题 适中 GESP编程能力等级认证 ·GESP-Python五级 · 未分类

唯一分解定理保证:若一个数未被任何不超过其平方根的质数筛去,则它一定是质数。

A
正确
B
错误
答案与解析
正确答案:对
唯一分解定理表明每个大于1的整数均可唯一表示为质因数的乘积。若一个数不能被任何不超过其平方根的质数整除,则不存在小于等于该数平方根的质因数,进而无法被分解为更小质数的乘积。此时该数不能写成两个大于1的整数之积,因此只能是质数。判断依据在于:所有合数必有质因数不超过其平方根,反之未被筛去则说明无此类质因数。
题目详情
22 判断题 适中 GESP编程能力等级认证 ·GESP-Python五级 · 未分类

假设数组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 判断题 适中 GESP编程能力等级认证 ·GESP-Python五级 · 未分类

若一个问题满足最优子结构性质,则一定可以用贪心算法得到最优解。()

A
正确
B
错误
答案与解析
正确答案:错
分析问题是否具备最优子结构性质,即原问题的最优解是否包含其子问题的最优解。考察贪心算法适用条件,需验证该问题是否同时满足贪心选择性质和最优子结构。贪心选择性质要求局部最优选择能导向全局最优解,可通过构造法或交换论证判断每次贪心决策能否保持最优性。若仅满足最优子结构而不满足贪心选择性质,则无法保证贪心算法得到最优解。动态规划适用于具有最优子结构的问题,而贪心算法是更特殊的情形,需额外满足贪心选择性质。
题目详情
24 判断题 适中 GESP编程能力等级认证 ·GESP-Python五级 · 未分类

线性筛相比埃氏筛的核心改进在于:埃氏筛中一个合数可能被多个质数重复标记,线性筛通过"每个合数只被其最大质因子筛去"的策略,保证每个合数恰好被标记一次,从而实现O(n)的时间复杂度。

A
正确
B
错误
答案与解析
正确答案:错
这道题暂未补解析。
题目详情
25 判断题 适中 GESP编程能力等级认证 ·GESP-Python五级 · 未分类

任何递归程序都可以改写为等价的非递归程序,但改写后的非递归程序一定需要显式地使用栈来模拟递归调用过程。

A
正确
B
错误
答案与解析
正确答案:错
分析递归程序转化为非递归程序时控制流的管理方式;考察是否必须引入显式栈结构来保存调用上下文;考虑原递归调用的深度和分支结构对状态存储的需求;对比隐式调用栈与显式数据结构在状态保存上的等价性;探讨是否存在不依赖栈结构的转化方法,如通过循环变量重构或尾调用优化实现状态迭代。
题目详情
26 简答题 适中 GESP编程能力等级认证 ·GESP-Python五级 · 未分类

有限不循环小数

时间限制: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 简答题 适中 GESP编程能力等级认证 ·GESP-Python五级 · 未分类

找数

时间限制: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)
题目详情