首页 › 题库 › GESP编程能力等级认证 › GESP-Python五级

GESP-Python五级 题库

共 296 道题 ,第 14 / 15 页 · 按题型筛选,点「查看答案」核对解析
261 判断题 偏易 GESP编程能力等级认证 ·GESP-Python五级 · 7.1 归并排序

一般说来,冒泡排序算法优于归并排序。

A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情
262 判断题 偏易 GESP编程能力等级认证 ·GESP-Python五级 · 综合练习

Python的内置函数 sorted() 可以对支持 for-in 循环的 str 、 list 、 tuple 、 dict 、 set 排序,且是稳定排序。

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
263 判断题 偏易 GESP编程能力等级认证 ·GESP-Python五级 · 综合练习

下面的Python代码将输出0-99(包含0和99)之间的整数,顺序随机。

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
264 判断题 偏易 GESP编程能力等级认证 ·GESP-Python五级 · 综合练习

下面的Python代码执行后将输出 [0, 5, 1, 6, 2, 3, 4] 。

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

有一个存储了 n 个整数的线性表,分别用 Python 列表(数组)和自定义单链表两种方式实现。在已知元素下标(或结点对象引用)的前提下,Python 列表的随机访问操作时间复杂度为O(1);而在 Python 实现的单链表中,已知某结点对象的引用时,在该结点之后插入一个新结点的操作时间复杂度也为O(1)。

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

若数组a 已按升序排列,则下面代码可以正确实现“在a 中查找第一个大于等于x 的元素的位置”。

def lowerBound(a, x):
    l = 0
    r = len(a)
    while l < r:
        mid = (l + r) // 2
        if a[mid] >= x:
            r = mid
        else:
            l = mid + 1
    return l

if __name__ == "__main__":
    a1 = [1, 3, 5, 7, 9]
    x1 = 5
    print(f"数组{a1}中第一个≥{x1}的位置: {lowerBound(a1, x1)}")

    x2 = 6
    print(f"数组{a1}中第一个≥{x2}的位置: {lowerBound(a1, x2)}")

    x3 = 10
    print(f"数组{a1}中第一个≥{x3}的位置: {lowerBound(a1, x3)}")

    x4 = 0
    print(f"数组{a1}中第一个≥{x4}的位置: {lowerBound(a1, x4)}")


A
正确
B
错误
答案与解析
正确答案:对
使用二分查找策略,初始化左指针l为0,右指针r为数组长度。循环条件为l小于r,取中点mid。若a[mid]大于等于x,则第一个满足条件的位置在mid或其左侧,更新r为mid;否则位置在mid右侧,更新l为mid加1。循环结束后l即为首个大于等于x的元素位置。边界情况由指针自然收敛处理,无需额外判断。
题目详情
267 判断题 适中 GESP编程能力等级认证 ·GESP-Python五级 · 未分类

快速排序只要每次都选取中间元素作为枢轴,就一定是稳定排序。

A
正确
B
错误
答案与解析
正确答案:错
快速排序的稳定性取决于相等元素的相对位置是否在划分过程中保持不变。选取中间元素作为枢轴仅影响划分策略,不改变快速排序在交换元素时可能打乱相等元素顺序的机制。无论枢轴如何选择,只要存在跨越相等元素的交换操作,就可能发生顺序颠倒。稳定性与枢轴选取位置无直接关联,而由具体实现中的元素交换方式决定。划分过程将数组分为小于和大于枢轴的两部分,相等元素若分布在枢轴两侧,可能因交换而改变原有次序。因此,选取中间元素作为枢轴不能保证相等元素的相对位置不变。
题目详情
268 判断题 适中 GESP编程能力等级认证 ·GESP-Python五级 · 未分类

若某算法满足递推式:

T (n) = 2T(n/2) + O (n)
A
正确
B
错误
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
269 判断题 适中 GESP编程能力等级认证 ·GESP-Python五级 · 未分类

在一个数组中,如果两个元素a [i] 和a [j]满足i < j 且a [i] > a [j],则a [i] 和a [j]是一个逆序对。

下面代码可以正确统计数组a 区间[l ,r] 内的逆序对总数。

cnt = 0
def merge_count(a , l , m , r):
    global cnt
    i = l
    j = m + 1
    while i <= m and j <= r:
        if a [i] <= a [j]: 
            i += 1
        else:
            cnt += (m - i + 1)
            j += 1
if __name__  == "__main__":
    a = [2 , 4 , 1 , 3]
    merge_count(a , 0 , 1 , 3)
    print(f "跨区间逆序对数量:{cnt}")


A
正确
B
错误
答案与解析
正确答案:错
使用分治法将数组递归分割为子区间,通过归并排序过程中的合并阶段统计逆序对。在合并两个有序子区间时,设置双指针分别指向左右区间的起始位置,当右区间元素小于左区间当前元素时,说明左区间剩余元素均与右区间当前元素构成逆序对,累计左区间剩余元素个数至计数器。每次合并操作完成后,确保该区间内元素有序,不影响上层逆序对的正确统计。全局计数器在每次满足逆序条件时更新,最终返回区间[l, r]内的总逆序对数。算法正确性依赖于归并过程中跨区间逆序对的精确捕获与子区间内部逆序对的递归处理。
题目详情
270 判断题 适中 GESP编程能力等级认证 ·GESP-Python五级 · 未分类

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

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

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

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

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

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

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

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

数字移动
时间限制:3.0 s
内存限制:512.0 MB
题目描述
小 A 有一个包含 N 个正整数的序列 A = A₁ , A₂, … …A_N,序列 A 恰好包含成对不同的正整数。形式化地,对于任意 1 ≤ i ≤ N ,存在唯一一个 j 满足 1 ≤j≤ N, i≠ j, A_i = A_j。
小 A 希望每对相同的数字在序列中相邻,为了实现这一目的,小 A 每次操作会选择任意 i (1 ≤ i ≤ N),将当前序列的第 i 个数字移动到任意位置,并花费对应数字的体力。

例如,假设序列 A = {1 , 2, 1 , 3, 2, 3},小 A 可以选择 i = 2,将 A₂ = 2 移动到 A₃=1 的后面,此时序列变为{1 , 1 , 2, 3, 2, 3},耗费 2 点体力。小 A 也可以选择 i = 3,将 A₃=1 移动到A₂ = 2 的前面,此时序列变为{1 , 1 , 2, 3, 2, 3},花费 1 点体力

小 A 可以执行任意次操作,但他希望自己每次花费的体力尽可能小。小 A 希望你能帮他计算出一个最小的 X,使得他能够在每次花费的体力均不超过 X 的情况下令每对相同的数字在序列中相邻。
输入格式
第一行一个正整数 N,代表序列长度,保证 N 为偶数。
第二行包含 N 个正整数 A₁ , A₂ , · · . , A_N,代表序列 A。且对于任意 1 ≤ i ≤ N,存在唯一一个j 满足1 ≤ j ≤ N, i≠ j, A_i= A_j。
数据保证小 A 至少需要执行一次操作。
输出格式
输出一行,代表满足要求的 X 的最小值。
样例
输入样例

6
1  2  1  3  2  3

输出样例

1

仅移动数值1即可完成全部配对,所有操作体力≤1,最小X=1。 数据范围 对于40%的测试点,保证 1 ≤ N, A_i ≤ 100。 对于所有测试点,保证 1 ≤ N, A_i ≤ 10⁵。

答案与解析
参考答案
# 输入n和a数组
n = int(input())
a = []
while len(a) < n:
    a.extend(map(int, input().split()))

# 答案的上下界
left, right = 0, 1000000
ans = 1000000

# 二分搜索
while left <= right:
    # 考虑mid的力气能否完成任务
    mid = (left + right) // 2
    # 筛选出所有大于mid的数字
    b = [x for x in a if x > mid]
    # 先假设能够完成任务
    possible = True
    for i in range(0, len(b), 2):
        # 如果两个相同且大于mid的数字 ,中间还有其它的大于mid的数字 ,则本任务无法完成
        # 以 (1  2  1  3)为例 ,两个1之间存在2。假设最大只能挪动1 ,则不论如何两个1之间的2不会被挪动,最终无法完成配对
        if b[i] != b[i+1]:
            possible = False
            break
    # 如果能够成功 ,则尝试更小的mid
    if possible:
        ans = mid
        right = mid - 1
    else:
        left = mid + 1
print(ans)
题目详情
276 简答题 偏难 GESP编程能力等级认证 ·GESP-Python五级 · 1.1 素数与合数

相等序列
时间限制:3.0 s
内存限制:512.0 MB
题目描述

小 A 有一个包含 N 个正整数的序列A = {A₁ , A₂ , · · ,A_N}。小 A 每次可以花费 1 个金币执行以下任意一种操作:

1. 选择序列中一个正整数 A_i( 1 ≤ i ≤ N),将 A_i 变为 A_i × P,P 为任意质数;
2. 选择序列中一个正整数 A_i( 1 ≤ i ≤ N),将 A_i 变为 A_i ÷ P,P 为任意质数,要求 A_i 能整除 P。
小 A 想请你帮他计算出令序列中所有整数都相同,最少需要花费多少金币。
输入格式
第一行一个正整数 N,含义如题面所示。
第二行包含 N 个正整数 A₁ , A₂ , · · ,A_N,代表序列 A。
输出格式
输出一行,代表最少需要花费的金币数量。
样例
输入样例

5
10  6  35  105  42

输出样例

8

数据范围
对于60%的测试点,保证 1 ≤ N, A_i ≤ 100。
对于所有测试点,保证 1 ≤ N, A_i ≤ 10⁵。

答案与解析
参考答案
tokens = []
def get_val() :
    while not tokens:
        tokens.extend(input().split())
    return int(tokens.pop(0))

# 一共有多少数
n = get_val()
# key:质数
# value:一个列表 ,num[p][exp]表示有多少数质因数分解后可以包含p^exp
# 因为一个数最大就到10^5 ,相当于是10w ,所以列表最多包含20个数肯定够用 ,即2^20
num = {}

for _ in range(n) :
    # 统计一下各个输入数字有多少质因数
    x = get_val()
    d = 2
    # 质因数必定小于根号x
    tmp = x
    while d * d <= tmp:
        # 如果找到了一个数是x的因数
        if tmp % d == 0 :
            cnt = 0
            # 那就一直除以这个数 ,并且更新x的质因数数目
            # 这样一来剩下能够整除x的必定是质数
            while tmp % d == 0 :
                tmp //= d
                cnt += 1
            if d not in num:
                num[d] = [0] * 20
            # 数字x包含d^cnt ,更新状态
            num[d][cnt] += 1
        d += 1
    # 如果x是质数
    if tmp > 1 :
        if tmp not in num:
            num[tmp] = [0] * 20
        num[tmp][1] += 1

ans = 0
for p in num:
    counts = num[p]
    # 计算有多少数字不包含这个质因数
    counts[0] = n - sum(counts)
    # 寻找中位数指数
    # 也就是寻找一个指数e,使得一半的数字包含超过e次方的p,另一半不包含
    pos = 0
    median_exponent = 0
    for j in range(20) :
        pos += counts[j]
        if pos * 2 >= n:
            median_exponent = j
            break
    # 计算代价
    for j in range(20) :
        if counts[j] :
            ans += counts[j] * abs(j - median_exponent)
print(ans)
题目详情
277 简答题 偏难 GESP编程能力等级认证 ·GESP-Python五级 · 综合练习

试题名称:数字选取

时间限制:1.0 s

内存限制:512.0 MB

答案与解析
参考答案
n = int(input())
# p[0]、p[1]占位/置0,2~n初始标记为1(是质数)
p = [1] * (n + 1)
p[0] = p[1] = 0

# 只筛到根号n
for i in range(2, int(n ** 0.5) + 1):
    if p[i] == 1:  # i是质数,筛掉它所有倍数
        # 从i*i开始,步长i
        for j in range(i * i, n + 1, i):
            p[j] = 0

# sum(p) 等于1~n内质数总个数
print(sum(p))
题目详情
278 简答题 偏难 GESP编程能力等级认证 ·GESP-Python五级 · 综合练习

试题名称:有趣的数字和

时间限制:1.0 s

内存限制:512.0 MB

答案与解析
参考答案
def cal2(n, p):
    """
    计算奇偶性为p的 0~n 的有趣的数之和,要求n为2^k - 1的形式
    :return: 有趣的数量, 有趣的数之和
    """
    if n == 0:
        return 1 - p, 0
    if n == 1:
        return 1, p
    return (n + 1) // 2, n * (n + 1) // 4


def cal(n, p):
    """
    计算奇偶性为p的 0~n 的有趣的数之和
    :return: 有趣的数量, 有趣的数之和
    """
    if n <= 1:
        return cal2(n, p)
    x = 1
    while x * 2 <= n:
        x *= 2
    # 找出最大x=2^k,x-1=2^k-1 <= n
    cntl, sl = cal2(x - 1, p)
    # 剩下部分:最高位1去掉,剩余数位奇偶性相反 1-p
    cntr, sr = cal(n - x, 1 - p)
    # 总数 = 左半部分 + 右半部分
    total_cnt = cntl + cntr
    # 总和 = 左半和 + 右半和 + 高位x 乘右边数字个数
    total_sum = sl + sr + x * cntr
    return total_cnt, total_sum


# 主程序
l, r = map(int, input().split())
# 0 ~ l-1 的符合条件数字总和
_, ansl = cal(l - 1, 1)
# 0 ~ r 的符合条件数字总和
_, ansr = cal(r, 1)
# [l, r] 区间和 = 0~r总和 - 0~l-1总和
print(ansr - ansl)
题目详情
279 简答题 偏难 GESP编程能力等级认证 ·GESP-Python五级 · 综合练习

奖品兑换

答案与解析
参考答案
# 接受小A持有的两种券的数量
n, m = map(int, input().split())
# 兑换1份奖品分别所需两种券的数量
a, b = map(int, input().split())

# 统一处理:把持有券、所需券都调整为 (少, 多) 的顺序,简化后续计算
n, m = min(n, m), max(n, m)
a, b = min(a, b), max(a, b)


def check(v):
    """
    检测手头的券能否兑换 v 份礼品
    :param v: 目标礼品数目
    :return: 能兑换返回True,不能返回False
    """
    # 兑换v份礼品原始需求:x=少券总需求,y=多券总需求
    x, y = a * v, b * v

    # 如果多券需求超过持有上限,调整兑换组合
    if y >= m and b > a:
        t = (y - m + (b - a) - 1) // (b - a)
        y -= t * (b - a)
        x += t * (b - a)

    # 调整后两种券需求都不超过持有量则可行
    return x <= n and y <= m


# 二分查找最大可兑换份数
l, r = 0, int(1e9)
while l < r:
    mid = (l + r + 1) // 2
    if check(mid):
        l = mid
    else:
        r = mid - 1

print(r)
题目详情
280 简答题 偏难 GESP编程能力等级认证 ·GESP-Python五级 · 综合练习

最大公因数

答案与解析
参考答案
# 读取数字个数n、查询次数q
n, q = map(int, input().split())
# 读取数组并升序排序
a = sorted(list(map(int, input().split())))

# 欧几里得算法求最大公约数
def gcd(a, b):
    if a == 0 or b == 0:
        return a + b
    return gcd(b, a % b)

# 计算相邻元素差值的整体最大公约数
g = 0
for i in range(1, n):
    diff = a[i] - a[i - 1]
    g = gcd(g, diff)

# 处理每组查询
for i in range(q):
    val = a[0] + i + 1
    print(gcd(g, val))
题目详情