GESP-Python五级 题库
题关于Python 实现的单链表、双链表和循环链表,下列说法正确的是()。
双向循环链表中要在结点p 之前插入新结点s(均非空),以下操作正确的是()。
下面函数删除单向链表中val == x 的节点,并且使用哑结点统一对头结点和中间节点的删除操作。横线处应填()。
对如下代码实现的欧几里得算法(辗转相除法),调用gcd(48 , 18) 得到的调用序列为()。
def gcd(a, b): if b == 0: return a else: return gcd(b, a % b)
下面代码实现了欧拉(线性)筛,横线处应填写()。
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
埃氏筛中将内层循环从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
下面程序的运行结果为()。
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)
在升序数组中查找第一个大于等于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)}")关于递归函数调用,下列说法错误的是()。
给定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()
下面代码用分治求“最大连续子段和”,其时间复杂度为()。
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组: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)有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)下面代码实现两个整数除法,其中被除数为一个“大整数”,用字符串表示,除数是一个小整数,用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()
下面关于排序算法的描述中,不正确的是( )。
有一个存储了 n 个整数的线性表,分别用 Python 列表(数组)和自定义单链表两种方式实现。在已知元素下标(或结点对象引用)的前提下,Python 列表的随机访问操作时间复杂度为O(1);而在 Python 实现的单链表中,已知某结点对象的引用时,在该结点之后插入一个新结点的操作时间复杂度也为O(1)。
若数组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 [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}")