GESP-Python五级 题库

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

题关于Python 实现的单链表、双链表和循环链表,下列说法正确的是()。

A
在Python 实现的单链表中,若已知任意结点对象的引用,则可以在O(1)时间内删除该结点。
B
Python 实现的循环链表中一定不存在值为None 的引用属性。
C
在Python 实现的循环双链表中,尾结点对象的next 属性值一定为None。
D
在Python 实现的带头结点的循环单链表中,判定链表是否为空只需判断头结点对象的next 属性是否引用头结点自身(即head.next is head)。
答案与解析
正确答案:D
这道题暂未补解析。
题目详情
2 单选题 适中 GESP编程能力等级认证 ·GESP-Python五级 · 未分类

双向循环链表中要在结点p 之前插入新结点s(均非空),以下操作正确的是()。

A
s.next=pp .prev=sq.next=ss .prev=q
B
s .prev=ps.next=p.next p.next.prev=sp.next=s
C
s.next=ps .prev=p .prev p.prev.next=sp .prev=s
D
s.next=ps .prev=nullptrp .prev=s
答案与解析
正确答案:C
这道题暂未补解析。
题目详情
3 单选题 适中 GESP编程能力等级认证 ·GESP-Python五级 · 未分类

下面函数删除单向链表中val == x 的节点,并且使用哑结点统一对头结点和中间节点的删除操作。横线处应填()。

A
cur = cur.next
B
cur.next = cur.next.next
C
cur.next = None
D
cur.next = nullptr
答案与解析
正确答案:B
使用哑结点后,当前指针cur从dummy开始,遍历链表。当cur.next存在时,判断其值是否等于x。若相等,则通过修改cur.next指向其下下个节点跳过目标节点,此时不应移动cur,因为下一个节点可能仍需删除。若不相等,则将cur向前移动一个节点。循环继续直到遍历结束。返回dummy.next作为新头节点。填空处位于删除操作后的分支,需决定删除后cur的移动行为。
题目详情
4 单选题 适中 GESP编程能力等级认证 ·GESP-Python五级 · 未分类

对如下代码实现的欧几里得算法(辗转相除法),调用gcd(48 , 18) 得到的调用序列为()。

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)


A
gcd(48 ,18) -> gcd(18 ,12) -> gcd(12 ,6) -> gcd(6 ,0)
B
gcd(48 ,18) -> gcd(30 ,18) -> gcd(12 ,18)
C
gcd(48 ,18) -> gcd(18 ,30) -> gcd(30 ,6)
D
gcd(48 ,18) -> gcd(12 ,18) -> gcd(6 ,12)
答案与解析
正确答案:A
函数gcd接收两个参数a和b,当b不为0时,递归调用gcd(b, a % b);每次递归将原b作为新的a,原a对b取模的结果作为新的b。初始调用为gcd(48, 18),进入递归过程:首先计算48 % 18得12,生成下一层调用gcd(18, 12);接着计算18 % 12得6,生成gcd(12, 6);再计算12 % 6得0,生成gcd(6, 0);此时b为0,递归终止,返回当前a的值。整个调用链由连续取模操作驱动,每一步的第二个参数均为前一步的模运算结果,直到模为0停止。
题目详情
5 单选题 适中 GESP编程能力等级认证 ·GESP-Python五级 · 未分类

下面代码实现了欧拉(线性)筛,横线处应填写()。

def euler_sieve_for(n):
    if n < 2:
        return []
    is_composite = [False] * (n + 1)
    primes = []

    for i in range(2, n + 1):
        if not is_composite[i]:
            primes.append(i)

        for j in range(len(primes)):  # 填空处
            p = primes[j]
            if i * p > n:
                break
            is_composite[i * p] = True
            if i % p == 0:
                break
    return primes


A
for j in range(len(primes+1)):
B
for j in range(len(primes)+1):
C
for j in range(len(primes)):
D
for j in range(len(primes)-1):
答案与解析
正确答案:C
函数目标是生成不超过n的质数列表。使用欧拉筛时,每个合数仅被其最小质因子筛去。外层循环遍历2到n的整数i,内层循环遍历已记录的质数列表primes中的元素p。当i能被p整除时,说明p是i的最小质因子,之后的合数将由更大的i处理,因此立即break。若i为质数,则加入primes。is_composite数组用于标记合数,避免重复筛选。内层循环需遍历当前全部已得质数,故循环范围应为primes的有效索引区间。j作为索引变量,应覆盖0到len(primes)-1的所有值,确保访问每个已知质数p = primes[j]。循环上限为len(primes),下限为0,步长为1,因此range参数应为len(primes)。
题目详情
6 单选题 适中 GESP编程能力等级认证 ·GESP-Python五级 · 未分类

埃氏筛中将内层循环从j = i*i 开始而不是j = 2*i 的主要原因是()。

def eratosthenes_sieve_for(n):
    if n < 2:
        return []
    is_composite = [False] * (n + 1)
    primes = []

    for i in range(2, n + 1):
        if is_composite[i]:
            continue
        primes.append(i)

        # 用for循环模拟C++的 j = i*i; j <=n; j +=i
        for j in range(i * i, n + 1, i):
            is_composite[j] = True

    return primes


A
因为2*i 一定不是合数
B
i*i 一定是质数
C
小于i*i 的i 的倍数已被更小质因子筛过
D
这样可以把时间复杂度降为O(n)
答案与解析
正确答案:C
埃氏筛法标记合数时,对于当前质数i,其倍数中需被筛去的合数从i*i开始。因小于i*i的i的倍数可表示为k*i(k < i),其中k必有小于i的质因子,这些倍数已在处理更小质数时被标记。内层循环跳过2*i、3*i等直至i*i,是因它们已被先前步骤覆盖。时间复杂度仍为O(n log log n),未降至O(n)。i*i不一定是质数,且2*i在i>1时为合数。
题目详情
7 单选题 适中 GESP编程能力等级认证 ·GESP-Python五级 · 未分类

下面程序的运行结果为()。

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.sort()

    l = 0
    r = a[-1] - a[0]

    while l < r:
        mid = (l + r + 1) // 2
        if check(n, a, 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
2
B
3
C
4
D
5
答案与解析
正确答案:B
函数 check 接收四个参数:n 表示数组长度,a 为升序排列的数值数组,k 为目标数量,dist 为最小距离。遍历数组 a,统计满足相邻元素差值不小于 dist 的元素个数 cnt,返回 cnt 是否大于等于 k。函数 solve 对数组 a 排序后,使用二分查找确定最大化的最小距离。左边界 l 初始化为 0,右边界 r 初始化为数组最大值与最小值之差。在二分过程中,计算中点 mid,通过 check 函数判断是否存在至少 k 个元素,其相邻元素间距离不小于 mid。若满足条件,则尝试增大距离;否则减小距离。循环持续至区间收敛。
题目详情
8 单选题 适中 GESP编程能力等级认证 ·GESP-Python五级 · 未分类

在升序数组中查找第一个大于等于x 的位置,下面循环中横线应填()。

def lowerBound(a, x):
    l = 0
    r = len(a)
    while l < r:
        mid = l + (r - l) // 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)}")


A
r = mid
B
r = mid - 1
C
l = mid
D
l = mid + 1
答案与解析
正确答案:A
使用二分查找在升序数组中定位第一个大于等于x的位置。初始化左指针l为0,右指针r为数组长度。循环条件为l < r,取中点mid = (l + r) // 2。若a[mid] >= x,则mid可能是解,将r更新为mid以保留该位置;否则a[mid] < x,说明mid及左侧均不可能满足条件,将l更新为mid + 1以排除该区域。循环结束时l即为首个满足条件的位置。填空处位于a[mid] >= x分支内,需维护右边界向左收缩的逻辑。
题目详情
9 单选题 适中 GESP编程能力等级认证 ·GESP-Python五级 · 未分类

关于递归函数调用,下列说法错误的是()。

A
递归调用层次过深时,可能会耗尽栈空间导致栈溢出
B
尾递归函数可以通过编译器优化来避免栈溢出
C
所有递归函数都可以通过循环结构来改写,从而避免栈溢出
D
栈溢出发生时,程序会抛出异常并可以继续执行后续代码
答案与解析
正确答案:D
递归函数调用时,每次调用都会在调用栈中创建新的栈帧,保存局部变量和返回地址。调用层次过深会导致栈空间耗尽,引发栈溢出。尾递归在特定条件下可被编译器优化为迭代形式,复用栈帧,避免栈空间持续增长。理论上,所有递归逻辑均可转换为循环结构,通过显式维护状态数据实现等价功能。栈溢出属于运行时严重错误,触发后程序控制流中断,无法保证后续代码的正常执行路径。
题目详情
10 单选题 适中 GESP编程能力等级认证 ·GESP-Python五级 · 未分类

给定n 根木头,第i 根长度为a [i]。要切成不少于m 段等长木段,求最大可能长度,则横线上应填写()。

def check(a, m, x):
    cnt = 0
    for length in a:
        if x == 0:
            return True
        cnt += length
        if cnt >= m:
            return True
    return cnt >= m

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    n = int(input[idx])
    idx += 1
    m = int(input[idx])
    idx += 1

    a = []
    mx = 0
    for _ in range(n):
        num = int(input[idx])
        idx += 1
        a.append(num)
        mx = max(mx, num)

    l = 1
    r = mx
    ans = 0

    while l <= r:
        mid = l + (r - l) // 2
        if check(a, m, mid):
            ans = mid
            _________________
        else:
            _________________

    print(ans)

if __name__ == "__main__":
    main()


A
l = mid + 1 和 r = mid - 1
B
r = mid - 1 和l = mid + 1
C
l = mid + 1 和 r = mid
D
l = mid - 1 和 r = mid + 1
答案与解析
正确答案:A
使用二分查找确定最大可能长度。左边界为1,右边界为最长木头的长度。每次取中点作为候选长度,通过check函数验证是否能切出至少m段。若可以,则尝试更大的长度,更新左边界;否则尝试更小的长度,更新右边界。循环直至区间收敛,得到最大可行解。
题目详情
11 单选题 适中 GESP编程能力等级认证 ·GESP-Python五级 · 未分类

下面代码用分治求“最大连续子段和”,其时间复杂度为()。

import sys
def solve(a , l , r):
    if l == r:
        return a [l]
    mid = l + (r - l) // 2
    left = solve(a , l , mid)
    right = solve(a , mid + 1 , r)
    sum_val = 0
    lmax = -sys .maxsize - 1
    for i in range(mid , l - 1 , -1):
        sum_val += a [i]
        lmax = max (lmax , sum_val)
    sum_val = 0
    rmax = -sys .maxsize - 1
    for i in range(mid + 1 , r + 1):
        sum_val += a [i]
        rmax = max (rmax , sum_val)
    return max(left , right , lmax + rmax)

if __name__ == "__main__":
    a1 = [-2 , 1 , -3 , 4 , -1 , 2 , 1 , -5 , 4]
    print(solve(a1 , 0 , len(a1)-1))
    a2 = [-5 , -3 , -1 , -4]
    print(solve(a2 , 0 , len(a2)-1))
    a3 = [10]
    print(solve(a3 , 0 , 0))
A
O(n2)
B
O(nlogn)
C
O(logn)
D
O(n)
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
12 单选题 适中 GESP编程能力等级认证 ·GESP-Python五级 · 未分类

游戏大赛决赛,两组选手分别按得分从小到大排好队,现在要把他们合并成一个有序排行榜。

A组:A = {12 , 35 , 67 , 89},B组:B = {20 , 45 , 55 , 78},下面是归并合并函数的核心循环,横线处应填入()。

A = [12, 35, 67, 89]
B = [20, 45, 55, 78]

i = 0
j = 0
result = []

while i < len(A) and j < len(B):
    if A[i] < B[j]:  # 填空处
        result.append(A[i])
        i += 1
    else:
        result.append(B[j])
        j += 1

while i < len(A):
    result.append(A[i])
    i += 1

while j < len(B):
    result.append(B[j])
    j += 1

print("合并后的有序排行榜: ", result)


A
if A [i+1] <= B [j]:
B
if A [i] <= B [j+1]:
C
if A [i] <= B [j]:
D
if i < j :
答案与解析
正确答案:C
初始化两个指针i和j分别指向数组A和B的首元素,创建空列表result存储合并结果。在while循环中,比较A[i]与B[j]的值,将较小的元素追加到result中,并将对应数组的指针后移一位。若某一数组遍历完毕,则将另一数组剩余元素依次追加至result。循环继续条件为i小于A的长度且j小于B的长度。当其中一个指针越界时,退出循环并处理剩余元素。
题目详情
13 单选题 适中 GESP编程能力等级认证 ·GESP-Python五级 · 未分类

有n位同学的成绩已经从小到大排好序,现在对它执行下面这段以第一个元素为pivot 的快速排序,请问此次排序的时间复杂度是()。

def quicksort(a , l , r):
    if l >= r:
        return
    pivot = a [l]
    i , j = l , r
    while i < j :
        while i < j and a [j] >= pivot :
            j -= 1
        while i < j and a [i] <= pivot :
            i += 1
        if i < j :
            a [i], a [j] = a [j], a [i]
    a [l], a [i] = a [i], a [l]
    quicksort(a , l , i - 1)
    quicksort(a , i + 1 , r)

if __name__ == "__main__":
    scores = [60 , 70 , 80 , 90 , 100]
    print("排序前:", scores)
    quicksort(scores , 0 , len(scores)-1)
    print("排序后:", scores) # 输出:[60 , 70 , 80 , 90 , 100]

def quicksort_with_log(a , l , r , depth=0):
    if l >= r:
        return
    print(f "递归深度{depth},处理区间[{l },{r }],数组:{a [l:r+1]}")
    pivot = a [l]
    i , j = l , r
    while i < j :
        while i < j and a [j] >= pivot : j -= 1
        while i < j and a [i] <= pivot : i += 1
        if i < j : a [i], a [j] = a [j], a [i]
    a [l], a [i] = a [i], a [l]
    quicksort_with_log(a , l , i-1 , depth+1)
    quicksort_with_log(a , i+1 , r , depth+1)

scores2 = [60 ,70 ,80 ,90 ,100]
print("\n递归过程:")
quicksort_with_log(scores2 , 0 , 4)


A
O(n)
B
O(nlogn)
C
O(n2)
D
O(logn)
答案与解析
正确答案:C
这道题暂未补解析。
题目详情
14 单选题 适中 GESP编程能力等级认证 ·GESP-Python五级 · 未分类

下面代码实现两个整数除法,其中被除数为一个“大整数”,用字符串表示,除数是一个小整数,用int 表示,则横线处应该填写()。

def big_integer_division():
    s, b = input().split()
    b = int(b)
    a = [int(c) for c in s]

    c = []
    rem = 0
    for i in range(len(a)):
        rem = rem * 10 + a[i]
        q = rem // b
        c.append(q)
        rem = rem % b  # 填空处

    pos = 0
    while pos < len(c) - 1 and c[pos] == 0:
        pos += 1

    for i in range(pos, len(c)):
        print(c[i], end='')
    print()

    print(rem)

if __name__ == "__main__":
    big_integer_division()


A
rem =rem / b
B
rem = rem % b
C
rem = b
D
rem = q
答案与解析
正确答案:B
遍历被除数的每一位,将当前余数乘以10并加上该位得到新的被除数部分;计算该部分与除数的商并记录;更新余数为该部分对除数取模的结果。循环结束后,可能存在前导零的商需要处理。通过指针定位第一个非零商位,若所有位均为零则保留一位。此步骤确保结果正确表示商的数值形式。
题目详情
15 单选题 适中 GESP编程能力等级认证 ·GESP-Python五级 · 未分类

下面关于排序算法的描述中,不正确的是( )。

A
冒泡排序和插入排序都是稳定的排序算法
B
快速排序和归并排序都是不稳定的排序算法
C
冒泡排序和插入排序最好时间复杂度均为O(n)
D
归并排序在最好、最坏和平均三种情况的时间复杂度均为O(nlogn)
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
16 判断题 适中 GESP编程能力等级认证 ·GESP-Python五级 · 未分类

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

A
正确
B
错误
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
17 判断题 适中 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的元素位置。边界情况由指针自然收敛处理,无需额外判断。
题目详情
18 判断题 适中 GESP编程能力等级认证 ·GESP-Python五级 · 未分类

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

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

若某算法满足递推式:

T (n) = 2T(n/2) + O (n)
A
正确
B
错误
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
20 判断题 适中 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]内的总逆序对数。算法正确性依赖于归并过程中跨区间逆序对的精确捕获与子区间内部逆序对的递归处理。
题目详情