精华内容
下载资源
问答
  • 对n个记录进行归并排序
    万次阅读
    2018-11-30 17:07:08

    2-1

    对N个记录进行归并排序,归并趟数的数量级是: (1分)

    1. O(logN)
    2. O(N)
    3. O(NlogN)
    4. O(N​2​​)

    2-2

    对N个记录进行归并排序,空间复杂度为: (1分)

    1. O(logN)
    2. O(N)
    3. O(NlogN)
    4. O(N​2​​)

    2-3

    给出关键字序列{ 431, 56, 57, 46, 28, 7, 331, 33, 24, 63 },下面哪个选择是按次位优先(LSD)链式基数排序进行了一趟分配和收集的结果? (2分)

    1. →331→431→33→63→24→56→46→57→7→28
    2. →56→28→431→331→33→24→46→57→63→7
    3. →431→331→33→63→24→56→46→57→7→28
    4. →57→46→28→7→33→24→63→56→431→331

    2-4

    输入10​5​​个只有一位数字的整数,可以用O(N)复杂度将其排序的算法是:(1分)

    1. 快速排序
    2. 插入排序
    3. 桶排序
    4. 希尔排序

    2-5

    数据序列{ 3, 1, 4, 11, 9, 16, 7, 28 }只能是下列哪种排序算法的两趟排序结果?(2分)

    1. 冒泡排序
    2. 快速排序
    3. 插入排序
    4. 堆排序

    2-6

    对10TB的数据文件进行排序,应法使用的方是:(1分)

    1. 希尔排序
    2. 堆排序
    3. 归并排序
    4. 快速排序

    2-7

    在内部排序时,若选择了归并排序而没有选择插入排序,则可能的理由是:(2分)

    1. 归并排序的程序代码更短
    2. 归并排序占用的空间更少
    3. 归并排序的运行效率更高
    1. 仅 2
    2. 仅 3
    3. 仅 1、2
    4. 仅 1、3

    2-8

    下列排序方法中,若将顺序村吃更换为链式存储,则算法的时间效率会降低的是:(2分)

    1.插入排序;2.选择排序;3.起泡排序;4.希尔排序;5.堆排序

    1. 仅1、2
    2. 仅2、3
    3. 仅3、4
    4. 仅4、5

    2-9

    { 12,9,11,8,7,4,5,13,23 }是下列哪种方法第二趟排序后的结果? (2分)

    1. 归并排序
    2. 堆排序
    3. 插入排序
    4. 基数排序

    2-10

    输入10​4​​个只有一位数字的整数,可以用O(N)复杂度将其排序的算法是:(1分)

    1. 桶排序
    2. 快速排序
    3. 插入排序
    4. 希尔排序

    2-11

    将序列{ 2, 12, 16, 88, 5, 10, 34 }排序。若前2趟排序的结果如下:

    • 第1趟排序后:2, 12, 16, 10, 5, 34, 88
    • 第2趟排序后:2, 5, 10, 12, 16, 34, 88

    则可能的排序算法是:(2分)

    1. 冒泡排序
    2. 快速排序
    3. 归并排序
    4. 插入排序

    2-12

    将序列{ 2, 12, 16, 88, 5, 10, 34 }排序。若前2趟排序的结果如下:

    • 第1趟排序后:2, 12, 16, 10, 5, 34, 88
    • 第2趟排序后:2, 5, 10, 12, 16, 34, 88

    则可能的排序算法是:(2分)

    1. 冒泡排序
    2. 归并排序
    3. 插入排序
    4. 快速排序

    2-13

    将序列{ 2, 12, 16, 88, 5, 10, 34 }排序。若前2趟排序的结果如下:

    • 第1趟排序后:2, 12, 16, 10, 5, 34, 88
    • 第2趟排序后:2, 5, 10, 12, 16, 34, 88

    则可能的排序算法是:(2分)

    1. 冒泡排序
    2. 归并排序
    3. 快速排序
    4. 插入排序

    2-14

    在对N个元素进行排序时,基于比较的算法中,其“最坏时间复杂度”中最好的是: (1分)

    1. O(logN)
    2. O(N)
    3. O(NlogN)
    4. O(N​2​​)

    2-15

    下列排序算法中,哪种算法可能出现:在最后一趟开始之前,所有的元素都不在其最终的位置上?(设待排元素个数N>2) (2分)

    1. 冒泡排序
    2. 插入排序
    3. 堆排序
    4. 快速排序

    2-16

    若数据元素序列{ 11,12,13,7,8,9,23,4,5 }是采用下列排序方法之一得到的第二趟排序后的结果,则该排序算法只能是: (2分)

    1. 冒泡排序
    2. 选择排序
    3. 插入排序
    4. 归并排序

    2-17

    数据序列{ 3,2,4,9,8,11,6,20 }只能是下列哪种排序算法的两趟排序结果? (2分)

    1. 冒泡排序
    2. 选择排序
    3. 插入排序
    4. 快速排序

    2-18

    对一组数据{ 2,12,16,88,5,10 }进行排序,若前三趟排序结果如下: 第一趟排序结果:2,12,16,5,10,88 第二趟排序结果:2,12,5,10,16,88 第三趟排序结果:2,5,10,12,16,88 则采用的排序方法可能是: (2分)

    1. 冒泡排序
    2. 希尔排序
    3. 归并排序
    4. 基数排序

    2-19

    就排序算法所用的辅助空间而言,堆排序、快速排序、归并排序的关系是: (1分)

    1. 堆排序 < 归并排序 < 快速排序
    2. 堆排序 > 归并排序 > 快速排序
    3. 堆排序 < 快速排序 < 归并排序
    4. 堆排序 > 快速排序 > 归并排序

    2-20

    下面四种排序算法中,稳定的算法是: (1分)

    1. 堆排序
    2. 希尔排序
    3. 归并排序
    4. 快速排序

    2-21

    在基于比较的排序算法中,哪种算法的最坏情况下的时间复杂度不高于O(NlogN)? (1分)

    1. 冒泡排序
    2. 归并排序
    3. 希尔排序
    4. 快速排序

    2-22

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

    1. 冒泡排序
    2. 直接选择排序
    3. 堆排序
    4. 快速排序

    2-23

    输入10​5​​个只有一位数字的整数,可以用O(N)复杂度将其排序的算法是: (1分)

    1. 快速排序
    2. 插入排序
    3. 希尔排序
    4. 基数排序

    2-24

    排序方法中,从未排序序列中依次取出元素与已排序序列中的元素进行比较,将其放入已排序序列的正确位置的方法称为: (1分)

    1. 插入排序
    2. 选择排序
    3. 快速排序
    4. 归并排序
    更多相关内容
  • 解析在下面 2-4,10,23题目写的有点...空间复杂度就是O(N),因为需要开一临时数组 x2-4: 就一位,数也不多,直接桶排序最好,速度是线性的 x2-5: 用排除法很好做。。。至于为啥是快排我也不知道。。。...

    解析在下面

    2-4,10,23题目写的有点问题,应该是104,105

    解析:

    p1-1:

    注意哦,人家问的不是时间复杂度,而是归并趟数的数量级,应该是O(logN) 

    x2-2:

    空间复杂度就是O(N),因为需要开一个临时数组

    x2-4:

    就一位,个数也不多,直接桶排序最好,速度是线性的

    x2-5:

    用排除法很好做。。。至于为啥是快排我也不知道。。。

    x2-6:

    对于10TB的海量数据,数据不可能一次全部载入内存,传统的排序方法就不适用了,需要用到外排序的方法。外排序采用分治思想,即先对数据分块,对块内数据进行排序,然后采用归并排序的思想进行排序,得到数据的一个有序序列。

    x2-7:

    归并一般用于外排序,如果用于内排,而不用插入 这种简单排序,

    可能的原因也就只有c了。

    a肯定错

    b插入排序是不占空间的

    x2-8:

    这个很难

    插入排序、选择排序、起泡排序原本时间复杂度是O(n2),更换为链式存储后的时间复杂度还是O(n2)。希尔排序和堆排序都利用了顺序存储的随机访问特性(堆排序的这个特性体现在:取出最大堆的根节点后,更新堆的过程),而链式存储不支持这种性质,所以时间复杂度会增加,因此选D。

    x2-9:

    因为堆排序就是每次删除最大堆,并把它放在最后,其实这个过程有点像冒泡我觉得

    x2-10:

    同2-4:

    x2-11,12,13:

    第一步:以34为主元

    第二部,左边递归排序

    x2-15:

    这个很明显就是插入排序的特点

    x2-16:

    这个题很好!!!

    考查各排序算法的特点。
    解答本题要对不同排序算法的特点极为清楚。
    对于起泡排序和选择排序而言,每一趟过后都能确定一个元素的最终位置,而由题目中所说,前两个元素和后两个元素均不是最小或最大的两个元素并按序排列。
    (二路)归并排序,第一趟排序结束都可以得到若干个有序子序列,而此时的序列中并没有两两元素有序排列。
    插入排序在每趟排序结束后能保证前面的若干元素是有序的,而此时第二趟排序后,序列的前三个元素是有序的,符合其特点。故正确答案是B。

    x2-17:

    和上一题差不多,也可以用排除法分析,只能是快排

    x2-19:

    看表

    x2-21:

    归并排序用于都是O(NlogN)

    x2-22:

    看图

    x2-23:

    这个没有桶排序,但是只有一位,那就用它的升级版基数排序即可

    后面的不用看了

     

     

     

     

     

     

    1-1

    对N个记录进行归并排序,归并趟数的数量级是O(NlogN)。 (2分)

    T         F

    2-1

    对N个记录进行归并排序,归并趟数的数量级是: (1分)

    1. O(logN)
    2. O(N)
    3. O(NlogN)
    4. O(N​2​​)

    作者: DS课程组

    单位: 浙江大学

    2-2

    对N个记录进行归并排序,空间复杂度为: (1分)

    1. O(logN)
    2. O(N)
    3. O(NlogN)
    4. O(N​2​​)

    作者: DS课程组

    单位: 浙江大学

    2-3

    给出关键字序列{ 431, 56, 57, 46, 28, 7, 331, 33, 24, 63 },下面哪个选择是按次位优先(LSD)链式基数排序进行了一趟分配和收集的结果? (2分)

    1. →331→431→33→63→24→56→46→57→7→28
    2. →56→28→431→331→33→24→46→57→63→7
    3. →431→331→33→63→24→56→46→57→7→28
    4. →57→46→28→7→33→24→63→56→431→331

    作者: DS课程组

    单位: 浙江大学

    2-4

    输入10​5​​个只有一位数字的整数,可以用O(N)复杂度将其排序的算法是:(1分)

    1. 快速排序
    2. 插入排序
    3. 桶排序
    4. 希尔排序

    作者: 陈越

    单位: 浙江大学

    2-5

    数据序列{ 3, 1, 4, 11, 9, 16, 7, 28 }只能是下列哪种排序算法的两趟排序结果?(2分)

    1. 冒泡排序
    2. 快速排序
    3. 插入排序
    4. 堆排序

    作者: 陈越

    单位: 浙江大学

    2-6

    对10TB的数据文件进行排序,应使用的方法是:(1分)

    1. 希尔排序
    2. 堆排序
    3. 归并排序
    4. 快速排序

    作者: DS课程组

    单位: 浙江大学

    2-7

    在内部排序时,若选择了归并排序而没有选择插入排序,则可能的理由是:(2分)

    1. 归并排序的程序代码更短
    2. 归并排序占用的空间更少
    3. 归并排序的运行效率更高
    1. 仅 2
    2. 仅 3
    3. 仅 1、2
    4. 仅 1、3

    作者: 考研试卷

    单位: 浙江大学

    2-8

    下列排序方法中,若将顺序村吃更换为链式存储,则算法的时间效率会降低的是:(2分)

    1.插入排序;2.选择排序;3.起泡排序;4.希尔排序;5.堆排序

    1. 仅1、2
    2. 仅2、3
    3. 仅3、4
    4. 仅4、5

    作者: 考研试卷

    单位: 浙江大学

    2-9

    { 12,9,11,8,7,4,5,13,23 }是下列哪种方法第二趟排序后的结果? (2分)

    1. 归并排序
    2. 堆排序
    3. 插入排序
    4. 基数排序

    作者: DS课程组

    单位: 浙江大学

    2-10

    输入10​4​​个只有一位数字的整数,可以用O(N)复杂度将其排序的算法是:(1分)

    1. 桶排序
    2. 快速排序
    3. 插入排序
    4. 希尔排序

    作者: 陈越

    单位: 浙江大学

    2-11

    将序列{ 2, 12, 16, 88, 5, 10, 34 }排序。若前2趟排序的结果如下:

    • 第1趟排序后:2, 12, 16, 10, 5, 34, 88
    • 第2趟排序后:2, 5, 10, 12, 16, 34, 88

    则可能的排序算法是:(2分)

    1. 冒泡排序
    2. 快速排序
    3. 归并排序
    4. 插入排序

    作者: 陈越

    单位: 浙江大学

    2-12

    将序列{ 2, 12, 16, 88, 5, 10, 34 }排序。若前2趟排序的结果如下:

    • 第1趟排序后:2, 12, 16, 10, 5, 34, 88
    • 第2趟排序后:2, 5, 10, 12, 16, 34, 88

    则可能的排序算法是:(2分)

    1. 冒泡排序
    2. 归并排序
    3. 插入排序
    4. 快速排序

    作者: 陈越

    单位: 浙江大学

    2-13

    将序列{ 2, 12, 16, 88, 5, 10, 34 }排序。若前2趟排序的结果如下:

    • 第1趟排序后:2, 12, 16, 10, 5, 34, 88
    • 第2趟排序后:2, 5, 10, 12, 16, 34, 88

    则可能的排序算法是:(2分)

    1. 冒泡排序
    2. 归并排序
    3. 快速排序
    4. 插入排序

    作者: 陈越

    单位: 浙江大学

    2-14

    在对N个元素进行排序时,基于比较的算法中,其“最坏时间复杂度”中最好的是: (1分)

    1. O(logN)
    2. O(N)
    3. O(NlogN)
    4. O(N​2​​)

    作者: DS课程组

    单位: 浙江大学

    2-15

    下列排序算法中,哪种算法可能出现:在最后一趟开始之前,所有的元素都不在其最终的位置上?(设待排元素个数N>2) (2分)

    1. 冒泡排序
    2. 插入排序
    3. 堆排序
    4. 快速排序

    作者: DS课程组

    单位: 浙江大学

    2-16

    若数据元素序列{ 11,12,13,7,8,9,23,4,5 }是采用下列排序方法之一得到的第二趟排序后的结果,则该排序算法只能是: (2分)

    1. 冒泡排序
    2. 选择排序
    3. 插入排序
    4. 归并排序

    作者: DS课程组

    单位: 浙江大学

    2-17

    数据序列{ 3,2,4,9,8,11,6,20 }只能是下列哪种排序算法的两趟排序结果? (2分)

    1. 冒泡排序
    2. 选择排序
    3. 插入排序
    4. 快速排序

    作者: DS课程组

    单位: 浙江大学

    2-18

    对一组数据{ 2,12,16,88,5,10 }进行排序,若前三趟排序结果如下: 第一趟排序结果:2,12,16,5,10,88 第二趟排序结果:2,12,5,10,16,88 第三趟排序结果:2,5,10,12,16,88 则采用的排序方法可能是: (2分)

    1. 冒泡排序
    2. 希尔排序
    3. 归并排序
    4. 基数排序

    作者: DS课程组

    单位: 浙江大学

    2-19

    就排序算法所用的辅助空间而言,堆排序、快速排序、归并排序的关系是: (1分)

    1. 堆排序 < 归并排序 < 快速排序
    2. 堆排序 > 归并排序 > 快速排序
    3. 堆排序 < 快速排序 < 归并排序
    4. 堆排序 > 快速排序 > 归并排序

    作者: DS课程组

    单位: 浙江大学

    2-20

    下面四种排序算法中,稳定的算法是: (1分)

    1. 堆排序
    2. 希尔排序
    3. 归并排序
    4. 快速排序

    作者: DS课程组

    单位: 浙江大学

    2-21

    在基于比较的排序算法中,哪种算法的最坏情况下的时间复杂度不高于O(NlogN)? (1分)

    1. 冒泡排序
    2. 归并排序
    3. 希尔排序
    4. 快速排序

    作者: DS课程组

    单位: 浙江大学

    2-22

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

    1. 冒泡排序
    2. 直接选择排序
    3. 堆排序
    4. 快速排序

    作者: DS课程组

    单位: 浙江大学

    2-23

    输入10​5​​个只有一位数字的整数,可以用O(N)复杂度将其排序的算法是: (1分)

    1. 快速排序
    2. 插入排序
    3. 希尔排序
    4. 基数排序

    作者: DS课程组

    单位: 浙江大学

    2-24

    排序方法中,从未排序序列中依次取出元素与已排序序列中的元素进行比较,将其放入已排序序列的正确位置的方法称为: (1分)

    1. 插入排序
    2. 选择排序
    3. 快速排序
    4. 归并排序

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

    展开全文
  • 对N个记录进行归并排序归并趟数的数量级是O(NlogN)。() [解析]归并的数量级在O(logN)? 每上下相邻的两层之间,从上层到下层的过程就是一趟归并 满二叉树深度为k的二叉树的最后一层结点数为2^k - 1 所以叶子数为N...

    1-3
    对N个记录进行归并排序,归并趟数的数量级是O(NlogN)。()
    [解析]归并的数量级在O(logN)?
    每上下相邻的两层之间,从上层到下层的过程就是一趟归并
    满二叉树深度为k的二叉树的最后一层结点个数为2^k - 1
    所以叶子数为N的完全二叉树,它的深度为log2N
    归并的趟数就是O(logN)

     
    void Merge(SqList L, int low, int mid, int high, SqList &res_L)
    {
    	p_left = low;
    	p_right = mid + 1;
    	p_res = low;
    	while (p_left <= mid && p_righ <= high)
    	{
    		
    	}
    }
    
    //T是辅助空间,和原顺序表一样大
    void MergeSort(SqList L, int low, int high, SqList &T)
    {
    	if (low == high)
    		T.elem[low] = L.elem[low];
    	else
    	{
    		mid = (low + high) / 2;
    		MergeSort(L, low, mid, T);
    		MergeSort(L, mid + 1, high, T);
    		Merge(T, low, mid, high, L);
    	}	
    }
    

    1-2
    基数排序是稳定的算法。(T)
    [解析]若基数排序 用的是队列或者顺序表,所以 对相同的关键字
    在存储进基数对应的表里的顺序不发生改变,从这个表中取出时也不发生改变

    1-4
    To sort N records by merge sort,
    the number of merge runs is O(NlogN).(F)
    [解析]O(logN)

    1-5

    Mergesort is stable.(F)

    2-8
    对N个记录进行归并排序,归并趟数的数量级是(B)
    A.O(logN)
    B.O(N)
    C.O(NlogN)
    D.O(N​2​​)

    2-9
    对N个记录进行归并排序,空间复杂度为:(B)
    A.O(logN)
    B.O(N)
    C.O(NlogN)
    D.O(N​2​​)
    [解析]需要开辟与原数组相同大小的辅助空间

    2-10
    给出关键字序列{ 321,156,57,46,28,7,331,33,34,63 },
    下面哪个选择是按次位优先(LSD)链式基数排序进行了一趟分配和
    收集的结果?(B)
    A.→331→321→33→63→34→156→46→57→7→28
    B.→321→331→33→63→34→156→46→57→7→28
    C.→156→28→321→331→33→34→46→57→63→7
    D.→57→46→28→7→33→34→63→156→321→331
    [解析]根据最低位按照和原序列的相对位置排序
    321 331 33 63 34 156 46 57 7 28

    2-11
    对给定序列{ 110,119,7,911,114,120,122 }采用次位优先
    (LSD)的基数排序,则两趟收集后的结果为:©
    A.7, 110, 119, 114, 911, 120, 122
    B.7, 110, 119, 114, 911, 122, 120
    C.7, 110, 911, 114, 119, 120, 122
    D.110, 120, 911, 122, 114, 7, 119
    [解析]
    需要注意的是 7 的倒数第 2 位是 0, 也就是7 == 007
    7 110 911 114 119 120 122

    2-12
    给出关键字序列{ 431, 56, 57, 46, 28, 7, 331, 33, 24, 63 },
    下面哪个选择是按次位优先(LSD)链式基数排序进行了一趟分配和
    收集的结果?©
    A.→331→431→33→63→24→56→46→57→7→28
    B.→56→28→431→331→33→24→46→57→63→7
    C.→431→331→33→63→24→56→46→57→7→28
    D.→57→46→28→7→33→24→63→56→431→331
    [解析]431 331 33 63 24 56 46 57 7 28

    2-4
    输入10​5​​个只有一位数字的整数,可以用O(N)复杂度将其排序的算法是:
    A.快速排序
    B.插入排序
    C.希尔排序
    D.基数排序
    [解析]基数排序

    7-2 链式基数排序 (20分)

    实现链式基数排序,待排序关键字n满足1≤n≤1000,最大关键字数位≤5。
    输入样例:

    第一行输入待排序个数n(1≤n≤1000),再输入n个数(n的数位≤5)。

    10
    278 109 63 930 589 184 505 269 8 83

    输出样例:

    输出每趟分配-收集后链表中的关键字,趟数为序列中最大值的数位(如样例中930的数位为3),每行结尾有空格。

    930 63 83 184 505 278 8 109 589 269
    505 8 109 930 63 269 278 83 184 589
    8 63 83 109 184 269 278 505 589 930

    //凎!考完六级刚难受着,又得写链式基数排序
    //没写完,不写了,不会
    #include <iostream>
    #include <cstdlib>
    #include <malloc.h>
    using namespace std;
    typedef int ElemType;
    typedef struct LNode
    {
    	ElemType data;
    	struct LNode *Next;
    }LNode, *LinkList;
    
    typedef struct 
    {
    	LinkList L;
    }Bucket;
    
    void CreatList(LinkList L, int len)
    {
    	L = (LNode*)malloc(sizeof(LNode));
    	if (L == NULL) exit(OVERFLOW);
    	L->Next = NULL;
    	LNode *p = L;
    	while (len--)
    	{
    		LNode *tempNode = (LNode*)malloc(sizeof(LNode));
    		if (tempNode == NULL) exit(OVERFLOW);
    		cin >> tempNode->data;
    		tempNode->Next = NULL;
    		p->Next = tempNode;
    		p = tempNode;
    	}
    }
    
    void InsertToList(LinkList &L, ElemType e)
    {
    	LNode *p = L;
    	while (p->Next != NULL)
    	{
    		p = p->Next;
    	}
    	LNode *temp_Node = (LNode*)malloc(sizeof(LNode));
    	temp_Node->data = e;
    	temp_Node->Next = NULL;
    	p->Next = temp_Node;
    }
    void Add(LinkList &LwithHead, LinkList &L)
    {
    	LNode *p = LwithHead;
    	while (p->Next != NULL)
    		p = p->Next;
    	p->Next = L;
    	L = NULL;
    }
    ElemType GetElemAt(LinkList list, int i)
    {
    	ElemType e;
    	LNode *p = list->Next;
    	while (i-- && p != NULL)
    		p = p->Next;
    	e = p->data;
    	return e;
    }
    void GetRoundCount(LinkList list)
    {
    	//不想邪了
    	return 10;
    }
    int GetRadixNumber(ElemType e, int k)
    {
    	while (k--)
    		e /= 10;
    	return e % 10;
    }
    
    void EnBucket(Bucket &bucket, ElemType e)
    {
    	InsertToList(bucket.L, e);
    }
    void Distribute(LinkList &list, int len, Bucket *bucket, int k)
    {
    	for (int i = 1; i <= len; i++)
    	{
    		int radix = GetRadixNumber(GetElemAt(list, i), k);
    		EnBucket(bucket[radix], GetElemAt(list, i));
    	}
    }
    
    void Collect(Bucket *bucket, LinkList &list)
    {
    	int j = 1;
    	for (int i = 0; i < 10; i++)
    	{
    		Add(list, bucket[i].L);
    	}
    }
    
    void RadixSort(LinkList &list)
    {
    	Bucket Bucket[10];
    	for (int i = 0; i < 10; i++)
    		Bucket[i].L = NULL;
    	int max_num_len = GetRoundCount(list);
    
    }
    int main()
    {
    	int len;
    	LinkList list;
    	Bucket bucket[10];
    	cin >> len;
    	CreatList(list, len);
    	
    	return 0;
    }
    
    展开全文
  • Round22—归并与基数排序

    千次阅读 2020-02-20 18:54:47
    1-1对N个记录进行归并排序归并趟数的数量级是O(NlogN)(F) 单选题 2-1对N个记录进行归并排序归并趟数的数量级是:(1分) O(logN) O(N) O(NlogN) O(N​2​​) 2-2对N个记录进行归并排序,空间复杂度为:(1...

    判断题

    1-1对N个记录进行归并排序,归并趟数的数量级是O(NlogN)(F)

    单选题

    2-1对N个记录进行归并排序,归并趟数的数量级是: (1分)

    • O(logN)
    • O(N)
    • O(NlogN)
    • O(N​2​​)

    2-2对N个记录进行归并排序,空间复杂度为: (1分)

    • O(logN)
    • O(N)
    • O(NlogN)
    • O(N​2​​)

    2-3给出关键字序列{ 431, 56, 57, 46, 28, 7, 331, 33, 24, 63 },下面哪个选择是按次位优先(LSD)链式基数排序进行了一趟分配和收集的结果? (2分)

    • →331→431→33→63→24→56→46→57→7→28
    • →56→28→431→331→33→24→46→57→63→7
    • →431→331→33→63→24→56→46→57→7→28
    • →57→46→28→7→33→24→63→56→431→331

    2-4输入10​5​​个只有一位数字的整数,可以用O(N)复杂度将其排序的算法是:(1分)

    • 快速排序
    • 插入排序
    • 桶排序
    • 希尔排序

    2-5数据序列{ 3, 1, 4, 11, 9, 16, 7, 28 }只能是下列哪种排序算法的两趟排序结果?(2分)

    • 冒泡排序
    • 快速排序
    • 插入排序
    • 堆排序

    2-6对10TB的数据文件进行排序,应使用的方法是:(1分)

    • 希尔排序
    • 堆排序
    • 归并排序
    • 快速排序

    2-7在内部排序时,若选择了归并排序而没有选择插入排序,则可能的理由是:(2分)

    1. 归并排序的程序代码更短
    2. 归并排序占用的空间更少
    3. 归并排序的运行效率更高
    • 仅 2
    • 仅 3
    • 仅 1、2
    • 仅 1、3

    2-8下列排序方法中,若将顺序村吃更换为链式存储,则算法的时间效率会降低的是:(2分)

    1.插入排序;2.选择排序;3.起泡排序;4.希尔排序;5.堆排序

    • 仅1、2
    • 仅2、3
    • 仅3、4
    • 仅4、5

    2-9{ 12,9,11,8,7,4,5,13,23 }是下列哪种方法第二趟排序后的结果? (2分)

    • 归并排序
    • 堆排序
    • 插入排序
    • 基数排序

    2-10输入10​4​​个只有一位数字的整数,可以用O(N)复杂度将其排序的算法是:(1分)

    • 桶排序
    • 快速排序
    • 插入排序
    • 希尔排序
    • 作者: 陈越

    2-11将序列{ 2, 12, 16, 88, 5, 10, 34 }排序。若前2趟排序的结果如下:

    • 第1趟排序后:2, 12, 16, 10, 5, 34, 88
    • 第2趟排序后:2, 5, 10, 12, 16, 34, 88

    则可能的排序算法是:(2分)

    • 冒泡排序
    • 快速排序
    • 归并排序
    • 插入排序

    2-12将序列{ 2, 12, 16, 88, 5, 10, 34 }排序。若前2趟排序的结果如下:

    • 第1趟排序后:2, 12, 16, 10, 5, 34, 88
    • 第2趟排序后:2, 5, 10, 12, 16, 34, 88

    则可能的排序算法是:(2分)

    • 冒泡排序
    • 归并排序
    • 插入排序
    • 快速排序

    2-13将序列{ 2, 12, 16, 88, 5, 10, 34 }排序。若前2趟排序的结果如下:

    • 第1趟排序后:2, 12, 16, 10, 5, 34, 88
    • 第2趟排序后:2, 5, 10, 12, 16, 34, 88

    则可能的排序算法是:(2分)

    • 冒泡排序
    • 归并排序
    • 快速排序
    • 插入排序

    2-14在对N个元素进行排序时,基于比较的算法中,其“最坏时间复杂度”中最好的是: (1分)

    • O(logN)
    • O(N)
    • O(NlogN)
    • O(N​2​​)

    2-15下列排序算法中,哪种算法可能出现:在最后一趟开始之前,所有的元素都不在其最终的位置上?(设待排元素个数N>2) (2分)

    • 冒泡排序
    • 插入排序
    • 堆排序
    • 快速排序

    2-16若数据元素序列{ 11,12,13,7,8,9,23,4,5 }是采用下列排序方法之一得到的第二趟排序后的结果,则该排序算法只能是: (2分)

    • 冒泡排序
    • 选择排序
    • 插入排序
    • 归并排序

    2-17数据序列{ 3,2,4,9,8,11,6,20 }只能是下列哪种排序算法的两趟排序结果? (2分)

    • 冒泡排序
    • 选择排序
    • 插入排序
    • 快速排序

    2-18对一组数据{ 2,12,16,88,5,10 }进行排序,若前三趟排序结果如下: 第一趟排序结果:2,12,16,5,10,88 第二趟排序结果:2,12,5,10,16,88 第三趟排序结果:2,5,10,12,16,88 则采用的排序方法可能是: (2分)

    • 冒泡排序
    • 希尔排序
    • 归并排序
    • 基数排序

    2-19就排序算法所用的辅助空间而言,堆排序、快速排序、归并排序的关系是: (1分)

    • 堆排序 < 归并排序 < 快速排序
    • 堆排序 > 归并排序 > 快速排序
    • 堆排序 < 快速排序 < 归并排序
    • 堆排序 > 快速排序 > 归并排序

    2-20下面四种排序算法中,稳定的算法是: (1分)

    • 堆排序
    • 希尔排序
    • 归并排序
    • 快速排序

    2-21在基于比较的排序算法中,哪种算法的最坏情况下的时间复杂度不高于O(NlogN)? (1分)

    • 冒泡排序
    • 归并排序
    • 希尔排序
    • 快速排序

    2-22下列排序算法中,时间复杂度不受数据初始状态影响,恒为O(NlogN)的是: (1分)

    • 冒泡排序
    • 直接选择排序
    • 堆排序
    • 快速排序

    2-23输入10​5​​个只有一位数字的整数,可以用O(N)复杂度将其排序的算法是: (1分)

    • 快速排序
    • 插入排序
    • 希尔排序
    • 基数排序

    2-24排序方法中,从未排序序列中依次取出元素与已排序序列中的元素进行比较,将其放入已排序序列的正确位置的方法称为: (1分)

    • 插入排序
    • 选择排序
    • 快速排序
    • 归并排序

    编程题

    7-1 排序 (25分)

    给定N个(长整型范围内的)整数,要求输出从小到大排序后的结果。

    本题旨在测试各种不同的排序算法在各种数据情况下的表现。各组测试数据特点如下:

    • 数据1:只有1个元素;
    • 数据2:11个不相同的整数,测试基本正确性;
    • 数据3:103个随机整数;
    • 数据4:104个随机整数;
    • 数据5:105个随机整数;
    • 数据6:105个顺序整数;
    • 数据7:105个逆序整数;
    • 数据8:105个基本有序的整数;
    • 数据9:105个随机正整数,每个数字不超过1000。

       

      输入格式:

      输入第一行给出正整数N(≤10​5​​),随后一行给出N个(长整型范围内的)整数,其间以空格分隔。

      输出格式:

      在一行中输出从小到大排序后的结果,数字间以1个空格分隔,行末不得有多余空格。

      输入样例:

      11
      4 981 10 -17 0 -20 29 50 8 43 -5
      

      输出样例:

      -20 -17 -5 0 4 8 10 29 43 50 981

         AC代码:

    #include <stdio.h>
    
    #define maxn 100010
    
    int a[maxn], b[maxn];
    int n;
    
    void merge_sort(int l, int r)
    {
        if(l >= r)
            return ;
        int mid = (l + r) >> 1;
        merge_sort(l, mid);
        merge_sort(mid + 1, r);
    
        int x;
        for(x = l; x <= r; x++)
            b[x] = a[x];
    
        int i = l, cnt = l, j = mid + 1;
        while(i <= mid && j <= r)
        {
            if(b[i] > b[j])
                a[cnt++] = b[j++];
            else
                a[cnt++] = b[i++];
        }
    
        while(i <= mid)
            a[cnt++] = b[i++];
    
        while(j <= r)
            a[cnt++] = b[j++];
    }
    
    int main()
    {
        int i, j;
        scanf("%d", &n);
        for(i = 0; i < n; i++)
            scanf("%d", a +i);
    
        merge_sort(0, n - 1);
    
        for(int i = 0; i < n; i++)
            printf("%d%c", a[i], i == n - 1 ? '\n' : ' ');
        return 0;
    }
    

     

    展开全文
  • PTA排序易错题

    千次阅读 2021-06-13 13:47:46
    对N个记录进行归并排序归并趟数的数量级是O(NlogN)。 A. B.错 原因:归并趟数为log2n 对N个记录进行简单选择排序,比较次数和移动次数分别为O(N​2)和O(N) A. B.错 原因:简单排序遍历并比较最大的(或最小的...
  • 对N个记录进行归并排序归并趟数的数量级是O(NlogN)F 应为O(logN) 选择题 2-1 对N个记录进行归并排序归并趟数的数量级是: A A.O(logN) B.O(N) C.O(NlogN) D.O(N​2) 2-2 对N个记录进行归并排序,空间复杂度为...
  • 排序算法-归并排序

    千次阅读 2021-12-30 14:53:40
    假定待排序表中含有n个记录,则可以看成是n个有序的子表,每子表的长度为1,然后两两归并,得到⌈n/2⌉\lceil n/2 \rceil⌈n/2⌉长度为2或1的有序表;再两两归并,如此一直重复,直到合并成一长度为n的有序表...
  • 排序 2021-1-20

    2021-01-20 21:41:21
    对N个记录进行归并排序归并趟数的数量级是O(NlogN)。 F 1-3 对N个记录进行排序,需要的额外空间为O(N)。 F 1-4 对N个记录进行简单选择排序,比较次数和移动次数分别为O(N^​2​​ )和O(N)。 T 1-5 对N个...
  • 归并排序

    2020-02-08 20:35:57
    归并排序算法的思想: 假设初始序列含 n 个记录,则可看成是 n 有序的子序列,每子序列的长度为1,然后两两归并,...当有 n 个记录时,需进行log2^n归并排序,每一趟归并,其关键字比较次数不超过 n ,元素移...
  • 对N个记录进行简单选择排序,比较次数和移动次数分别为O(N2)和O(N)。 T 1-3 对N个记录进行快速排序,在最坏的情况下,其时间复杂度是O(NlogN) F 1-4 希尔排序是稳定的算法。 F 1-5 对N个不同的数据采用冒泡排序进行...
  • 归并排序-nlogn

    2016-03-15 19:41:07
    void mergeArray(int a[], int first, int mid, int last, int temp[]) //有序数列合并 { int i = first; int j = mid + 1; int m = mid; int n = last; int k = 0; //每次把两数列中较小的值存在temp...
  • 所谓的归并,是将两或两以上的有序文件合并成为一新的有序文件,归并排序是把一n个记录的无序文件看成是由n个长度为1的有序子文件组成的文件,然后进行两两归并,如此重复,直至最后形成包含n个归并,得到...
  • 1.对N个记录进行归并排序归并趟数的数量级是: 选项 A O(logN) B O(N) C O(NlogN) D O(N2) 2.对N个记录进行归并排序,空间复杂度为: 选项 A O(logN) B O(N) C O(NlogN) D O(N2)...
  • 归并排序(Merge Sort)是一种基于分治法的高速算法。
  • 一、什么是排序算法1.1、排序定义一序列对象根据某个关键字进行排序。1.2、排序术语稳定:如果a原本在b前面,而a=b,排序之后a仍然在b的前面;不稳定:如果a原本在b的前面,而a=b,排序之后a可能会出现在b的后面;...
  • 目录1.归并排序2.逆序3.例题 1.归并排序 (1)....归并排序是建立在归并操作上的一种... 速度快,同时归并排序是稳定的排序,即相等的元素的顺序不会改变,如输人记录1(1) 3(2) 2(3) 2(4)5(5) (括号中是记录的关键字)时输出
  •  //归并方法:把两有序子序列合并成一有序序列  public void merge(int[]a, int[]b,int left, int mid, int right){  //该方法的具体功能:把左子序列a[left:mid] 和 右子序列a[mid+1:right] 归并到 b[left:...
  • 归并排序之求逆序

    万次阅读 多人点赞 2018-07-26 11:45:54
    何谓归并排序,先看下面一例子: 设有数列{6,202,100,301,38,8,1} 初始状态:6,202,100,301,38,8,1 第一次归并后:{6,202},{100,301},{8,38},{1}; 第二次归并后:{6,100,202,301},{1,8,38}; 第三次...
  • 归并排序(合并排序

    千次阅读 2016-03-27 21:52:42
    合并排序(MERGE SORT)是又一类不同的排序方法,合并的含义就是将两或两以上的有序数据序列合并成一新的有序数据序列,因此它又叫归并算法。它的基本思想就是假设数组A有N个元素,那么可以看成数组A是又N个...
  • python 归并排序(详解)

    2021-12-22 15:23:57
    一、归并排序 归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法采用经典的分治(divide-and-conquer)策略(分治法将问题分(divide)...将待排序序列R[0…n-1]看成是n个长度为1的有序序列,将相邻
  • 逆序之冒泡和归并排序

    千次阅读 2021-12-13 14:04:31
    逆序是一种常见的需求,比如行列式降阶法中确定正负号时需要逆序的个数。
  • 数据结构(26)--排序篇之归并排序

    千次阅读 2016-03-08 20:34:27
    参考书籍:数据结构(C语言版)严蔚敏吴伟民编著清华大学出版社 ... 1 2-路归并排序 归并就是将两或两以上的有序数据序列合并成一有序... 假设初始序列含有 n个记录,则可看成是 n个有序的子序列;每子序...
  • 归并排序(详情讲解)

    2022-05-19 16:45:52
    归并排序分类:二路归并排序 ,多路归并排序(详情讲解)
  • 假设初始序列有n个记录,则可看成是n个有序的子序列,每序列长度为1,然后两两归并,得到长度为2或者是1的有序子序列;再两两归并,,,,如此重复,直到得到一长度为n的有序序列为止,这种排序方法称为2-路...
  • 归并排序算法

    千次阅读 2021-01-12 10:17:42
    文章目录一、归并排序介绍二、归并排序的思想2.1 归并排序的基本思想2.2 归并的基本步骤三、归并排序的代码实现 一、归并排序介绍 归并排序(merge sorting)是利用归并的思想实现的排序方法,该算法采用经典的分治...
  • 二路归并排序 子序列长度从1到n/2(把数组划分为2个子序列) 从左往右一次比较2个子序列 非递归实现 子序列长度,h从1开始到?,作2倍变化2h 子序列数,根据剩余子序列的个数执行相应的操作(剩余子序列数大于2...
  • 1. 冒泡排序Bubble sort 冒泡排序的算法思路在于无序表进行多...第2趟比较交换时,最大项已经就位,需要排序的数据减少为n-1,共有n-2相邻数据进行比较 第3趟比较 n-3 数据 第n-1趟比较1数据 直到第n-1趟完成后
  • 目录排序算法一、概念二、插入排序1、直接插入排序2、希尔排序三、交换排序1、冒泡排序2、快速排序四、选择排序1、简单选择排序五、归并排序1、2-路归并排序六、各种排序方法的比较1、性能比较2、选择排序的方法 ...
  • 非递归算法——快速排序归并排序

    千次阅读 多人点赞 2022-07-12 16:16:10
    ​哈喽大家好,我是保护小周ღ,本期为大家带来的是常见排序算法中的快速排序归并排序非递归算法,分享所有源代码,粘贴即可运行,保姆级讲述,包您一看就会,快来试试吧~ ​
  • 1) 排序 n 元素,元素为随机生成的长为1..32的字符串(字符串均为英文小写字母),n的取值为:2^2,2^5,2^8,2^11,2^14,2^17; 2) 算法:直接插入排序,堆排序归并排序,快速排序; 3) 字符串大小判断标准...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 145,987
精华内容 58,394
热门标签
关键字:

对n个记录进行归并排序