某个应用中，需要对输入数据进行排序，输入数据序列基本有序（如输入为1,2,5,3,4,6,8,7）。在这种情况下，采用（1）排序算法最好，时间复杂度为（2）。 2、____A.O（n） B.O（nlgn） C.O（n^2） D.O（n^2lgn）

题目
某个应用中，需要对输入数据进行排序，输入数据序列基本有序（如输入为1,2,5,3,4,6,8,7）。在这种情况下，采用（1）排序算法最好，时间复杂度为（2）。
2、____

A.O（n）
B.O（nlgn）
C.O（n^2）
D.O（n^2lgn）
相似考题

1.下列排序方法中,在最坏情况下算法的时间复杂度为 O(n^2)的有________。A、堆排序B、快速排序C、希尔排序D、冒泡排序

2.● 以下关于快速排序算法的描述中，错误的是 （64） 。在快速排序过程中，需要设立基准元素并划分序列来进行排序。若序列由元素{12,25,30,45,52,67,85}构成，则初始排列为 （65） 时，排序效率最高（令序列的第一个元素为基准元素）。（64）A. 快速排序算法是不稳定的排序算法B. 快速排序算法在最坏情况下的时间复杂度为O(n1gn)C. 快速排序算法是一种分治算法D. 当输入数据基本有序时，快速排序算法具有最坏情况下的时间复杂度（65）A. 45,12,30,25,67,52,85B. 85,67,52,45,30,25,12C. 12,25,30,45,52,67,85D. 45,12,25,30,85,67,52

3.以下关于快速排序算法的描述中，错误的是( )。在快速排序过程中，需要设立基准元素并划分序列来进行排序。若序列由元素{12，25，30，45，52，67，85}构成，则初始排列为( )时，排序效率最高(令序列的第一个元素为基准元素)。A．快速排序算法是不稳定的排序算法B．快速排序算法在最坏情况下的时间复杂度为0(nlgn)C．快速排序算法是一种分治算法D．当输入数据基本有序时，快速排序算法具有最坏情况下的时间复杂度

4.在其最好情况下的算法时间复杂度为O(n)。A．插入排序B．归并排序C．快速排序D．堆排序

更多“某个应用中，需要对输入数据进行排序，输入数据序列基本有序（如输入为1,2,5,3,4,6,8,7）。在这种情况下，采用（1）排序算法最好，时间复杂度为（2）。 ”相关问题

  • 第1题：

    在原始序列已经有序(升序或降序)的情况下，(60)算法的时间复杂度为O(n2)。

    A．堆排序

    B．插入排序

    C．快速排序

    D．归并排序


    正确答案：C
    解析：无论原始序列中的元素如何排列，归并排序和堆排序算法的时间复杂度都是 O(nlgn)。快速排序算法处理的最好情况指每次都是将待排序列划分为均匀的两部分，此时算法时间复杂度是O(nlgn)。在原始序列已经有序(升序或降序)的情况下，快速排序算法的时间复杂度反而为O(n2)。插入排序是将一个新元素插入已经排列好的序列中。如果在数据已经是升序的情况下，新元素只需插入到序列尾部，这就是插入排序的最好情况，此时计算时间为O(n)。

  • 第2题：

    ● 若总是以待排序列的第一个元素作为基准元素进行快速排序，那么最好情况下的时间复杂度为 （65） 。


    正确答案：C

  • 第3题：

    对n个基本有序的整数进行排序，若采用插入排序算法，则时间和空间复杂度分别为（62）；若采用快速排序算法，则时间和空间复杂度分别为（63）。

    A.O（n2）和O（n）

    B.O（n）和O（n）

    C.O（n2）和O（1）

    D.O（n）和O（1）


    正确答案：C
    本题考查基本排序算法的时间复杂度与空间复杂度。

  • 第4题：

    直接选择排序的平均时间复杂度为(17)。最好情况下时间复杂度为O(n)的排序算法是(18)。在最好和最花情况下的时间复杂度均为O(nlogn)且稳定的排序方法是(19)。

    A．O(n)

    B．O(nlogn)

    C．O(n2)

    D．O(logn)


    正确答案：C

  • 第5题：

    下列排序算法中时间复杂度不受数据初始状态影响，恒为O(n2)的是

    A、堆排序

    B、起泡排序

    C、直接选择排序

    D、快速排序


    正确答案：C

  • 第6题：

    某个应用中，需要对输入数据进行排序，输入数据序列基本有序(如输入为1,2,5,3,4,6,8,7)。在这种情况下，采用(请作答此空)排序算法最好，时间复杂度为( )。

    A.插入
    B.归并
    C.堆
    D.快速

    答案：A
    解析：
    当序列基本有序时，使用插入排序效率是最高的，能达到这种算法的最优效果，O(n)。

  • 第7题：

    某个应用中，需要对输入数据进行排序，输入数据序列基本有序（如输入为1,2,5,3,4,6,8,7）。在这种情况下，采用（1）排序算法最好，时间复杂度为（2）。
    1、____

    A.插入
    B.归并
    C.堆
    D.快速

    答案：A
    解析：
    当一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到插入排序法，时间复杂度为O（n^2），是稳定的排序方法。

  • 第8题：

    现需要对一个基本有序的数组进行排序。此时最适宜采用的算法为（64）排算法，时间复杂度为（65）。

    A.插入
    B.快速
    C.归并
    D.堆

    答案：A
    解析：
    对于基本有序数组采用插入排序效率是最高的，时间复杂度为O（n），快速排序适用于无序数组，对于有序数组来说时间复杂度是O（n2），属于最坏的情况。

  • 第9题：

    快速排序当数据表初态为有序排列时，算法的效率最低，时间复杂度为（）


    正确答案:O(n2)

  • 第10题：

    当输入序列已经基本有序时，起泡排序需要比较关键码的次数，比快速排序还要少。


    正确答案:正确

  • 第11题：

    直接选择排序算法在最好情况下的时间复杂度为O（n）。


    正确答案:错误

  • 第12题：

    判断题
    在初始数据表已经有序时，快速排序算法的时间复杂度为O（nlog2n ）。
    A

    对

    B

    错


    正确答案： 错
    解析： 暂无解析

  • 第13题：

    下列排序方法中，最好情况下，时间复杂度为O(n)的算法是______。

    A．选择排序

    B．归并排序

    C．快速排序

    D．直接插入排序


    正确答案：D
    解析：各种排序算法性能比较如下：

  • 第14题：

    下列排序算法中，时间复杂度不受数据初始化状态影响，恒为0(log2n)的是()。

    A.堆排序

    B.冒泡排序

    C.直接选择排序

    D.快速排序


    正确答案：D

  • 第15题：

    阅读下列函数说明和C代码，回答下面问题。

    [说明]

    冒泡排序算法的基本思想是：对于无序序列(假设扫描方向为从前向后，进行升序排列)，两两比较相邻数据，若反序则交换，直到没有反序为止。一般情况下，整个冒泡排序需要进行众(1≤k≤n)趟冒泡操作，冒泡排序的结束条件是在某一趟排序过程中没有进行数据交换。若数据初态为正序时，只需1趟扫描，而数据初态为反序时，需进行n-1趟扫描。在冒泡排序中，一趟扫描有可能无数据交换，也有可能有一次或多次数据交换，在传统的冒泡排序算法及近年的一些改进的算法中[2，3]，只记录一趟扫描有无数据交换的信息，对数据交换发生的位置信息则不予处理。为了充分利用这一信息，可以在一趟全局扫描中，对每一反序数据对进行局部冒泡排序处理，称之为局部冒泡排序。

    局部冒泡排序的基本思想是：对于N个待排序数据组成的序列，在一趟从前向后扫描待排数据序列时，两两比较相邻数据，若反序则对后一个数据作一趟前向的局部冒泡排序，即用冒泡的排序方法把反序对的后一个数据向前排到适合的位置。扫描第—对数据对，若反序，对第2个数据向前冒泡，使前两个数据成为，有序序列；扫描第二对数据对，若反序，对第3个数据向前冒泡，使得前3个数据变成有序序列；……；扫描第i对数据对时，其前i个数据已成有序序列，若第i对数据对反序，则对第i+1个数据向前冒泡，使前i+1个数据成有序序列；……；依次类推，直至处理完第n-1对数据对。当扫描完第n-1对数据对后，N个待排序数据已成了有序序列，此时排序算法结束。该算法只对待排序列作局部的冒泡处理，局部冒泡算法的

    名称由此得来。

    以下为C语言设计的实现局部冒泡排序策略的算法，根据说明及算法代码回答问题1和问题2。

    [变量说明]

    define N=100 //排序的数据量

    typedef struct{ //排序结点

    int key；

    info datatype；

    ......

    }node;

    node SortData[N]; //待排序的数据组

    node类型为待排序的记录(或称结点)。数组SortData[]为待排序记录的全体称为一个文件。key是作为排序依据的字段，称为排序码。datatype是与具体问题有关的数据类型。下面是用C语言实现的排序函数，参数R[]为待排序数组，n是待排序数组的维数，Finish为完成标志。

    [算法代码]

    void Part-BubbleSort (node R[], int n)

    {

    int=0 ; //定义向前局部冒泡排序的循环变量

    //暂时结点，存放交换数据

    node tempnode；

    for (int i=0；i＜n-1；i++) ;

    if (R[i].key＞R[i+1].key)

    {

    (1)

    while ( (2) )

    {

    tempnode=R[j] ;

    (3)

    R[j-1]=tempnode ;

    Finish=false ;

    (4)

    } // end while

    } // end if

    } // end for

    } // end function

    阅读下列函数说明和C代码，将应填入(n)处的字句写在的对应栏内。


    正确答案：(1)j=i+1； (2)j＞0& &R[j].keyR[j-1].key (3)R[j]=R[j-1]; //反序则交换数据 (4)j--；(或j=j-1；)
    (1)j=i+1； (2)j＞0& &R[j].keyR[j-1].key (3)R[j]=R[j-1]; //反序，则交换数据 (4)j--；(或j=j-1；)

  • 第16题：

    某个应用中，需要对输入数据进行排序，输入数据序列基本有序(如输入为1,2,5,3,4,6,8,7)。在这种情况下，采用（ ）排序算法最好，时间复杂度为（ ）。

    A.插入 B.归并 C.堆 D.快速 A.O(n) B. O(nlgn) C.O(n^2) D. O(n^2lgn)


    正确答案：A,A

  • 第17题：

    某个应用中，需要对输入数据进行排序，输入数据序列基本有序(如输入为1,2,5,3,4,6,8,7)。在这种情况下，采用( )排序算法最好，时间复杂度为(请作答此空)。

    A.O(n)
    B.O(nlgn)
    C.O(n^2)
    D.O(n^2lgn)

    答案：A
    解析：
    当序列基本有序时，使用插入排序效率是最高的，能达到这种算法的最优效果，O(n)。

  • 第18题：

    最好情况下的算法时间复杂度为O(n)的是()。

    A.插入排序
    B.归并排序
    C.快速排序
    D.堆排序

    答案：A
    解析：

  • 第19题：

    某个应用中，需要对输入数据进行排序，输入数据序列基本有序（如输入为1,2,5,3,4,6,8,7）。在这种情况下，采用（ ）排序算法最好。

    A.插入
    B.归并
    C.堆
    D.快速

    答案：A
    解析：
    当一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到插入排序法，时间复杂度为O（n^2），是稳定的排序方法。

  • 第20题：

    在一般输入数据的程序里，输入多多少少会影响到算法的计算复杂度，为了消除这种影响可用（）对输入进行预处理。

    • A、蒙特卡罗算法
    • B、拉斯维加斯算法
    • C、舍伍德算法
    • D、数值概率算法

    正确答案:B

  • 第21题：

    在初始数据表已经有序时，快速排序算法的时间复杂度为O（nlog2n）。


    正确答案:错误

  • 第22题：

    设初始记录关键字基本有序，则快速排序算法的时间复杂度为O（nlog2n）。


    正确答案:错误

  • 第23题：

    填空题
    快速排序当数据表初态为有序排列时，算法的效率最低，时间复杂度为（）

    正确答案： O(n2)
    解析： 暂无解析

相关内容