GESP-Python五级 题库
下面代码实现了归并排序。下述关于归并排序的说法中,不正确的是( )。
下述python代码实现了快速排序算法,下面说法错误的是( )。

快速排序平均情况下比归并排序的比较、赋值、交换等操作的总数量少,所以命名为“快速”。
在平均情况下,划分的递归层数为
,每层中的总循环数为n,总时间为
。
在最差情况下,每轮划分操作都将长度为 的数组划分为长度为 0 和n-1的两个子数组,此时递归层数达到
,每层中的循环数为 ,总时间为
。
划分函数中“从右往左查找”与“从左往右查找”的顺序可以互换。
下述python代码实现了归并排序算法,则横线上应填写( )。


i < mid
j < right
i <= mid
j <= right
下列归并算法程序中,横线处应该填入的是( )。
merge_sort函数是递归分的过程,merge函数是合并两个有序序列的过程,对于left和right这两个数组合并,所以应该是i<left的长度,j<right的长度。
下列快速排序算法中,横线处应该填入的是( )。
p是基准值,接下来我们要把比p小的值放到p的左边,比p大的放到p的右边,p的取值应该是arr数组中的随意一个值即可,ABC选项都有越界的风险,所以D最合适。
下面有关快速排序的说法,错误的是( )。
正确。快速排序通常通过递归将数组分割成子数组来实现。
错误。快速排序是一种不稳定排序算法。在排序过程中,相同元素的相对位置可能会改变。
正确。最坏情况下,如果数组已经有序或者逆序,快速排序的时间复杂度可能达到O(N²),尤其是当选择的基准元素不合适时。
正确。快速排序通过交换数组中的元素来排序,不需要额外的空间,因此是一种原地排序算法。
因此,选项B错误,快速排序算法不是稳定排序算法。
下面的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:])
下面的Python代码实现对 list 的快速排序,有关说法,错误的是( )。

qSort(less) + qSort(greater) + [pivot]
[pivot] + qSort(less) + qSort(greater)
qSort(less) + [pivot] + qSort(greater)
qSort(less) + pivot + qSort(greater)
在上题的归并排序算法中,代码
Left, Right = mergeSort(listData[:Middle]),
mergeSort(listData[Middle:]) 涉及到的算法有( )。
归并排序算法的基本思想是( )。
通过在数组的第一个、最中间和最后一个这3个数据中选择中间值作为枢轴(比较基准),快速排序算法可降低落入最坏情况的概率。()
下面的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)排序。( )
下面的Python代码实现如果对一维list【形如:[32,12,32,13,42,1],而不是[(1,3),(3,1),(321,321),(32,13)]】进行快速排序,该排序是稳定排序。( )

