首页 › 题库 › GESP编程能力等级认证 › 7 分治算法

GESP-Python五级 题库

共 28 道题 ,第 1 / 2 页 · 按题型筛选,点「查看答案」核对解析
章节 7 分治算法 清除
1 单选题 适中 GESP编程能力等级认证 ·GESP-Python五级 · 7.1 归并排序

下面代码实现了归并排序。下述关于归并排序的说法中,不正确的是( )。

def merge(arr, temp, l, mid, r):
    i = l
    j = mid + 1
    k = l
    while i <= mid and j <= r:
        if arr[i] <= arr[j]:
            temp[k] = arr[i]
            i += 1
        else:
            temp[k] = arr[j]
            j += 1
        k += 1
    while i <= mid:
        temp[k] = arr[i]
        i += 1
        k += 1
    while j <= r:
        temp[k] = arr[j]
        j += 1
        k += 1
    for p in range(l, r + 1):
        arr[p] = temp[p]
def merge_sort(arr, temp, l, r):
    if l >= r:
        return
    mid = l + (r - l) // 2
    merge_sort(arr, temp, l, mid)
    merge_sort(arr, temp, mid + 1, r)
    merge(arr, temp, l, mid, r)
def merge_sort_wrapper(arr):
    if not arr:
        return []
    temp = [0] * len(arr)
    merge_sort(arr, temp, 0, len(arr) - 1)
    return arr
A
归并排序的平均复杂度是 O(nlogn)。
B
归并排序需要O(n) 的额外空间。
C
归并排序在最坏情况的时间复杂度是 O(n²)。
D
归并排序适合大规模数据。
答案与解析
正确答案:C
归并排序最好、平均、最坏复杂度均为O(nlogn),C描述错误。
题目详情
2 单选题 适中 GESP编程能力等级认证 ·GESP-Python五级 · 7.2 快速排序

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

A

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

B

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

C

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

D

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

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

下述python代码实现了归并排序算法,则横线上应填写( )。

A

i < mid

B

j < right

C

i <= mid

D

j <= right

答案与解析
正确答案:D
这道题暂未补解析。
题目详情
4 单选题 适中 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
这道题暂未补解析。
题目详情
5 单选题 适中 GESP编程能力等级认证 ·GESP-Python五级 · 7.1 归并排序

下列归并算法程序中,横线处应该填入的是( )

def merge_sort(array):
	if len(array) == 1:
		return array
	_________________________
	return merge(left, right)
	
def merge(left, right):
	left_index, right_index, merge_array = 0, 0, list()
	while left_index < len(left) and right_index < len(right):
		if left[left_index] <= right[right_index]:
			merge_array.append(left[left_index])
			left_index += 1
		else:
			merge_array.append(right[right_index])
			right_index += 1
	merge_array = merge_array + left[left_index:] + right[right_index:]
	return merge_array
A
left = merge_sort(array[:len(array)-1//2])
right = merge_sort(array[len(array)-1//2:])
B
left = merge_sort(array[len(array)//2-1])
right = merge_sort(array[len(array)//2:])
C
left = merge_sort(array[len(array)//2-1])
right = merge_sort(array[len(array)//2])
D
left = merge_sort(array[:len(array)//2])
right = merge_sort(array[len(array)//2:])
答案与解析
正确答案:D
这道题暂未补解析。
题目详情
6 单选题 适中 GESP编程能力等级认证 ·GESP-Python五级 · 7.1 归并排序

下列归并算法程序中,横线处应该填入的是( )。

def merge_sort(arr):
	if len(arr) <= 1:
		return arr
	mid = len(arr) // 2
	left = arr[:mid]
	right = arr[mid:]
	merge_sort(left)
	merge_sort(right)
	return merge(left, right)

def merge(left, right):
	result = []
	i, j = 0, 0
	———————————————————————————————
		if left[i] < right[j]:
			result.append(left[i])
			i += 1
		else:
			result.append(right[j])
			j += 1
	result += left[i:]
	result += right[j:]
	return result


A
while i > len(left) and j < len(right):
B
while i < len(left) and j > len(right):
C
while i > len(left) and j > len(right):
D
while i < len(left) and j < len(right):
答案与解析
正确答案:D

merge_sort函数是递归分的过程,merge函数是合并两个有序序列的过程,对于left和right这两个数组合并,所以应该是i<left的长度,j<right的长度。

题目详情
7 单选题 适中 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最合适。

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

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

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

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

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

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

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

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

题目详情
9 单选题 适中 GESP编程能力等级认证 ·GESP-Python五级 · 7.1 归并排序

下面的Python代码中merge()函数的两个参数均为list类型,且是已按相同规则排序的数据。下面有关说法中,正确的是(   )。

A
第3-7行代码将导致死循环,因为没有循环变量及其改变
B
第5行和第7行代码执行后,result的成员值为None
C
第9行和第11行是否被执行,与arr1和arr2的成员值有关,如果值转换为False,将不会被执行merge()函数的代码没有错
D
误,执行后参数arr1和arr2将合并成新的list保存到result之中,且有序
答案与解析
正确答案:D
这道题暂未补解析。
题目详情
10 单选题 适中 GESP编程能力等级认证 ·GESP-Python五级 · 7.1 归并排序

下面Python代码以递归方式实现合并排序,并假设 merge(left,right) 函数能对有序(同样排序规则)的left 和 right 排序。横线处应填上代码是(   )。

A

mergeSort(listData[:Middle]), mergeSort(listData[Middle:])

B

mergeSort(listData[:Middle-1]), mergeSort(listData[Middle+1:])

C

mergeSort(listData[:Middle]), mergeSort(listData[Middle+1:])

D

mergeSort(listData[:Middle-1]), mergeSort(listData[Middle:])

答案与解析
正确答案:A
这道题暂未补解析。
题目详情
11 单选题 适中 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
这道题暂未补解析。
题目详情
12 单选题 适中 GESP编程能力等级认证 ·GESP-Python五级 · 7.1 归并排序

下面Python代码用于归并排序,其中 merge() 函数被调用次数为(     )。

A
0
B
1
C
6
D
7
答案与解析
正确答案:C
这道题暂未补解析。
题目详情
13 单选题 适中 GESP编程能力等级认证 ·GESP-Python五级 · 7.1 归并排序

在上题的归并排序算法中,代码

Left, Right = mergeSort(listData[:Middle]),

mergeSort(listData[Middle:]) 涉及到的算法有(     )。

A
搜索算法
B
分治算法
C
贪心算法
D
递推算法
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
14 单选题 适中 GESP编程能力等级认证 ·GESP-Python五级 · 7.1 归并排序

归并排序算法的基本思想是(     )。

A
将数组分成两个子数组,分别排序后再合并。
B
随机选择一个元素作为枢轴,将数组划分为两个部分。
C
从数组的最后一个元素开始,依次与前一个元素比较并交换位置。
D
比较相邻的两个元素,如果顺序错误就交换位置。
答案与解析
正确答案:A
这道题暂未补解析。
题目详情
15 判断题 偏易 GESP编程能力等级认证 ·GESP-Python五级 · 7.2 快速排序

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

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

快速排序和归并排序都是稳定的排序算法。

A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情
17 判断题 偏易 GESP编程能力等级认证 ·GESP-Python五级 · 7.1 归并排序

下面的Python代码用于归并排序(merge sort),已测试执行正确。假如整体交换 merge() 和 merge_sort() 两个函数的先后位置,则程序执行将触发异常。( )

A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情
18 判断题 偏易 GESP编程能力等级认证 ·GESP-Python五级 · 7.1 归并排序

基于上一题的Python代码。上题代码在执行时,将输出一次 HERE 字符串,因为merge_sort()递归调用在print("HERE") 之前,因此merge()函数仅被调用一次。( )

A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情
19 判断题 偏易 GESP编程能力等级认证 ·GESP-Python五级 · 7.1 归并排序

基于上上题的Python代码。代码片段 left_arr = merge_sort(arr[:mid]) 和 right_arr = merge_sort(arr[mid:]) 因为切片,将产生的新的list,对于大容量list的排序,将需要大量额外存储空间,可以优化为就地(implace)排序。( )

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

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

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