数据结构（海南联盟）第九章测试_智慧树知到答案2021年

第九章 排序：本章主要围绕数据结构中的数据运算：排序运算展开讲解。本章涉及的内容包括排序的相关概念；插入类排序；快速排序；选择类排序；归并排序；基数排序。插入类排序里面包含直接插入排序；折半插入排序；表插入排序；希尔排序。快速排序包含起泡排序；快速排序；选择排序包含简单选择排序；树形选择排序和堆排序。基数排序包含多关键字排序和链式基数排序。9.1导读:本节为排序的导读
9.2排序的相关概念:本节主要介绍一下概念：排序、内部排序、外部排序、内部排序的分类、排序方法的稳定性、排序方法的不稳定性、排序的存储结构、排序算法的效率分析。
9.3直接插入排序:本节介绍直接插入排序的算法思想、算法实现以及分析算法的性能。在讲解过程中，给出算法演示进一步理解算法思想。
9.4折半插入排序:本节介绍折半插入排序的算法思想、算法实现以及分析算法的性能。在讲解过程中，给出算法演示进一步理解算法思想。
9.5表插入排序:本节介绍表插入排序的算法思想、算法的存储结构。在讲解过程中，给出算法演示进一步理解算法思想。
9.6希尔排序:本节介绍希尔排序的算法思想、算法实现以及算法性能。在讲解过程中，给出算法演示进一步理解算法思想。
9.7起泡排序:本节介绍起泡排序的算法思想、算法实现以及算法性能。在讲解过程中，给出算法演示进一步理解算法思想。
9.8快速排序:本节介绍快速排序的算法思想、算法实现以及算法性能。在讲解过程中，给出算法演示进一步理解算法思想。
9.9简单选择排序:本节介绍简单选择排序的算法思想、算法实现以及算法性能。在讲解过程中，给出算法演示进一步理解算法思想。
9.10树形选择排序:本节介绍树形选择排序的算法思想。在讲解过程中，给出算法演示进一步理解算法思想。
9.11堆排序:本节介绍堆的定义、堆排序的基本思想、如何将无序序列建成堆、堆的重新调整，已经堆排序算法的性能分析。
9.12归并排序:本节主要介绍归并排序的算法思想已经算法性能分析，结合实例进行算法演示，进一步理解算法思想。
9.13基数排序:本节主要介绍基数排序算法思想，两种基数排序算法：多关键字排序和链式基数排序，以及基数排序的算法性能分析。
9.14内部排序方法的比较排序:本节从各类排序算法的时间复杂度、空间复杂度、算法的稳定性方面进行比较。

[单选题]从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置上的方法，这种排序方法称为（   ）。
选择排序
归并排序
插入排序
冒泡排序
答案：插入排序
[单选题]从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为（   ）。
选择排序
冒泡排序
归并排序
插入排序[单选题]对n个关键字作快速排序，在最坏情况下，算法的时间复杂度是（   ）。
O(n)
O(n2)
O(n3)
O(nlog2n)[单选题]下列关键字序列中，（   ）是堆。
16，72，31，23，94，53
16，23，53，31，94，72
16，53，23，94，31，72
94，23，31，72，16，53[单选题]下述几种排序方法中，（   ）是稳定的排序方法。
快速排序
堆排序
希尔排序
归并排序[单选题]在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是（    ）。
希尔排序
选择排序
起泡排序
插入排序[单选题]在待排序的元素序列基本有序的前提下，效率最高的排序方法是（     ）。
选择排序
插入排序
归并排序
快速排序[单选题]在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置至少需比较（    ）次。
6
4
3
5[单选题]大多数排序算法都有两个基本的操作：（    ）和（    ）。
插入和比较
移动和删除
插入和删除
比较和移动[单选题]对ｎ个不同的排序码进行冒泡排序，在元素无序的情况下比较的次数为（    ）。
n(n-1)/2
 n
n-1
n+1[单选题]下列关于堆的描述不正确的是（    ）。
堆的形状是一棵完全二叉树
堆是利用完全二叉树中双亲结点和孩子结点之间的内在关系，在当前无序的序列中选择关键字最大的或最小的记录
堆是一种插入排序
堆是一种选择排序[单选题]若对n个记录的集合进行冒泡排序，在最坏的情况下所需要的时间是（    ）。
O(nlog2n)
O(n3)
O(n2) 
O(n)[单选题]假设要将序列（Q, H, C, Y, P, A, M, S, R, D, F, X）中的关键码按字母序的升序重新排列，则初始步长为4的希尔（shell）排序一趟的结果是（     ）。
H C Q P A M S R D F X Y
P A C S Q H F X R D M Y
F H C D P A M Q R S Y X
A D C R F Q M S Y P H X[单选题]用某种排序方法对线性表（25, 84, 21, 47, 15, 27, 68, 35, 20）进行排列时，元素序列的变化情况如下：(1) 25, 84, 21, 47, 15, 27, 68, 35, 20(2) 20, 15, 21,25, 47, 27, 68, 35, 84(3) 15, 20, 21, 25, 35, 27, 47, 68,84(4) 15, 20, 21, 25, 27, 35, 47, 68, 84则所有的排序方法是（     ）。
快速排序
选择排序
归并排序
插入排序[单选题]有一组记录的排序码为（25, 48, 16, 35, 79, 82, 23, 40, 36, 72），其中含有5个长度为2的有序表，按归并排序的方法对该序列进行一趟归并的结果是（     ）。
16 25 35 48 79 23 36 40 72 82
16 25 35 48 23 40 79 82 36 72
16 25 48 35 79 82 23 36 40 72
16 25 35 48 79 82 23 36 40 72