GESP-Python五级 题库
下面的代码实现线性筛法(欧拉筛),横线处应填入( )。

i % p == 0
p % i == 0
i == p
i * p == n
线性筛算法中有语句 if p * i > n break; ,其目的是( )。

降低常数但复杂度仍是
保证每个合数只被其最小质因子筛到一次,从而
提高缓存命中率,复杂度仍
不重要,是否 break 都一样
唯一分解定理描述的是()。
每个整数都能表示为任意素数的乘积
每个大于 1 的整数能唯一分解为素数幂乘积(忽略顺序)
合数不能分解为素数乘积
素数只有两个因子:1 和自身
给定一个 n x n 的矩阵 matrix ,矩阵的每一行和每一列都按升序排列。下面代码返回矩阵中第 k 小的元素,则两处横线上应分别填写( )。





下述python代码实现了快速排序算法,下面说法错误的是( )。

快速排序平均情况下比归并排序的比较、赋值、交换等操作的总数量少,所以命名为“快速”。
在平均情况下,划分的递归层数为
,每层中的总循环数为n,总时间为
。
在最差情况下,每轮划分操作都将长度为 的数组划分为长度为 0 和n-1的两个子数组,此时递归层数达到
,每层中的循环数为 ,总时间为
。
划分函数中“从右往左查找”与“从左往右查找”的顺序可以互换。
下述python代码实现了归并排序算法,则横线上应填写( )。


i < mid
j < right
i <= mid
j <= right
假设你是一家电影院的排片经理,只有一个放映厅。你有一个电影列表 movies ,其中 movies[i] =[start_i, end_i] 表示第 i 部电影的开始和结束时间。请你找出最多能安排多少部不重叠的电影,则横线上应分别填写的代码为( )。

movies
lastEnd
movies[i][0]
movies[i][1]
给定一个整数数组 nums ,下面代码找到一个具有最大和的连续子数组,并返回其最大和。则下面说法错误的是( )。


上述代码采用分治算法实现
本题算法采用贪心算法
时间复杂度:
由于采用递归方式实现,空间复杂度:
给定一个由非负整数组成的数组 digits ,表示一个非负整数的各位数字(最高位在数组首位)。下面代码对该整数执行 +1 操作,并返回结果数组,则横线上应填写( )。





以下哪种情况使用链表比数组更合适?
数据量固定且读多写少
需要频繁在中间或开头插入、删除元素
需要高效随机访问元素
存储空间必须连续
有关下列Python代码的说法,错误的是( )

执行 SORTED({1:1,2:4,3:9}) 不会报错
执行 SORTED(range(10)) 不会报错
执行 SORTED([1,20,3], Reverse = True)[::-1] 不会报错
执行 SORTED([1,None,'123']) 不会报错
下列Python代码用于判断一个正整数是否是质数(素数),相关说法中正确的是( )。

代码存在错误,比如5是质数,但因为 5 % 5 余数是0返回了False
finish_number 的值应该是 N // 2 ,当前写法将导致错误
当前while循环正确的前提是:所有大于3的质数都符合 6k±1 形式
while循环修改如下,其执行效果与执行时间相同

下列Python代码用于求解两个正整数的最大公约数,相关说法中错误的是( )

gcd0()函数的时间复杂度为 O(logN)
gcd1()函数的时间复杂度为 O(N)
一般说来, gcd0() 的效率高于 gcd1()
gcd1() 中的代码 range(small, 0, -1) 应该修改为range(small, 1, -1)
在Python中,可以用字典模拟单向或双向链表的实现。下面的代码模拟单向链表,和链表对象相比,有关其 缺点的说法,错误的是( )。

类型安全差,易出错。比如: node1["NEXT"] = node2 不会报错,导致逻辑错误
内存开销大。字典需要保存键名称以及哈希表
无法封装方法,如 insert() 插入函数较为常用,但其代码需要分散在外部
重复存储,难以保证一致性。如在 node1['next'] = node2 代码中, node1['next'] 的值为 node2 ,而 node2 自身也将保存一份
基于上题代码,模拟单向链表实现插入新节点函数insertNode()的代码如下,横线处应填入的代码是( )。





下面的Python代码用于实现双向链表。is_empty()函数用于判断链表是否为空,如为空返回True,否则False。 横线处不能填入的代码是( )。

self.tail is None
self._size == 0
self == None
self.head is None
基于上题代码正确的前提下,填入相应代码完善append()函数,用于在尾部增加新节点( )。

self.tail.next = new_node
new_node.prev = self.tail
self.tail.next = new_node
self.tail = new_node
new_node.prev = self.tail
self.tail.next = new_node
new_node.prev = self.tail
self.tail.next = new_node
self.tail = new_node
下面的Python代码,用于求一系列数据中的最大值。有关其算法说法错误的是( )。

该算法采用分治算法
该算法是递归实现
该算法采用贪心算法
该算法不是递推算法
基于上题的find_max()实现,下面的说法错误的是( )。
find_max() 适用于 str
find_max() 适用于 list
find_max() 适用于 tuple
find_max() 适用于 dict
下面的Python代码,用于求一系列数据中的最大值。有关其算法说法错误的是( )。

本题的 find_max() 函数采用分治算法
和上上题的 find_max() 函数相比,本题 find_max() 运行效率相对较低,因为需要分配额外的内存空间,用以存储nums的切片结果
和上上题的 find_max() 函数相比,本题 find_max() 的空间复杂度与之相同,不需要额外的存储资源
本题的 find_max() 的时间复杂度为 O(n log n)