参考答案和解析
正确
更多“在快速排序算法中,基础子问题可以是1个元素的数组,也可以是10个元素的数组。前者不需要排序,后者可以用冒泡排序。”相关问题
  • 第1题:

    阅读以下算法说明,根据要求回答问题1~问题3。

    [说明]

    快速排序是一种典型的分治算法。采用快速排序对数组A[p..r]排序的3个步骤如下。

    1.分解:选择一个枢轴(pivot)元素划分数组。将数组A[p..r]划分为两个子数组(可能为空)A[p..q-1]和A[q+1..r],使得A[q]大于等于A[p..q-1]中的每个元素,小于A[q+1..r]中的每个元素。q的值在划分过程中计算。

    2.递归求解:通过递归的调用快速排序,对子数组A[p..q-1]和A[q+1..r]分别排序。

    3.合并:快速排序在原地排序,故无需合并操作。

    下面是快速排序的伪代码,请将空缺处(1)~(3)的内容填写完整。伪代码中的主要变量说明如下。

    A:待排序数组

    p,r:数组元素下标,从p到r

    q:划分的位置

    x:枢轴元素

    i:整型变量,用于描述数组下标。下标小于或等于i的元素的值,小于或等于枢轴元素的值

    j:循环控制变量,表示数组元素下标


    正确答案:这是一道考查快速排序算法伪代码的分析题。快速排序是对冒泡排序的一种改进其基本思想是:通过一趟排序将要排序的数据分割成独立的两部分其中一部分的所有数据都比另外一部分的所有数据都要小然后再按此方法对这两部分数据分别进行快速排序整个排序过程可以递归进行以此达到整个数据变成有序序列。快速排序最核心的处理是进行划分即PARTITION操作:根据枢轴元素的值把一个较大的数组分成两个较小的子数组一个子数组的所有元素的值小于等于枢轴元素的值一个子数组的所有元素的值大于枢轴元素的值而子数组内的元素不排序。划分时以最后一个元素为枢轴元素从左到右依次访问数组的每一个元素判断其与枢轴元素的大小关系并进行元素的交换如图2-30所示。 在[问题1]所给出的伪代码中当for循环结束后A[p..i]中的值应小于等于枢轴元素值x而A[i+1..r-1]中的值应大于枢轴元素值x。此时A[i+1]是第一个比A[r]大的元素因此A[r]与A[i+1]进行交换得到划分后的两个子数组。PARTITION操作返回枢轴元素的位置因此返回值为i+l。
    这是一道考查快速排序算法伪代码的分析题。快速排序是对冒泡排序的一种改进,其基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。快速排序最核心的处理是进行划分,即PARTITION操作:根据枢轴元素的值,把一个较大的数组分成两个较小的子数组,一个子数组的所有元素的值小于等于枢轴元素的值,一个子数组的所有元素的值大于枢轴元素的值,而子数组内的元素不排序。划分时,以最后一个元素为枢轴元素,从左到右依次访问数组的每一个元素,判断其与枢轴元素的大小关系,并进行元素的交换,如图2-30所示。 在[问题1]所给出的伪代码中,当for循环结束后,A[p..i]中的值应小于等于枢轴元素值x,而A[i+1..r-1]中的值应大于枢轴元素值x。此时A[i+1]是第一个比A[r]大的元素,因此A[r]与A[i+1]进行交换,得到划分后的两个子数组。PARTITION操作返回枢轴元素的位置,因此返回值为i+l。

  • 第2题:

    快速排序算法在排序过程中,在待排序数组中确定一个元素为基准元素,根据基准元素把待排序数组划分成两个部分,前面一部分元素值小于等于基准元素,而后面一部分元素值大于基准元素。然后再分别对前后两个部分进一步进行划分。根据上述描述,快速排序算法采用了 (61) 算法设计策略。已知确定基准元素操作的时间复杂度为,则快速排序算法的最好和最坏情况下的时间复杂度为 (62) 。

    A.分治

    B.动态规划

    C.贪心

    D.回溯


    正确答案:A
    本题考查快速排序算法。快速排序算法是应用最为广泛的排序算法之一。其基本思想是将n个元素划分为两个部分:一部分元素值小于某个数;另一部分元素值大于某个数,该数的位置确定;然后进一步划分前面部分和后面部分。根据该叙述,可以知道,这里采用的是分治算法设计策略。由于已知划分操作的时间复杂度为,不需要合并子问题的答案。对于最好的情况,应该是每次划分都把n个元素划分为大约2个n/2个元素的子数组,此时T(n)=2T(n/2)+解该递归式,可得时间复杂度为。若刚好划分的极度不均衡,即每个划分刚好把n个元素划分为一边0个元素,一边n-l个元素,此时T(n)=T(n/1)+解该递归式,可得时间复杂度为。

  • 第3题:

    快速排序算法是,在排序过程中,在待排序数组中确定一个元素为基准元素,根据基准元素把待排序数组划分成两个部分,前面一部分元素值小于基准元素,而后面一部分元素值大于基准元素。然后再分别对前后两个部分进一步进行划分。根据上述描述,快速排序算法采用了 ( ) 算法设计策略。已知确定着基准元素操作的时间复杂度为O(n),则快速排序算法的最好和最坏情况下的时间复杂度为 (请作答此空) 。

    A.O(n)和O(nlgn)
    B.O(n)和O(n2)
    C.O(nlgn)和O(nlgn)
    D.O(nlgn)和O(n2)

    答案:D
    解析:
    将数据分成若干份,每份单独处理后再合并,其思想为分治。
    理想情况下,快速排序每次将数据划分为规模相近的两部分,并递归至不可再划分,因此其时间复杂度为O(nlgn)。在最坏情况下,每次划分都极不均匀,如一个类别中仅有一个元素,另一个类别中包含剩余所有元素。这时划分的复杂度为O(n),次操作的总复杂度为O(n2)。

  • 第4题:

    快速排序算法在排序过程中,在待排序数组中确定一个元素为基准元素,根据基准元素把待排序数组划分成两个部分,前面一部分元素值小于等于基准元素,而后面一部分元素值大于基准元素。然后再分别对前后两个部分进一步进行划分。根据上述描述,快速排序算法采用了( )算法设计策略。已知确定基准元素操作的时间复杂度为Θ(n),则快速排序算法的最好和最坏情况下的时间复杂度为(请作答此空)。


    答案:D
    解析:
    快速排序采用分治法的思想。快速排序最好情况的时间复杂度是O(nlog2n)。最坏情况下,即初始序列按关键字有序或者基本有序时,快速排序的时间复杂度为O(n2)。

  • 第5题:

    若要求对大小为n的数组进行排序的时间复杂度为,且是稳定的(即如果待排序的序列中两个数据元素具有相同的值,在排序前后它们的相对位置不变),则可选择的排序方法是( )

    A.快速排序
    B.归并排序
    C.堆排序
    D.冒泡排序

    答案:B
    解析:
    常见的排序方法的基本情况如图所示,满足时间复杂度且是稳定的方法只有归并排序最符合,

  • 第6题:

    下列排序算法中,()不能保证每趟排序至少能将一个元素放到其最终的位置上。

    • A、希尔排序
    • B、快速排序
    • C、冒泡排序
    • D、堆排序

    正确答案:A

  • 第7题:

    对用数组存储的线性表(16,15,32,11,6,30),用快速排序算法进行由小到大排序,若排序下标范围为0~5,选择元素16作为支点,调用一趟快速排序算法后,元素16在数组中的下标位置为()


    正确答案:3

  • 第8题:

    冒泡排序算法中降序排序指的是()

    • A、从高到低排列数组元素值
    • B、从低到高排列数组元素的值
    • C、由横向到纵向排列数组元素的值
    • D、由纵向到横向排列数组元素的值

    正确答案:A

  • 第9题:

    一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完,这种排序算法被称为()。

    • A、冒泡排序
    • B、选择排序
    • C、插入排序
    • D、快速排序

    正确答案:B

  • 第10题:

    单选题
    下列排序算法中()不能保证每趟排序至少能将一个元素放到其最终的位置上。
    A

    快速排序

    B

    shell排序

    C

    堆排序

    D

    冒泡排序


    正确答案: D
    解析: 暂无解析

  • 第11题:

    单选题
    一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完,这种排序算法被称为()。
    A

    冒泡排序

    B

    选择排序

    C

    插入排序

    D

    快速排序


    正确答案: D
    解析: 暂无解析

  • 第12题:

    单选题
    下列排序算法中,()算法可能会出现下面情况:在最后一趟开始之前,所有元素都不在其最终的位置上。
    A

    堆排序

    B

    冒泡排序

    C

    快速排序

    D

    插入排序


    正确答案: C
    解析: 暂无解析

  • 第13题:

    在待排序的元素序列基本有序的前提下,效率最高的排序算法是______。

    A.冒泡排序

    B.选择排序

    C.快速排序

    D.归并排序


    正确答案:A

  • 第14题:

    ● 如果待排序序列中两个元素具有相同的值,在排序前后它们的相互位置发生颠倒,则称该排序算法是不稳定的。 (41) 是稳定的排序方法,因为这种方法在比较相邻元素时,值相同的元素并不进行交换。

    (41)

    A. 冒泡排序

    B. 希尔排序

    C. 快速排序

    D. 简单选择排序


    正确答案:A

  • 第15题:

    快速排序算法在排序过程中,在待排序数组中确定一个元素为基准元素,根据基准元素把待排序数组划分成两个部分,前面一部分元素值小于等于基准元素,而后面一部分元素值大于基准元素。然后再分别对前后两个部分进一步进行划分。根据上述描述,快速排序算法采用了(请作答此空)算法设计策略。已知确定基准元素操作的时间复杂度为Θ(n),则快速排序算法的最好和最坏情况下的时间复杂度为( )。

    A.分治
    B.动态规划
    C.贪心
    D.回溯

    答案:A
    解析:
    快速排序采用分治法的思想。快速排序最好情况的时间复杂度是O(nlog2n)。最坏情况下,即初始序列按关键字有序或者基本有序时,快速排序的时间复杂度为O(n2)。

  • 第16题:

    下列排序算法中,不能保证每趟排序至少能将一个元素放到其最终的位置上的是()。

    A.快速排序
    B.shell排序
    C.堆排序
    D.冒泡排序

    答案:B
    解析:
    shell排序每次使待排序记录基本有序,但不能保证每趟排序至少能将一个元素放到其最终的位置上。

  • 第17题:

    快速排序算法在排序过程中,在待排序数组中确定一个元素为基准元素,根据基准元素把待排序数组划分成两个部分,前面一部分元素值小于等于基准元素,而后面一部分元素值大于基准元素。然后再分别对前后两个部分进一步进行划分。根据上述描述,快速排序算法采用了()算法设计策略。

    • A、分治
    • B、动态规划
    • C、贪心
    • D、回溯

    正确答案:A

  • 第18题:

    下列排序算法中,()算法可能会出现下面情况:在最后一趟开始之前,所有元素都不在其最终的位置上。

    • A、堆排序
    • B、冒泡排序
    • C、快速排序
    • D、插入排序

    正确答案:D

  • 第19题:

    采用下列排序算法对n个元素进行排序,其排序趟数肯定为n-1趟的排序方法有()。

    • A、选择和插入
    • B、冒泡和快速
    • C、插入和快速
    • D、选择和冒泡

    正确答案:A

  • 第20题:

    对相邻的元素进行两两比较,顺序相反则进行交换,不断重复直到元素全部有序的排序算法称为()

    • A、冒泡排序
    • B、快速排序
    • C、插入排序
    • D、选择排序

    正确答案:A

  • 第21题:

    在下列算法中,()算法可能出现下列情况:在最后一趟开始之前,所有的元素都不在其最终的位置上。

    • A、堆排序
    • B、冒泡排序
    • C、插入排序
    • D、快速排序

    正确答案:C

  • 第22题:

    填空题
    对用数组存储的线性表(16,15,32,11,6,30),用快速排序算法进行由小到大排序,若排序下标范围为0~5,选择元素16作为支点,调用一趟快速排序算法后,元素16在数组中的下标位置为()

    正确答案: 3
    解析: 暂无解析

  • 第23题:

    单选题
    下列排序算法中,()不能保证每趟排序至少能将一个元素放到其最终的位置上。
    A

    希尔排序

    B

    快速排序

    C

    冒泡排序

    D

    堆排序


    正确答案: D
    解析: 快速排序的每趟排序能将作为枢轴的元素放到最终位置;冒泡排序的每趟排序能将最大或最小的元素放到最终位置;堆排序的每趟排序能将最大或最小的元素放到最终位置。

  • 第24题:

    单选题
    对相邻的元素进行两两比较,顺序相反则进行交换,不断重复直到元素全部有序的排序算法称为()
    A

    冒泡排序

    B

    快速排序

    C

    插入排序

    D

    选择排序


    正确答案: D
    解析: 暂无解析