一、 单项选择题（共71题）
对n个元素的序列进行冒泡排序时，最少的比较次数是（ ）。
A. n B. n-1 C. n/2 D. log2n
答案：B若一个元素序列基本有序，则选用（ ）方法较快。
A. 直接插入排序 B. 简单选择排序 C. 堆排序 D. 快速排序
答案：A在对n个元素进行冒泡排序的过程中，第一趟排序至多需要进行（ ）对相邻元素之间的交换。
A. n B. n - 1 C. n + 1 D. n/2
答案：B在对n个元素进行直接插入排序的过程中，共需要进行（ ）趟。 A. n B. n + 1 C. n - 1 D. 2n
答案：C对下列4个序列用快速排序方法进行排序，以序列的第1个元素为基准进行划分。在第1趟划分过程中，元素移动次数最多的是序列（ ）。
A. 70，75，82，90，23，16，10，68
B. 70，75，68，23，10，16，90，82
C. 82，75，70，16，10，90，68，23
D. 23，10，16，70，82，75，68，90
答案：A若对n个元素进行直接插入排序，在进行第i趟排序时，假定元素r[i+l]的插入位置为r[j]，则需要移动元素的次数为（ ）
A. j - i B. i - j - 1 C. i - j D. i - j + 1
答案：D若对n个元素进行简单选择排序，则进行任一趟排序的过程中，为寻找最小值元素所需要的时间复杂度为（ ）
A. O(1) B.O(logn) C. O(n2) D. O(n)
答案：D对下列4个序列进行快速排序，各以第一个元素为基准进行第一次划分，则在该次划分过程中需要移动元素次数最多的序列为（ ）
A. 1，3，5，7，9
B. 9，7，5，3，1
C. 5，3，1，7，9
D. 5，7，9，1，3
答案：D一组记录的关键码为（46，24，57，23，40，15），则利用选择排序的方法，第二趟排序的结果是（ ）。
A. 15，46，57，24，40，23
B. 15，23，57，46，40，24
C. 15，23，24，46，40，57
D. 15，23，24，40，46，57
答案：B在“局部有序”或序列长度较小的情况下，最佳内部排序方法是（ ）。
A. 直接插入排序 B. 冒泡排序 C. 简单选择排序 D. 归并排序
答案：A在对n个元素进行快速排序的过程中，最好情况下需要进行（ ）趟。
A. n B. n/2 C. log2n D. 2n
答案：C在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是（ ）。
A. 希尔排序 B. 冒泡排序 C. 插入排序 D. 选择排序
答案：D一组记录的关键码为（46，24，57，23，40，15），则利用冒泡排序的方法，第二趟排序的结果是（ ）。
A. 24，23，40，15，46，57
B. 24，46，23，40，15，57
C. 24，40，23，46，15，57
D. 23，24，15，46，40，57
答案：A假定对元素序列(7，3，5，9，1，12，8，15）进行快速排序，则进行第一次划分后，得到的左区间中元素的个数为（ ）
A. 2 B. 3 C. 4 D. 5
答案：B冒泡排序在最好情况下的时间复杂度为（ ）。
A. O(1) B. O(log2n) C. O(n) D. O(n2)
答案：C若对n个元素进行直接插入排序，在进行任意一趟排序的过程中，为寻找插入位置而需要的时间复杂度为（ ）
A. O(1) B. O(n) C. O(n2) D. O(logn)
答案：B在对n个元素进行简单选择排序的过程中，在第i趟需要从（ ）个元素中选择出最小值元素。
A. n - i + 1 B. n - i C. i D. i + 1
答案：A假定一个初始堆为（1，5，3，9，12，7，15，10），则进行第一趟堆排序后得到的结果为（ ）
A. 3，5，7，9，12，10，15，1
B. 3，5，9，7，12，10，15，1
C. 3，7，5，9，12，10，15，1
D. 3，5，7，12，9，10，15，1
答案：A若对n个元素进行直接插入排序，则进行第i趟排序过程前，有序表中的元素个数为（ ）
A. i B. i + 1 C. i - 1 D. 1
答案：A对n个元素进行直接插入排序时间复杂度为（ ）
A. O(1) B. O(n) C. O(n2) D. O(logn)
答案：C在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7个记录60插入到有序表时，则需比较（ ）次。
A. 7 B. 6 C. 4 D. 3
答案：D在对n个元素进行快速排序的过程中，最坏情况下需要进行（ ）趟。
A. n B. n - 1 C. n/2 D. logn
答案：B在对n个元素进行冒泡排序的过程中，最坏情况下的时间复杂度为（ ）
A. O(1) B. O(logn) C. 0(n2) D. 0(n)
答案：C下面排序方法中，比较次数与序列的初始状态无关的是（ ）。 A. 希尔排序 B. 冒泡排序 C. 直接插入排序 D. 简单选择排序
答案：D在平均情况下速度最快的排序方法为（ ） A. 简单选择排序 B. 冒泡排序 C. 堆排序 D. 快速排序 答案：D
从未排序的序列中依次取出元素与已排序序列中的元素进行比较，然后将其放在排序序列的合适位置，该排序方法称为（ ）排序法。
A. 选择 B. 希尔 C. 插入 D. 冒泡
答案：C在对n个元素进行冒泡排序的过程中，至少需要（ ）趟完成。 A. 1 B. n C. n - 1 D. n/2
答案：A若对n个元素进行直接插入排序，在进行第i趟排序时，为寻找插入位置最多需要进行（ ）次元素的比较，假定第0号元素放有待查的键值。
A. i B. i - 1 C. i + 1 D. 1
答案：C若要从1000个元素中得到10个最小值元素，最好采用（ ）方法。
A. 直接插入排序 B. 简单选择排序 C. 堆排序 D. 快速排序
答案：B在下述排序算法中，所需辅助存储空间最多的是（ (1) ），所需辅助存储空间最小的是（ (2) ），平均速度最快的是（ (3) ）。
A.快速排序 B. 归并排序 C. 堆排序 D. 希尔排序
答案：B C A在文件局部有序或文件长度较小的情况下，最佳内部排序的方法是（ ）。
A. 直接插入排序 B. 冒泡排序 C. 简单选择排序 D. 希尔排序
答案：A快速排序在最坏情况下时间复杂度是O(n2)，比（ ）的性能差。
A. 堆排序 B. 冒泡排序 C. 简单选择排序 D. 直接插入排序
答案：A若需在O(nlogn)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（ ）。
A. 快速排序 B. 堆排序 C. 归并排序 D. 希尔排序
答案：C如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用（ ）方法最快。
A. 冒泡排序 B. 快速排序 C. 希尔排序 D. 堆排序
答案：B以下结点序列是堆的为（ ）。
A. 100,90,80,60,85,75,20,25,10,70,65,50
B. 100,70,50,20,90,75,60,25,10,85,65,80
C. 100,80,90,60,85,75,20,25,10,70,65,50
D. 100,50,70,20,90,75,60,25,10,85,65,80
答案：A若要尽可能快地完成对实数数组的排序，且要求排序是稳定的，则应选（ ）。
A. 快速排序 B. 堆排序 C. 归并排序 D. 希尔排序
答案：C从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（ ）排序法。
A. 插入排序 B. 交换排序 C. 选择排序 D. 归并排序
答案：A直接插入排序在最好情况下的时间复杂度为（ ）。
A. O(logn) B. O(n) C. O(nlogn) D. O(n2)
答案：B从未排序的序列中，依次取出元素，与已排序序列的元素比较后，放入已排序序列中的恰当位置上，这是（
插入）排序。从未排序的序列中，挑选出元素，放在已排序序列的某一端位置，这是（选择）排序。逐次将待排序的序列中的相邻元素两两比较，凡是逆序则进行交换，这是（冒泡）排序。如果整个排序过程都在内存中进行，称为（内部）排序。排序算法的复杂性与排序算法的（运算量大小与占用存储多少）有关。设待排序的记录为(20,16,13,14,19)，经过下列过程将这些记录排序。 20,16,13,14,19 16,20,13,14,19 13,16,20,14,19 13,14,16,20,19 13,14,16,19,20 所用的排序方法是（ ）。
A. 直接插入排序 B. 冒泡排序 C. 希尔排序 D. 堆排序
答案：A对下列4个序列用快速排序的方法进行排序，以序列的第一个元素为基础进行划分，在第一趟划分过程中，元素移动次数最多的是（ ）序列。
A. 70,75,82,90,23,16,10,68
B. 70,75,68,23,10,16,90,82
C. 82,75,70,16,10,90,68,23
D. 23,10,16,70,82,75,68,90
答案：A用快速排序的方法对包含几个关键字的序列进行排序，最坏情况下，执行的时间为（ ）。
A. O(n) B. O(log2n) C. O(nlog2n) D. O(n2)
答案：D在所有排序方法中，关键码（即关键字）比较的次数与记录的初始排列次序无关的是（ ）。
A. 希尔排序 B. 冒泡排序 C. 直接插入排序 D. 简单选择排序
答案：D在归并排序过程中，需归并的趟数为（ log2n ）。
一组记录的排序代码为{46,79,56,38,40,84}，则利用堆排序的方法建立的初始堆为（ ）。
A. {79,46,56,38,40,80}
B. {84,79,56,38,40,46}
C. {84,79,56,46,40,38}
D. {84,56,79,40,46,38}
答案：B一组记录的排序代码为{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}
答案：C每次把待排序的区间划分为左、右两个子区间，其中左区间中元素的排序码均小于等于基准元素的排序码，右区间中元素的排序码均大于等于基准元素的排序码，此种排序方法叫做（ ）。
A. 堆排序 B. 快速排序 C. 冒泡排序 D. 希尔排序
答案：B一组记录的排序码为一个字母序列{Q,D,F,X,A,P,N,B,Y,M,C,W}，按归并排序方法对该序列进行一趟归并后的结果为（ ）。
A. D,F,Q,X,A,B,N,P,C,M,W,Y
B. D,F,Q,A,P,X,B,N,Y,C,M,W
C. D,Q,F,X,A,P,N,B,Y,M,C,W
D. D,Q,F,X,A,P,B,N,M,Y,C,W
答案：D一组记录的排序码为{25,48,16,35,79,82,23,40,36,72}，其中，含有5个长度为2的有序表，按归并排序方法对该序列进行一趟归并后的结果为（ ）。
A. 16,25,35,48,23,40,79,82,36,72
B. 16,25,35,48,79,82,23,36,40,72
C. 16,25,48,35,79,82,23,36,40,72
D. 16,25,35,48,79,23,36,40,72,82
答案：A设有1000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好选用（ ）排序法。
A. 冒泡排序 B. 快速排序 C. 堆排序 D. 希尔排序
答案：C在待排序的元素序列基本有序的前提下，效率最高的排序方法是（ ）。
A. 直接插入排序 B. 简单选择排序 C. 快速排序 D. 归并排序
答案：A用某种排序方法对线性表{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. 快速排序
答案：D快速排序方法在（ ）情况下最不利于发挥其长处。
A. 要排序的数据量太大
B. 要排序的数据中含有多个相同值
C. 要排序的数据已基本有序
D. 要排序的数据个数为整数
答案：C在内部排序中，通常要对被排序数据序列进行多趟扫描。各种排序方法有其不同排序实施过程和(时间)复杂性。对给定的整数序列（541，132，984，746，518，181，946，314，205，827）进行从小到大的排序时，采用冒泡排序和直接选择排序时若先选出大元素，则第一趟扫描结果分别是（ (1) ）和（ (2) ）；采用快速排序（以中间元素518为基准）的第一趟扫描结果是（ (3) ）。设被排序序列有N个元素，冒泡排序和直接选择排序的平均时间复杂性是（ (4) ）；快速排序的平均时间复杂性是（ (5) ）。
(1)(2)(3)：
A. (181，132，314，205，541，518，946，827，746，984)
B. (541，132，827，746，518，181，946，314，205，984)
C. (205，132，314，181，518，746，946，984，541，827)
D. (541，132，984，746，827，181，946，314，205，518)
E. (132，541，746，518，181，946，314，205，827，984)
F. (132，541，746，984，181，518，314，946，205，827)
(4)(5): A. O(nlog2n) B. O(n) C. O(log2n) D. O(n2)
答案：EBCDA将5个不同的数据进行排序，至多需要比较（ ）次。
A. 8 B. 9 C. 10 D. 25
答案:C排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为（ ）。
A. 希尔排序 B. 冒泡排序 C. 插入排序 D. 选择排序
答案：C从未排序序列中挑选元素，并将其依次插入已排序序列（初始时为空）的一端的方法，称为（ ）。
A. 希尔排序 B. 归并排序 C. 插入排序 D. 选择排序
答案：D对ｎ个不同的排序码按从小到大顺序进行冒泡排序，在下列（ ）。情况下比较的次数最多。
A. 从小到大排列好的
B. 从大到小排列好的
C. 元素无序
D. 元素基本有序 答案：B对ｎ个不同的排序码进行冒泡排序，在元素无序的情况下比较的次数为（ ）。 A. n + 1 B. n C. n - 1 D. n(n-1)/2
答案：D快速排序在下列（ ）情况下最易发挥其长处。
A. 被排序数据已基本有序
B. 被排序数据中含有多个相同排序码
C. 被排序数据完全无序
D. 被排序数据中的最大值和最小值相差悬殊
答案：D对有n个记录的表作快速排序，在最坏情况下，算法的时间复杂度是（ ）。
A. O(n)
B. O(n2)
C. O(nlog2n)
D. O(n3)
答案：B若一组记录的排序码为（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
答案：C在最好情况下，下列排序算法中（ ）排序算法所需比较关键字次数最少。
A. 冒泡 B. 归并 C. 快速 D. 直接插入
答案：D下列关键字序列中，（ ）是堆。
A. 16, 72, 31, 23, 94, 53
B. 94, 23, 31, 72, 16, 53
C. 16, 53, 23, 94，31, 72
D. 16, 23, 53, 31, 94, 72
答案：D堆排序是一种（ ）排序。
A. 插入 B. 选择 C. 交换 D. 归并
答案：B堆的形状是一棵（ ）。
A. 二叉排序树 B. 满二叉树 C. 完全二叉树 D. 平衡二叉树
答案：C若一组记录的排序码为（46, 79, 56, 38, 40, 84），则利用堆排序的方法建立的初始堆为（ ）。
A. 79, 46, 56, 38, 40, 84
B. 84, 79, 56, 38, 40, 46
C. 84, 79, 56, 46, 40, 38
D. 84, 56, 79, 40, 46, 38
答案：B下述几种排序方法中，平均查找长度（ASL）最小的是（ ）。 A. 插入排序 B. 快速排序 C. 归并排序 D. 选择排序
答案：B下述几种排序方法中，要求内存最大的是（ ）。
A. 插入排序 B. 快速排序 C. 归并排序 D. 选择排序
答案：C目前以比较为基础的内部排序方法中，其比较次数与待排序的记录的初始排列状态无关的是（ ）。
A. 插入排序 B. 二分插入排序 C. 快速排序 D. 冒泡排序
答案：C在堆排序方法中，每趟排序的定义是：将待排序关键字调整为堆后，将堆顶元素与待排序序列的最后一个元素进行交换。如果待排序序列为{100, 70, 50, 20, 90, 75, 60, 25}，要求按关键字从小到大的顺序排序，则各趟排序的结果为： 第1趟排序的结果为20，95，75，25，70，50，60，100； 第2趟排序的结果为（ (1) ）；第3趟排序的结果为（ (2) ）； 第4趟排序的结果为（ (3) ）；第5趟排序的结果为（ (4) ）； 第6趟排序的结果为（ (5) ）； 第7趟排序的结果为20,25,50,60,70,75,90,100。
供选答案：
(1)(2)(3)(4)(5)：
A. 20, 50, 60, 25, 70, 75, 90, 100
B. 25, 50, 20, 60, 70, 75, 90, 100
C. 60, 70, 75, 25, 20, 50, 90, 100
D. 50, 70, 60, 25, 20, 75, 90, 100
E. 20, 25, 50, 60, 70, 75, 90, 100
F. 20, 25, 50, 70, 90, 75, 60, 100
G. 20, 25, 50, 60, 90, 75, 70, 100
H. 25, 20, 70, 60, 50, 75, 90, 100
答案：CDABE
二、 填空题（共15题）
- 用冒泡排序方法对线性表(12、5、8、32、21、6)进行排序时，第3趟排序的结果是（ ）。
答案：5，8，6，12，21，32 - 对n个元素进行冒泡排序，在（ ）情况下比较次数最多，其比较次数为（ ）。
答案：元素从大到小排列， n(n-1)/2 - 若对一组记录（46，79，56，38，40，80，35，50，74）进行直接插入排序，当把第8个记录插入到前面已排序的有序表时，为寻找插入位置需比较（ ）次。
答案：4 - 设序列中元素的初始状态是按键值递增排序的，分别用堆排序、快速排序、冒泡排序和归并排序方法对其仍按递增顺序进行排序，则（ ）最省时间，（ ）最费时间。
答案：冒泡排序 快速排序 - 假定一组记录为（46，79，56，64，38，40，84，43），在冒泡排序的过程中进行第一趟排序时，元素79将最终下沉到其后第（ ）个元素的位置。
答案：4 - 在时间复杂性为O(n2)的所有排序方法中，（ ）排序方法是不稳定的。
答案：快速 - 假定一组记录为（46，79，56，25，76，38，40，80)，对其进行快速排序的第一次划分后，右区间内元素的个数为（ ）。
答案：4 - 在简单选择排序中，记录比较次数的时间复杂度为（ ），记录移动次数的时间复杂度为（ ）。
答案：O(n2)； O(n) - 对线性表{12，5，8，32，21，6}进行升序排序时，用冒泡排序方法第1趟排序的结果是（ ）；用简单选择排序方法第1趟排序的结果是（ ）。
答案：5，8，12，21，6，32； 5，12，8，32，21，6 - 在所有排序方法中，（ ）排序方法采用的是折半查找法的思想。
答案：快速 - （ ）排序方法能够每次从无序表中顺序查找出一个最小值。
答案：简单选择排序 - （ ）排序方法使键值大的记录逐渐下沉，使键值小的记录逐渐上浮。
答案：冒泡 - 对n个元素进行直接插入排序，在进行第i趟排序时，假定元素r[i + 1]的插入位置为r[j]，则需要移动元素的次数为（ ）。
答案：i - j + 1 - 用选择排序方法对线性表(12、5、8、32、21、6)进行排序时，第3趟排序的结果是（ ）。
答案：5，6，8，32，21，12 - 假定一个堆为（38，40，56，79，46，84），则利用堆排序方法进行第一趟交换和对根结点筛运算后得到的结果为（ ）。
答案：(40，46，56，79，84，38)
三、简答题（共23题）
- 给出一组关键字（19，01，26，92，87，11，43，87，21)，进行冒泡排序，列出每一遍排序后关键字的排列次序，并统计每遍排序所进行的关键字比较次数。
答案：初始关键字序列为： (19，01，26，92，87，11，43，87，21)
第一遍排序比较8次，交换6次后成为： （01，19，26，87，11，43，87，21，92）
第二遍排序比较7次，交换3次后成为： (01，19，26，11，43，87，21，87，92)
第三遍排序比较6次，交换2次后成为： (01，19，11，26，43，21，87，87，92）
第四遍排序比较5次，交换2次后成为： （01，11，19，26，21，43，87，87，92）
第五遍排序比较4次，交换1次后成为： （01，11，19，21，26，43，87，87，92）
第六遍排序比较3次，交换0次。排序完毕。 - 堆排序为什么是不稳定的排序？试举例说明。
答案：因为在堆排序时，在调整堆的过程中，有可能改变具有相同关键字的元素的先后次序，故该排序方法是不稳定的。例如，初始序列为8，5，5，按从小到大进行排序，则初始状态为：
显然，两个5的相对顺序发生了变化，所以是不稳定的。 - 对序列{24，86，15，55，31，36}进行直接插入排序求排序过程及排序结果。
答案：直接插入排序：在已排好的序列中用顺序法查找插入位置，找到后将该位置原来的记录及其后面所有记录顺序后移一个位置，空出该位置插入新记录。由上述排序思想可得排序过程及排序结果如下：
初始排序序列为{24}，56，15，55，31，36
第1趟排序结果为{24，86}，15，55，31，36
第2趟排序结果为{15，24，86}，55，31，36
第3趟排序结果为{15，24，55，86}，31，36
第4趟排序结果为{15，24，31，55，86}，36
第5趟排序结果为{15，24，31，36，55，86}
