《数据结构考研试题精选及答案第10章 排序》由会员分享，可在线阅读，更多相关《数据结构考研试题精选及答案第10章 排序（31页珍藏版）》请在金锄头文库上搜索。
1、 第 10 章 排序一、选择题一、选择题 1某内排序方法的稳定性是指( )。 【南京理工大学 1997 一、10（2 分） 】 A该排序算法不允许有相同的关键字记录 B该排序算法允许有相同的关键 字记录 C平均时间为 0（n log n）的排序方法 D以上都不对 2下面给出的四种排序法中( )排序法是不稳定性排序法。 【北京航空航天大学 1999 一、10 （2 分） 】A. 插入 B. 冒泡 C. 二路归并 D. 堆积 3下列排序算法中，其中（ ）是稳定的。 【福州大学 1998 一、3 (2 分)】 A. 堆排序，冒泡排序 B. 快速排序，堆排序 C. 直接选择排序，归并排序 D. 归并排
2、序，冒泡排序 4稳定的排序方法是（ ） 【北方交通大学 2000 二、3（2 分） 】 A直接插入排序和快速排序 B折半插入排序和起泡排序 C简单选择排序和四路归并排序 D树形选择排序和 shell 排序 5下列排序方法中，哪一个是稳定的排序方法？（ ） 【北方交通大学 2001 一、 8（2 分） 】 A直接选择排序 B二分法插入排序 C希尔排序 D快速排序 6若要求尽可能快地对序列进行稳定的排序，则应选（A快速排序 B归并排序 C冒泡排序） 。 【北京邮电大学 2001 一、5（2 分） 】 7如果待排序序列中两个数据元素具有相同的值，在排序前后它们的相互位置发生颠倒， 则称该排序算法是不
3、稳定的。 （ ）就是不稳定的排序方法。 【清华大学 1998 一、3 (2 分） 】 A起泡排序 B归并排序 CShell 排序 D直接插入排序 E简单选 择排序 8若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选（ ）排序为宜。 A直接插入 B直接选择 C堆 D快速 E基数 【中科院计算所 2000 一、 5（2 分） 】 9若需在 O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序 方法是（ ） 。A. 快速排序 B. 堆排序 C. 归并排序 D. 直接插入排序 【中国科技大学 1998 二、4（2 分） 】 【中科院计算所 1998 二、4（2 分）
4、 】 10下面的排序算法中，不稳定的是（ ） 【北京工业大学 1999 一、2 (2 分)】 A.起泡排序 B.折半插入排序 C.简单选择排序 D.希尔排序 E.基数排序 F.堆 排序。 11下列内部排序算法中： 【北京工业大学 2000 一、1 (10 分 每问 2 分)】 A快速排序 B.直接插入排序 C. 二路归并排序 D. 简单选择排序 E. 起泡排 序 F. 堆排序 （1） 其比较次数与序列初态无关的算法是（ ） （2）不稳定的排序算法是（ ） （3）在初始序列已基本有序（除去 n 个元素中的某 k 个元素后即呈有序，k 快速排序 归并排序E以上答案都不对 【西安交通大学 1996
5、三、1 (3 分)】 59排序方法有许多种， （1）法从未排序的序列中依次取出元素，与已排序序列（初始时 为空）中的元素作比较，将其放入已排序序列的正确位置上；（2）法从未排序的序列中挑 选元素，并将其依次放入已排序序列（初始时为空）的一端； 交换排序方法是对序列中的 元素进行一系列比较，当被比较的两元素逆序时，进行交换；（3）和（4）是基于这类方 法的两种排序方法， 而（4）是比（3）效率更高的方法；（5）法是基于选择排序的一种 排序方法，是完全二叉树结构的一个重要应用。 【北方交通大学 1999 一、3 （5 分） 】 （1）-（5）: A选择排序 B快速排序 C插入排序 D起泡排序 E归
6、并排序 Fshell 排序 G堆排序 H基数排序 类似本题的另外叙述有：类似本题的另外叙述有： （1）排序的方法有很多种， （ ）法从未排序的序列中依次取出元素与已排序序列中 的元素比较，将其放在已排序序列的正确位置上；（ ）法从未排序序列中挑选元素， 并将其依次放入已排序序列的一端；交换排序法是对序列中的元素进行一系列比较，当被 比较的两元素逆序时，进行交换。 （ ）和（ ）是基于这类方法的两种排序方法，而 ( )是比( )效率更高的方法。供选择的答案： A. 快速排序 B. 选择排序 C. 归并排序 D冒泡排序 E直接 插入排序 【山东大学 1998 三、2 (5 分)】 【山东工业大学
7、2000 三、2 （7 分） 】 60设要将序列（q,h,c,y,p,a,m,s,r,d,f,x） 中的关键码按字母升序重新排序， （1）（ ）是初始步长为 4 的 shell 排序一趟扫描的结果； （2）（ ）是对排序初 始建堆的结果； （3）（ ）是以第一个元素为分界元素的快速一趟扫描的结果。 从下面供选择的答案中选出正确答案填入括号内。 【厦门大学 2000 六、3 （16%/3 分） 】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
8、 ,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 类似本题的另外叙述有：类似本题的另外叙述有： （1）在内排序的过程中,通常需要对待排序的关键码进行多编扫描,采用不同重新排序 方法,会产生不同的排序中间结果。设要将序列中的关键码按 字母序的升序排列，则( 1 )是冒泡排序一趟扫描的结果,( 2 )是初始步长为 4 的希尔 (SHELL)排序一趟扫描的结果,( 3 ) 是合并排序一趟扫描的结果,( 4 )是以第一个元 素为分界元素的快速排序一趟扫描的结果,( 5 )是堆
9、排序初始建堆的结果。供选择的答 案: 【上海海运学院 1997 二、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,xD. 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对由 n 个记录所组成的表按关键码排序时,下列各个常用排序算法的平均比较次数分别 是:二路归并排序为( 1 ),直接插入排序为( 2 ),快速排序为( 3 ),其中,归并排 序和快速排序所需要的辅助存储分别是( 4 )和( 5 )。
10、【上海海运学院 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 B2N-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) 【南京理工大
11、学 1996 一、2 （2 分） 】 64已知待排序的 n 个元素可分为 n/k 个组，每个组包含 k 个元素，且任一组内的各元素 均分别大于前一组内的所有元素和小于后一组内的所有元素，若采用基于比较的排序， 其时间下界应为（ ） 。A. O(nlog2n) B. O(nlog2k) C. O(klog2n) D. O(klog2k) 【中国科技大学 1998 二、 9 （2 分） 】 类似本题的另外叙述有：类似本题的另外叙述有： (1)已知待排序的 N 个元素可分为 N/K 个组，每个组包含 K 个元素，且任一组内的各元 素均分别大于前一组内的所有元素和小于后一组内的所有元素,若采用基于比较
12、的排序,其 时间下界应为( ) A. O(klog2k) B. O(klog2n) C. O(nlog2k) D. O(nlog2n) 【中科院计算所 1998 二、 9 （2 分） 】 65采用败者树进行 k 路平衡归并的外部排序算法，其总的归并效率与 k （ ） A 有关 B无关 【北京工业大学 2000 一 、2 (3 分)】 66采用败者树进行 K 路平衡归并时，总的（包括访外）归并效率与 K（ ） 。 A有关 B无关 【北京工业大学 2001 一、4 (2 分)】 二、判断题：二、判断题：1当待排序的元素很大时，为了交换元素的位置，移动元素要占用较多的时间，这是影响 时间复杂度的主要
13、因素。 （ ）【长沙铁道学院 1998 一、10 (1 分)】 2内排序要求数据一定要以顺序方式存储。 （ ）【南京理工大学 1997 二、2（2 分）】 3排序算法中的比较次数与初始元素序列的排列无关。 （）【南京航空航天大学 1997 一、 8 （1 分） 】 4排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。（ ） 【南京航空航天大学 1996 六、9 （1 分） 】 5在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该 算法是不稳定的。 （ ）【上海交通大学 1998 一、18】 6直接选择排序算法在最好情况下的时间复杂度为 O（N） 。 （ ）
14、【合肥工业大学 2001 二、 10（1 分） 】 7两分法插入排序所需比较次数与待排序记录的初始排列状态相关。 （）【上海交通大学 1998 一、15】 8在初始数据表已经有序时，快速排序算法的时间复杂度为 O(nlog2n )。 （ ） 【合肥工业大学 2000 二、9（1 分） 】 9在待排数据基本有序的情况下，快速排序效果最好。 （ ）【南京理工大学 1997 二、 4（2 分） 】 10当待排序记录已经从小到大排序或者已经从大到小排序时，快速排序的执行时间最省。 （ ） 【上海交通大学 1998 一、16】 11快速排序的速度在所有排序方法中为最快,而且所需附加空间也最少。 （ ） 【北京邮电大学 1998 一、7 （2 分） 】 12堆肯定是一棵平衡二叉树。 （ ）【南京航空航天大学 1997 一、6 （1 分） 】 13堆是满二叉树。（ ）【南京航空航天大学 1996 六、6 （1 分） 】 14 （101，88，46，70，34，39，45，58，66，10）是堆。 （ ）【北京邮电大学 1999 二、 1 （2 分） 】 15在用堆排序算法排序时，如果要进行增序排序，则需要采用“大根堆” 。 （ ） 【合肥工业大学 2000 二、10（1 分） 】 16堆排序是稳
