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)有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()
下面关于排序算法的描述中,不正确的是( )。
假设函数 gcd() 函数能正确求两个正整数的最大公约数,则下面的 lcm(a ,b) 函数能正确找到两个正整数 a 和 b 的最小公倍数。()
在 Python 实现的单链表中,已知引用 p 指向要删除的节点(该节点不是尾节点),若想在 O(1) 时间复杂度内删除这个节点,可行的做法是:用 p 的后继节点 p.next 的值覆盖 p 自身的值,再用 p 的后继节点的 next 引用覆盖 p 的 next 引用,最后断开 p 的后继节点的引用以辅助垃圾回收。()
4. 在求解所有不大于 n 的素数时,线性筛法(欧拉筛)都应当优先于埃氏筛法使用,因为线性筛法的时间复杂度为 O(n),低于埃氏筛法的O(n loglogn)。()
二分查找仅适用于有序数据。若输入数据无序,当仅进行一次查找时,为了使用二分而排序通常不划算。()
通过在数组的第一个、最中间和最后一个这3个数据中选择中间值作为枢轴(比较基准),快速排序算法可降低落入最坏情况的概率。()
贪心算法在每一步都做出当前看来最优的局部选择,并且一旦做出选择就不再回溯;而分治算法将问题分解为若干子问题分别求解,再将子问题的解合并得到原问题的解。()
以下 fib 函数计算第 n 项斐波那契数( fib(0)=0 , fib(1)=1 ),其时间复杂度为 O(n)。()
使用贪心算法解决问题时,通过对每一步求局部最优解,最终一定能找到全局最优解。()
基于下面定义的函数,通过判断isDivisibleBy9(n) == isDigitSumDivisibleBy9(n) 代码可验算如果一个数能被9整除,则它的各位数字之和能被9整除。

假设函数 gcd() 函数能正确求两个正整数的最大公约数,则下面的findMusicalPattern(4,6) 函数返回2。

。
。