首页 › 题库 › GESP编程能力等级认证 › 7.1 归并排序

GESP-Python五级 题库

共 21 道题 ,第 1 / 2 页 · 按题型筛选,点「查看答案」核对解析
章节 7.1 归并排序 清除
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.1 归并排序

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

A

i < mid

B

j < right

C

i <= mid

D

j <= right

答案与解析
正确答案:D
这道题暂未补解析。
题目详情
3 单选题 适中 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
这道题暂未补解析。
题目详情
4 单选题 适中 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的长度。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

归并排序算法体现了分治算法,每次将大的待排序数组分成大小大致相等的两个小数组,然后分别对两个小数组进行排序,最后对排好序的两个小数组合并成有序数组。

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

归并排序的空间复杂度为O(n)

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

归并排序的时间复杂度为O(n log n)

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

归并排序是基于分治思想的,时间复杂度为O(nlogn)。

题目详情
18 判断题 偏易 GESP编程能力等级认证 ·GESP-Python五级 · 7.1 归并排序

归并排序和快速排序都采用递归实现,也都是不稳定排序。( )

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

归并排序

递归实现:归并排序通常使用递归来实现。它将数组(或链表)分成两半,分别对左右两半部分进行排序,然后再将排好序的两个部分合并起来

稳定性:归并排序是一种稳定的排序算法。稳定性指的是当有两个相等的元素在排序后的序列中的相对位置保持不变。

快速排序

递归实现:快速排序也通常采用递归来实现。它选择一个基准元素,将小于基准的元素放在基准的左边,大于基准的元素放在基准的右边,然后递归地对左右两个部分进行排序。

稳定性:快速排序是一种不稳定的排序算法。不稳定性指的是排序后相等元素的相对位置可能发生变化。

题目详情
19 判断题 偏易 GESP编程能力等级认证 ·GESP-Python五级 · 7.1 归并排序

归并排序的空间复杂度是 。(   )

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

归并排序的时间复杂度是 。(   )

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