2022年数据结构练习题-排序 .pdf

《2022年数据结构练习题-排序 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构练习题-排序 .pdf（3页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、排序一、选择题1某内排序方法的稳定性是指( )。 【南京理工大学 1997 一、 10（ 2分） 】A该排序算法不允许有相同的关键字记录 B该排序算法允许有相同的关键字记录C平均时间为0（n log n）的排序方法 D以上都不对2 下面给出的四种排序法中( )排序法是不稳定性排序法。 【北京航空航天大学 1999 一、10 （2 分） 】 A. 插入 B. 冒泡 C. 二路归并 D. 堆4稳定的排序方法是（）【北方交通大学 2000 二、 3（2 分） 】A直接插入排序和快速排序 B折半插入排序和起泡排序C简单选择排序和四路归并排序 D 树形选择排序和shell排序9若需在 O(nlog2n)

2、 的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（） 。 A. 快速排序 B. 堆排序 C. 归并排序 D. 直接插入排序【中国科技大学 1998 二、 4（2 分） 】 【中科院计算所 1998 二、 4（2 分） 】12排序趟数与序列的原始状态有关的排序方法是( )排序法。 【北京航空航天大学 1999 一、 9（2 分） 】 A 插入 B. 选择 C. 冒泡 D. 快速13下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是。( ) A选择排序法 B. 插入排序法 C. 快速排序法 D. 堆积排序法【北京航空航天大学 2000 一、 10（2 分） 】17

3、数据序列（8，9，10，4，5，6，20， 1，2）只能是下列排序算法中的( )的两趟排序后的结果。A选择排序 B.冒泡排序 C.插入排序 D.堆排序【合肥工业大学 1999 一、 3 （2 分） 】18数据序列（ 2，1，4，9，8，10，6，20）只能是下列排序算法中的( )的两趟排序后的结果。A. 快速排序 B. 冒泡排序 C. 选择排序 D. 插入排序【合肥工业大学 2000 一、 3 （2 分） 】19对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为（1） 84 47 25 15 21 （2） 15 47 25 84 21 （3） 15 21 25

4、 84 47 （4） 15 21 25 47 84 则采用的排序是 ( )。【南京理工大学 1997 一、 2 （2 分） 】A. 选择 B. 冒泡 C. 快速 D. 插入22下列排序算法中( )不能保证每趟排序至少能将一个元素放到其最终的位置上。A.快速排序 B. shell排序 C. 堆排序 D.冒泡排序【合肥工业大学 2001 一、 3（2 分） 】24下列序列中， （）是执行第一趟快速排序后所得的序列。【福州大学 1998 一、9 (2 分) 】 A. 68，11， 18，69 23，93，73 B. 68，11，69，23 18， 93，73 C. 93，73 68， 11，69，2

5、3，18 D. 68，11，69，23， 18 93，73 26一组记录的关键码为（46，79，56，38，40， 84） ，则利用快速排序的方法，以第一个名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 3 页 - - - - - - - - - 记录为基准得到的一次划分结果为（） 。【燕山大学 2001 一、 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,3

6、8,46,84,56,79) 27. 在下面的排序方法中，辅助空间为O（n）的是 ( ) 。 【南京理工大学 1999 一、 17（1 分） 】 A希尔排序 B. 堆排序 C. 选择排序 D. 归并排序28下列排序算法中，在待排序数据已有序时，花费时间反而最多的是( )排序。 A 冒泡 B. 希尔 C. 快速 D. 堆【南京理工大学 2001 一、 12 （1.5 分） 】29. 下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的是：（）。A. 直接插入排序 B. 快速排序 C. 直接选择排序 D. 堆排序30. 对初始状态为递增序列的表按递增顺序排序

7、，最省时间的是（）算法，最费时间的是（）算法。 A. 堆排序 B. 快速排序 C. 插入排序 D. 归并排序【南开大学 2000 一、 5】34下列排序算法中， （）算法可能会出现下面情况：在最后一趟开始之前，所有元素都不在其最终的位置上。【南开大学 2000 一、 4】 【西北大学 2001 二、 1】 A. 堆排序 B. 冒泡排序 C. 快速排序 D. 插入排序35. 下列排序算法中，占用辅助空间最多的是：( ) 【厦门大学 2002 五、2 （8 分）】A. 归并排序 B. 快速排序 C. 希尔排序 D. 堆排序37. 在排序算法中，每次从未排序的记录中挑出最小（或最大）关键码字的记录，

8、加入到已排序记录的末尾，该排序方法是（） 。 【中山大学 1999 一、 11】 A. 选择 B. 冒泡 C. 插入 D. 堆38用直接插入排序方法对下面四个序列进行排序（由小到大），元素比较次数最少的是（） 。A 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 90,69,80,46,21,32,94,40 【北方交通大学 2001 一、 15 （2 分） 】39直接插入排序在最好情况下的时间复杂度为（） 【北京邮电大学 1999 一、 5 （2分） 】 A O(logn) B O(n

9、) C O(n*logn) D O(n2) 40. 若用冒泡排序方法对序列10,14,26,29,41,52从大到小排序， 需进行 （） 次比较。A. 3 B. 10 C. 15 D. 25 【南京理工大学 1999 一、 11（4分） 】47快速排序在最坏情况下的时间复杂度是( ),比( )的性能差。AO(NlogN) B O(N2) C O(N3) D 堆排序 E冒泡排序F选择排序【山东工业大学 1995 二、 2 （4 分） 】48. 快速排序方法在（）情况下最不利于发挥其长处。【燕山大学 2001 一、 3 （2分） 】A. 要排序的数据量太大 B. 要排序的数据中含有多个相同值C.

10、要排序的数据个数为奇数 D. 要排序的数据已基本有序53在对 n 个元素的序列进行排序时，堆排序所需要的附加存储空间是（） 。 A. O(log2n) B. O(1) C. O(n) D. O(nlog2n) 【西安电子科技大学2001 应用一、10（ 2 分） 】名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 3 页 - - - - - - - - - 56. 归并排序中，归并的趟数是( )。 【南京理工大学 2000 一、 19（ 1.5 分） 】AO（n） BO(l

11、ogn) CO(nlogn) DO(n*n) 61对由 n 个记录所组成的表按关键码排序时, 下列各个常用排序算法的平均比较次数分别是: 二路归并排序为( 1 ),直接插入排序为( 2 ),快速排序为( 3 ),其中 , 归并排序和快速排序所需要的辅助存储分别是( 4 )和( 5 )。【上海海运学院 1998 二、4 （ 5分） 】1-5:A. O(1) B. O （nlog2n） C. O （n） D. O （ n2） E. O （ n(log2n)2） F. O （log2n）62将两个各有N个元素的有序表归并成一个有序表, 其最少的比较次数是( ) AN B 2N-1 C2N DN-1【中科院计算所 1998 二、 7 （2 分） 】 【中国科技大学 1998 二、 7 （2 分） 】63. 基于比较方法的n 个数据的内部排序。最坏情况下的时间复杂度能达到的最好下界是（） 。A. O(nlogn) B. O(logn) C. O(n) D. O(n*n) 【南京理工大学 1996 一、2 （ 2 分） 】名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 3 页 - - - - - - - - -