首页 › 题库 › GESP编程能力等级认证 › 7.2 快速排序

GESP-Python五级 题库

共 7 道题 · 按题型筛选,点「查看答案」核对解析
章节 7.2 快速排序 清除
1 单选题 适中 GESP编程能力等级认证 ·GESP-Python五级 · 7.2 快速排序

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

A

快速排序平均情况下比归并排序的比较、赋值、交换等操作的总数量少,所以命名为“快速”。

B

在平均情况下,划分的递归层数为 ,每层中的总循环数为n,总时间为。

C

在最差情况下,每轮划分操作都将长度为 的数组划分为长度为 0 和n-1的两个子数组,此时递归层数达到,每层中的循环数为 ,总时间为。

D

划分函数中“从右往左查找”与“从左往右查找”的顺序可以互换。

答案与解析
正确答案:D
这道题暂未补解析。
题目详情
2 单选题 适中 GESP编程能力等级认证 ·GESP-Python五级 · 7.2 快速排序

考虑以下python代码实现的快速排序算法,将数据从小到大排序,则横线上应填的最佳代码是( )。

def partition(arr, low, high):
	pivot = arr[high]
	i = low - 1

	for j in range(low, high):
	_________________________________

	arr[i + 1], arr[high] = arr[high], arr[i + 1]
	return i + 1

def quick_sort(arr, low, high):
	if low < high:
		pi = partition(arr, low, high)
		quick_sort(arr, low, pi - 1)
		quick_sort(arr, pi + 1, high)
A
if arr[i] < pivot:
	i += 1
	arr[i], arr[j] = arr[j], arr[i]
B
if arr[j] < pivot:
	j += 1
C
if arr[i] < pivot:
	j += 1
	arr[i], arr[i] = arr[j], arr[i]
D
if arr[j] < pivot:
	i += 1
	arr[i], arr[j] = arr[j], arr[i]
答案与解析
正确答案:D
这道题暂未补解析。
题目详情
3 单选题 适中 GESP编程能力等级认证 ·GESP-Python五级 · 7.2 快速排序

下列快速排序算法中,横线处应该填入的是( )。

def quick(arr):
	if len(arr) <= 1:
		return arr
		
	____________________
	left = [x for x in arr if x < p]
	middle = [x for x in arr if x == p]
	right = [x for x in arr if x > p]
	return quick(left) + middle + quick(right)


A
p = arr[len() // 2]
B
p = arr[len(arr)+1 // 2]
C
p = arr[len(arr)-1 // 2]
D
p = arr[len(arr) // 2]
答案与解析
正确答案:D

p是基准值,接下来我们要把比p小的值放到p的左边,比p大的放到p的右边,p的取值应该是arr数组中的随意一个值即可,ABC选项都有越界的风险,所以D最合适。

题目详情
4 单选题 适中 GESP编程能力等级认证 ·GESP-Python五级 · 7.2 快速排序

下面有关快速排序的说法,错误的是( )。

A
快速排序算法通常采用递归实现。
B
快速排序算法是一种稳定排序算法。
C
如果被排序数组或者list已排序或逆序,其时间复杂度是 O(N^2)
D
快速排序是一种原地(in-place)排序算法。
答案与解析
正确答案:B

正确。快速排序通常通过递归将数组分割成子数组来实现。

错误。快速排序是一种不稳定排序算法。在排序过程中,相同元素的相对位置可能会改变。

正确。最坏情况下,如果数组已经有序或者逆序,快速排序的时间复杂度可能达到O(N²),尤其是当选择的基准元素不合适时。

正确。快速排序通过交换数组中的元素来排序,不需要额外的空间,因此是一种原地排序算法。

因此,选项B错误,快速排序算法不是稳定排序算法。

题目详情
5 单选题 适中 GESP编程能力等级认证 ·GESP-Python五级 · 7.2 快速排序

下面的Python代码实现对 list 的快速排序,有关说法,错误的是(   )。

A

qSort(less) + qSort(greater) + [pivot]

B

[pivot] + qSort(less) + qSort(greater)

C

qSort(less) + [pivot] + qSort(greater)

D

qSort(less) + pivot + qSort(greater)

答案与解析
正确答案:C
这道题暂未补解析。
题目详情
6 判断题 偏易 GESP编程能力等级认证 ·GESP-Python五级 · 7.2 快速排序

通过在数组的第一个、最中间和最后一个这3个数据中选择中间值作为枢轴(比较基准),快速排序算法可降低落入最坏情况的概率。()

A
对
B
错
答案与解析
正确答案:对
三数取中法避免有序数组导致的最坏划分,优化快排性能。
题目详情
7 判断题 偏易 GESP编程能力等级认证 ·GESP-Python五级 · 7.2 快速排序

下面的Python代码实现如果对一维list【形如:[32,12,32,13,42,1],而不是[(1,3),(3,1),(321,321),(32,13)]】进行快速排序,该排序是稳定排序。( )

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