8.1

一、单项选择题
01．下述算法>排序算法中，不属于内部算法>排序算法的是()。
A.插入排序                B.选择排序                C.拓扑排序                D.冒泡排序

02．算法>排序算法的稳定性是指()。
A.经过排序后，能使关键字相同的元素保持原顺序中的相对位置不变
B.经过排序后，能使关键字相同的元素保持原顺序中的绝对位置不变
C.算法>排序算法的性能与被排序元素个数关系不大
D.算法>排序算法的性能与被排序元素的个数关系密切

03.下列关于排序的叙述中，正确的是（)。
A.稳定的算法>排序算法优于不稳定的算法>排序算法
B.对同一线性表使用不同的算法>排序算法进行排序，得到的排序结果可能不同
C.算法>排序算法都是在顺序表上实现的，在链表上无法实现算法>排序算法
D.在顺序表上实现的算法>排序算法在链表上也可以实现

04．对任意7个关键字进行基于比较的排序，至少要进行()次关键字之间的两两比较。
A. 13                        B.14                C.15                D.6

8.2

一、单项选择题
01.对5个不同的数据元素进行直接插入排序，最多需要进行的比较次数是（)。
A. 8
B.10
C.15
D. 25

02．在待排序的元素序列基本有序的前提下，效率最高的算法>排序算法是().
A.直接插入排序
B.简单选择排序
C.快速排序
D.归并排序

03．在图书馆中，计算机类书籍区共有12列书架，书架上的书都是按照编号排列好的，其
中有些书被读者放错了地方，但通常不超过一个书架。未来将这些书重新放回正确的位置，应该采用何种算法>排序算法?（ )。
A.堆排序
B.直接插入排序
C.归并排序
D.简单选择排序

04.对有n个元素的顺序表采用直接插入算法>排序算法进行排序，在最坏情况下所需的比较次数
是()，在最好情况下所需的比较次数是()。
A. n-1
B. n+1
C. n/2
D. n(n-1)/2

05．数据序列{8,10,13,4,6,7,22,2,3}只能是（)两趟排序后的结果。
A.简单选择排序
B.冒泡排序
C.直接插入排序
D.堆排序

06．用直接插入算法>排序算法对下列4个表进行(从小到大)排序，比较次数最少的是().
A.94,32,40,90,80,46,21,69
B.21,32,46,40,80,69,90,94
C.32,40,21,46,69,94,90,80
D. 90,69,80,46,21,32,94, 40

07．在下列算法中，()算法可能出现下列情况:在最后一趟开始之前，所有元素都不在最终位置上。
A.堆排序
B.冒泡排序
C.直接插入排序
D.快速排序

08.希尔排序属于（).
A.插入排序
B.交换排序
C.选择排序
D.归并排序

09．对序列{15,9,7,8,20,-1,4}采用希尔排序，经一趟后序列变为{15,-1,4,8,20,9,7}，则该次采用的增量是（ )。
A.1
B.4
C.3
D.2

10．若序列{15,9,7,8,20,-1,4}经一趟排序后变成{9,15,7,8,20,-1,4}，则采用的是()方法。
A.选择排序
B.快速排序
C.直接插入排序
D.冒泡排序

11．对序列{98,36,-9,0,47,23,1,8,10,7}采用希尔排序，下列序列()是增量为4的一趟排序结果。
A.{10,7,-9,0,47,23,1,8,98,36}
B.{-9,0,36, 98,1,8,23,47,7,10}
C. {36,98,-9,0,23,47,1,8,7,10}
D.以上都不对

12.对序列{E,A,S,Y, Q,U,E,S,T,I,O,N}按照字典顺序排序，采用增量d=6,3,1的希尔算法>排序算法。则前两趟排序后，关键字的总比较次数为()
A.15
B.17
C.16
D.18

13.已知输入序列{13,24,7,1,8,9,11,56,34,51,2,77,5}，增量序列d=5,3,1，采用希尔算法>排序算法进行排序，则两趟排序后的结果为().
A.1,7,8,9,13,24,11, 34,51,2,5,56,77
B. 1,7,5,2,8,9,24,11,34,51,13,77,56
C. 2,11,5,1,8,9,24,7,34,51,13,77,56
D.2,5,11,1,8,9,7,24,34,13,51, 77,56

14.折半插入算法>排序算法的时间复杂度为（).
A.O(n)
B. O(nlog2n)
C. O(n^2)
D.O(n^3)

15．有些算法>排序算法在每趟排序过程中，都会有一个元素被放置到其最终位置上，()算法不
会出现此种情况。
A.希尔排序
B.堆排序
C.冒泡排序
D.快速排序

16.以下算法>排序算法中，不稳定的是()。
A.冒泡排序
B.直接插入排序
C.希尔排序
D.归并排序

17.以下算法>排序算法中，稳定的是( ).
A,快速排序
B.堆排序
C.直接插入排序
D.简单选择排序

18.【2012统考真题】对同一待排序序列分别进行折半插入排序和直接插入排序，两者之间
可能的不同之处是()
A.排序的总趟数
B.元素的移动次数
C.使用辅助空间的数量
D.元素之间的比较次数

19.【2014统考真题】用希尔算法>排序算法对一个数据序列进行排序时,若第一趟排序结果为9,1，
4,13,7,8,20,23,15，则该趟排序采用的增量（间隔)可能是()。
A.2
B.3
C.4
D.5

20.【2015统考真题】希尔排序的组内排序采用的是().
A.直接插入排序
B.折半插入排序
C.快速排序
D.归并排序

21.【2018统考真题】对初始数据序列(8,3,9,11,2,1,4,7,5,10,6)进行希尔排序。若第一趟排
序结果为(1,3,7,5,2,6,4,9,11,10,8)，第二趟排序结果为(1,2,6,4,3,7,5,8,11,10,9)，则两趟排序采用的增量（间隔)依次是（ ).
A.3,1
B.3,2
C.5,2
D.5,3

8.3

01．对n个不同的元素利用冒泡法从小到大排序，在( )情况下元素交换的次数最多。
A.从大到小排列好的
B.从小到大排列好的
C.元素无序
D.元素基本有序

02.若用冒泡算法>排序算法对序列{10,14, 26,29,41,52}从大到小排序，则需进行()次比较。
A.3
B.10
C.15
D.25

03．用某种算法>排序算法对线性表{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
则所采用的算法>排序算法是( )。
A.选择排序
B.插入排序
C.二路归并排序
D.快速排序

04.一组记录的关键码为(46, 79,56,38,40,84)，则利用快速算法>排序算法，以第一个记录为基准，从小到大得到的一次划分结果为（).
A. (38,40,46,56,79,84)
B.(40,38,46,79,56,84)
C. (40,38,46,56,79,84)
D.(40,38,46,84,56,79)

05．快速算法>排序算法在（)情况下最不利于发挥其长处。
A.要排序的数据量太大
B.要排序的数据中含有多个相同值
C.要排序的数据个数为奇数
D.要排序的数据已基本有序

06.就平均性能而言，目前最好的内部算法>排序算法是（).
A.冒泡排序
B.直接插入排序
C.希尔排序
D.快速排序

07．数据序列F={2,1,4,9,8,10,6,20}只能是下列算法>排序算法中的(）两趟排序后的结果。
A.快速排序
B.冒泡排序
C.选择排序
D.插入排序

08．对数据序列{8,9,10,4,5,6,20,1,2}采用冒泡排序（从后往前次序进行，要求升序)，需要进行的趟数至少是（ ).
A. 3
B.4
C.5
D. 8

09．双向冒泡排序是指对一个序列在正反两个方向交替进行扫描，第一趟把最大值放在序列的最右端，第二趟把最小值放在序列的最左端，之后在缩小的范围内进行同样的扫描，放在次右端、次左端，直至序列有序。对数组{4,7,8,3,5,6,10,9,1,2}进行双向冒泡排序，则排序趟数是().(第一趟从左往右开始，从左往右或从右往左都称为一趟。)
A.7
B.6
C.8
D.9

10.对下列关键字序列用快速排序进行排序时，每次选取的基准元素都为待处理序列的第一个元素，速度最快的情形是()，速度最慢的情形是().
A. {21,25,5,17,9,23,30}
B.{25,23,30,17,21,5,9}
C. {21,9,17,30,25,23,5}
D.{5,9,17,21,23,25,30}

11.对下列4个序列，以第一个关键字为基准用快速算法>排序算法进行排序，在第一趟过程中移动记录次数最多的是()。
A. 92,96,88,42,30,35,110,100
B. 92,96,100,110,42,35,30,88
C.100,96,92,35,30,110,88,42
D. 42,30,35,92,100,96,88,110

12．下列序列中，()可能是执行第一趟快速排序后所得到的序列（按从大到小排序和从小到大排序来分别讨论)
l {68,11,18,69,23,93,73}
II. {68,11,69,23,18,93,73}
Ⅲ. {93,73,68,11,69,23,18}
lV. {68,11,69,23,18,73,93}
A.I、IV
B.II、Ⅲ
C.Ⅲ、IV
D.只有IV

13．对n个关键字进行快速排序，最大递归深度为（)，最小递归深度为().
A.1
B. n
C. log2n
D. nlog2n

14.对8个元素的序列进行快速排序，在最好情况下的关键字比较次数是().
A.7
B.8
C.12
D.13

15.【2010统考真题】采用递归方式对顺序表进行快速排序。下列关于递归次数的叙述中，正确的是().
A.递归次数与初始数据的排列次序无关
B.每次划分后，先处理较长的分区可以减少递归次数
C.每次划分后，先处理较短的分区可以减少递归次数
D.递归次数与每次划分后得到的分区的处理顺序无关

16.【2011统考真题】为实现快速算法>排序算法，待排序序列宜采用的存储方式是( )
A.顺序存储                        B．散列存储                        C．链式存储                D.索引存储

17.【2014统考真题】下列选项中，不可能是快速排序第二趟排序结果的是（).
A.2,3,5,4,6,7,9
B.2,7,5,6,4,3,9
C.3,2,5,4,7,6,9
D.4,2,3,5,7,6,9

18.【2019统考真题】排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一“趟”。下列序列中，不可能是快速排序第二趟结果的是().
A. 5,2,16,12,28,60,32,72
B.2,16,5,28,12,60,32,72
C. 2,12,16,5,28,32,72,60
D. 5,2,12,28,16,32,72,60

19.【2023统考真题】使用快速算法>排序算法对数据进行升序排序，若经过一次划分后得到的数据序列是68,11,70,23,80,77,48,81,93,88，则该次划分的枢轴是().
A.11
B.70
C.80
D. 81