8.4.3
01.在以下排序算法中，每次从未排序的记录中选取最小关键字的记录，加入已排序记录的
末尾，该排序算法是( ).
A.简单选择排序
B.冒泡排序
C.堆排序
D.直接插入排序
02．简单选择排序算法的比较次数和移动次数分别为()。
A.O(n)，O(log2n)
B.O(log2n),O(n^2)
C.O(n^2)，O(n)
D.O(nlog2n)，O(n)
03.若只想得到100000个元素组成的序列中第10个最小元素之前的部分排序的序列,用()方法最快。
A.冒泡排序
B.快速排序
C.归并排序
D.堆排序
04.下列()是一个堆。
A.19,75,34,26,97,56
B.97,26,34,75,19,56
C. 19,56, 26,97,34,75
D.19,34,26,97,56,75
05．在含有n个关键字的小根堆中，关键字最大的记录有可能存储在（)位置。
A. n/2
B.n/2 +2
C. 1
D. n/2-1
06．向具有n个结点的堆中插入一个新元素的时间复杂度为()，删除一个元素的时间复杂度为（).
A.O(1)
B.O(n)
C.O(log2n)
D.O(nlog2n)
07．构建n个记录的初始堆，其时间复杂度为();对n个记录进行堆排序，最坏情况下其
时间复杂度为().
A.O(n)
B.O(n^2)
C.O(log2n)
D.O(nlog2n)
08.下列4种排序算法中，排序过程中的比较次数与序列初始状态无关的是( )。
A.简单选择排序
B.直接插入排序
C.快速排序
D.冒泡排序
09．对由相同的n个整数构成的二叉排序树和小根堆，下列说法中不正确的是（).
A.二叉排序树的高度大于或等于小根堆的高度
B.对二叉排序树进行中序遍历可以得到从小到大的序列
C.从小根堆的根结点到任意叶结点的路径构成从小到大的序列
D.对小根堆进行层序遍历可以得到从小到大的序列
10.有一组数据(15,9,7,8,20,-1,7,4)，用堆排序的筛选方法建立的初始小根堆为()。
A. -1,4,8,9,20,7,15,7
B.-1,7,15,7,4,8,20,9
C. -1,4,7,8,20,15,7,9
D.A、B、C均不对
11.对关键字序列{23,17,72,60,25,8,68,71,52}进行堆排序，输出两个最小关键字后的剩
余堆是()。
A.{23,72,60,25,68,71,52}
B.{23,25,52,60,71,72,68}
C.{71,25,23,52,60,72,68}
D.{23,25,68,52,60,72,71}
12．堆排序分为两个阶段:第一阶段将给定的序列构造成一个初始堆，第二阶段逐次输出堆顶元素，并调整使其保持堆的性质。设有给定序列{48,62,35,77,55,14,35,98}，若在堆排序的第一阶段将该序列构造成一个大根堆，则交换元素的次数为().
A.5
B.6
C.7
D.8
13.已知大根堆{62,34,53,12,8,46,22},删除堆顶元素后需要重新调整堆，则在此过程中关键字的比较次数为（).
A.2
B.3
C.4
D.5
14.哪种数据结构从根结点到任意叶结点的路径都是有序的（).
A．红黑树 B.二叉查找树 C.哈夫曼树 D.堆
15.【2009统考真题】已知关键字序列{5,8,12,19,28,20,15,22}是小根堆，插入关键字3，调整好后得到的小根堆是().
A.3,5,12,8,28,20,15,22,19
B.3,5,12,19,20,15, 22,8,28
C.3,8,12,5,20,15, 22, 28,19
D.3,12,5,8,28,20,15,22,19
16.【2011统考真题】已知序列{25,13,10,12,9}是大根堆，在序列尾部插入新元素18，再将其调整为大根堆，调整过程中元素之间进行的比较次数是( ).
A.1
B.2
C.4
D.5
17.【2015统考真题】已知小根堆为8,15,10,21,34,16,12，删除关键字8之后需重建堆，在此过程中，关键字之间的比较次数是().
A.1
B.2
C.3
D.4
18.【2018统考真题】在将序列(6,1,5,9,8,4,7)建成大根堆时，正确的序列变化过程是()。
A. 6,1,7,9,8,4,5→6,9,7,1,8,4,5→9,6,7,1,8,4,5→9,8,7,1,6,4,5
B.6,9,5,1,8,4,7→6,9,7,1,8,4,5→9,6,7,1,8,4,5-9,8,7,1,6,4,5
C. 6,9,5,1,8,4,7→9,6,5,1,8,4,7→9,6,7,1,8,4,5-9,8,7,1,6,4,5
D.6,1,7,9,8,4,5一7,1,6,9,8,4,5一7,9,6,1,8,4,5→9,7,6,1,8,4,5→9,8,6,1,7,4,5
19.【2020统考真题】下列关于大根堆（至少含2个元素）的叙述中，正确的是().
Ⅰ可以将堆视为一棵完全二叉树
Ⅱ.可以采用顺序存储方式保存堆
Ⅲ.可以将堆视为一棵二叉排序树
IV．堆中的次大值一定在根的下一层
A．仅Ⅰ、Ⅱ B.仅Ⅱ、Ⅲ C.仅Ⅰ、Ⅱ和IV D.Ⅰ、Ⅲ和IV
20.【2021统考真题】将关键字6,9,1,5,8,4,7依次插入初始为空的大根堆H,得到的H是( )。
A. 9,8,7,6,5,4,1
B. 9,8,7,5,6,1,4
C. 9,8,7,5,6,4,1
D. 9,6,7,5,8,4,1
8.5
01．以下排序算法中，( )在一趟结束后不一定能选出一个元素放在其最终位置上。
A.简单选择排序
B.冒泡排序
C.归并排序
D.堆排序
02.以下排序算法中，()不需要进行关键字的比较。
A.快速排序
B.归并排序
C.基数排序
D.堆排序
03.在下列排序算法中，平均情况下空间复杂度为O(n)的是()，最坏情况下空间复杂度为O(n)的是()。
Ⅰ希尔排序 Ⅱ.堆排序 Ⅲ.冒泡排序
IV.归并排序 V.快速排序 VI.基数排序
A. I、IV、VI
B.Ⅱ、Ⅴ
C. IV、 Ⅴ
D.IV
04．下列排序算法中，排序过程中比较次数的数量级与序列初始状态无关的是（).
A.归并排序
B.插入排序
C.快速排序
D.冒泡排序
05.二路归并排序中，归并趟数的数量级是()。
A. O(n)
B. O(log2n)
C. O(nlog2n)
D. O(n^2)
06．若对27个元素只进行三趟多路归并排序，则选取的归并路数最少为().
A.2
B.3
C.4
D.5
07．将两个各有N个元素的有序表合并成一个有序表，最少的比较次数是()，最多的比较次数是( ).
A.N
B.2N-1
C.2N
D.N-1
08.用归并排序算法对序列{1,2,6,4,5,3,8,7}进行排序，共需要进行()次比较。
A.12
B.13
C.14
D.15
09.一组经过第一趟二路归并排序后的记录的关键字为{25,50,15,35,80，85,20,40,36,70}，其中包含5个长度为2的有序表，用二路归并排序算法对该序列进行第二趟归并后的结果为()。
A. 15,25,35,50,80,20,85,40,70,36
B. 15,25,35,50,20,40,80,85,36,70
C. 15,25,50,35,80,85,20,36,40,70
D. 15,25,35,50,80,20,36,40,70,85
10．若将中国人按照生日（不考虑年份，只考虑月、日)来排序，则使用下列排序算法时，最快的是( )。
A.归并排序
B.希尔排序
C.快速排序
D.基数排序
11.设线性表中每个元素有两个数据项k1和k2，现对线性表按以下规则进行排序:先看数据项k1，k1值小的元素在前，大的元素在后;在k1值相同的情况下，再看k2，k2值小的元素在前，大的元素在后。满足这种要求的排序算法是()。
A.先按k1进行直接插入排序，再按k2进行简单选择排序
B.先按k2进行直接插入排序，再按k1进行简单选择排序
C.先按k1进行简单选择排序，再按k2进行直接插入排序
D.先按k2进行简单选择排序，再按k1进行直接插入排序
12.对{05,46,13,55,94,17,42}进行基数排序，一趟排序的结果是()
A. 05,46,13,55,94,17,42
B. 05,13,17,42,46,55,94
C. 42,13,94,05,55,46,17
D. 05,13,46,55,17,42,94
13.有n个十进制整数进行基数排序，其中最大的整数为5位，则基数排序过程中临时建立的队列个数是().
A. n
B.2
C. 5
D.10
14.下列各种排序算法中，(）需要的附加存储空间最大。
A.快速排序
B.堆排序
C.归并排序
D.插入排序
15.【2013统考真题】已知两个长度分别为m和n的升序链表，若将它们合并为长度为m+n的一个降序链表，则最坏情况下的时间复杂度是()。
A. O(n)
B. O(mn)
C. O(min(m, n))
D. O(max(m, n))
16.【2013统考真题】对给定的关键字序列110,119,007,911,114,120,122进行基数排序，第二趟分配、收集后得到的关键字序列是().
A. 007,110,119,114,911,120,122
B. 007,110,119,114,911,122,120
C. 007,110,911,114,119,120,122
D. 110,120,911,122,114,007,119
17.【2015统考真题】下列排序算法中，元素的移动次数与关键字的初始状态无关的是().
A.直接插入排序
B.冒泡排序
C.基数排序
D.快速排序
18.【2021统考真题】设数组S[]={93,946,372,9,146,151,301,485,236,327,43,892}，采用最低位优先(LSD)基数排序将S排列成升序序列。第一趟分配、收集后，元素372之前、之后紧邻的元素分别是().
A. 43,892
B. 236,301
C. 301,892
D. 485,301
19.【2022统考真题】使用二路归并排序对含n个元素的数组M进行排序时，二路归并排序
的功能是()。
A.将两个有序表合并为一个新的有序表
B.将M划分为两部分，两部分的元素个数大致相等
C.将M划分为n个部分，每个部分中仅含有一个元素
D.将M划分为两部分，一部分元素的值均小于另一部分元素的值
8.6
01．若要求排序是稳定的，且关键字为实数，则在下列排序算法中应选( ).
A.直接插入排序
B.选择排序
C.基数排序
D.快速排序
02.以下排序算法中时间复杂度为O(nlog2n)且稳定的是()。
A.堆排序
B.快速排序
C.归并排序
D.直接插入排序
03．设被排序的结点序列共有n个结点，在该序列中的结点已十分接近有序的情况下，用直
接插入排序、归并排序和快速排序对其进行排序，这些算法的时间复杂度应为()。
A.O(n),O(n), O(n)
B. O(n),O(nlog2n), O(nlog2n)
C. O(n), O(nlog2n), O(n^2)
D. O(n^2), O(nlog2n), O(n^2)
04.下列排序算法中属于稳定排序的是（①)，平均时间复杂度为O(nlog,n)的是(②)，在最
好的情况下，时间复杂度可以达到线性时间的有(③)。(注:多选题)
Ⅰ冒泡排序 Ⅱ.堆排序 Ⅲ.选择排序 IV.直接插入排序
V．希尔排序 VI.归并排序 VII.快速排序
05．就排序算法所用的辅助空间而言，堆排序、快速排序和归并排序的关系是().
A．堆排序<快速排序<归并排序
B．堆排序<归并排序<快速排序
C．堆排序>归并排序>快速排序
D．堆排序>快速排序>归并排序
06.．排序趟数与序列的原始状态无关的排序算法是()。
Ⅰ.直接插入排序 Ⅱ．简单选择排序 Ⅲ．冒泡排序 IV．基数排序
A. Ⅰ、Ⅲ B.Ⅰ、Ⅱ、IV C. Ⅰ、Ⅱ、Ⅲ D. Ⅰ、IV
07．对n个元素进行排序，其排序趟数肯定为n-1趟的排序算法是()。
A.直接插入排序和快速排序
B.冒泡排序和快速排序
C.简单选择排序和直接插入排序
D.简单选择排序和冒泡排序
08．若序列的原始状态为{1,2,3,4,5,10, 6,7,8,9}，要想使得排序过程中的元素比较次数最
少，则应该采用()方法。
A.插入排序
B.选择排序
C.希尔排序
D.冒泡排序
09.一般情况下，以下查找效率最低的数据结构是()。
A.有序顺序表
B.二叉排序树
C.堆
D.平衡二叉树
10．排序趟数与序列的原始状态有关的排序算法是(）排序算法。
A．插入
B.选择
C.冒泡
D.基数
11．对于同等大小的不同初始序列，总比较次数一定的是().
A．折半插入排序和简单选择排序
B．基数排序和归并排序
C．冒泡排序和快速排序
D. 堆排序
12．一台计算机具有多核CPU，可以同时执行相互独立的任务。归并排序的各个归并段可以
并行执行，在下列排序算法中，不可以并行执行的有（).
Ⅰ.基数排序 Ⅱ.快速排序 Ⅲ.冒泡排序 IV．堆排序
A.Ⅰ、Ⅲ
B.Ⅰ、Ⅱ
C.Ⅰ、Ⅲ、IV
D.Ⅱ、IV
13.【2009统考真题】若数据元素序列{11,12,13,7,8,9,23,4,5}是采用下列排序算法之一得
到的第二趟排序后的结果，则该排序算法只能是（)。
A．冒泡排序
B．插入排序
C．选择排序
D．二路归并排序
14.【2010统考真题】对一组数据(2,12,16,88,5,10)进行排序，若前3趟排序结果如下:
第一趟排序结果:2,12,16,5,10,88
第二趟排序结果:2,12,5,10,16,88
第三趟排序结果:2,5,10,12,16,88
则采用的排序算法可能是()。
A.冒泡排序
B.希尔排序
C.归并排序
D.基数排序
15.【2012统考真题】在内部排序过程中，对尚未确定最终位置的所有元素进行一遍处理称
为一趟排序。下列排序算法中，每趟排序结束都至少能够确定一个元素最终位置的方法是().
Ⅰ简单选择排序 Ⅱ.希尔排序 Ⅲ．快速排序 IV．堆排序 V.二路归并排序
A.仅Ⅰ、Ⅲ、IV
B.仅Ⅰ、Ⅲ、V
C.仅Ⅱ、Ⅲ、IV
D.仅 Ⅲ、IV、V
16.【2017统考真题】在内部排序时，若选择了归并排序而未选择插入排序，则可能的理由
是().
Ⅰ归并排序的程序代码更短
Ⅱ.归并排序的占用空间更少
Ⅲ.归并排序的运行效率更高
A.仅Ⅱ
B.仅Ⅲ
C.仅Ⅰ、Ⅱ
D.仅Ⅰ、Ⅲ
17.【2017统考真题】下列排序算法中，若将顺序存储更换为链式存储，则算法的时间效率
会降低的是()。
Ⅰ插入排序 Ⅱ．选择排序 Ⅲ.冒泡排序 IV．希尔排序 V．堆排序
A.仅Ⅰ、Ⅱ
B.仅Ⅱ、Ⅲ
C.仅Ⅲ、IV
D.仅IV、V
18.【2019统考真题】选择一个排序算法时，除算法的时空效率外，下列因素中，还需要考
虑的是().
Ⅰ数据的规模 Ⅱ．数据的存储方式 Ⅲ．算法的稳定性 IV．数据的初始状态
A.仅Ⅲ
B.仅Ⅰ、Ⅱ
C.仅Ⅱ、Ⅲ、IV
D. Ⅰ、Ⅱ、Ⅲ、IV
19.【2020统考真题】对大部分元素已有序的数组排序时，直接插入排序比简单选择排序效
率更高，其原因是().
Ⅰ.直接插入排序过程中元素之间的比较次数更少
Ⅱ.直接插入排序过程中所需的辅助空间更少
Ⅲ．直接插入排序过程中元素的移动次数更少
A.仅Ⅰ
B.仅Ⅲ
C.仅Ⅰ、Ⅱ
D.Ⅰ、Ⅱ和Ⅲ
20.【2022统考真题】对数据进行排序时，若采用直接插入排序而不采用快速排序，则可能的原因是()
Ⅰ大部分元素已有序
Ⅱ.待排序元素数量很少
Ⅲ.要求空间复杂度为O(1)
IV．要求排序算法是稳定的
A．仅Ⅰ、Ⅱ
B．仅Ⅲ、IV
C．仅Ⅰ、Ⅱ、IV
D．Ⅰ、Ⅱ、Ⅲ、IV
21.【2023统考真题】下列排序算法中，不稳定的是()。
Ⅰ希尔排序 Ⅱ.归并排序 Ⅲ．快速排序 IV．堆排序 V．基数排序
A.仅Ⅰ、Ⅱ
B.仅Ⅱ、V
C.仅Ⅰ、Ⅲ、IV
D.仅Ⅲ、IV、 V
