首页 › 题库 › GESP编程能力等级认证 › 2 算法复杂度

GESP-Python五级 题库

共 22 道题 ,第 1 / 2 页 · 按题型筛选,点「查看答案」核对解析
章节 2 算法复杂度 清除
1 单选题 适中 GESP编程能力等级认证 ·GESP-Python五级 · 2.1 多项式复杂度

下述python代码实现了快速排序算法,最差情况时间复杂度是()。

def partition(arr, low, high):
    i = low
    j = high
    pivot = arr[low]
    while i < j:
        while i < j and arr[j] >= pivot:
            j -= 1
        while i < j and arr[i] <= pivot:
            i += 1
        if i < j:
            arr[i], arr[j] = arr[j], arr[i]
    arr[i], arr[low] = arr[low], arr[i]
    return i
def quick_sort(arr, low, high):
    if low >= high:
        return
    p = partition(arr, low, high)
    quick_sort(arr, low, p - 1)
    quick_sort(arr, p + 1, high)
def quick_sort_wrapper(arr):
    if not arr:
        return []
    quick_sort(arr, 0, len(arr) - 1)
    return arr
A
O(n)
B
O(logn)
C
O(n²)
D
O(nlogn)
答案与解析
正确答案:C
有序/逆序数组做快排,每次划分只分出一个元素,递归深度n,时间复杂度O(n²)。
题目详情
2 单选题 适中 GESP编程能力等级认证 ·GESP-Python五级 · 2.1 多项式复杂度

下面折半查找程序的时间复杂度为( )

def binary_search(arr, x):
	low = 0
	high = len(arr) - 1
	while low <= high:
		mid = (low + high) // 2
		if arr[mid] == x:
			return mid
		elif arr[mid] > x:
			high = mid - 1
		else:
			low = mid + 1
	return -1


A
O(n∗logn)
B
O(n)
C
O(logn)
D
O(n2)
答案与解析
正确答案:C
这道题暂未补解析。
题目详情
3 单选题 适中 GESP编程能力等级认证 ·GESP-Python五级 · 2.1 多项式复杂度

关于算法复杂度,下列说法不正确的是()

A
简单的for循环的时间复杂度是O(1)
B
归并排序的时间复杂度是O(nlog(n))
C
选择排序中的内循环时间复杂度是(O(n2))
D
递归的 Fibonacci 数列计算时间复杂度是O(2n)
答案与解析
正确答案:A
这道题暂未补解析。
题目详情
4 单选题 适中 GESP编程能力等级认证 ·GESP-Python五级 · 2.1 多项式复杂度

上面代码的时间复杂度是( )。

A
O(logN)
B
O(NlogN)
C
O(N)
D
O(N^2)
答案与解析
正确答案:A

这段代码的主要操作是:

1、两层嵌套循环:外层循环遍历字符串的每个字符作为子字符串的起点,内层循环则从这个起点开始,尝试所有可能的子字符串长度(直到字符串末尾)。

外层循环:for i in range(len(srcStr)),执行次数为n(n 是字符串长度)。

内层循环:for j in range(i + 2, len(srcStr) + 1),对于外层循环的每次迭代,内层循环的次数大致为n - i - 1(因为从i+2 开始到字符串末尾)。

2、内层循环的累加:如果我们把内层循环的每次迭代都加起来,我们会发现这是一个等差数列的和,大致为n + (n-1) + (n-2) + … + 2 + 1,这个和是n(n+1)/2 - 1,但在分析时间复杂度时,我们更关心的是它的阶(order),即O(n^2)。

3、其他操作:虽然代码中还有回文检查和排序操作,但这些操作的时间复杂度相对于内层循环的O(n^2) 来说是可以忽略的(特别是当考虑到平均情况和最坏情况时的实际影响)。

因此,我们可以简单地说,这段代码的时间复杂度是O(n^2),其中n 是输入字符串的长度。这意味着随着输入字符串长度的增加,算法的执行时间将呈平方级增长。

题目详情
5 单选题 适中 GESP编程能力等级认证 ·GESP-Python五级 · 2.1 多项式复杂度

上题代码的时间复杂度是( )。

A
O(logN)
B
O(NlogN)
C
O(N)
D
O(N^2)
答案与解析
正确答案:C

整体时间复杂度仍然是主要由循环决定,为C

题目详情
6 单选题 适中 GESP编程能力等级认证 ·GESP-Python五级 · 2.1 多项式复杂度

不同的排序算法,其空间复杂度也不同。与冒泡法排序空间复杂度相同的是(   )

A
归并排序
B
快速排序
C
计数排序
D
插入排序
答案与解析
正确答案:D
这道题暂未补解析。
题目详情
7 单选题 适中 GESP编程能力等级认证 ·GESP-Python五级 · 2.1 多项式复杂度

下面Python代码的平均时间复杂度是(   )。

A
O(N)
B
O(logN)
C
O(NlogN)
D
O(N2)
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
8 单选题 适中 GESP编程能力等级认证 ·GESP-Python五级 · 2.1 多项式复杂度

在上题的算法中,其时间复杂度是(  )。

A
O(N)
B
O(logN)
C
O(NlogN)
D
O(N2)
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
9 单选题 适中 GESP编程能力等级认证 ·GESP-Python五级 · 2.1 多项式复杂度

在上题的算法中,其时间复杂度是(   )。

A
O(N)
B
O(logN)
C
O(NlogN)
D
O(N2)
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
10 判断题 偏易 GESP编程能力等级认证 ·GESP-Python五级 · 2.1 多项式复杂度

在 Python 实现的单链表中,已知引用 p 指向要删除的节点(该节点不是尾节点),若想在 O(1) 时间复杂度内删除这个节点,可行的做法是:用 p 的后继节点 p.next 的值覆盖 p 自身的值,再用 p 的后继节点的 next 引用覆盖 p 的 next 引用,最后断开 p 的后继节点的引用以辅助垃圾回收。()

A
对
B
错
答案与解析
正确答案:对
覆盖节点值、跳过后继,无需遍历前驱,时间复杂度O(1)。
题目详情
11 判断题 偏易 GESP编程能力等级认证 ·GESP-Python五级 · 2.1 多项式复杂度

以下 fib 函数计算第 n 项斐波那契数( fib(0)=0 , fib(1)=1 ),其时间复杂度为 O(n)。()

def fib(n) :
    if n &lt;= 1 :
        return n
    return fib(n - 1) + fib(n - 2)
A
对
B
错
答案与解析
正确答案:错
朴素递归斐波那契存在大量重复计算,时间复杂度O(2ⁿ)。
题目详情
12 判断题 偏易 GESP编程能力等级认证 ·GESP-Python五级 · 2.1 多项式复杂度

下面递归实现的斐波那契数列的时间复杂度为。

A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情
13 判断题 偏易 GESP编程能力等级认证 ·GESP-Python五级 · 2.1 多项式复杂度

下面代码采用分治算法求解汉诺塔问题,时间复杂度为。

A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情
14 判断题 偏易 GESP编程能力等级认证 ·GESP-Python五级 · 2.1 多项式复杂度

快速排序算法的时间复杂度与输入是否有序无关,始终稳定为 。

A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情
15 判断题 偏易 GESP编程能力等级认证 ·GESP-Python五级 · 2.1 多项式复杂度

时间复杂度对比O(1)<O(logn)<O(n)<O(nlogn)<O(n2logn)<O(n2)<O(n3) 。

A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情
16 判断题 偏易 GESP编程能力等级认证 ·GESP-Python五级 · 2.1 多项式复杂度

贪婪算法的复杂度通常是线性的,即O(n),其中n是输入的大小

A
对
B
错
答案与解析
正确答案:对

宏观考虑的话,在不考虑其他如排序这样的运算的情况下,贪心算法通常是线性的,就是一次考虑每一个物品的最优情况即可。

题目详情
17 判断题 偏易 GESP编程能力等级认证 ·GESP-Python五级 · 2.1 多项式复杂度

二分查找算法的复杂度通常表示为O(log n),其中n是数组的长度

A
对
B
错
答案与解析
正确答案:对

二分查找的时间复杂度为O(logn)。

题目详情
18 判断题 偏易 GESP编程能力等级认证 ·GESP-Python五级 · 2.1 多项式复杂度

在Python中,set或dict因为存储时即自动排序,因此可以用二分法查找,时间复杂度为 O(logN)。( )

A
对
B
错
答案与解析
正确答案:错

在 Python 中,set 和 dict 并不是自动排序的。它们分别用于存储唯一元素(set)和键值对(dict),但都不保证元素的顺序。set 的元素是无序的,而 dict 的元素(即键值对)虽然在 Python 3.7+ 中是按照插入顺序排序的(这被称为插入顺序保留),但这并不意味着它们是“自动排序”以支持二分查找等高效查找算法。

二分查找是一种在有序数组中查找特定元素的快速算法,其时间复杂度为 O(log n)。由于 set 和 dict 都不是基于有序数组实现的,因此不能使用二分查找来在这些数据结构上查找元素。

题目详情
19 判断题 偏易 GESP编程能力等级认证 ·GESP-Python五级 · 2.1 多项式复杂度

在Python中,当对dict类型进行in运算查找元素是否存在时,其时间复杂度为 O(1) ,set类型也如此。(   )

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
20 判断题 偏易 GESP编程能力等级认证 ·GESP-Python五级 · 2.1 多项式复杂度

冒泡排序是就地排序,空间复杂度为 O(1) 。(   )

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情