GESP-Python五级 题库
下面代码实现了归并排序。下述关于归并排序的说法中,不正确的是( )。
下述python代码实现了归并排序算法,则横线上应填写( )。


i < mid
j < right
i <= mid
j <= right
下列归并算法程序中,横线处应该填入的是( )。
merge_sort函数是递归分的过程,merge函数是合并两个有序序列的过程,对于left和right这两个数组合并,所以应该是i<left的长度,j<right的长度。
下面的Python代码中merge()函数的两个参数均为list类型,且是已按相同规则排序的数据。下面有关说法中,正确的是( )。

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

mergeSort(listData[:Middle]), mergeSort(listData[Middle:])
mergeSort(listData[:Middle-1]), mergeSort(listData[Middle+1:])
mergeSort(listData[:Middle]), mergeSort(listData[Middle+1:])
mergeSort(listData[:Middle-1]), mergeSort(listData[Middle:])
在上题的归并排序算法中,代码
Left, Right = mergeSort(listData[:Middle]),
mergeSort(listData[Middle:]) 涉及到的算法有( )。
归并排序算法的基本思想是( )。
下面的Python代码用于归并排序(merge sort),已测试执行正确。假如整体交换 merge() 和 merge_sort() 两个函数的先后位置,则程序执行将触发异常。( )

基于上一题的Python代码。上题代码在执行时,将输出一次 HERE 字符串,因为merge_sort()递归调用在print("HERE") 之前,因此merge()函数仅被调用一次。( )
基于上上题的Python代码。代码片段 left_arr = merge_sort(arr[:mid]) 和 right_arr = merge_sort(arr[mid:]) 因为切片,将产生的新的list,对于大容量list的排序,将需要大量额外存储空间,可以优化为就地(implace)排序。( )
归并排序算法体现了分治算法,每次将大的待排序数组分成大小大致相等的两个小数组,然后分别对两个小数组进行排序,最后对排好序的两个小数组合并成有序数组。
归并排序和快速排序都采用递归实现,也都是不稳定排序。( )
归并排序
递归实现:归并排序通常使用递归来实现。它将数组(或链表)分成两半,分别对左右两半部分进行排序,然后再将排好序的两个部分合并起来
稳定性:归并排序是一种稳定的排序算法。稳定性指的是当有两个相等的元素在排序后的序列中的相对位置保持不变。
快速排序
递归实现:快速排序也通常采用递归来实现。它选择一个基准元素,将小于基准的元素放在基准的左边,大于基准的元素放在基准的右边,然后递归地对左右两个部分进行排序。
稳定性:快速排序是一种不稳定的排序算法。不稳定性指的是排序后相等元素的相对位置可能发生变化。
