第10章 排序排序排序
一、选择题 1．某内排序方法的稳定性是指．某内排序方法的稳定性是指( )( )( )。。 【南京理工大学【南京理工大学 1997 1997 1997 一、一、一、101010（（2分）
】 A ．该排序算法不允许有相同的关键字记录该排序算法不允许有相同的关键字记录 B B B．．
该排序算法允许有相同的关键字记录记录
C ．平均时间为0（n log n n log n）的排序方法）的排序方法）的排序方法
D D D．以上都不对．以上都不对．以上都不对
2．下面给出的四种排序法中下面给出的四种排序法中( )( )( )排序法是不稳定性排序法。排序法是不稳定性排序法。【北京航空航天大学北京航空航天大学 1999 1999 1999 一、一、10 10 （（2分）
】 A. A. 插入插入插入 B. B. B. 冒泡冒泡冒泡 C. C. C. 二路归并二路归并二路归并 D. D. D. 堆积堆积堆积 3．下列排序算法中，其中（．下列排序算法中，其中（ ）是稳定的。）是稳定的。）是稳定的。 【福州大学【福州大学 1998 1998 1998 一、一、一、3 (23 (2分)】
A. A. 堆排序，冒泡排序堆排序，冒泡排序堆排序，冒泡排序
B. B. B. 快速排序，堆排序快速排序，堆排序快速排序，堆排序
C. C. 直接选择排序，归并排序直接选择排序，归并排序直接选择排序，归并排序
D. D. D. 归并排序，冒泡排序归并排序，冒泡排序归并排序，冒泡排序
4．稳定的排序方法是（．稳定的排序方法是（ ）） 【北方交通大学【北方交通大学【北方交通大学 2000 2000 2000 二、二、二、33（2分）
】 A ．直接插入排序和快速排序．直接插入排序和快速排序 B B B．折半插入排序和起泡排序．折半插入排序和起泡排序．折半插入排序和起泡排序
C ．简单选择排序和四路归并排序．简单选择排序和四路归并排序
D D D．树形选择排序和．树形选择排序和shell 排序排序
5．下列排序方法中，哪一个是稳定的排序方法？（．下列排序方法中，哪一个是稳定的排序方法？（ ） 【北方交通大学【北方交通大学【北方交通大学 2001 2001 2001 一、一、一、88（2分）】
A ．直接选择排序．直接选择排序
B B B．二分法插入排序．二分法插入排序．二分法插入排序
C C C．希尔排序．希尔排序．希尔排序
D D D．快速排序．快速排序．快速排序
6．若要求尽可能快地对序列进行稳定的排序，则应选（．若要求尽可能快地对序列进行稳定的排序，则应选（A A ．快速排序．快速排序 B B B．归并排序．归并排序．归并排序 C C C．冒．冒泡排序）。
【北京邮电大学【北京邮电大学 2001 2001 2001 一、一、一、55（2分）
】 7．如果待排序序列中两个数据元素具有相同的值，在排序前后它们的相互位置发生颠倒，则称该排序算法是不稳定的。（ ）就是不稳定的排序方法。）就是不稳定的排序方法。【清华大学【清华大学 1998 1998 1998 一、一、一、3 3 (2分）】
A ．起泡排序．起泡排序
B B B．归并排序．归并排序．归并排序
C C C．．Shell 排序排序
D D D．直接插入排序．直接插入排序．直接插入排序
E E E．简单选．简单选择排序择排序
8．若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选（．若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选（ ）排序为宜。）排序为宜。）排序为宜。
A ．直接插入．直接插入
B B B．直接选择．直接选择．直接选择
C C C．堆．堆．堆
D D D．快速．快速．快速
E E E．基数．基数．基数 【中科院计算所【中科院计算所【中科院计算所 2000 2000 2000 一、一、5（2分）】
9．若需在O(nlog 2n)n)的时间内完成对数组的排序，的时间内完成对数组的排序，的时间内完成对数组
的排序，且要求排序是稳定的，且要求排序是稳定的，则可选择的排序方
法是（法是（ ））
。 A. A. 快速排序快速排序快速排序 B. B. B. 堆排序堆排序堆排序 C. C. C. 归并排序归并排序归并排序 D. D. D. 直接插入排序直接插入排序直接插入排序
【中国科技大学【中国科技大学 1998 1998 1998 二、二、二、44（2分）】 【中科院计算所【中科院计算所 1998 1998 1998 二、二、二、44（2分）
】 1010．下面的排序算法中，不稳定的是（．下面的排序算法中，不稳定的是（．下面的排序算法中，不稳定的是（ ）） 【北京工业大学【北京工业大学 1999 1999 1999 一、一、一、2 (22 (2分)】
A.A.起泡排序起泡排序起泡排序
B. B. B.折半插入排序折半插入排序折半插入排序
C. C. C.简单选择排序简单选择排序简单选择排序
D. D. D.希尔排序希尔排序希尔排序
E. E. E.基数排序基数排序基数排序
F. F. F.堆堆排序。排序。
1111．下列内部排序算法中：．下列内部排序算法中：．下列内部排序算法中： 【北京工业大学【北京工业大学【北京工业大学 2000 2000 2000 一、一、一、1 (101 (10分 每问2分)】
A ．快速排序．快速排序 B. B. B.直接插入排序直接插入排序直接插入排序 C. C. C. 二路归并排序二路归并排序二路归并排序 D. D. D. 简单选择排序简单选择排序简单选择排序 E. E. E. 起泡排序起泡排序起泡排序 F. F. 堆排序堆排序堆排序
（1） 其比较次数与序列初态无关的算法是（其比较次数与序列初态无关的算法是（ ）） （（2）不稳定的排序算法是（）不稳定的排序算法是（ ））
（3）在初始序列已基本有序（除去n 个元素中的某k 个元素后即呈有序，个元素后即呈有序，k<<n k<<n k<<n）的情况下，）的情况下，排序效率最高的算法是（排序效率最高的算法是（ ））
（4）排序的平均时间复杂度为O(n O(n••logn)logn)的算法是（的算法是（的算法是（ ）为）为O(n O(n••n)n)的算法是（的算法是（的算法是（ ））
1212．．排序趟数与序列的原始状态有关的排序方法是排序趟数与序列的原始状态有关的排序方法是( )( )( )排序法。排序法。【北京航空航天大学【北京航空航天大学 1999 1999 一、一、99（2分）
】 A A．插入．插入．插入 B. B. B. 选择选择选择 C. C. C. 冒泡冒泡冒泡 D. D. D. 快速快速快速 1313．下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是。．下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是。．下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是。( ) ( )
A ．选择排序法．选择排序法 B. B. B. 插入排序法插入排序法插入排序法 C. C. C. 快速排序法快速排序法快速排序法 D. D. D. 堆积排序法堆积排序法堆积排序法
【北京航空航天大学【北京航空航天大学 2000 2000 2000 一、一、一、101010（（2分）
】 1414．对下列四种排序方法，在排序中关键字比较次数同记录初始排列无关的是．对下列四种排序方法，在排序中关键字比较次数同记录初始排列无关的是．对下列四种排序方法，在排序中关键字比较次数同记录初始排列无关的是( )( )( )。。
A ．直接插入．直接插入 B. B. B. 二分法插入二分法插入二分法插入 C. C. C. 快速排序快速排序快速排序 D. D. D. 归并排序归并排序归并排序
【南京理工大学【南京理工大学 2000 2000 2000 一、一、一、7 7 7 （（1.5分）
】 1515．．在下列排序算法中在下列排序算法中,，哪一个算法的时间复杂度与初始排序无关（ ））。【北京理工大学北京理工大学 2001 2001 六、六、4 4 4 （（2）
】 A ． 直接插入排序直接插入排序 B. B. B. 气泡排序气泡排序气泡排序 C. C. C. 快速排序快速排序快速排序 D. D. D. 直接选择排序直接选择排序直接选择排序
1616．比较次数与排序的初始状态无关的排序方法是．比较次数与排序的初始状态无关的排序方法是．比较次数与排序的初始状态无关的排序方法是( )( )( )。。【北方交通大学【北方交通大学 2000 2000 2000 二、二、二、22（2分）】
A ．直接插入排序．直接插入排序
B B B．起泡排序．起泡排序．起泡排序
C C C．快速排序．快速排序．快速排序
D D D．简单选择排序．简单选择排序．简单选择排序
1717．数据序列（．数据序列（．数据序列（88，9，1010，，4，5，6，2020，，1，2）只能是下列排序算法中的）只能是下列排序算法中的( )( )( )的两趟排的两趟排序后的结果。序后的结果。 A ．选择排序．选择排序 B. B. B.冒泡排序冒泡排序冒泡排序 C. C. C.插入排序插入排序插入排序 D. D. D.堆排序堆排序堆排序
【合肥工业大学【合肥工业大学【合肥工业大学 1999 1999 1999 一、一、一、3 3 3 （（2分）
】 1818．数据序列（．数据序列（．数据序列（22，1，4，9，8，1010，，6，2020）只能是下列排序算法中的）只能是下列排序算法中的）只能是下列排序算法中的( )( )( )的两趟排序后的两趟排序后
的结果。的结果。
A. A. 快速排序快速排序快速排序
B. B. B. 冒泡排序冒泡排序冒泡排序
C. C. C. 选择排序选择排序选择排序
D. D. D. 插入排序插入排序插入排序
【合肥工业大学【合肥工业大学 2000 2000 2000 一、一、一、3 3 3 （（2分）
考研要多少分】 1919．对一组数据（．对一组数据（．对一组数据（848484，，4747，，2525，，1515，，2121）排序，数据的排列次序在排序的过程中的变化为）排序，数据的排列次序在排序的过程中的变化为）排序，数据的排列次序在排序的过程中的变化为
（1） 84 47 25 15 21 84 47 25 15 21 （（2） 15 47 25 84 21 15 47 25 84 21 （（3） 15 21 25 84 47 15 21 25 84 47 （（4） 15 21 25 47 84
则采用的排序是则采用的排序是 ( ) ( ) ( )。。 【南京理工大学【南京理工大学【南京理工大学 1997 1997 1997 一、一、一、2 2 2 （（2分）
】 A. A. 选择选择选择 B. B. B. 冒泡冒泡冒泡 C. C. C. 快速快速快速 D. D. D. 插入插入插入
2020．对序列．对序列．对序列{15{15{15，，9，7，8，2020，，-1-1，，4}4}进行排序，进行一趟后数据的排列变为进行排序，进行一趟后数据的排列变为进行排序，进行一趟后数据的排列变为{4{4{4，，9，-1-1，，8，2020，，7，15}15}；则采用的是（；则采用的是（；则采用的是（ ）排序。）排序。【南京理工大学【南京理工大学 1998 1998 1998 一、一、一、88（2分）
】
A. A. 选择选择选择 B. B. B. 快速快速快速 C. C. C. 希尔希尔希尔 D. D. D. 冒泡冒泡冒泡
2121．若上题的数据经一趟排序后的排列为．若上题的数据经一趟排序后的排列为．若上题的数据经一趟排序后的排列为{9{9{9，，1515，，7，8，2020，，-1-1，，4}4}，则采用的是（，则采用的是（，则采用的是（ ））排序。排序。
A ．选择．选择 B. B. B. 堆堆 C. C. 直接插入直接插入直接插入 D. D. D. 冒泡冒泡冒泡 【南京理工大学【南京理工大学【南京理工大学 1998 1998 1998 一、一、一、99（2分）】
2222．下列排序算法中．下列排序算法中．下列排序算法中( )( )( )不能保证每趟排序至少能将一个元素放到其最终的位置上。不能保证每趟排序至少能将一个元素放到其最终的位置上。不能保证每趟排序至少能将一个元素放到其最终的位置上。
A.A.快速排序快速排序快速排序
B. B. shell 排序排序
C. C. C. 堆排序堆排序堆排序
D. D. D.冒泡排序冒泡排序冒泡排序 【合肥工业大学【合肥工业大学【合肥工业大学 2001 2001 2001 一、一、一、33（2分）】
2323．下列排序算法中．下列排序算法中．下列排序算法中( )( )( )排序在一趟结束后不一定能选出一个元素放在其最终位置上。排序在一趟结束后不一定能选出一个元素放在其最终位置上。排序在一趟结束后不一定能选出一个元素放在其最终位置上。
A. A. 选择选择选择
B. B. B. 冒泡冒泡冒泡
C. C. C. 归并归并归并
D. D. D. 堆堆
【南京理工大学【南京理工大学 2001 2001 2001 一、一、一、77（1.5分）】【哈尔滨工业大学【哈尔滨工业大学 2001 2001 2001 二、二、二、44（2分）
】 2424．下列序列中，．下列序列中，（ ）是执行第一趟快速排序后所得的序列。）是执行第一趟快速排序后所得的序列。）是执行第一趟快速排序后所得的序列。 【福州大学【福州大学【福州大学 1998 1998 1998 一、一、一、9 9 (2分)】
A. [68 A. [68，，1111，，1818，，69] [2369] [23，，9393，，73]
B. [6873] B. [68，，1111，，6969，，23] [1823] [18，，9393，，73]
C. [93 C. [93，，73] [6873] [68，，1111，，6969，，2323，，18]
D. [6818] D. [68，，1111，，6969，，2323，，18] [9318] [93，，73]
2525．有一组数据（．有一组数据（．有一组数据（151515，，9，7，8，2020，，-1-1，，7，4） 用快速排序的划分方法进行一趟划分后数据的排序为据的排序为 ( ) ( ) ( )（按递增序）（按递增序）。 【南京理工大学【南京理工大学【南京理工大学 1996 1996 1996 一、一、一、4 4 4 （（2分）】 A ．下面的B ，C ，D 都不对。都不对。 B B B．．9，7，8，4，-1-1，，7，1515，，20
C ．2020，，1515，，8，9，7，-1-1，，4，7 D. 97 D. 9，，4，7，8，7，-1-1，，1515，，20
2626．一组记录的关键码为（．一组记录的关键码为（．一组记录的关键码为（464646，，7979，，5656，，3838，，4040，，8484））
，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（记录为基准得到的一次划分结果为（ ））。 【燕山大学【燕山大学【燕山大学 2001 2001 2001 一、一、一、44（2分）
】 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)
27. 27. 在下面的排序方法中，辅助空间为在下面的排序方法中，辅助空间为O （n ）的是）的是( ) ( ) ( ) 。。【南京理工大学【南京理工大学 1999 1999 1999 一、一、一、1717（1分）】
A A．希尔排序．希尔排序．希尔排序 B. B. B. 堆排序堆排序堆排序 C. C. C. 选择排序选择排序选择排序 D. D. D. 归并排序归并排序归并排序
2828．下列排序算法中，在待排序数据已有序时，花费时间反而最多的是．下列排序算法中，在待排序数据已有序时，花费时间反而最多的是．下列排序算法中，在待排序数据已有序时，花费时间反而最多的是( )( )( )排序。排序。排序。
A A．． 冒泡冒泡 B. B. B. 希尔希尔希尔 C. C. C. 快速快速快速 D. D. D. 堆堆 【南京理工大学【南京理工大学【南京理工大学 2001 2001 2001 一、一、一、12 12 12 （（1.5分）
】 29.29.下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的是：（据初始特性影响的是：（ ）。）。）。
A. A. 直接插入排序直接插入排序直接插入排序
B. B. B. 快速排序快速排序快速排序
C. C. C. 直接选择排序直接选择排序直接选择排序
D. D. D. 堆排序堆排序堆排序
30. 30. 对初始状态为递增序列的表按递增顺序排序，对初始状态为递增序列的表按递增顺序排序，对初始状态为递增序列的表按递增顺序排序，最省时间的是（最省时间的是（最省时间的是（ ）算法，最费时间的）算法，最费时间的
是（是（ ）算法。）算法。）算法。
A. A. 堆排序堆排序堆排序
B. B. B. 快速排序快速排序快速排序
C. C. C. 插入排序插入排序插入排序
D. D. D. 归并排序归并排序归并排序 【南开大学【南开大学【南开大学 2000 2000 一、一
、55】
31. 31. 就平均性能而言，目前最好的内排序方法是就平均性能而言，目前最好的内排序方法是就平均性能而言，目前最好的内排序方法是( )( )( )排序法。排序法。【西安电子科技大学【西安电子科技大学 1998 1998 一、一、9 (29 (2分）
】 A. A. 冒泡冒泡冒泡 B. B. B. 希尔插入希尔插入希尔插入 C. C. C. 交换交换交换 D. D. D. 快速快速快速 3232．如果只想得到．如果只想得到
1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用（ ）方法最快。）方法最快。）方法最快。
A ．起泡排序．起泡排序
B B B．快速排列．快速排列．快速排列
C C C．．Shell 排序排序
D D D．堆排序．堆排序．堆排序
E E E．简单选择排序．简单选择排序．简单选择排序
【清华大学【清华大学 1998 1998 1998 一、一、一、2 2 2 （（2分）
】 类似本题的另外叙述有：
(1)(1)设有设有5000个无序的元素个无序的元素,，希望用最快的速度挑选出其中前十个最大的元素希望用最快的速度挑选出其中前十个最大的元素,，在以下的排序方法中序方法中( )( )( )最好最好最好??为什么为什么? ? ? 【山东工业大学【山东工业大学【山东工业大学 1995 1995 1995 二、二、二、4 4 4 （（3分）
】 A ．快速排序．快速排序 B B B．堆排序．堆排序．堆排序 C C C．归并排序．归并排序．归并排序 D D D．基数排序．基数排序．基数排序 E E E．．SHELL 排序排序
(2)(2)数据表中有数据表中有10000个元素，如果仅要求求出其中最大的10个元素，则采用个元素，则采用( )( )( )算法算法最节省时间。最节省时间。
A. A. 堆排序堆排序堆排序
B. B. B. 希尔排序希尔排序希尔排序
C. C. C. 快速排序快速排序快速排序
D. D. D. 直接选择排序直接选择排序直接选择排序 【北京理工大学【北京理工大学 2000 2000 2000 一、一、一、5 5 （2分）】
(3)(3)设有设有1000个无序的元素，希望用最快的速度挑选出其中前十个最大的元素，在以下的排序方法中采用哪一种最好？排序方法中采用哪一种最好？ ( ) ( ) ( ) 【东北大学【东北大学【东北大学 1999 1999 1999 一、一、一、5 (35 (3分)】
A. A. 快速排序快速排序快速排序
B. B. B. 归并排序归并排序归并排序
C. C. C. 堆排序堆排序堆排序
D. D. D.基数排序基数排序基数排序
E.shell E.shell 排序排序
3333．在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是（．在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是（．在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是（ ））
A ．直接插入排序．直接插入排序
B B B．冒泡排序．冒泡排序．冒泡排序
C C C．简单选择排序．简单选择排序．简单选择排序 【山东工业大学【山东工业大学【山东工业大学 1995 1995 1995 二、二、二、1 1 1 （（2分）】
类似本题的另外叙述有：
(1)(1)在文件在文件在文件""局部有序局部有序""或文件长度较小的情况下，最佳内部排序的方法是（或文件长度较小的情况下，最佳内部排序的方法是（ ））。
A. A. 直接插入排序直接插入排序直接插入排序
B. B. B. 冒泡排序冒泡排序冒泡排序
C. C. C. 简单选择排序简单选择排序简单选择排序
D. D. D. 快速排序快速排序快速排序 【山东大学【山东大学 2001 2001 2001 二、二、 2 (1分)】
(2)(2)在待排序的元素序列基本有序的前提下，效率最高的排序方法是（在待排序的元素序列基本有序的
前提下，效率最高的排序方法是（在待排序的元素序列基本有序的前提下，效率最高的排序方法是（ ））。 【武汉大学【武汉大学 2000 2000 二、二、二、66】
A. A.插入排序插入排序插入排序
B. B. B. 选择排序选择排序选择排序
C. C. C. 快速排序快速排序快速排序
D. D. D. 归并排序归并排序归并排序
3434．下列排序算法中，．下列排序算法中，（ ）算法可能会出现下面情况：在最后一趟开始之前，所有元素）算法可能会出现下面情况：在最后一趟开始之前，所有元素
都不在其最终的位置上。【南开大学【南开大学 2000 2000 2000 一、一、一、44】 【西北大学【西北大学 2001 2001 2001 二、二、二、11】
A. A. 堆排序堆排序堆排序
B. B. B. 冒泡排序冒泡排序冒泡排序
C. C. C. 快速排序快速排序快速排序
D. D. D. 插入排序插入排序插入排序
35. 35. 下列排序算法中，下列排序算法中，占用辅助空间最多的是：( ) 【厦门大学【厦门大学 2002 2002 2002 五、五、2
（8分）】 A. A. 归并排序归并排序归并排序 B. B. B. 快速排序快速排序快速排序 C. C. C. 希尔排序希尔排序希尔排序 D. D. D. 堆排序堆排序 3636．．
从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为已排序序列的合适位置，该排序方法称为( )( )( )排序法。排序法。【北京航空航天大学【北京航空航天大学 1999 1999 1999 一、一、一、88（2分）】
A. A. 插入插入插入
B. B. B. 选择选择选择
C. C. C. 希尔希尔希尔
D. D. D. 二路归并二路归并二路归并
37. 37. 在排序算法中，在排序算法中，在排序算法中，每次从未排序的记录中挑出最小（或最大）关键码字的记录，每次从未排序的记录中挑出最小（或最大）关键码字的记录，每次从未排序的记录中挑出最小（或最大）关键码字的记录，加入到已加入到已排序记录的末尾，该排序方法是（排序记录的末尾，该排序方法是（ ））。【中山大学【中山大学 1999 1999 1999 一、一、一、111111】】
A. A. 选择选择选择
B. B. B. 冒泡冒泡冒泡
C. C. C. 插入插入插入
D. D. D. 堆堆 3838．用直接插入排序方法对下面四个序列进行排序（由小到大）．用直接插入排序方法对下面四个序列进行排序（由小到大）
，元素比较次数最少的是（ ））
。 A ． 94,32,40,90,80,46,21,69 B 94,32,40,90,80,46,21,69 B．． 32,40,21,46,69,94,90,80
C ． 21,32,46,40,80,69,90,94
D 21,32,46,40,80,69,90,94 D．． 90,69,80,46,21,32,94,40
【北方交通大学【北方交通大学 2001 2001 2001 一、一、一、15 15 15 （（2分）
】 3939．直接插入排序在最好情况下的时间复杂度为（．直接插入排序在最好情况下的时间复杂度为（．直接插入排序在最好情况下的时间复杂度为（ ））【北京邮电大学【北京邮电大学 1999 1999 1999 一、一、一、5 5 5 （（2
分）】 A A．． O(logn) B O(logn) B．． O(n) C O(n) C．． O(n*logn) D O(n*logn) D．． O(n 2)
40. 40. 若用冒泡排序方法对序列若用冒泡排序方法对序列若用冒泡排序方法对序列{10,14,26,29,41,52}{10,14,26,29,41,52}{10,14,26,29,41,52}从大到小排序，从大到小排序，需进行需进行 （ ））
次比较。 A. 3 B. 10 C. 15 D. 25 A. 3 B. 10 C. 15 D. 25 【南京理工大学【南京理工大学【南京理工大学 1999 1999 1999 一、一、一、111111（（4分）】
类似本题的另外叙述有：
(1)(1)若用冒泡排序对关键字序列若用冒泡排序对关键字序列若用冒泡排序对关键字序列{18,16,14,12,10,8},{18,16,14,12,10,8},{18,16,14,12,10,8}，进行从小到大的排序，所需进行的关进行从小到大的排序，所需进行的关键字比较总次数是（键字比较总次数是（ ）） 【北京工商大学【
北京工商大学 2001 2001 2001 一、一、一、44（3分）
】 A. 10 B. 15 C. 21 D. 34
41. 41. 采用简单选择排序，比较次数与移动次数分别为采用简单选择排序，比较次数与移动次数分别为采用简单选择排序，比较次数与移动次数分别为( )( )( )。。【南京理工大学【南京理工大学 2000 2000 2000 一、一、一、1818（1.5分）】
A. O （n ）,O(logn)
B. O(logn),0(n*n)
C. 0(n*n),0(n)
D. 0(nlogn),0(n)
42. 42. 对序列对序列对序列{15{15{15，，9，7，8，2020，，-1-1，，4，} } 用希尔排序方法排序，经一趟后序列变为用希尔排序方法排序，经一趟后序列变为用希尔排序方法排序，经一趟后序列变为{15{15{15，，-l -l，，4，8，2020，，9，7}7}则该次采用的增量是则该次采用的增量是则该次采用的增量是 ( ) ( ) ( ) 【南京理工大学【南京理工大学【南京理工大学 1999 1999 1999 一、一、一、151515（（1分）
】 A. l B. 4 C. 3 D. 2
4343．对下列关键字序列用快速排序法进行排序时，速度最快的情形是（．对下列关键字序列用快速排序法进行排序时，速度最快的情形是（．对下列关键字序列用快速排序法进行排序时，速度最快的情形是（ ））
。 A ． {21,25,5,17,9,23,30} B {21,25,5,17,9,23,30} B．．{25,23,30,17,21,5,9}
C ． {21,9,17,30,25,23,5} {21,9,17,30,25,23,5} Ｄ．Ｄ．Ｄ． {5,9,17,21,23,25,30} {5,9,17,21,23,25,30} {5,9,17,21,23,25,30}【北方交通大学【北方交通大学【北方交通大学 2001 2001 2001 一、一、一、18 18 （2分）】
4444．．对关键码序列2828，，1616，，3232，，1212，，6060，，2，5，72快速排序，从小到大一次划分结果为（ ））
。 A. (2,5,12,16)26(60,32,72) B. (5,16,2,12)28(60,32,72)
C. (2,16,12,5)28(60,32,72)
D. (5,16,2,12)28(32,60,72) 【青岛大学【青岛大学 2000 2000 2000 三、三、4 （2分）】
4545．对．对n 个记录的线性表进行快速排序为减少算法的递归深度，以下叙述正确的是（个记录的线性表进行快速排序为减少算法的递归深度，以下叙述正确的是（ ）） A ．每次分区后，先处理较短的部分．每次分区后，先处理较短的部分 B B B．每次分区后，先处理较长的部分．每次分区后，先处理较长的部分．每次分区后，先处理较长的部分
C ．与算法每次分区后的处理顺序无关与算法每次分区后的处理顺序无关
D D D．．以上三者都不对以上三者都不对 【北方交通大学【北方交通大学 2000 2000 2000 二、二、5 5 （（2分）
】 4646．．当n 个整型数据是有序时，个整型数据是有序时，对这对这n 个数据用快速排序算法排序，个数据用快速排序算法排序，则时间复杂度是则时间复杂度是则时间复杂度是 ( ( 6 )，当用递归算法求n!n!时，时，算法的时间复杂度是算法的时间复杂度是 ( ( 7 )，则：(6)-(7)=（ ））
【南京理工大学1999 一、（6-76-7））
（4分）】 A. O(n) B. O(nlogn) C. O(n*n) D. O(logn) 4747．快速排序在最坏情况下的时间复杂度是．快速排序在最坏情况下的时间复杂度是．快速排序在最坏情况下的时间复杂度是( ),( ),( )，比比( )( )的性能差。的性能差。的性能差。
A ．O(NlogN)
B O(NlogN) B．．O(N 2)
C ) C．．O(N 3)
D ) D．堆排序．堆排序
E ．冒泡排序
F ．选择排序．选择排序
【山东工业大学【山东工业大学 1995 1995 1995 二、二、二、2 2 2 （（4分）
】 48. 48. 快速排序方法在（快速排序方法在（快速排序方法在（ ）情况下最不利于发挥其长处。）情况下最不利于发挥其长处。）情况下最不利于发挥其长处。 【燕山大学【燕山大学【燕山大学 2001 2001 2001 一、一、一、3 3 3 （（2分）】
A. A. 要排序的数据量太大要排序的数据量太大要排序的数据量太大
B. B. B. 要排序的数据中含有多个相同值要排序的数据中含有多个相同值要排序的数据中含有
多个相同值
C. C. 要排序的数据个数为奇数要排序的数据个数为奇数要排序的数据个数为奇数
D. D. D. 要排序的数据已基本有序要排序的数据已基本有序要排序的数据已基本有序 4949．．在含有n 个关键字的小根堆（堆顶元素最小）中，关键字最大的记录有可能存储在（ ））位置上。位置上。
A A．．ën/2û
B B．．ën/2û -1
C -1 C．．1
D 1 D．．ën/2û +2 +2 【中科院计算所【中科院计算所2000 2000 一、一、一、44（2分）】
50. 50. 以下序列不是堆的是以下序列不是堆的是以下序列不是堆的是( )( )( )。。【西安电子科技大学【西安电子科技大学 2001 2001应用一、应用一、5 5 5 （（2分）
】 A. (100,85,98,77,80,60,82,40,20,10,66) B. (100,98,85,82,80,77,66,60,40,20,10)
C. (10,20,40,60,66,77,80,82,85,98,100)
D. (100,85,40,77,80,60,66,98,82,10,20)
5151．下列四个序列中，哪一个是堆（．下列四个序列中，哪一个是堆（．下列四个序列中，哪一个是堆（ ））。 【北京工商大学【北京工商大学 2001 2001 2001 一、一、一、8 8 8 （（3分）
】 A. 75,65,30,15,25,45,20,10 B. 75,65,45,10,30,25,20,15
C. 75,45,65,30,15,25,20,10
D. 75,45,65,10,25,30,20,15
52. 52. 堆排序是堆排序是（ ））类排序，堆排序平均执行的时间复杂度和需要附加的存储空间复杂度分别是（）分别是（）
A. A. 插入插入插入
B. B. B. 交换交换交换
C. C. C. 归并归并归并
D. D. D. 基数基数基数
E. E. E. 选择选择选择
F. O F. O（（n 2）和O （1）
G. O G. O（（nlog 2n ）和O （1）
H. O H. O（（nlog 2n ）和O （n ） I. O I. O（（n 2）和O （n ） 【西北大学【西北大学【西北大学 2001 2001 2001 二、二、二、22】
5353．在对．在对n 个元素的序列进行排序时，堆排序所需要的附加存储空间是（个元素的序列进行排序时，堆排序所需要的附加存储空间是（ ））
。 A. O(log 2n) B. O(1) C. O(n) D. O(nlog 2n) n) 【西安电子科技大学【西安电子科技大学2001应用一、1010（（2分）
】 5454．． 对n n 个记录的文件进行堆排序，最坏情况下的执行时间是多少？（个记录的文件进行堆排序，最坏情况下的执行时间是多少？（个记录的文件进行堆排序，最坏情况下的执行时间是多少？（ ））
A ．O （log 2n ）
B ．O （n ）
C C．．O （nlog 2n ）
D D．．O （n*n n*n）） 【北方交通大学【北方交通大学 2001 2001 2001 一、一、一、99（2分）】
55. 55. 有一组数据有一组数据（1515，，9，7，8，2020，，-1-1，，7，4），用堆排序的筛选方法建立的初始堆为用堆排序的筛选方法建立的初始堆为 （ ））
A ．-1-1，，4，8，9，2020，，7，1515，，7
B 7 B．．-1-1，，7，1515，，7，4，8，2020，，9
C ．-1-1，，4，7，8，2020，，1515，，7，9
D 9 D．．A ，B ，C 均不对。均不对。 【南京理工大学【南京理工大学 1996 1996 1996 二、二、5（2分）】
发布评论