2024年4月30日发(作者：)
第10章 排序
排序
排序
一、选择题
1．某内排序方法的稳定性是指( )】
．某内排序方法的稳定性是指
( )。
( )
。 【南京理工大学 1997
【南京理工大学
1997 一、
1997
一、10
一、
10（
10
（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 (2
一、
3 (2分)】
A. 堆排序，冒泡排序
A.
堆排序，冒泡排序 B.
堆排序，冒泡排序
B. 快速排序，堆排序
B.
快速排序，堆排序
快速排序，堆排序
C. 直接选择排序，归并排序
C.
直接选择排序，归并排序 D.
直接选择排序，归并排序
D. 归并排序，冒泡排序
D.
归并排序，冒泡排序
归并排序，冒泡排序
4．稳定的排序方法是（ 】
．稳定的排序方法是（
）
） 【北方交通大学
【北方交通大学 2000
【北方交通大学
2000 二、
2000
二、3
二、
3（2分）
A．直接插入排序和快速排序 B
．直接插入排序和快速排序
B．折半插入排序和起泡排序
B
．折半插入排序和起泡排序
．折半插入排序和起泡排序
C．简单选择排序和四路归并排序 D
．简单选择排序和四路归并排序
D．树形选择排序和
D
．树形选择排序和shell排序
排序
5．下列排序方法中，哪一个是稳定的排序方法？（
．下列排序方法中，哪一个是稳定的排序方法？（
） 【北方交通大学
【北方交通大学 2001
【北方交通大学
2001 一、
2001
一、8
一、
8
（2分）】
A．直接选择排序 B
．直接选择排序
B．二分法插入排序
B
．二分法插入排序 C
．二分法插入排序
C．希尔排序
C
．希尔排序 D
．希尔排序
D．快速排序
D
．快速排序
．快速排序
6．若要求尽可能快地对序列进行稳定的排序，则应选（A
．若要求尽可能快地对序列进行稳定的排序，则应选（
A．快速排序 B
．快速排序
B．归并排序
B
．归并排序 C
．归并排序
C．冒
C
．冒
泡排序）。
【北京邮电大学 2001 】
【北京邮电大学
2001 一、
2001
一、5
一、
5（2分）
7．如果待排序序列中两个数据元素具有相同的值，在排序前后它们的相互位置发生颠倒，
则称该排序算法是不稳定的。（ ）就是不稳定的排序方法。【清华大学 1998 (2
）就是不稳定的排序方法。
【清华大学
1998 一、
1998
一、3
一、
3
分）】
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
2
n)的时间内完成对数组的排序，
n)
的时间内完成对数组的排序，且要求排序是稳定的，
的时间内完成对数组的排序，
且要求排序是稳定的，则可选择的排序方
法是（ 。
法是（
）
）
A. 快速排序
A.
快速排序 B.
快速排序
B. 堆排序
B.
堆排序 C.
堆排序
C. 归并排序
C.
归并排序 D.
归并排序
D. 直接插入排序
D.
直接插入排序
直接插入排序
【中国科技大学 1998 】 【中科院计算所 1998 】
【中国科技大学
1998 二、
1998
二、4
二、
4（2分）
【中科院计算所
1998 二、
1998
二、4
二、
4（2分）
10．下面的排序算法中，不稳定的是（
10
．下面的排序算法中，不稳定的是（
．下面的排序算法中，不稳定的是（
）
） 【北京工业大学 1999
【北京工业大学
1999 一、
1999
一、2 (2
一、
2 (2分)】
A.起泡排序
A.
起泡排序 B.
起泡排序
B.折半插入排序
B.
折半插入排序 C.
折半插入排序
C.简单选择排序
C.
简单选择排序 D.
简单选择排序
D.希尔排序
D.
希尔排序 E.
希尔排序
E.基数排序
E.
基数排序 F.
基数排序
F.堆
F.
堆
排序。
排序。
11．下列内部排序算法中：
11
．下列内部排序算法中：
．下列内部排序算法中：
【北京工业大学
【北京工业大学 2000
【北京工业大学
2000 一、
2000
一、1 (10
一、
1 (10分 每问2分)】
A．快速排序 B.
．快速排序
B.直接插入排序
B.
直接插入排序 C.
直接插入排序
C. 二路归并排序
C.
二路归并排序 D.
二路归并排序
D. 简单选择排序
D.
简单选择排序 E.
简单选择排序
E. 起泡排序
E.
起泡排序
起泡排序
F. 堆排序
F.
堆排序
堆排序
（1） 其比较次数与序列初态无关的算法是（
其比较次数与序列初态无关的算法是（
）
） （
（2）不稳定的排序算法是（
）不稳定的排序算法是（
）
）
（3）在初始序列已基本有序（除去n个元素中的某k个元素后即呈有序，k< 个元素后即呈有序， k< k< ）的情况下， 排序效率最高的算法是（ 排序效率最高的算法是（ ） ） （4）排序的平均时间复杂度为O(n• O(n •logn)的算法是（ logn) 的算法是（ 的算法是（ ）为 ）为O(n• O(n •n)的算法是（ n) 的算法是（ 的算法是（ ） ） 12．排序趟数与序列的原始状态有关的排序方法是( )【北京航空航天大学 1999 12 ． 排序趟数与序列的原始状态有关的排序方法是 ( )排序法。 ( ) 排序法。 【北京航空航天大学 1999 一、9】 一、 9（2分） A．插入 A ．插入 B. ．插入 B. 选择 B. 选择 C. 选择 C. 冒泡 C. 冒泡 D. 冒泡 D. 快速 D. 快速 快速 13．下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是。 13 ．下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是。( ) ．下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是。 ( ) A．选择排序法 B. ．选择排序法 B. 插入排序法 B. 插入排序法 C. 插入排序法 C. 快速排序法 C. 快速排序法 D. 快速排序法 D. 堆积排序法 D. 堆积排序法 堆积排序法 【北京航空航天大学 2000 】 【北京航空航天大学 2000 一、 2000 一、10 一、 10（ 10 （2分） 14．对下列四种排序方法，在排序中关键字比较次数同记录初始排列无关的是 14 ．对下列四种排序方法，在排序中关键字比较次数同记录初始排列无关的是( ) ．对下列四种排序方法，在排序中关键字比较次数同记录初始排列无关的是 ( )。 ( ) 。 A．直接插入 B. ．直接插入 B. 二分法插入 B. 二分法插入 C. 二分法插入 C. 快速排序 C. 快速排序 D. 快速排序 D. 归并排序 D. 归并排序 归并排序 【南京理工大学 2000 】 【南京理工大学 2000 一、 2000 一、7 一、 7 （ 7 （1.5分） 15．在下列排序算法中,（ ）。【北京理工大学 2001 15 ． 在下列排序算法中 ,哪一个算法的时间复杂度与初始排序无关 ） 北京理工大学 2001 六、4 】 六、 4 （ 4 （2） A． 直接插入排序 B. 直接插入排序 B. 气泡排序 B. 气泡排序 C. 气泡排序 C. 快速排序 C. 快速排序 D. 快速排序 D. 直接选择排序 D. 直接选择排序 直接选择排序 16．比较次数与排序的初始状态无关的排序方法是【北方交通大学 2000 16 ．比较次数与排序的初始状态无关的排序方法是( ) ．比较次数与排序的初始状态无关的排序方法是 ( )。 ( ) 。 【北方交通大学 2000 二、 2000 二、2 二、 2 （2分）】 A．直接插入排序 B ．直接插入排序 B．起泡排序 B ．起泡排序 C ．起泡排序 C．快速排序 C ．快速排序 D ．快速排序 D．简单选择排序 D ．简单选择排序 ．简单选择排序 17．数据序列（ 17 ．数据序列（8 ．数据序列（ 8，9，10， 10 ，4，5，6，20， 20 ，1，2）只能是下列排序算法中的( ) ）只能是下列排序算法中的 ( )的两趟排 ( ) 的两趟排 序后的结果。 序后的结果。 A．选择排序 B. ．选择排序 B.冒泡排序 B. 冒泡排序 C. 冒泡排序 C.插入排序 C. 插入排序 D. 插入排序 D.堆排序 D. 堆排序 堆排序 【合肥工业大学】 【合肥工业大学 1999 【合肥工业大学 1999 一、 1999 一、3 一、 3 （ 3 （2分） 18．数据序列（ 18 ．数据序列（2 ．数据序列（ 2，1，4，9，8，10， 10 ，6，20）只能是下列排序算法中的 20 ）只能是下列排序算法中的( ) ）只能是下列排序算法中的 ( )的两趟排序后 ( ) 的两趟排序后 的结果。 的结果。 A. 快速排序 A. 快速排序 B. 快速排序 B. 冒泡排序 B. 冒泡排序 C. 冒泡排序 C. 选择排序 C. 选择排序 D. 选择排序 D. 插入排序 D. 插入排序 插入排序 【合肥工业大学 2000 】 【合肥工业大学 2000 一、 2000 一、3 一、 3 （ 3 （2分） 19．对一组数据（ 19 ．对一组数据（84 ．对一组数据（ 84， 84 ，47， 47 ，25， 25 ，15， 15 ，21）排序，数据的排列次序在排序的过程中的变化为 21 ）排序，数据的排列次序在排序的过程中的变化为 ）排序，数据的排列次序在排序的过程中的变化为 （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. 插入 插入 20．对序列 20 ．对序列{15 ．对序列 {15， {15 ，9，7，8，20， 20 ，-1， -1 ，4}进行排序，进行一趟后数据的排列变为 4} 进行排序，进行一趟后数据的排列变为{4 进行排序，进行一趟后数据的排列变为 {4， {4 ，9，-1， -1 ，8， 20，【南京理工大学 1998 】 20 ，7，15}；则采用的是（ 15} ；则采用的是（ ；则采用的是（ ）排序。 ）排序。 【南京理工大学 1998 一、 1998 一、8 一、 8（2分） A. 选择 A. 选择 B. 选择 B. 快速 B. 快速 C. 快速 C. 希尔 C. 希尔 D. 希尔 D. 冒泡 D. 冒泡 冒泡 21．若上题的数据经一趟排序后的排列为 21 ．若上题的数据经一趟排序后的排列为{9 ．若上题的数据经一趟排序后的排列为 {9， {9 ，15， 15 ，7，8，20， 20 ，-1， -1 ，4}，则采用的是（ 4} ，则采用的是（ ，则采用的是（ ） ） 排序。 排序。 A．选择 B. ．选择 B. 堆 B. 堆 C. 直接插入 C. 直接插入 D. 直接插入 D. 冒泡 D. 冒泡 冒泡 【南京理工大学 【南京理工大学 1998 【南京理工大学 1998 一、 1998 一、9 一、 9（2 分）】 22．下列排序算法中 22 ．下列排序算法中( ) ．下列排序算法中 ( )不能保证每趟排序至少能将一个元素放到其最终的位置上。 ( ) 不能保证每趟排序至少能将一个元素放到其最终的位置上。 不能保证每趟排序至少能将一个元素放到其最终的位置上。 A.快速排序 A. 快速排序 B. 快速排序 B. shell排序 C. 排序 C. 堆排序 C. 堆排序 D. 堆排序 D.冒泡排序 D. 冒泡排序 冒泡排序 【合肥工业大学 【合肥工业大学 2001 【合肥工业大学 2001 一、 2001 一、3 一、 3 （2分）】 23．下列排序算法中 23 ．下列排序算法中( ) ．下列排序算法中 ( )排序在一趟结束后不一定能选出一个元素放在其最终位置上。 ( ) 排序在一趟结束后不一定能选出一个元素放在其最终位置上。 排序在一趟结束后不一定能选出一个元素放在其最终位置上。 A. 选择 A. 选择 B. 选择 B. 冒泡 B. 冒泡 C. 冒泡 C. 归并 C. 归并 D. 归并 D. 堆 D. 堆 【南京理工大学 2001 】【哈尔滨工业大学 2001 】 【南京理工大学 2001 一、 2001 一、7 一、 7（1.5分） 【哈尔滨工业大学 2001 二、 2001 二、4 二、 4（2分） 24．下列序列中，（ ）是执行第一趟快速排序后所得的序列。 24 ．下列序列中， ）是执行第一趟快速排序后所得的序列。 ）是执行第一趟快速排序后所得的序列。 【福州大学 【福州大学 1998 【福州大学 1998 一、 1998 一、9 一、 9 (2分)】 A. [68， A. [68 ，11， 11 ，18， 18 ，69] [23， 69] [23 ，93， 93 ，73] B. [68， 73] B. [68 ，11， 11 ，69， 69 ，23] [18， 23] [18 ，93， 93 ，73] C. [93， C. [93 ，73] [68， 73] [68 ，11， 11 ，69， 69 ，23， 23 ，18] D. [68， 18] D. [68 ，11， 11 ，69， 69 ，23， 23 ，18] [93， 18] [93 ，73] 25．有一组数据（ 25 ．有一组数据（15 ．有一组数据（ 15， 15 ，9，7，8，20， 20 ，-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，15， 15 ，20 C．20， 20 ，15， 15 ，8，9，7，-1， -1 ，4，7 D. 9， 7 D. 9 ，4，7，8，7，-1， -1 ，15， 15 ，20 26．一组记录的关键码为（，则利用快速排序的方法，以第一个 26 ．一组记录的关键码为（46 ．一组记录的关键码为（ 46， 46 ，79， 79 ，56， 56 ，38， 38 ，40， 40 ，84） 84 ） 记录为基准得到的一次划分结果为（ 。 【燕山大学】 记录为基准得到的一次划分结果为（ ） ） 【燕山大学 2001 【燕山大学 2001 一、 2001 一、4 一、 4（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. 在下面的排序方法中，辅助空间为【南京理工大学 1999 27. 在下面的排序方法中，辅助空间为O（n）的是( ) ）的是 ( ) 。 ( ) 。 【南京理工大学 1999 一、 1999 一、17 一、 17 （1分）】 A．希尔排序 A ．希尔排序 B. ．希尔排序 B. 堆排序 B. 堆排序 C. 堆排序 C. 选择排序 C. 选择排序 D. 选择排序 D. 归并排序 D. 归并排序 归并排序 28．下列排序算法中，在待排序数据已有序时，花费时间反而最多的是 28 ．下列排序算法中，在待排序数据已有序时，花费时间反而最多的是( ) ．下列排序算法中，在待排序数据已有序时，花费时间反而最多的是 ( )排序。 ( ) 排序。 排序。 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 一、5 一、 5】 31. 就平均性能而言，目前最好的内排序方法是【西安电子科技大学 1998 31. 就平均性能而言，目前最好的内排序方法是( ) 就平均性能而言，目前最好的内排序方法是 ( )排序法。 ( ) 排序法。 【西安电子科技大学 1998 一、9 (2】 一、 9 (2分） A. 冒泡希尔插入 C. C. 交换 A. 冒泡 B. 冒泡 B. 希尔插入 B. 希尔插入 C. 交换 D. 交换 D. 快速 D. 快速 快速 32．如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用 32 ．如果只想得到 （ ）方法最快。 ）方法最快。 ）方法最快。 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 (3 一、 5 (3分)】 A. 快速排序 A. 快速排序 B. 快速排序 B. 归并排序 B. 归并排序 C. 归并排序 C. 堆排序 C. 堆排序 D. 堆排序 D.基数排序 D. 基数排序 基数排序 排序 排序 33．在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是（ 33 ．在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是（ ．在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是（ ） ） 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 二、6 二、 6】 A.插入排序 A. 插入排序 B. 插入排序 B. 选择排序 B. 选择排序 C. 选择排序 C. 快速排序 C. 快速排序 D. 快速排序 D. 归并排序 D. 归并排序 归并排序 34．下列排序算法中，（ ）算法可能会出现下面情况：在最后一趟开始之前，所有元素 34 ．下列排序算法中， ）算法可能会出现下面情况：在最后一趟开始之前，所有元素 都不在其最终的位置上。【南开大学 2000 【南开大学 2000 一、 2000 一、4 一、 4】 【西北大学 2001 【西北大学 2001 二、 2001 二、1 二、 1】 A. 堆排序 A. 堆排序 B. 堆排序 B. 冒泡排序 B. 冒泡排序 C. 冒泡排序 C. 快速排序 C. 快速排序 D. 快速排序 D. 插入排序 D. 插入排序 插入排序 35. 下列排序算法中，（8分）】 35. 下列排序算法中，占用辅助空间最多的是：( ) 【厦门大学 2002 【厦门大学 2002 五、 2002 五、2 A. 归并排序 A. 归并排序 B. 归并排序 B. 快速排序 B. 快速排序 C. 快速排序 C. 希尔排序 C. 希尔排序 D. 希尔排序 D. 堆排序 D. 堆排序 36．从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在 36 ． 已排序序列的合适位置，该排序方法称为( )【北京航空航天大学 1999 已排序序列的合适位置，该排序方法称为 ( )排序法。 ( ) 排序法。 【北京航空航天大学 1999 一、 1999 一、8 一、 8 （2分）】 A. 插入 A. 插入 B. 插入 B. 选择 B. 选择 C. 选择 C. 希尔 C. 希尔 D. 希尔 D. 二路归并 D. 二路归并 二路归并 37. 在排序算法中， 37. 在排序算法中，每次从未排序的记录中挑出最小（或最大）关键码字的记录， 在排序算法中， 每次从未排序的记录中挑出最小（或最大）关键码字的记录，加入到已 每次从未排序的记录中挑出最小（或最大）关键码字的记录， 加入到已 排序记录的末尾，该排序方法是（ 。【中山大学 1999 排序记录的末尾，该排序方法是（ ） ） 【中山大学 1999 一、 1999 一、11 一、 11】 11 】 A. 选择 A. 选择 B. 选择 B. 冒泡 B. 冒泡 C. 冒泡 C. 插入 C. 插入 D. 插入 D. 堆 D. 堆 38．用直接插入排序方法对下面四个序列进行排序（由小到大），元素比较次数最少的是 38 ．用直接插入排序方法对下面四个序列进行排序（由小到大） （ ）。 ） 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分） 39．直接插入排序在最好情况下的时间复杂度为（【北京邮电大学 1999 39 ．直接插入排序在最好情况下的时间复杂度为（ ．直接插入排序在最好情况下的时间复杂度为（ ） ） 【北京邮电大学 1999 一、 1999 一、5 一、 5 （ 5 （2 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) 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 一、11 一、 11（ 11 （4 分）】 类似本题的另外叙述有： (1)若用冒泡排序对关键字序列 (1) 若用冒泡排序对关键字序列{18,16,14,12,10,8}, 若用冒泡排序对关键字序列 {18,16,14,12,10,8},进行从小到大的排序，所需进行的关 {18,16,14,12,10,8}, 进行从小到大的排序，所需进行的关 键字比较总次数是（ 】 键字比较总次数是（ ） ） 【北京工商大学 2001 【北京工商大学 2001 一、 2001 一、4 一、 4（3分） A. 10 B. 15 C. 21 D. 34 41. 采用简单选择排序，比较次数与移动次数分别为【南京理工大学 2000 41. 采用简单选择排序，比较次数与移动次数分别为( ) 采用简单选择排序，比较次数与移动次数分别为 ( )。 ( ) 。 【南京理工大学 2000 一、 2000 一、18 一、 18 （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，20， 20 ，-1， -1 ，4，} 用希尔排序方法排序，经一趟后序列变为 } 用希尔排序方法排序，经一趟后序列变为{15 用希尔排序方法排序，经一趟后序列变为 {15， {15 ，-l， -l ， 4，8，20，】 20 ，9，7}则该次采用的增量是 7} 则该次采用的增量是 ( ) 则该次采用的增量是 ( ) 【南京理工大学 ( ) 【南京理工大学 1999 【南京理工大学 1999 一、 1999 一、15 一、 15（ 15 （1分） A. l B. 4 C. 3 D. 2 43．对下列关键字序列用快速排序法进行排序时，速度最快的情形是（。 43 ．对下列关键字序列用快速排序法进行排序时，速度最快的情形是（ ．对下列关键字序列用快速排序法进行排序时，速度最快的情形是（ ） ） 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分）】 44．对关键码序列28，16，32，12，60，2，5，72快速排序，从小到大一次划分结果为（ ）。 44 ． 28 ， 16 ， 32 ， 12 ， 60 ， ） 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 4 （2 【青岛大学 2000 三、 2000 三、 分）】 45．对 45 ．对n个记录的线性表进行快速排序为减少算法的递归深度，以下叙述正确的是（ 个记录的线性表进行快速排序为减少算法的递归深度，以下叙述正确的是（ ） ） A．每次分区后，先处理较短的部分 B ．每次分区后，先处理较短的部分 B．每次分区后，先处理较长的部分 B ．每次分区后，先处理较长的部分 ．每次分区后，先处理较长的部分 C．与算法每次分区后的处理顺序无关 D 与算法每次分区后的处理顺序无关 D． D ．以上三者都不对 以上三者都不对 【北方交通大学 2000 【北方交通大学 2000 二、 2000 二、 5 （】 5 （2分） 46．6 )， 46 ．当n个整型数据是有序时，对这 个整型数据是有序时， 对这n个数据用快速排序算法排序，则时间复杂度是 个数据用快速排序算法排序， 则时间复杂度是 ( 则时间复杂度是 ( 当用递归算法求n!时，7 )，则：(6)-(7)=（ ）【南京理工大学1999 n! 时，算法的时间复杂度是 ( 算法的时间复杂度是 ( ） 一、（6-7）（4分）】 6-7 ） A. O(n) B. O(nlogn) C. O(n*n) D. O(logn) 47．快速排序在最坏情况下的时间复杂度是 47 ．快速排序在最坏情况下的时间复杂度是( ), ．快速排序在最坏情况下的时间复杂度是 ( ),比 ( ), 比( )的性能差。 ( ) 的性能差。 的性能差。 23 A．O(NlogN) B． O(NlogN) B ．O(N) C． ) C ．O(N) 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. 要排序的数据已基本有序 要排序的数据已基本有序 49．在含有n个关键字的小根堆（堆顶元素最小）中，关键字最大的记录有可能存储在（ ） 49 ． ） 位置上。 位置上。 A． A ． ë n/2 û B． B ． ë n/2 û -1 C． -1 C ．1 D． 1 D ． ë n/2 û +2 【中科院计算所 +2 【中科院计算所2000 一、 2000 一、4 一、 4 （2分）】 50. 以下序列不是堆的是【西安电子科技大学 2001】 50. 以下序列不是堆的是( ) 以下序列不是堆的是 ( )。 ( ) 。 【西安电子科技大学 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) 51．下列四个序列中，哪一个是堆（。 【北京工商大学 2001 】 51 ．下列四个序列中，哪一个是堆（ ．下列四个序列中，哪一个是堆（ ） ） 【北京工商大学 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. 选择 选择 2 F. O（ F. O （n）和O（1） G. O（ G. O （nlog 2 n）和O（1） 2 H. O（ H. O （nlog 2 n）和O（n） I. O（ I. O （n）和O（n） 【西北大学 【西北大学 2001 【西北大学 2001 二、 2001 二、2 二、 2】 53．在对。 53 ．在对n个元素的序列进行排序时，堆排序所需要的附加存储空间是（ 个元素的序列进行排序时，堆排序所需要的附加存储空间是（ ） ） A. O(log 2 n) B. O(1) C. O(n) D. O(nlog 2 n) 【西安电子科技大学 n) 【西安电子科技大学2001应用一、 10（】 10 （2分） 54． 54 ． 对n 个记录的文件进行堆排序，最坏情况下的执行时间是多少？（ n 个记录的文件进行堆排序，最坏情况下的执行时间是多少？（ 个记录的文件进行堆排序，最坏情况下的执行时间是多少？（ ） ） A．O（log 2 n）B．O（n） C． C ．O（nlog 2 n） D． D ．O（n*n） n*n ） 【北方交通大学 2001 【北方交通大学 2001 一、 2001 一、9 一、 9 （2分）】 55. 有一组数据（15，9，7，8，20，-1，7，4），用堆排序的筛选方法建立的初始堆为 （ ） 55. 有一组数据 15 ， 20 ， -1 ， 用堆排序的筛选方法建立的初始堆为 ） A．-1， -1 ，4，8，9，20， 20 ，7，15， 15 ，7 B． 7 B ．-1， -1 ，7，15， 15 ，7，4，8，20， 20 ，9 C．-1， -1 ，4，7，8，20， 20 ，15， 15 ，7，9 D． 9 D ．A，B，C均不对。 均不对。 【南京理工大学 1996 【南京理工大学 1996 二、 1996 二、 5（2分）】 56. 归并排序中，归并的趟数是【南京理工大学 2000 】 56. 归并排序中，归并的趟数是( ) 归并排序中，归并的趟数是 ( )。 ( ) 。 【南京理工大学 2000 一、 2000 一、19 一、 19（ 19 （1.5分） A．O（n） B． B ．O(logn) C． O(logn) C ．O(nlogn) D． O(nlogn) D ．O(n*n) 类似本题的另外叙述有： (1)归并排序的时间复杂性是（。 【中山大学 1999 (1) 归并排序的时间复杂性是（ 归并排序的时间复杂性是（ ） ） 【中山大学 1999 一、 1999 一、12 一、 12】 12 】 A.O（） D. O（） A.O （N*N） N*N ） B. O（ B. O （N） C. O（ C. O （N*LOG（ N*LOG （N） D. O （LOG（ LOG （N） 57． 57 ． 在排序算法中每一项都与其它各项进行比较，计算出小于该项的项的个数，以确定该 项的位置叫( ) 项的位置叫 ( ) A．插入排序 B枚举排序 C选择排序 D交换排序【北京邮电大学 2000 6 （20/8 插入排序 B． B ． 枚举排序 C． C ． 选择排序 D． D ． 【北京邮电大学 2000 二、 2000 二、 分）】 58．就排序算法所用的辅助空间而言，堆排序，快速排序，归并排序的关系是 58 ．就排序算法所用的辅助空间而言，堆排序，快速排序，归并排序的关系是 ．就排序算法所用的辅助空间而言，堆排序，快速排序，归并排序的关系是 （ ） ） A．堆排序〈 ．堆排序〈 快速排序〈归并排序 快速排序〈归并排序 B．堆排序〈 ．堆排序〈 归并排序〈 归并排序〈 快速排序 快速排序 C．堆排序〉 ．堆排序〉 归并排序 归并排序 〉快速排序 〉快速排序 D．堆排序 > ．堆排序 > 快速排序 > 快速排序 > 快速排序 > 归并排序 > 归并排序 归并排序 E．以上答案都不对 E ．以上答案都不对 ．以上答案都不对 【西安交通大学 【西安交通大学 1996 【西安交通大学 1996 三、 1996 三、1 (3 三、 1 (3分)】 59．排序方法有许多种，（1）法从未排序的序列中依次取出元素，与已排序序列（初始时为 59 ．排序方法有许多种， 空）中的元素作比较，将其放入已排序序列的正确位置上；（2）法从未排序的序列中挑选元 素，并将其依次放入已排序序列（初始时为空）的一端； 素，并将其依次放入已排序序列（初始时为空）的一端； 交换排序方法是对序列中的元素 进行一系列比较，当被比较的两元素逆序时，进行交换；（3）和（4 ）和（ 4）是基于这类方法的两 种排序方法， （5）法是基于选择排序的一种排序方法， 种排序方法， 而（4 而（ 4）是比（3 ）是比（ 3）效率更高的方法； 是完全二叉树结构的一个重要应用。 】 是完全二叉树结构的一个重要应用。 【北方交通大学 1999 【北方交通大学 1999 一、 1999 一、3 一、 3 （ 3 （5分） （1）--（ -- （5）: A．选择排序 : A ．选择排序 B ．选择排序 B．快速排序 B ．快速排序 C ．快速排序 C．插入排序 C ．插入排序 D ．插入排序 D．起泡排序 D ．起泡排序 ．起泡排序 E．归并排序 F ．归并排序 F． F ．shell排序 G 排序 G．堆排序 G ．堆排序 H ．堆排序 H．基数排序 H ．基数排序 ．基数排序 类似本题的另外叙述有： （1）排序的方法有很多种，（ ） ）法从未排序的序列中依次取出元素与已排序序列中的 元素比较，将其放在已排序序列的正确位置上；（ ）法从未排序序列中挑选元素，并将 ）法从未排序序列中挑选元素，并将 其依次放入已排序序列的一端；交换排序法是对序列中的元素进行一系列比较，当被比较的 两元素逆序时，进行交换。（ ）和（ ）和（ ）和（ ）是基于这类方法的两种排序方法，而 ）是基于这类方法的两种排序方法，而 ( ) ）是基于这类方法的两种排序方法，而 ( ) 是比( ) 是比 ( )效率更高的方法。供选择的答案： ( ) 效率更高的方法。供选择的答案： 效率更高的方法。供选择的答案： A. 快速排序 A. 快速排序 B. 快速排序 B. 选择排序 B. 选择排序 C. 选择排序 C. 归并排序 C. 归并排序 D 归并排序 D．冒泡排序 D ．冒泡排序 E ．冒泡排序 E．直接 E ．直接 插入排序 【山东大学 1998 】 【山东大学 1998 三、 1998 三、2 (5 三、 2 (5分)】 【山东工业大学 2000 【山东工业大学 2000 三、 2000 三、2 三、 2 （ 2 （7分） 60．设要将序列（ 60 ．设要将序列（q,h,c,y,p,a,m,s,r,d,f,x ．设要将序列（ q,h,c,y,p,a,m,s,r,d,f,x） q,h,c,y,p,a,m,s,r,d,f,x ） 中的关键码按字母升序重新排序， 中的关键码按字母升序重新排序， 中的关键码按字母升序重新排序， （1）（ ）是初始步长为 ）是初始步长为4的shell排序一趟扫描的结果； 排序一趟扫描的结果； （ （2）（ ）是对排序初始 ）是对排序初始 建堆的结果； 建堆的结果； （3）（ ）（ ）是以第一个元素为分界元素的快速一趟扫描的结果。 ）是以第一个元素为分界元素的快速一趟扫描的结果。 ）是以第一个元素为分界元素的快速一趟扫描的结果。 从下面供选择的答案中选出正确答案填入括号内。 】 从下面供选择的答案中选出正确答案填入括号内。 【厦门大学 2000 【厦门大学 2000 六、 2000 六、3 六、 3 （ 3 （16%/3分） A. f ,h ,c ,d ,p ,a ,m ,q ,r ,s A. f ,h ,c ,d ,p ,a ,m ,q ,r ,s ,y ,x B. p ,q ,r ,s ,y ,x B. p ,a ,c ,s ,y ,x B. p ,a ,c ,s ,q ,d ,a ,c ,s ,q ,d ,f ,x ,q ,d ,f ,x ,r ,h ,m ,y ,f ,x ,r ,h ,m ,y C. a ,d ,c ,r ,f ,q ,m ,s ,y ,p C. a ,d ,c ,r ,f ,q ,m ,s ,y ,p ,h ,x D. h ,s ,y ,p ,h ,x D. h ,c ,q ,p ,h ,x D. h ,c ,q ,p ,a ,m ,c ,q ,p ,a ,m ,s ,r ,a ,m ,s ,r ,d ,f ,x ,y ,s ,r ,d ,f ,x ,y E. h ,q ,c ,y ,a ,p ,m ,s ,d ,r ,f ,x 类似本题的另外叙述有： （1）在内排序的过程中, ）在内排序的过程中 ,通常需要对待排序的关键码进行多编扫描, 通常需要对待排序的关键码进行多编扫描 ,采用不同重新排序 方法,设要将序列 方法 ,会产生不同的排序中间结果。 设要将序列 中的关键码按字 母序的升序排列，则( 1 ) 母序的升序排列，则 ( 1 )是冒泡排序一趟扫描的结果 ( 1 ) 是冒泡排序一趟扫描的结果,( 2 ) 是冒泡排序一趟扫描的结果 ,( 2 )是初始步长为 ,( 2 ) 是初始步长为4的希尔 (SHELL)排序一趟扫描的结果 (SHELL) 排序一趟扫描的结果,( 3 ) 排序一趟扫描的结果 ,( 3 ) 是合并排序一趟扫描的结果 ,( 3 ) 是合并排序一趟扫描的结果,( 4 ) 是合并排序一趟扫描的结果 ,( 4 )是以第一个元 ,( 4 ) 是以第一个元 素为分界元素的快速排序一趟扫描的结果,( 5 )供选择的答案: 素为分界元素的快速排序一趟扫描的结果 ,( 5 )是堆排序初始建堆的结果。 ,( 5 ) 是堆排序初始建堆的结果。 供选择的答案 : 【上海海运学院 1997 】 【上海海运学院 1997 二、 1997 二、3 二、 3 （ 3 （5分） 1-5:A. f,h,c,d,p,a,m,q,r,s,y,x B. p,a,c,s,q,d,f,x,r,h,m,y C. a,d,c,r,f,q,m,s,y,p,h,x D. h,c,q,p,a,m,s,r,d,f,x,y E. h,q,c,y,a,p,m,s,d,r,f,x 61．对由 61 ．对由n个记录所组成的表按关键码排序时, 个记录所组成的表按关键码排序时 ,下列各个常用排序算法的平均比较次数分别 是:二路归并排序为( 1 ), 二路归并排序为 ( 1 ),直接插入排序为 ( 1 ), 直接插入排序为( 2 ), 直接插入排序为 ( 2 ),快速排序为 ( 2 ), 快速排序为( 3 ), 快速排序为 ( 3 ),其中 ( 3 ), 其中, 其中 ,归并排 序和快速排序所需要的辅助存储分别是( 4 ) 序和快速排序所需要的辅助存储分别是 ( 4 )和 ( 4 ) 和( 5 )。 ( 5 ) 。 【上海海运学院 【上海海运学院 1998 【上海海运学院 1998 二、 1998 二、 4 （】 4 （5分） 22 1-5:A. O(1) B. O（nlog 2 n） C. O（n） D. O（n） E. O（n(log 2 n)） F. O（log 2 n） 62．将两个各有 62 ．将两个各有N个元素的有序表归并成一个有序表, 个元素的有序表归并成一个有序表 ,其最少的比较次数是( ) 其最少的比较次数是 ( ) A．N B． N B ．2N-1 C． 2N-1 C ．2N D． 2N D ．N-1 【中科院计算所 1998 】 【中国科技大学 1998 】 【中科院计算所 1998 二、 1998 二、7 二、 7 （ 7 （2分） 【中国科技大学 1998 二、 1998 二、7 二、 7 （ 7 （2分） 63. 基于比较方法的 63. 基于比较方法的n个数据的内部排序。最坏情况下的时间复杂度能达到的最好下界是 （ ）。 ） A. O(nlogn) B. O(logn) C. O(n) D. O(n*n) 【南京理工大学】 O(n*n) 【南京理工大学 1996 【南京理工大学 1996 一、 1996 一、2 一、 2 （ 2 （2分） 64． 64 ．已知待排序的n个元素可分为n/k个组，每个组包含k个元素，且任一组内的各元素均 分别大于前一组内的所有元素和小于后一组内的所有元素，若采用基于比较的排序，其 时间下界应为（ 。 时间下界应为（ ） ） A. O(nlog 2 n) B. O(nlog 2 k) C. O(klog 2 n) D. O(klog 2 k) 【中国科技大学 k) 【中国科技大学 1998 【中国科技大学 1998 二、 1998 二、 9 （】 9 （2分） 类似本题的另外叙述有： (1)已知待排序的每个组包含K个元素，且任一组内的各元素 (1) 已知待排序的N个元素可分为N/K个组， 均分别大于前一组内的所有元素和小于后一组内的所有元素, 均分别大于前一组内的所有元素和小于后一组内的所有元素 ,若采用基于比较的排序, 若采用基于比较的排序 ,其时 间下界应为( ) 间下界应为 ( ) A. O(klog 2 k) B. O(klog 2 n) C. O(nlog 2 k) D. O(nlog 2 n) 【中科院计算所 1998 【中科院计算所 1998 二、 1998 二、9 （2 分）】 65．采用败者树进行 65 ．采用败者树进行k路平衡归并的外部排序算法，其总的归并效率与k （ k （ ） ） A． 有关 B 有关 B．无关 B ．无关 ．无关 【北京工业大学 【北京工业大学 2000 【北京工业大学 2000 一 2000 一 、2 (3分)】 66．采用败者树进行。 66 ．采用败者树进行K路平衡归并时，总的（包括访外）归并效率与K（ ） ） A．有关 B ．有关 B．无关 B ．无关 ．无关 【北京工业大学 【北京工业大学 2001 【北京工业大学 2001 一、 2001 一、4 (2 一、 4 (2分)】 二、判断题： 1．当待排序的元素很大时，为了交换元素的位置，移动元素要占用较多的时间，这是影响 时间复杂度的主要因素。（ 时间复杂度的主要因素。（ ）【长沙铁道学院 ）【长沙铁道学院 1998 ）【长沙铁道学院 1998 一、 1998 一、10 (1 一、 10 (1分)】 2．内排序要求数据一定要以顺序方式存储。 】 ．内排序要求数据一定要以顺序方式存储。 （ ） ）【南京理工大学 1997 【南京理工大学 1997 二、 1997 二、2 二、 2（2分） 3．排序算法中的比较次数与初始元素序列的排列无关。（） ．排序算法中的比较次数与初始元素序列的排列无关。 （）【南京航空航天大学 1997 【南京航空航天大学 1997 一、 1997 一、 8 （】 8 （1分） 4．排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。（ ．排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。（ ） ） 【南京航空航天大学 1996 】 【南京航空航天大学 1996 六、 1996 六、9 六、 9 （ 9 （1分） 5．在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该 算法是不稳定的。（ 算法是不稳定的。（ ）【上海交通大学 ）【上海交通大学 1998 ）【上海交通大学 1998 一、 1998 一、18 一、 18】 18 】 6．直接选择排序算法在最好情况下的时间复杂度为O（N）。（ ）【合肥工业大学 2001 【合肥工业大学 2001 二、 2001 二、 10（】 10 （1分） 7．两分法插入排序所需比较次数与待排序记录的初始排列状态相关。（）【上海交通大学 1998 上海交通大学 1998 一、15 一、 15】 15 】 8．在初始数据表已经有序时，快速排序算法的时间复杂度为O(nlog 2 n )。（ n ) 。（ 。（ ） ） 【合肥工业大学 2000 】 【合肥工业大学 2000 二、 2000 二、9 二、 9（1分） 9．在待排数据基本有序的情况下，快速排序效果最好。（ ．在待排数据基本有序的情况下，快速排序效果最好。 （ ） ）【南京理工大学 1997 【南京理工大学 1997 二、 1997 二、 4（2分）】 10．当待排序记录已经从小到大排序或者已经从大到小排序时，快速排序的执行时间最省。 10 ．当待排序记录已经从小到大排序或者已经从大到小排序时，快速排序的执行时间最省。 （ ） ） 【上海交通大学 1998 【上海交通大学 1998 一、 1998 一、16 一、 16】 16 】 11．快速排序的速度在所有排序方法中为最快 11 ．快速排序的速度在所有排序方法中为最快, ．快速排序的速度在所有排序方法中为最快 ,而且所需附加空间也最少。（ 而且所需附加空间也最少。（ ） ） 【北京邮电大学 1998 】 【北京邮电大学 1998 一、 1998 一、7 一、 7 （ 7 （2分） 12．堆肯定是一棵平衡二叉树。（】 12 ．堆肯定是一棵平衡二叉树。（ ．堆肯定是一棵平衡二叉树。（ ）【南京航空航天大学 ）【南京航空航天大学 1997 ）【南京航空航天大学 1997 一、 1997 一、6 一、 6 （ 6 （1分） 13．堆是满二叉树。（】 13 ．堆是满二叉树。（ ．堆是满二叉树。（ ）【南京航空航天大学 ）【南京航空航天大学 1996 ）【南京航空航天大学 1996 六、 1996 六、6 六、 6 （ 6 （1分） 14．（101， 14 ． 101 ，88， 88 ，46， 46 ，70， 70 ，34， 34 ，39， 39 ，45， 45 ，58， 58 ，66， 66 ，10）是堆。（ 10 ）是堆。（ ）是堆。（ ）【北京邮电大学 1999 ）【北京邮电大学 1999 二、 1999 二、 1 （】 1 （2分） 15．在用堆排序算法排序时，如果要进行增序排序，则需要采用“大根堆”。（ 15 ．在用堆排序算法排序时，如果要进行增序排序，则需要采用“大根堆” 。（ ） ） 【合肥工业大学 2000 】 【合肥工业大学 2000 二、 2000 二、10 二、 10（ 10 （1分） 16．堆排序是稳定的排序方法。（ 16 ．堆排序是稳定的排序方法。（ ．堆排序是稳定的排序方法。（ ）【上海交通大学 ）【上海交通大学 1998 ）【上海交通大学 1998 一、 1998 一、19 一、 19】 19 】 17．归并排序辅助存储为。（ 】 17 ．归并排序辅助存储为O（1） 。（ ）【青岛大学 ）【青岛大学 2000 ）【青岛大学 2000 四、 2000 四、9 四、 9（1分） 18．在分配排序时，最高位优先分配法比最低位优先分配法简单。（ ）【上海交通大学 1998 18 ． ） 【上海交通大学 1998 一、20 一、 20】 20 】 19． 冒泡排序和快速排序都是基于交换两个逆序元素的排序方法, 19 ． 冒泡排序和快速排序都是基于交换两个逆序元素的排序方法 ,冒泡排序算法的最坏时间 n 复杂性是O(n*n),而快速排序算法的最坏时间复杂性是 O(n*n), 而快速排序算法的最坏时间复杂性是O(nlog 2 ),所以快速排序比冒泡排 ), 所以快速排序比冒泡排 序算法效率更高。 序算法效率更高。 （ ） ） 【上海海运学院 1997 】 【上海海运学院 1997 一、 1997 一、9 一、 9（1分） 20．交换排序法是对序列中的元素进行一系列比较，当被比较的两个元素逆序时，进行交换， 20 ． 冒泡排序和快速排序是基于这类方法的两种排序方法，冒泡排序算法的最坏时间复杂性是 O（n*n）；所以快速排序比冒泡排序效 n*n ） ，而快速排序算法的最坏时间复杂性是O（nlog 2 n） 率更高。（ 率更高。（ ） ） 【上海海运学院 1998 】【上海海运学院 1995 】 【上海海运学院 1998 一、 1998 一、10 一、 10 （ 10 （1分） 【上海海运学院 1995 一、 1995 一、10 一、 10（ 10 （1分） 21．快速排序和归并排序在最坏情况下的比较次数都是 21 ．快速排序和归并排序在最坏情况下的比较次数都是O(nlog 2 n)。（ n) 。（ 。（ ） ） 【上海海运学院1996一、9】 一、 9（1分） 22．（ ）【北京邮电大学 2000 22 ．在任何情况下，归并排序都比简单插入排序快。 ） 【北京邮电大学 2000 一、 2000 一、4 （1 分）】 23．归并排序在任何情况下都比所有简单排序速度快。 23 ．归并排序在任何情况下都比所有简单排序速度快。（ ．归并排序在任何情况下都比所有简单排序速度快。 （ ） ）【北京邮电大学 2002 【北京邮电大学 2002 一、 2002 一、9 一、 9 （1分）】 24．快速排序总比简单排序快。（】 24 ．快速排序总比简单排序快。（ ．快速排序总比简单排序快。（ ）【东南大学 ）【东南大学 2001 ）【东南大学 2001 一、 2001 一、9 一、 9 （ 9 （1分） 25. 中序周游（遍历）平衡的二叉排序树，可得到最好排序的关键码序列。（ 25. 中序周游（遍历）平衡的二叉排序树，可得到最好排序的关键码序列。（ 中序周游（遍历）平衡的二叉排序树，可得到最好排序的关键码序列。（ ） ） 【中山大学 1994 】 【中山大学 1994 一、 1994 一、4 一、 4 （ 4 （2分） 26．外部排序是把外存文件调入内存, 26 ． 外部排序是把外存文件调入内存 ,可利用内部排序的方法进行排序, 可利用内部排序的方法进行排序 ,因此排序所花的时间 取决于内部排序的时间。( )】 取决于内部排序的时间。 ( )【北京邮电大学 ( ) 【北京邮电大学 1998 【北京邮电大学 1998 一、 1998 一、8 一、 8 （ 8 （2分） 27．在外部排序时，利用选择树方法在能容纳m个记录的内存缓冲区中产生的初始归并段的 27 ． 平均长度为2m个记录。( )】 个记录。 ( )【上海海运学院 ( ) 【上海海运学院 1999 【上海海运学院 1999 一、 1999 一、10 一、 10（ 10 （1分） 28．为提高在外排序过程中，对长度为 28 ．为提高在外排序过程中，对长度为N的初始序列进行“置换—选择”排序时，可以得到 的最大初始有序段的长度不超过N/2。 N/2 。( ) 29．排序速度，进行外排序时，必须选用最快的内排序算法。 29 ．排序速度，进行外排序时，必须选用最快的内排序算法。( ) ．排序速度，进行外排序时，必须选用最快的内排序算法。 ( ) 30．在完成外排序过程中，每个记录的 30 ．在完成外排序过程中，每个记录的I/O次数必定相等。( ) 次数必定相等。 ( )【大连海事大学 ( ) 【大连海事大学 2001 【大连海事大学 2001 一、 2001 一、 20 (每题 20 ( 每题1分)】 31．影响外排序的时间因素主要是内存与外设交换信息的总次数。( )【东北大学 1997 31 ． 【东北大学 1997 二、 1997 二、 5 (2分)】 三、填空题 1．若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的______ ．若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的 ______和记 ______ 和记 录的_____ 录的 _____。 _____ 。 【北京邮电大学 2001 】 【北京邮电大学 2001 二、 2001 二、7 二、 7 （ 7 （4分） 2. 外排序的基本操作过程是【西安电子科技大学 1998 】 2. 外排序的基本操作过程是_______ 外排序的基本操作过程是 _______和 _______ 和_______。 _______ 。 【西安电子科技大学 1998 二、 1998 二、3 二、 3 （ 3 （3分） （1）外部排序中两个相对独立的阶段是___ ）外部排序中两个相对独立的阶段是 ___和 ___ 和___。【西安电子科技大学 ___ 。【西安电子科技大学 1999 。【西安电子科技大学 1999软件 软件 一、8 一、 8 （2分）】 3. 属于不稳定排序的有【青岛大学 2002 】 3. 属于不稳定排序的有__________ 属于不稳定排序的有 __________。 __________ 。 【青岛大学 2002 三、 2002 三、5 三、 5 （ 5 （2分） 4．分别采用堆排序，快速排序，冒泡排序和归并排序，对初态为有序的表，则最省时间的 是_____算法，最费时间的是【福州大学 1998 _____ 算法，最费时间的是______ 算法，最费时间的是 ______算法。 ______ 算法。 【福州大学 1998 二、 1998 二、10 (2 二、 10 (2分)】 类似本题的另外叙述有： （1）设表中元素的初始状态是按健值递增的，分别用堆排序， 设表中元素的初始状态是按健值递增的， 分别用堆排序，快速排序，冒泡排序和归并 分别用堆排序， 快速排序，冒泡排序和归并 排序方法对其进行排序（按递增顺序）， __排序最省时间，__排序最费时间。【厦门大学 2001 __ 排序最省时间， __ 排序最费时间。 【厦门大学 2001 一、5 一、 5 （ 5 （14%/5分）】 分）】 2 5. 不受待排序初始序列的影响，时间复杂度为 5. 不受待排序初始序列的影响，时间复杂度为O(N)的排序算法是_____ 的排序算法是 _____，在排序算法的最 _____ ，在排序算法的最 后一趟开始之前，所有元素都可能不在其最终位置上的排序算法是_____【中国人民大学 所有元素都可能不在其最终位置上的排序算法是 _____。 _____ 。 【中国人民大学 2001 一、 2001 一、3 一、 3 （ 3 （2分）】 分）】 6．直接插入排序用监视哨的作用是_______【南京理工大学 2001 】 ．直接插入排序用监视哨的作用是 _______。 _______ 。 【南京理工大学 2001 二、 2001 二、8 二、 8 （ 8 （2分） 7．对n个记录的表]进行简单选择排序，所需进行的关键字间的比较次数为_______ ] 进行简单选择排序， 所需进行的关键字间的比较次数为 _______。 _______ 。 【华中理工大学 2000 】 【华中理工大学 2000 一、 2000 一、10 一、 10 （ 10 （1分） 8. 用链表表示的数据的简单选择排序，结点的域为数据域 8. 用链表表示的数据的简单选择排序，结点的域为数据域data ，指针域 data ，指针域 next ，指针域 next ；链表首 next ；链表首 指针为head ，链表无头结点。 head ，链表无头结点。 ，链表无头结点。 selectsort(head) p=head; while (p(1)_______) {q=p; r=(2)_______ while((3)______ ) {if ((4)_______ ) q=r; r=(5)_______ ; } tmp=q->data; q->data=p->data; p->data=tmp; p= (6)_______ ; } 【南京理工大学】 } 【南京理工大学 2000 【南京理工大学 2000 三、 2000 三、2 三、 2 （ 2 （6分） 9．下面的c函数实现对链表head进行选择排序的算法, 进行选择排序的算法 ,排序完毕, 排序完毕 ,链表中的结点按结点值从 小到大链接。请在空框处填上适当内容, 小到大链接。请在空框处填上适当内容 ,每个空框只填一个语句或一个表达式： 每个空框只填一个语句或一个表达式： #include typedef struct node {char data; struct node *link; }node; node *select(node *head) {node *p,*q,*r,*s; p=(node *)malloc(sizeof(node)); 类似本题的另外叙述有： p->link=head; head=p; while(p->link!=null) {q=p->link; r=p; while ((1)____) { if (q->link->data q=q->link; } if ((2)____) {s=r->link; r->link=s->link; s->link= ((3)_____); ((4)_____);} ((5)____) ; } p=head; head=head->link; free(p); return(head); } 【复旦大学】 } 【复旦大学 1999 【复旦大学 1999 六（ 1999 六（15 六（ 15分） 10．下面的排序算法的思想是：第一趟比较将最小的元素放在r[1]中，最大的元素放在r[n] 10 ． r[1] 中， 中，第二趟比较将次小的放在r[2]中，将次大的放在 r[2] 中，将次大的放在r[n-1]中，„ r[n-1] 中，„,依次下去，直到待排 序列为递增序。（注：<-->。 （注： <-->）代表两个变量的数据交换） <--> ）代表两个变量的数据交换） void sort(SqList &r,int n) { i=1; while((1)__) { min=max=1; for (j=i+1;(2)____ ;++j) {if((3)____) min=j; else if(r[j].key>r[max].key) max=j; } if((4)_____) r[min] < ---- >r[j]; if(max!=n-i+1){if ((5)___) r[min] < ---- > r[n-i+1]; else ((6)__); } i++; } }//sort 【南京理工大学】 }//sort 【南京理工大学 2001 【南京理工大学 2001 三、 2001 三、2 三、 2 （ 2 （10分） 11．表插入排序的基本思想是在结点中设一指针字段，插入 11 ．表插入排序的基本思想是在结点中设一指针字段，插入Ri时Rl到Ri-1己经用指针按 排序码不减次序链结起夹，这时采用顺序比较的方法找到Ri应插入的位置，做链表插入。 如此反复，直到把Rn插入为止。 插入为止。 （(6分)请完成下列表插人的算法；【山东工业大学 2000 （16分）】 山东大学 1998 【 （1） 山东工业大学 2000 五 2000 五 山东大学 1998 五】 五】 ①. R[0].LINK← . R[0].LINK ←(1)___; R[N].LINK← (1)___; R[N].LINK ←(2)___; ②. 循环， . 循环，I 循环， I以-1为步长，从(3)___ 为步长，从 (3)___到 (3)___ 到(4)___执行 (4)___ 执行 执行 （ （1）P← R[0].LINK; Q← R[0].LINK; Q ← 0 （2）循环，当P>0且(5)__ 时，反复执行 (5)__ 时，反复执行 时，反复执行 Q← Q ←P； P← P ←(6)___ （3）R[Q].LINK← R[Q].LINK ←I; R[I].LINK← I; R[I].LINK ←P （ （2）(2分) 表插入排序的最大比较次数是 ) 表插入排序的最大比较次数是(7)__ 表插入排序的最大比较次数是 (7)__； (7)__ ； （（2分）表插入排序的最小比较次数是(8)__ （3） 分）表插入排序的最小比较次数是 (8)__； (8)__ ； （（2分）记录移动的次数是(9)__ （4） 分）记录移动的次数是 (9)__； (9)__ ； （5）（2分）需要附加的存储空间是(10)__ 分）需要附加的存储空间是 (10)__； (10)__ ； （6）（2分）该排序算法是否是稳定的(11)____ 分）该排序算法是否是稳定的 (11)____。 (11)____ 。 12. 设用希尔排序对数组 12. 设用希尔排序对数组{98 设用希尔排序对数组 {98， {98 ，36， 36 ，-9， -9 ，0，47， 47 ，23， 23 ，1，8，10， 10 ，7}进行排序， 7} 进行排序，给出的步长（也 给出的步长 （也 称增量序列）依次是4，2，1则排序需__________ 则排序需 __________趟，写出第一趟结束后，数组中数据的 __________ 趟，写出第一趟结束后，数组中数据的 排列次序__________ 排列次序 __________。 __________ 。 【南京理工大学 1997 】 【南京理工大学 1997 三、 1997 三、5 三、 5 （ 5 （2分） 13．从平均时间性能而言，【青岛大学 2001 】 13 ．从平均时间性能而言，__________ ．从平均时间性能而言， __________排序最佳。 __________ 排序最佳。 【青岛大学 2001 六、 2001 六、5 六、 5 （ 5 （3分） 14．对于 14 ．对于7个元素的集合{1 个元素的集合 {1， {1 ，2，3，4，5，6，7}进行快速排序，具有最小比较和交换次数 7} 进行快速排序，具有最小比较和交换次数 的初始排列次序为_____【长沙铁道学院 1997 的初始排列次序为 _____。 _____ 。 【长沙铁道学院 1997 二、 1997 二、1 (2 二、 1 (2分)】 15．快速排序在【长沙铁道学院 1998 15 ．快速排序在_____ ．快速排序在 _____的情况下最易发挥其长处。 _____ 的情况下最易发挥其长处。 【长沙铁道学院 1998 二、 1998 二、5 (2 二、 5 (2分)】 类似本题的另外叙述有： (1)快速排序法在 (1) 快速排序法在_____ 快速排序法在 _____情况下最不利于发挥其长处，在 _____ 情况下最不利于发挥其长处，在_____ 情况下最不利于发挥其长处，在 _____情况下最易发挥其长处。 _____ 情况下最易发挥其长处。 情况下最易发挥其长处。 【山东大学 2001 【山东大学 2001 三、 2001 三、5 (2 三、 5 (2分)】 16．【合肥工业大学 2001 16 ．在数据表有序时，快速排序算法的时间复杂度是____ 快速排序算法的时间复杂度是 ____。 ____ 。 【合肥工业大学 2001 三、 2001 三、10 （2 分）】 17．堆排序的算法时间复杂度为：【合肥工业大学 1999 】 17 ．堆排序的算法时间复杂度为：_____ ．堆排序的算法时间复杂度为： _____。 _____ 。 【合肥工业大学 1999 三、 1999 三、10 三、 10 （ 10 （2分） 18． 18 ．PROC sift(VAR r： PROC sift(VAR r ：listtype;k,m:integer); {假设 { 假设r[]中各元素满足堆的性质， r[] 中各元素满足堆的性质，本算法调整r[k]使整个序列 r[k] 使整个序列]中各元素 ] 中各元素 满足堆的性质。} 满足堆的性质。 } i:=k; j:= (1)__; x:=r[k].key; finished:=false; t:=r[k]; WHILE (j<=m) AND NOT finished DO [IF(j IF x<=r[j].key THEN finished:=(3)__ ELSE [r[i]:= (4)___; i:=j; j:= (5)____] ]; r[i]:=t; ENDP;{sift} 【燕山大学】 ENDP;{sift} 【燕山大学 1998 【燕山大学 1998 四、 1998 四、2 四、 2 （ 2 （15分） 19．设 19 ．设n为结点个数，datatype 为结点个数， datatype为结点信息类型。为了进行堆排序，定义： 为结点信息类型。为了进行堆排序，定义： TYPE node=RECORD key： TYPE node=RECORD key ：integer； integer ；info： info ：datatype END； datatype END ； VAR heap： VAR heap ：] OF node l， l ，r，i，j：0..n ;x： 0..n ;x ：node； node ； 在下面的算法描述中填入正确的内容，使其实现1964年Floyd提出的建堆筛选法，要求堆 建成后便找到了最小的关键码。 建成后便找到了最小的关键码。 筛选算法sift(l,r,heap)： sift(l,r,heap) ： 步 步1．[准备] i 准备 ] i← ] i ←l; j ← l; j ←(1)___; x← (1)___; x ←heap[i] 步 步2．[过筛] 过筛 ] 循环：当 ] 循环：当(2)____ 循环：当 (2)____时反复执行 (2)____ 时反复执行 时反复执行 ⑴．若 ⑴．若j heap[j].key>heap[j+1].key 则(3)____ ⑵．若 ⑵．若(4)___ ⑵．若 (4)___则 (4)___ 则heap[i]← heap[i] ←heap[j]; (5)____; (6)____ 否则跳出循环 heap[j]; (5)____; (6)____ 否则跳出循环 否则跳出循环 步 步3.[结束 3.[ 结束] 结束 ] heap[i] ←】 heap[i] ← (7)____ 【山东工业大学 (7)____ 【山东工业大学 1996 【山东工业大学 1996 三、 1996 三、2 三、 2 （ 2 （7分） 20．以下程序的功能是利用堆进行排序。请在空白处填上适当语句，使程序完整。 20 ．以下程序的功能是利用堆进行排序。请在空白处填上适当语句，使程序完整。 ．以下程序的功能是利用堆进行排序。请在空白处填上适当语句，使程序完整。 PROCEDURE sift(VAR r:arr;k,m:integer); VAR i,j,x:integer; t:rec; finished:boolean; BEGIN i:=k; (1)___; x:=r[i].key; (2)___; t:=r[k]; WHILE (j<=m) AND NOT finished DO BEGIN IF (j IF x<=r[j].key THEN finished:=true ELSE BEGIN(4)____; (5)____; (6)____END; END; (7)___ END; PROCEDURE heapsort(VAR r:arr); VAR i:integer; x:rec; BEGIN FOR i:=n DIV 2 DOWNTO 1 DO (8)___; FOR i:=n DOWNTO 2 DO BEGIN x:=r[1]; (9)___; r[i]:=x; (10)___ END; END; 【北方交通大学】 END; 【北方交通大学 2000 【北方交通大学 2000 四 2000 四 （20分） 21．堆是一种有用的数据结构。试判断下面的关键码序列中哪一个是堆 21 ．堆是一种有用的数据结构。试判断下面的关键码序列中哪一个是堆__________ ．堆是一种有用的数据结构。试判断下面的关键码序列中哪一个是堆 __________。 __________ 。 ①16， 16 ，72， 72 ，31， 31 ，23， 23 ，94， 94 ，53 ② 53 ②94， 94 ，53， 53 ，31， 31 ，72， 72 ，16， 16 ，23 ③ 23 ③16， 16 ，53， 53 ，23， 23 ，94， 94 ， 31， 31 ，72 ④16， 16 ，31， 31 ，23， 23 ，94， 94 ，53， 53 ，72 ⑤ 72 ⑤94， 94 ，31， 31 ，53， 53 ，23， 23 ，16， 16 ，72 堆排序是一种_(1)_ 堆排序是一种 _(1)_类型的排序，它的一个基本问题是如何建堆，常用的建堆算法是 _(1)_ 类型的排序，它的一个基本问题是如何建堆，常用的建堆算法是 1964年Floyd提出的_(2)_ 提出的 _(2)_，对含有 _(2)_ ，对含有n个元素的序列进行排序时, 个元素的序列进行排序时 ,堆排序的时间复杂度是 _(3)_，所需要的附加结点是 _(3)_ ，所需要的附加结点是_(4)_ ，所需要的附加结点是 _(4)_。 _(4)_ 。 【山东工业大学 1994 】 【山东工业大学 1994 一、 1994 一、2 一、 2 （ 2 （5分） 22．堆是一种有用的数据结构. 堆实质上是一棵_(2)_ 22 ． 堆是一种有用的数据结构 . 堆排序是一种 . 堆排序是一种_(1)_ 堆排序是一种 _(1)_排序， _(1)_ 排序， 堆实质上是一棵 _(2)_结点的层次 _(2)_ 结点的层次 序列。对含有N个元素的序列进行排序时，堆排序的时间复杂度是_(3)_ 个元素的序列进行排序时，堆排序的时间复杂度是 _(3)_，所需的附加存储 _(3)_ ，所需的附加存储 结点是_(4)_关键码序列05， 结点是 _(4)_。 _(4)_ 。 05 ，23， 23 ，16， 16 ，68， 68 ，94， 94 ，72， 72 ，71， 71 ，73是否满足堆的性质_(5)_ 是否满足堆的性质 _(5)_。 _(5)_ 。 【山 东工业大学 1996 】 东工业大学 1996 三、 1996 三、1 三、 1 （ 1 （5分） 23．将如下的堆排序算法补写完整。说明如下： 23 ．将如下的堆排序算法补写完整。说明如下： ．将如下的堆排序算法补写完整。说明如下： TYPE heaptype=]OF integer； TYPE heaptype=]OF integer ； 过程heapsort的功能是将数组h中的前n个记录按关键字递减的次序排序。heapsort 个记录按关键字递减的次序排序。 heapsort 调用过程sift时的参数h，k，r有如下定义：以 h[k+1] 有如下定义：以 h[k+1]， h[k+1] ，h[k+2]，„ h[k+2] ，„,h[r]为根的子树已 ,h[r] 为根的子树已 经是堆；执行sift后，以h[k]， h[k] ，h[k+1],h[k+2],„ h[k+1],h[k+2], „,h[r] 为根的子树都成为堆。 ,h[r] 为根的子树都成为堆。 为根的子树都成为堆。 PROC sift（； PROC sift （VAR h： VAR h ：heaptype； heaptype ；k，r：integer） integer ） VAR i， VAR i ，j，x：integer； integer ；finish： finish ：boolean； boolean ； BEGIN i:=k； BEGIN i:=k ；x:=h[i]； x:=h[i] ；j:=2*j； j:=2*j ； ((1)____); WHILE (j<=r) AND NOT finish DO [IF (j IF x>h[j] THEN [(2)____ ] ELSE finish:=true; (3)____ ] END; PROC heapsort(VAR h:heaptype; n:integer); VAR k,r,i,j:integer; BEGIN FOR k:=n DIV 2 DOWNTO 1 DO sift ((4)____) ; FOR r:=n DOWNTO 2 DO [x:=h[1]; h[1]:=h[r]; h[r]:=x; ((5)____) ] END; 【北京工业大学 END; 【北京工业大学 1997 【北京工业大学 1997 五、 1997 五、2 (16 五、 2 (16分)】 24．设有字母序列{Q,D,F,X,A,P,N,B,Y,M,C,W}, 24 ． 设有字母序列 {Q,D,F,X,A,P,N,B,Y,M,C,W},请写出按 {Q,D,F,X,A,P,N,B,Y,M,C,W}, 请写出按2路归并排序方法对该序列进行一 趟扫描后的结果_______ 趟扫描后的结果 _______。 _______ 。 【北方交通大学 【北方交通大学 2001 【北方交通大学 2001 二、 2001 二、7 二、 7】 25. 阅读下列程序说明和 25. 阅读下列程序说明和PASCAL程序，把应填入其中______ 程序，把应填入其中 ______处的字句写在答题纸上。程序 ______ 处的字句写在答题纸上。程序 说明： 说明： 本题给出的是将数组a的元素a 1 ，a 2 ,„,a n 从大到小排序的子程序。子程序采用改进的 选择排序方法，该方法基于以下思想： 选择排序方法，该方法基于以下思想： 在选择第一大元过程中, 在选择第一大元过程中 , a 1 与a j (j=n,n-1,„ (j=n,n-1, „,2)逐个比较，若发现 ,2) 逐个比较，若发现a j1 >a 1 ，则a j1 与a 1 变 换，变换后新的a j1 有性质a j1 ≥a t (j1 j2 与a 1 交换，则交换后 (j1 ≤n),若再有 n), 若再有a j2 >a 1 的a j2 也有性质a j2 ≥a t (j2 (j2 ≤n)。如在挑选第一大元过程中，与 n) 。如在挑选第一大元过程中，与a 1 交换的元素有k(k≥ k(k ≥0) 个，依次为a j1 ,a j2 ,„,a jk ,则它们都满足这一性质，它们的下标满足n≥j1>j2>„ j1>j2> „>jk>1。有 >jk>1 。有 了这些下标，在确定第二大元时，可只考虑a 2 与a j (j=jk,jk-1,„倘若jk=2， (j=jk,jk-1, „,3) 逐个比较。 ,3) 逐个比较。 jk=2 ， 则可不经比较就知道它是第二大元。在选择第二大元过程中，将与a 2 交换过的元素下标也 标记下来，可供选择其他大元使用，但在选择第二大元时，应保证与a 2 交换的那些位置上 的新值也都满足上述性质，依次类推，顺序选择第一，第二,„,第n-1大元，实现对a的排 序。 序。 设程序包含有常量和类型定义： 设程序包含有常量和类型定义： 设程序包含有常量和类型定义： CONST maxn=1000; TYPE vector=axn] OF integer; index= 1..maxn; PROCEDURE sort(VAR a:vector;n:index) VAR p:vector; i,j,k,m,t:integer; BEGIN k:=0; i:=1; m:=n; WHILE i BEGIN FOR j:=m DOWNTO i+1 DO IF a[i] BEGIN t:=a[i]; a[i]:=a[j]; a[j]:=t; k:=k+1;（ BEGIN t:=a[i]; a[i]:=a[j]; a[j]:=t; k:=k+1; （(1)____） (1)____ ）END; REPEAT（ REPEAT （(2)____） (2)____ ）; IF（ IF （(3)____） (3)____ ）THEN（ THEN （(4)____） (4)____ ） ELSE BEGIN m:=p[k]; k:=k-1; END; UNTIL (i IF （ IF （(5)___） (5)___ ） BEGIN t:=a[i];（ BEGIN t:=a[i]; （(6)____） (6)____ ）;（(7)____） (7)____ ）END END END; 【上海海运学院】 END; 【上海海运学院 1997 【上海海运学院 1997 七（ 1997 七（14 七（ 14分） 26．下列算法为奇偶交换排序，思路如下：第一趟对所有奇数的 26 ．下列算法为奇偶交换排序，思路如下：第一趟对所有奇数的i,将 i, 将a[i]和 a[i] 和a[i+1]进行比 a[i+1] 进行比 较,第二趟对所有偶数的i,将 i, 将a[i]和 a[i] 和a[i+1]进行比较 a[i+1] 进行比较, 进行比较 ,每次比较时若a[i]>a[i+1],将二者交 a[i]>a[i+1], 将二者交 换;以后重复上述二趟过程, 以后重复上述二趟过程 ,直至整个数组有序。 直至整个数组有序。 程序.(a) 程序 .(a) PROCEDURE oesort(VAR a:] OF integer); VAR flag:boolean; i,t:integer; BEGIN REPEAT flag:=false; FOR i:=1 TO n step 2 DO IF(a[i]>a[i+1]) THEN [flag:= (1)____; t:=a[i+1]; a[i+1]:=a[i]; (2)____] FOR i:= (3)____ DO IF (a[i]>a[i+1]) THEN [flag:= (4)____ ; t:=a[i+1];a[i+1]:=a[i]; a[i]:=t;] UNTIL (5)___ ; END; 程序（b 程序（ b） void oesort (int a[n]) {int flag,i,t; do {flag=0; for(i=1;i if(a[i]>a[i+1]) {flag=(1)__; t=a[i+1]; a[i+1]=a[i]; (2)____;} for (3)____ if (a[i]>a[i+1]) {flag=(4)____;t=a[i+1]; a[i+1]=a[i]; a[i]=t;} }while (5)_; } 【上海大学】 } 【上海大学 2000 【上海大学 2000 一、 2000 一、1 一、 1 （ 1 （10分） 27．关键码序列（，要按照关键码值递增的次序进 27 ．关键码序列（ Q ．关键码序列（ Q， Q ，H，C，Y，Q，A，M，S，R，D，F，X） 行排序，若采用初始步长为4的Shell排序法，则一趟扫描的结果是_____ 则一趟扫描的结果是 _____； _____ ；若采用以第一 个元素为分界元素的快速排序法，则扫描一趟的结果是______ 个元素为分界元素的快速排序法，则扫描一趟的结果是 ______。 ______ 。 【北京大学 【北京大学 1997 【北京大学 1997 一、 1997 一、4 一、 4 （4分）】 类似本题的另外叙述有： (1)设有字符序列 (1) 设有字符序列Q、H、C、Y、P、A、M、S、R、D、F、X要求按字符升序排序，采用初始 步长为４的希尔（shell） shell ）排序，一趟扫描的结果是____; 一趟扫描的结果是 ____;采用以首元素为分界元素的快速排 ____; 采用以首元素为分界元素的快速排 序，一趟扫描的结果是_____ 序，一趟扫描的结果是 _____。 _____ 。 【北京工业大学 1999 【北京工业大学 1999 一、 1999 一、7 (8 一、 7 (8分)】 28．外部排序的基本方法是归并排序，但在之前必须先生成【北京邮电大学2001 二、 28 ．外部排序的基本方法是归并排序，但在之前必须先生成___ ．外部排序的基本方法是归并排序，但在之前必须先生成 ___。 ___ 。 2001 二、 6（2分）】 29．磁盘排序过程主要是先生成 29 ．磁盘排序过程主要是先生成 ．磁盘排序过程主要是先生成 ，然后对 ，然后对 ，然后对 合并，而提高排序速度很重要的 合并，而提高排序速度很重要的 是 ，】 ，我们将采用 我们将采用 方法来提高排序速度。 方法来提高排序速度。 方法来提高排序速度。 【山东工业大学 1995 【山东工业大学 1995 一、 1995 一、4（4分） 30． 30 ．设输入的关键字满足k1>k2>„ k1>k2> „>kn， >kn ，缓冲区大小为m，用置换- 用置换 -选择排序方法可产生____ 选择排序方法可产生 ____ 个初始归并段。 个初始归并段。 【武汉大学 2000 【武汉大学 2000 一、 2000 一、9 一、 9】 31．下面是一改进了的快速排序算法，请填空并简要说明支持 31 ．下面是一改进了的快速排序算法，请填空并简要说明支持improveqsort递归所需要的 最大栈空间用量。 最大栈空间用量。 PROCEDURE improveqsort(VAR list:afile;m,n:integer); {设list[m].key<=list[n+1].key} VAR i,j,k:integer; BEGIN WHILE m BEGIN i:=m; j:=n+1; k:=list[m].key; REPEAT REPEAT i:=i+1 UNTIL list[i].key>=k; REPEAT j:=j-1 UNTIL list[j].key<=k; IF i UNTIL i>=j; interchange(list[m],list[j]); IF n-j>=j-m THEN BEGIN improveqsort(list, (1)____); (2)____; END ELSE BEGIN improveqsort(list, (3)____); (4)____; END END; {OF WHILE} END; 【东南大学】 END; 【东南大学 2001 【东南大学 2001 五（ 2001 五（10 五（ 10分） 四、应用题 1. 内部排序（名词解释）。 【燕山大学】 1. 内部排序（名词解释） 【燕山大学 1999 【燕山大学 1999 一、 1999 一、5 一、 5 （ 5 （2分） 2. 在各种排序方法中，哪些是稳定的？哪些是不稳定的？并为每一种不稳定的排序方法举 2. 在各种排序方法中，哪些是稳定的？哪些是不稳定的？并为每一种不稳定的排序方法举 出一个不稳定的实例。【大连海事大学 1996 【大连海事大学 1996 七、 1996 七、3 ( 七、 3 (４分 3 ( ４分) ４分 )】 类似本题的另外叙述有： (1) 举例说明堆排序是否为稳定排序法】 (1) 举例说明堆排序是否为稳定排序法. 举例说明堆排序是否为稳定排序法 . 【西安电子科技大学 . 【西安电子科技大学 1996 【西安电子科技大学 1996 三、 1996 三、4 三、 4 （ 4 （5分） (2) 选择排序算法是否稳定？为什么？】 (2) 选择排序算法是否稳定？为什么？ 选择排序算法是否稳定？为什么？ 【燕山大学 【燕山大学 2001 【燕山大学 2001 三、 2001 三、3 三、 3 （ 3 （5分） (3) 举例分析堆排序方法是否稳定。】 (3) 举例分析堆排序方法是否稳定。 举例分析堆排序方法是否稳定。 【北京邮电大学 【北京邮电大学 1993 【北京邮电大学 1993 二、 1993 二、3 二、 3 （ 3 （6分） (4) 堆排序是稳定排序吗？举例说明。】 (4) 堆排序是稳定排序吗？举例说明。 堆排序是稳定排序吗？举例说明。 【东南大学 【东南大学 1996 【东南大学 1996 一、 1996 一、5 一、 5 （ 5 （6分） (5) 试举例分析堆排序法是否稳定。】 (5) 试举例分析堆排序法是否稳定。 试举例分析堆排序法是否稳定。 【东南大学 【东南大学 1999 【东南大学 1999 一、 1999 一、5 一、 5 （ 5 （5分） (6) 树型选择排序通常采用顺序存储结构，①试指出n个元素的原始序列一般如何在该存 (6) 树型选择排序通常采用顺序存储结构， 储结构中存放（起始存储位置，次序），请说明理由。②讨论树形选择排序的稳定性。若稳 定，须说明理由；不稳定，须举反例，并尝试找出使它稳定的方法。【北京工业大学 1999 【北京工业大学 1999 七 1999 七 (10分)】 3．在执行某种排序算法的过程中出现了排序码朝着最终排序序列相反的方向移动，从而认 为该排序算法是不稳定的，这种说法对吗？为什么？ 】 为该排序算法是不稳定的，这种说法对吗？为什么？ 【燕山大学 2001 【燕山大学 2001 三、 2001 三、4 三、 4 （ 4 （5分） 4．设有5个互不相同的元素a、b、c、d、e，能否通过7次比较就将其排好序？如果能， 请列出其比较过程；如果不能，则说明原因。 】 请列出其比较过程；如果不能，则说明原因。 【北方交通大学 【北方交通大学 1996 【北方交通大学 1996 五（ 1996 五（10 五（ 10分） 5．对一个由n个关键字不同的记录构成的序列，能否用比2n-3少的次数选出该序列中关键 字取最大值和关键字取最小值的记录？请说明如何实现？在最坏的情况下至少进行多少次 比较？ 比较？ 【东南大学】 【东南大学 2000 【东南大学 2000 一、 2000 一、5 一、 5 （ 5 （8分） 6．利用比较的方法进行排序，在最坏的情况下，能达到的最好时间复杂性是什么？请给出 详细证明。 详细证明。
发布者：admin，转转请注明出处：http://www.yc00.com/web/1714449454a2448669.html
评论列表（0条）