目前最完整的数据结构1800题包括完整答案 第十章 排序
第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. 归并排序，冒泡排序
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．如果待排序序列中两个数据元素具有相同的值，在排序前后它们的相互位置发生颠倒，则称该排序算法是不稳定的。（）就是不稳定的排序方法。【清华大学 1998 一、3 (2分）】
A．起泡排序 B．归并排序 C．Shell排序 D．直接插入排序 E．简单选择排序
8．若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选（）排序为宜。
A．直接插入 B．直接选择 C．堆 D．快速 E．基数【中科院计算所 2000 一、5（2分）】
9．若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）。
A. 快速排序
B. 堆排序
C. 归并排序
D. 直接插入排序【中国科技大学 1998 二、4（2分）】【中科院计算所 1998 二、4（2分）】
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< （4）排序的平均时间复杂度为O(n?logn)的算法是（）为O(n?n)的算法是（） 12．排序趟数与序列的原始状态有关的排序方法是( )排序法。【北京航空航天大学 1999 一、9（2分）】 A．插入 B. 选择 C. 冒泡 D. 快速 13．下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是。( ) A．选择排序法 B. 插入排序法 C. 快速排序法 D. 堆积排序法【北京航空航天大学 2000 一、10（2分）】 14．对下列四种排序方法，在排序中关键字比较次数同记录初始排列无关的是( )。 A．直接插入 B. 二分法插入 C. 快速排序 D. 归并排序 【南京理工大学 2000 一、7 （1.5分）】 15．在下列排序算法中,哪一个算法的时间复杂度与初始排序无关（）。【北京理工大学 2001 六、4 （2）】 A．直接插入排序 B. 气泡排序 C. 快速排序 D. 直接选择排序 16．比较次数与排序的初始状态无关的排序方法是( )。【北方交通大学 2000 二、2（2分）】 A．直接插入排序 B．起泡排序 C．快速排序 D．简单选择排序17．数据序列（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 84 47 （4） 15 21 25 47 84 则采用的排序是 ( )。【南京理工大学 1997 一、2 （2分）】 A. 选择 B. 冒泡 C. 快速 D. 插入 20．对序列{15，9，7，8，20，-1，4}进行排序，进行一趟后数据的排列变为{4，9，-1，8，20，7，15}；则采用的是（）排序。【南京理工大学 1998 一、8（2分）】 A. 选择 B. 快速 C. 希尔 D. 冒泡 21．若上题的数据经一趟排序后的排列为{9，15，7，8，20，-1，4}，则采用的是（）排序。 A．选择 B. 堆 C. 直接插入 D. 冒泡【南京理工大学 1998 一、9（2分）】 22．下列排序算法中( )不能保证每趟排序至少能将一个元素放到其最终的位置上。 A.快速排序 B. shell排序 C. 堆排序 D.冒泡排序【合肥工业大学 2001 一、3（2分）】 23．下列排序算法中( )排序在一趟结束后不一定能选出一个元素放在其最终位置上。 A. 选择 B. 冒泡 C. 归并 D. 堆 【南京理工大学 2001 一、7（1.5分）】【哈尔滨工业大学 2001 二、4（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，23，18] D. [68，11，69，23，18] [93，73] 25．有一组数据（15，9，7，8，20，-1，7，4）用快速排序的划分方法进行一趟划分后数 据的排序为 ( )（按递增序）。【南京理工大学 1996 一、4 （2分）】 A．下面的B，C，D都不对。 B．9，7，8，4，-1，7，15，20 C．20，15，8，9，7，-1，4，7 D. 9，4，7，8，7，-1，15，20 26．一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个 记录为基准得到的一次划分结果为（）。【燕山大学 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,38,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. 对初始状态为递增序列的表按递增顺序排序，最省时间的是（）算法，最费时间的 是（）算法。 A. 堆排序 B. 快速排序 C. 插入排序 D. 归并排序【南开大学 2000 一、5】 31. 就平均性能而言，目前最好的内排序方法是( )排序法。【西安电子科技大学 1998 一、9 (2分）】 A. 冒泡 B. 希尔插入 C. 交换 D. 快速 32．如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用（）方法最快。 A．起泡排序 B．快速排列 C．Shell排序 D．堆排序 E．简单选择排序【清华大学 1998 一、2 （2分）】 类似本题的另外叙述有： (1)设有5000个无序的元素,希望用最快的速度挑选出其中前十个最大的元素,在以下的排 序方法中( )最好?为什么? 【山东工业大学 1995 二、4 （3分）】 A．快速排序 B．堆排序 C．归并排序 D．基数排序 E．SHELL排序 (2)数据表中有10000个元素，如果仅要求求出其中最大的10个元素，则采用( )算法 最节省时间。 A. 堆排序 B. 希尔排序 C. 快速排序 D. 直接选择排序【北京理工大学 2000 一、5 （2分）】 (3)设有1000个无序的元素，希望用最快的速度挑选出其中前十个最大的元素，在以下的 排序方法中采用哪一种最好？ ( ) 【东北大学 1999 一、5 (3分)】 A. 快速排序 B. 归并排序 C. 堆排序 D.基数排序 E.shell排序 33．在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是（）A．直接插入排序 B．冒泡排序 C．简单选择排序【山东工业大学 1995 二、1 （2分）】 类似本题的另外叙述有： (1)在文件"局部有序"或文件长度较小的情况下，最佳内部排序的方法是（）。 A. 直接插入排序 B. 冒泡排序 C. 简单选择排序 D. 快速排序【山东大学 2001 二、 2 (1分)】 (2)在待排序的元素序列基本有序的前提下，效率最高的排序方法是（）。【武汉大学2000 二、6】 A.插入排序 B. 选择排序 C. 快速排序 D. 归并排序 34．下列排序算法中，（）算法可能会出现下面情况：在最后一趟开始之前，所有元素都不在其最终的位置上。【南开大学 2000 一、4】【西北大学 2001 二、1】 A. 堆排序 B. 冒泡排序 C. 快速排序 D. 插入排序 35. 下列排序算法中，占用辅助空间最多的是：( ) 【厦门大学 2002 五、2 （8分）】 A. 归并排序 B. 快速排序 C. 希尔排序 D. 堆排序 36．从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为( )排序法。【北京航空航天大学 1999 一、8（2分）】 A. 插入 B. 选择 C. 希尔 D. 二路归并 37. 在排序算法中，每次从未排序的记录中挑出最小（或最大）关键码字的记录，加入到已排序记录的末尾，该排序方法是（）。【中山大学 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) 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分）】 类似本题的另外叙述有： (1)若用冒泡排序对关键字序列{18,16,14,12,10,8},进行从小到大的排序，所需进行的关键字比较总次数是（）【北京工商大学 2001 一、4（3分）】 A. 10 B. 15 C. 21 D. 34 41. 采用简单选择排序，比较次数与移动次数分别为( )。【南京理工大学 2000 一、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. 对序列{15，9，7，8，20，-1，4，} 用希尔排序方法排序，经一趟后序列变为{15，-l，4，8，20，9，7}则该次采用的增量是 ( ) 【南京理工大学 1999 一、15（1分）】 A. l B. 4 C. 3 D. 2 43．对下列关键字序列用快速排序法进行排序时，速度最快的情形是（）。 A． {21,25,5,17,9,23,30} B．{25,23,30,17,21,5,9} C． {21,9,17,30,25,23,5} Ｄ． {5,9,17,21,23,25,30}【北方交通大学 2001 一、18 （2分）】 44．对关键码序列28，16，32，12，60，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 三、4 （2分）】 45．对n个记录的线性表进行快速排序为减少算法的递归深度，以下叙述正确的是（）A．每次分区后，先处理较短的部分 B．每次分区后，先处理较长的部分 C．与算法每次分区后的处理顺序无关 D．以上三者都不对【北方交通大学 2000 二、5 （2分）】 46．当n个整型数据是有序时，对这n个数据用快速排序算法排序，则时间复杂度是 ( 6 )，当用递归算法求n!时，算法的时间复杂度是 ( 7 )，则：(6)-(7)=（）【南京理工大学1999 一、（6-7）（4分）】 A. O(n) B. O(nlogn) C. O(n*n) D. O(logn) 47．快速排序在最坏情况下的时间复杂度是( ),比( )的性能差。 A．O(NlogN) B．O(N2) C．O(N3) D．堆排序E．冒泡排序F．选择排序 【山东工业大学 1995 二、2 （4分）】 48. 快速排序方法在（）情况下最不利于发挥其长处。【燕山大学 2001 一、3 （2分）】 A. 要排序的数据量太大 B. 要排序的数据中含有多个相同值 C. 要排序的数据个数为奇数 D. 要排序的数据已基本有序 49．在含有n个关键字的小根堆（堆顶元素最小）中，关键字最大的记录有可能存储在（）位置上。 A．?n/2? B．?n/2? -1 C．1 D．?n/2? +2 【中科院计算所2000 一、4（2分）】 50. 以下序列不是堆的是( )。【西安电子科技大学 2001应用一、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 一、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. 堆排序是（）类排序，堆排序平均执行的时间复杂度和需要附加的存储空间复杂度分别是（） A. 插入 B. 交换 C. 归并 D. 基数 E. 选择 F. O（n2）和O（1） G. O（nlog2n）和O（1） H. O（nlog2n）和O（n） I. O（n2）和O（n）【西北大学 2001 二、2】53．在对n个元素的序列进行排序时，堆排序所需要的附加存储空间是（）。 A. O(log2n) B. O(1) C. O(n) D. O(nlog2n) 【西安电子科技大学2001应用一、10（2分）】 54．对n 个记录的文件进行堆排序，最坏情况下的执行时间是多少？（）A．O（log2n）B．O（n） C．O（nlog2n） D．O（n*n）【北方交通大学 2001 一、9（2分）】 55. 有一组数据（15，9，7，8，20，-1，7，4），用堆排序的筛选方法建立的初始堆为（） A．-1，4，8，9，20，7，15，7 B．-1，7，15，7，4，8，20，9 C．-1，4，7，8，20，15，7，9 D．A，B，C均不对。【南京理工大学 1996 二、5（2分）】 56. 归并排序中，归并的趟数是( )。【南京理工大学 2000 一、19（1.5分）】 A．O（n） B．O(logn) C．O(nlogn) D．O(n*n) 类似本题的另外叙述有： (1)归并排序的时间复杂性是（）。【中山大学 1999 一、12】 A.O（N*N） B. O（N） C. O（N*LOG（N）） D. O（LOG（N）） 57．在排序算法中每一项都与其它各项进行比较，计算出小于该项的项的个数，以确定该项的位置叫( ) A．插入排序 B．枚举排序 C．选择排序 D．交换排序【北京邮电大学 2000 二、6 （20/8分）】 58．就排序算法所用的辅助空间而言，堆排序，快速排序，归并排序的关系是（）A．堆排序〈快速排序〈归并排序B．堆排序〈归并排序〈快速排序 C．堆排序〉归并排序〉快速排序D．堆排序 > 快速排序 > 归并排序 E．以上答案都不对【西安交通大学 1996 三、1 (3分)】 59．排序方法有许多种，（1）法从未排序的序列中依次取出元素，与已排序序列（初始时为空）中的元素作比较，将其放入已排序序列的正确位置上；（2）法从未排序的序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端；交换排序方法是对序列中的元素 进行一系列比较，当被比较的两元素逆序时，进行交换；（3）和（4）是基于这类方法的两 种排序方法，而（4）是比（3）效率更高的方法；（5）法是基于选择排序的一种排序方法，是完全二叉树结构的一个重要应用。【北方交通大学 1999 一、3 （5分）】 （1）--（5）: A．选择排序 B．快速排序 C．插入排序 D．起泡排序 E．归并排序 F．shell排序 G．堆排序 H．基数排序 类似本题的另外叙述有： （1）排序的方法有很多种，（）法从未排序的序列中依次取出元素与已排序序列中的 元素比较，将其放在已排序序列的正确位置上；（）法从未排序序列中挑选元素，并将 其依次放入已排序序列的一端；交换排序法是对序列中的元素进行一系列比较，当被比较的 两元素逆序时，进行交换。（）和（）是基于这类方法的两种排序方法，而 ( ) 是比( )效率更高的方法。供选择的答案： A. 快速排序 B. 选择排序 C. 归并排序 D．冒泡排序 E．直接 插入排序 【山东大学 1998 三、2 (5分)】【山东工业大学 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 ,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 )是堆排序初始建堆的结果。供选择的答案: 【上海海运学院 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,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．对由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个元素的有序表归并成一个有序表,其最少的比较次数是( ) A．N B．2N-1 C．2N D．N-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分）】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个元素，且任一组内的各元素均分别大于前一组内的所有元素和小于后一组内的所有元素,若采用基于比较的排序,其时间下界应为( ) 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．当待排序的元素很大时，为了交换元素的位置，移动元素要占用较多的时间，这是影响时间复杂度的主要因素。（）【长沙铁道学院 1998 一、10 (1分)】 2．内排序要求数据一定要以顺序方式存储。（）【南京理工大学 1997 二、2（2分）】3．排序算法中的比较次数与初始元素序列的排列无关。（）【南京航空航天大学 1997 一、8 （1分）】 4．排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。（） 【南京航空航天大学 1996 六、9 （1分）】 5．在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的。（）【上海交通大学 1998 一、18】 6．直接选择排序算法在最好情况下的时间复杂度为O（N）。（）【合肥工业大学 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．堆排序是稳定的排序方法。（）【上海交通大学 1998 一、19】 17．归并排序辅助存储为O（1）。（）【青岛大学 2000 四、9（1分）】 18．在分配排序时，最高位优先分配法比最低位优先分配法简单。（）【上海交通大学 1998 一、20】 19．冒泡排序和快速排序都是基于交换两个逆序元素的排序方法,冒泡排序算法的最坏时间复杂性是O(n*n),而快速排序算法的最坏时间复杂性是O(nlog2n),所以快速排序比冒泡排序算法效率更高。（） 【上海海运学院 1997 一、9（1分）】 20．交换排序法是对序列中的元素进行一系列比较，当被比较的两个元素逆序时，进行交换，冒泡排序和快速排序是基于这类方法的两种排序方法，冒泡排序算法的最坏时间复杂性是O（n*n），而快速排序算法的最坏时间复杂性是O（nlog2n）；所以快速排序比冒泡排序效率更高。（） 【上海海运学院 1998 一、10 （1分）】【上海海运学院 1995 一、10（1分）】 21．快速排序和归并排序在最坏情况下的比较次数都是O(nlog2n)。（） 【上海海运学院1996一、9（1分）】 22．在任何情况下，归并排序都比简单插入排序快。（）【北京邮电大学 2000 一、4 （1分）】 23．归并排序在任何情况下都比所有简单排序速度快。（）【北京邮电大学 2002 一、9（1分）】 24．快速排序总比简单排序快。（）【东南大学 2001 一、9 （1分）】 25. 中序周游（遍历）平衡的二叉排序树，可得到最好排序的关键码序列。（） 【中山大学 1994 一、4 （2分）】 26．外部排序是把外存文件调入内存,可利用内部排序的方法进行排序,因此排序所花的时间取决于内部排序的时间。( )【北京邮电大学 1998 一、8 （2分）】 27．在外部排序时，利用选择树方法在能容纳m个记录的内存缓冲区中产生的初始归并段的平均长度为2m个记录。( )【上海海运学院 1999 一、10（1分）】 28．为提高在外排序过程中，对长度为N的初始序列进行“置换—选择”排序时，可以得到的最大初始有序段的长度不超过N/2。( ) 29．排序速度，进行外排序时，必须选用最快的内排序算法。( ) 30．在完成外排序过程中，每个记录的I/O次数必定相等。( )【大连海事大学 2001 一、20 (每题1分)】 31．影响外排序的时间因素主要是内存与外设交换信息的总次数。( )【东北大学 1997 二、 5 (2分)】 三、填空题 1．若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的______和记录的_____。 【北京邮电大学 2001 二、7 （4分）】 2. 外排序的基本操作过程是_______和_______。【西安电子科技大学 1998 二、3 （3分）】类似本题的另外叙述有： （1）外部排序中两个相对独立的阶段是___和___。【西安电子科技大学 1999软件一、8 （2分）】 3. 属于不稳定排序的有__________。【青岛大学 2002 三、5 （2分）】 4．分别采用堆排序，快速排序，冒泡排序和归并排序，对初态为有序的表，则最省时间的是_____算法，最费时间的是______算法。【福州大学 1998 二、10 (2分)】 类似本题的另外叙述有： （1）设表中元素的初始状态是按健值递增的，分别用堆排序，快速排序，冒泡排序和归并排序方法对其进行排序（按递增顺序）， __排序最省时间，__排序最费时间。【厦门大学 2001 一、5 （14%/5分）】 5. 不受待排序初始序列的影响，时间复杂度为O(N2)的排序算法是_____，在排序算法的最后一趟开始之前，所有元素都可能不在其最终位置上的排序算法是_____。【中国人民大学2001 一、3 （2分）】 6．直接插入排序用监视哨的作用是_______。【南京理工大学 2001 二、8 （2分）】 7．对n个记录的表r[1..n]进行简单选择排序，所需进行的关键字间的比较次数为_______。 【华中理工大学 2000 一、10 （1分）】 8. 用链表表示的数据的简单选择排序，结点的域为数据域data ，指针域 next ；链表首指针为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 三、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 六（15分）】 10．下面的排序算法的思想是：第一趟比较将最小的元素放在r[1]中，最大的元素放在r[n]中，第二趟比较将次小的放在r[2]中，将次大的放在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 【南京理工大学 2001 三、2 （10分）】 11．表插入排序的基本思想是在结点中设一指针字段，插入Ri时Rl到Ri-1己经用指针按排序码不减次序链结起夹，这时采用顺序比较的方法找到Ri应插入的位置，做链表插入。如此反复，直到把Rn插入为止。 （1）(6分)请完成下列表插人的算法；【山东工业大学 2000 五（16分）】【山东大学 1998 五】 ①. R[0].LINK←(1)___; R[N].LINK←(2)___; ②. 循环，I以-1为步长，从(3)___到(4)___执行 （1）P← R[0].LINK; Q← 0 （2）循环，当P>0且(5)__ 时，反复执行 Q←P； P←(6)___ （3）R[Q].LINK←I; R[I].LINK←P （2）(2分) 表插入排序的最大比较次数是(7)__； （3）（2分）表插入排序的最小比较次数是(8)__； （4）（2分）记录移动的次数是(9)__； （5）（2分）需要附加的存储空间是(10)__； （6）（2分）该排序算法是否是稳定的(11)____。 12. 设用希尔排序对数组{98，36，-9，0，47，23，1，8，10，7}进行排序，给出的步长（也称增量序列）依次是4，2，1则排序需__________趟，写出第一趟结束后，数组中数据的 排列次序__________。 【南京理工大学 1997 三、5 （2分）】 13．从平均时间性能而言，__________排序最佳。【青岛大学 2001 六、5 （3分）】14．对于7个元素的集合{1，2，3，4，5，6，7}进行快速排序，具有最小比较和交换次数的初始排列次序为_____。【长沙铁道学院 1997 二、1 (2分)】 15．快速排序在_____的情况下最易发挥其长处。【长沙铁道学院 1998 二、5 (2分)】类似本题的另外叙述有： (1)快速排序法在_____情况下最不利于发挥其长处，在_____情况下最易发挥其长处。 【山东大学 2001 三、5 (2分)】 16．在数据表有序时，快速排序算法的时间复杂度是____。【合肥工业大学 2001 三、10 （2分）】 17．堆排序的算法时间复杂度为：_____。【合肥工业大学 1999 三、10 （2分）】18．PROC sift(VAR r：listtype;k,m:integer); {假设r[k+1..m]中各元素满足堆的性质，本算法调整r[k]使整个序列r[k..m]中各元素满足堆的性质。} 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} 【燕山大学 1998 四、2 （15分）】 19．设n为结点个数，datatype为结点信息类型。为了进行堆排序，定义： TYPE node=RECORD key：integer；info：datatype END； VAR heap：ARRAY[1..n] OF node l，r，i，j：0..n ;x：node； 在下面的算法描述中填入正确的内容，使其实现1964年Floyd提出的建堆筛选法，要求堆建成后便找到了最小的关键码。 筛选算法sift(l,r,heap)： 步1．[准备] i←l; j ←(1)___; x←heap[i] 步2．[过筛] 循环：当(2)____时反复执行 ⑴．若j ⑵．若(4)___则heap[i]←heap[j]; (5)____; (6)____ 否则跳出循环 步3.[结束] heap[i] ← (7)____ 【山东工业大学 1996 三、2 （7分）】 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; 【北方交通大学 2000 四（20分）】 21．堆是一种有用的数据结构。试判断下面的关键码序列中哪一个是堆__________。 ①16，72，31，23，94，53 ②94，53，31，72，16，23 ③16，53，23，94，31，72 ④16，31，23，94，53，72 ⑤94，31，53，23，16，72 堆排序是一种_(1)_类型的排序，它的一个基本问题是如何建堆，常用的建堆算法是1964年Floyd提出的_(2)_，对含有n个元素的序列进行排序时,堆排序的时间复杂度是_(3)_，所需要的附加结点是_(4)_。 【山东工业大学 1994 一、2 （5分）】 22．堆是一种有用的数据结构. 堆排序是一种_(1)_排序，堆实质上是一棵_(2)_结点的层次序列。对含有N个元素的序列进行排序时，堆排序的时间复杂度是_(3)_，所需的附加存储结点是_(4)_。关键码序列05，23，16，68，94，72，71，73是否满足堆的性质_(5)_。【山东工业大学 1996 三、1 （5分）】 23．将如下的堆排序算法补写完整。说明如下： TYPE heaptype=ARRAY[1..n]OF integer； 过程heapsort的功能是将数组h中的前n个记录按关键字递减的次序排序。heapsort 调用过程sift时的参数h，k，r有如下定义：以 h[k+1]，h[k+2]，…,h[r]为根的子树已经是堆；执行sift后，以h[k]，h[k+1],h[k+2],…,h[r] 为根的子树都成为堆。 PROC sift（VAR h：heaptype；k，r：integer）； VAR i，j，x：integer；finish：boolean； BEGIN i:=k；x:=h[i]；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; 【北京工业大学 1997 五、2 (16分)】 24．设有字母序列{Q,D,F,X,A,P,N,B,Y,M,C,W},请写出按2路归并排序方法对该序列进行一趟扫描后的结果_______。【北方交通大学 2001 二、7】 25. 阅读下列程序说明和PASCAL程序，把应填入其中______处的字句写在答题纸上。程序说明： 本题给出的是将数组a的元素a1，a2,…,a n从大到小排序的子程序。子程序采用改进的选择排序方法，该方法基于以下思想： 在选择第一大元过程中, a1与a j(j=n,n-1,…,2)逐个比较，若发现a j1>a1，则a j1与a1变换，变换后新的a j1有性质a j1≥a t(j1 设程序包含有常量和类型定义： CONST maxn=1000; TYPE vector=ARRAY[1..maxn] 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;（(1)____）END; REPEAT（(2)____）; IF（(3)____）THEN（(4)____） ELSE BEGIN m:=p[k]; k:=k-1; END; UNTIL (i IF （(5)___） BEGIN t:=a[i];（(6)____）;（(7)____）END END END; 【上海海运学院 1997 七（14分）】 26．下列算法为奇偶交换排序，思路如下：第一趟对所有奇数的i,将a[i]和a[i+1]进行比较,第二趟对所有偶数的i,将a[i]和a[i+1]进行比较,每次比较时若a[i]>a[i+1],将二者交换;以后重复上述二趟过程,直至整个数组有序。 程序.(a) PROCEDURE oesort(VAR a:ARRAY[1..n] 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） 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 一、1 （10分）】 27．关键码序列（ Q，H，C，Y，Q，A，M，S，R，D，F，X），要按照关键码值递增的次序进行排序，若采用初始步长为4的Shell排序法，则一趟扫描的结果是_____；若采用以第一个元素为分界元素的快速排序法，则扫描一趟的结果是______。【北京大学 1997 一、4 （4分）】 类似本题的另外叙述有： (1)设有字符序列Q、H、C、Y、P、A、M、S、R、D、F、X要求按字符升序排序，采用初始步长为４的希尔（shell）排序，一趟扫描的结果是____;采用以首元素为分界元素的快速排序，一趟扫描的结果是_____。 【北京工业大学 1999 一、7 (8分)】 28．外部排序的基本方法是归并排序，但在之前必须先生成___。【北京邮电大学2001 二、6（2分）】 29．磁盘排序过程主要是先生成，然后对合并，而提高排序速度很重要的是，我们将采用方法来提高排序速度。【山东工业大学 1995 一、4（4分）】30．设输入的关键字满足k1>k2>…>kn，缓冲区大小为m，用置换-选择排序方法可产生____个初始归并段。 【武汉大学 2000 一、9】 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; 【东南大学 2001 五（10分）】 四、应用题 1. 内部排序（名词解释）。【燕山大学 1999 一、5 （2分）】 2. 在各种排序方法中，哪些是稳定的？哪些是不稳定的？并为每一种不稳定的排序方法举出一个不稳定的实例。【大连海事大学 1996 七、3 (４分)】 类似本题的另外叙述有： (1) 举例说明堆排序是否为稳定排序法. 【西安电子科技大学 1996 三、4 （5分）】 (2) 选择排序算法是否稳定？为什么？【燕山大学 2001 三、3 （5分）】 (3) 举例分析堆排序方法是否稳定。【北京邮电大学 1993 二、3 （6分）】 (4) 堆排序是稳定排序吗？举例说明。【东南大学 1996 一、5 （6分）】 (5) 试举例分析堆排序法是否稳定。【东南大学 1999 一、5 （5分）】 (6) 树型选择排序通常采用顺序存储结构，①试指出n个元素的原始序列一般如何在该存储结构中存放（起始存储位置，次序），请说明理由。②讨论树形选择排序的稳定性。若稳定，须说明理由；不稳定，须举反例，并尝试找出使它稳定的方法。【北京工业大学 1999 七(10分)】 3．在执行某种排序算法的过程中出现了排序码朝着最终排序序列相反的方向移动，从而认为该排序算法是不稳定的，这种说法对吗？为什么？【燕山大学 2001 三、4 （5分）】4．设有5个互不相同的元素a、b、c、d、e，能否通过7次比较就将其排好序？如果能，请列出其比较过程；如果不能，则说明原因。【北方交通大学 1996 五（10分）】5．对一个由n个关键字不同的记录构成的序列，能否用比2n-3少的次数选出该序列中关键字取最大值和关键字取最小值的记录？请说明如何实现？在最坏的情况下至少进行多少次比较？ 【东南大学 2000 一、5 （8分）】 6．利用比较的方法进行排序，在最坏的情况下，能达到的最好时间复杂性是什么？请给出详细证明。 【上海交通大学 2000 六（8分）】 7．以下概念的区别：拓扑排序与冒泡排序。【大连海事大学 1996 三、 2（3） (2分)】8．简述直接插入排序，简单选择排序，2-路归并排序的基本思想以及在时间复杂度和排序稳定性上的差别。 【西北工业大学 1999 二 (8分)】 9．快速排序，堆排序和希尔排序是时间性能较好的排序方法，也是稳定的排序方法。判断正误并改错。 【燕山大学 1998 二、5 （2分）】 10. 设LS是一个线性表，LS=(a1,a2,…,an),若采用顺序存储结构，则在等概率的前提下，插入一个元素需要平均移动的元素个数是多少？若元素插在a i与a i+1之间(0<=i<=n-1)的概率为(n-i)/(n*(n+1)/2)，则插入一个元素需要平均移动的元素个数又是多少？【西安电子科技大学 2001软件二、3 （5分）】 11．对于堆积排序法，快速排序法和归并排序法，若仅从节省存储空间考虑，则应该首先选取其中哪种方法？其次选取哪种方法？若仅考虑排序结果的稳定性，则应该选取其中哪种方法？若仅从平均情况下排序最快这一点考虑，则应该选取其中哪些方法？【北京航空航天大学 1998 一、10 （4分）】 12．在堆排序、快速排序和合并排序中：【吉林大学 2001 一、5 (6分)】 (1)．若只从存储空间考虑，则应首先选取哪种排序方法，其次选取哪种排序方法，最后选 取哪种排序方法？ (2)．若只从排序结果的稳定性考虑，则应选取哪种排序方法？ (3)．若只从平均情况下排序最快考虑，则应选取哪种排序方法？ (4)．若只从最坏情况下排序最快并且要节省内存考虑，则应选取哪种排序方法？ 13. 快排序、堆排序、合并排序、Shell排序中哪种排序平均比较次数最少，哪种排序占用空间最多，哪几种排序算法是不稳定的？【首都经贸大学 1997 一、3 （4分）】14．欲求前k个最大元素，用什么分类方法好？为什么？什么是稳定分类？分别指出下列算法是否是稳定分类算法，或易于改成稳定分类算法？ A．插入分类 B．快速分类 C．合并分类 D．堆分类 E．基数分类【东南大学 1994 一、3 （8分）】 15．考虑由三个不同关键词构成的序列：｛a,b,c｝，试画出直接插入排序算法的二叉判定树。 【吉林大学 2001 一、3 (4分)】 16. 请阅读下列算法，回答问题 PROCEDURE sort（r，n） BEGIN FOR i:=2 TO n DO BEGIN x:=r(i)；r(O):=x；j:=i-1； WHILE x.key BEGIN r(j+1):=r(j); j:=j-1 END; r(j+1):=x END END; 问题一：这是什么类型的排序算法，该排序算法稳定吗？ 问题二：设置r(O)的作用是什么？若将WHILE—DO 语句中判断条件改为x.key<=r(j).KEY, 该算法将会有什么变化，是否还能正确工作？【上海海运学院 1998 六（10分）】 17．下面是冒泡排序算法，请阅读并完成该程序，并回答以下问题： PROCEDURE bubblesort (r,n) BEGIN i:=1; m:=n-1; flag:=1; WHILE (i<=(1)___)AND(flag=(2)____) DO BEGIN flag:= (3)___; FOR j:=1 TO m DO IF r[j].key>r[j+1].key THEN BEGIN flag:= (4)___; t:=r[j]; r[j]:=r[j+1]; r[j+1]:=t END; i:=i+1;m:=m-1 END; END. （1）请在上面横线上填上适当的语句，完成该算法程序。 （2）设计标志flag的作用是什么？ （3）该算法结点的最大比较次数和最大移动次数是多少？ （4）该分类算法稳定吗？【上海海运学院 1996 六（12分） 1999 六（16分）】18．仔细阅读下面的过程，并回答有关的问题 PROCEDURE unknownname(VAR A:array[1..500] OF integer;n:integer); VAR i,j,x:integer; b:boolean; BEGIN b:=true; i:=1; WHILE (i BEGIN b:=false; FOR j:=1 TO(1)___DO IF(2)___ THEN BEGIN x:=A[j]; A[j]:=A[j+1]; A[j+1]:=x; (3)___ END; i:=i+1; END END; 【西安电子科技大学 2001计应用六（14分）】 （1）在中填上正确的语句，使该过程能完成预期的功能。 （2）该过程使用的是什么排序方法？ （3）当数组A的元素初始时已按值递增排序，该过程执行中会进行多少次比较？多少次交换？ （4）当数组A的元素初始时已按值递减排序，该过程执行中会进行多少次比较？多少次交换？ 19．写出下列排序算法的基本思想，并写出对序列（23，12，35，47，16，25，36，19，21，16）进行排序时每一趟的结果。 PROC bbsort(VAR r: sequence; n: integer); {r是一个数组} d:=1; pos[-1]:=1; pos[1]:=n; i:=1; exchanged:= true; WHILE exchanged DO [ exchanged:= false; WHILE i<>pos[d] DO [IF (r[i]-r[i+d])*d>0 THEN [r[i]与r[i+d]交换; exchanged:=true;]; i:=i+d; ] pos[d]:=pos[d]-d; i:=pos[d]; d:=-d; ] ENDP; 【山东科技大学 2002 五（12分）】 20．设要求从大到小排序。问在什么情况下冒泡排序算法关键字交换的次数为最大。 【南京航空航天大学 1996 九、1 （4分）】 21．设与记录R1,R2，…，Rn对应的关键词分别是K1，K2，…，Kn。如果存在Ri和Rj使得j 22．现有一文件Ｆ含有1000个记录，其中只有少量记录次序不对，且它们距离正确位置不远；如果以比较和移动次数作为度量，那末将其排序最好采用什么方法？为什么？【北方交通大学 1997 四（8分）】 23．分析下面排序算法中各带标号语句的频度及此算法的时间复杂度，并指出该算法是属于哪一种排序方法。【北京邮电大学 1996 一、2 （7分）】 PROCEDURE sort (VAR a: ARRAY [1..n] OF integer); BEGIN 1 FOR i:=1 TO n-1 DO 2 [j:=i; 3 FOR k:=j+1 TO n DO 4 IF a[k] 5 t:=a[i]; a[i]:=a[j]; a[j];=t ] END; 24．设待排序的关键码分别为28，13，72，85，39，41，6，20。按二分法插入排序算法已使前七个记录有序，中间结果如下: 【山东工业大学 1996 七（10分）】 6 13 28 39 41 72 85 20 i=1 m=4 r=7 试在此基础上，沿用上述表达方式，给出继续采用二分法插入第八个记录的比较过程。 (1) 使用二分法插入排序所要进行的比较次数，是否与待排序的记录的初始状态有关？ (2) 在一些特殊情况下，二分法插入排序比直接插入排序要执行更多的比较。这句话对吗？ 25．算法模拟（15分，问题1，2各6分，问题3占3分） 设待排序的记录共7个，排序码分别为8，3，2，5，9，1，6。 (1) 用直接插入排序。试以排序码序列的变化描述形式说明排序全过程（动态过程）要求按递减顺序排序。 (2) 用直接选择排序。试以排序码序列的变化描述形式说明排序全过程（动态过程）要求按递减顺序排序。 (3) 直接插入排序算法和直接选择排序算法的稳定性如何？【山东工业大学 1997 四（15分）】 26．在执行某个排序算法过程中，出现了排序关键字朝着最终排序序列相反的方向的移动，从而认为该算法是不稳定的。这种说法对么？为什么？【东北大学 2001 一、1( 4分)】类似本题的另外叙述有： (1) （冒泡）排序过程中，有的关键字在某趟排序中可能朝着与最终排序相反的方向移动，试举例说明之。快速排序过程中有没有这种现象？【东北大学 2000 一、5 (4分)】27. 对下面数据表，写出采用SHELL排序算法排序的每一趟的结果，并标出数据移动情况。（125，11，22， 34，15，44，76，66，100，8，14，20，2，5，1）。【合肥工业大学 1999 四、4 （5分）】 28.快速排序的最大递归深度是多少？最小递归深度是多少？【清华大学 1999 一、1 （2分）】 29. 已知某文件的记录关键字集为{50，10，50，40，45，85，80}，选择一种从平均性能而言是最佳的排序方法进行排序，且说明其稳定性。【西安电子科技大学 1996 五（10分）】30. 在内排序算法中，待排序的数据已基本有序时，花费时间反而最多的排序方法是哪种？ 【西安电子科技大学 2000计应用一、1 （5分）】 31．我们知道，对于n个元素组成的线性表进行快速排序时，所需进行的比较次数与这n 个元素的初始排序有关。问：【西安电子科技大学 2001计应用五（12分）】【中国矿业大学 2000 六（10分）】 （1）当n=7时，在最好情况下需进行多少次比较？请说明理由。 （2）当n=7时，给出一个最好情况的初始排序的实例。 （3）当n=7时，在最坏情况下需进行多少次比较？请说明理由。 （4）当n=7时，给出一个最坏情况的初始排序的实例。 类似本题的另外叙述有： (1) 快速排序（quick sorting）的效率与原始序列有关，现用快速排序算法对关键字分别为1—15的15 个元素进行排序 ①在最好情况下要进行几遍比较，给出一种原始序列实例； ②在最坏情况下要进行几遍比较，给出一种原始序列实例。【浙江大学 1995 七(12分)】 (2) 对N个元素组成的线性表进行快速排序时，所需进行的比较次数依赖于这N个元素的初始排列。对N=7，给出快速排序的一个最好情况的初始排列实例(7个元素可取自集合{l，2，3，4，5，6，7})。 【西北大学 2000 二、5(5分)】 32．有一随机数组(25,84,21,46,13,27,68,35,20),现采用某种方法对它们进行排序,其每趟排序结果如下, 则该排序方法是什么? 【武汉交通科技大学 1996 二、5 (6分)】初始:25,84,21,46,13,27,68,35,20 第一趟:20,13,21,25,46,27,68,35,84 第二趟:13,20,21,25,35,27,46,68,84 第三趟:13,20,21,25,27,35,46,68,84 33．快速排序是在所有情况下，排序速度最快吗？为什么？在何种情况下使用此排序法最好？ 【北京邮电大学 1993 一、1 （5分）】 34．对给定文件（28，07，39，10，65，14，61，17，50，21）选择第一个元素28进行划分，写出其快速排序第一遍的排序过程。【厦门大学 1998 七、1 （8分）】 类似本题的另外叙述有： (1) 对下列关键字序列进行快速排序(从小至大) (48, 38, 65, 95, 73, 13, 27, 50)要求给出快速排序的算法思想,并画出排序过程示意图。【南京航空航天大学 1999 五（10分）】 (2) 设记录的关键字集合K={23，9，39，5，68，12，62，48，33}，给定的增量序列D={4，2，1}，请写出对K按“SHELL方法”排序时各趟排序结束时的结果；若每次以表的第一元素为基准（或枢轴），写出对K按“快速排序方法”排序时，各趟排序结束时的结果。 【北京科技大学 1999 七（10分） 2000 七（10分）】 35．下面是一改进了的快速分类算法 1. PROCEDURE qsort1(VAR list:afile;m,n:integer); 2 (设list[m].key 3 VAR i,j,k:integer; 4 BEGIN 5 WHILE m 6 BEGIN 7 i:=m;j:=n+1; k:=list[m].key; 8 REPEAT 9 REPEAT i:=i+1 UNTIL list[i].key>=k; 10 REPEAT j:=j-1 UNTIL list[j].key<=k; 11 IF i 12 UNTIL i>=j; 13 interchange( list[m],list[j]); 14 IF n-j>=j-m 15 THEN BEGIN qsort1(list,m,j+1);m:=j+1;END 16 ELSE BEGIN qsort1(list,j+1,n);n:=j-1;END 17 END;(OF WHILE) 18 END. 问： （1）将第9、10行中的＞=，＜=分别改成＞，＜行吗？为什么？（5分） （2）该排序算法稳定否？举例说明（5分） （3）对输入文件（22，3，30，4，60，11，58，18，40，16），列表表示该文件在每次调用qsort1时的状态及相应m、n值。（5分） （4）若输入文件有n个记录，简要说明支持qsort1递归所需最大栈空间用量（设一层递归用一个单位栈空间）。（5分）【东南大学 1998 四（20分）】 36．如果只要找出一个具有n个元素的集合的第k（1≤k≤n）个最小元素，你所学过的排序方法中哪种最适合？给出实现的思想。【北方交通大学 1998 六（10分）】 37．已知快速排序和归并排序的算法分别如下所示： PROCEDURE qksort(VAR r:listtype; s,t:integer); BEGIN IF s qkpass(r,s,t,k); qksort(r,s,k-1); qksortd(r,k+1,t) END 数据结构1800例题与答案 第一章绪论 一、选择题（每小题2分） 1．算法的计算量的大小称为计算的（ B ）。【北京邮电大学2000 二、3 （20/8分）】 A．效率B．复杂性C．现实性D．难度 2．算法的时间复杂度取决于（C）。【中科院计算所1998 二、1 （2分）】 A．问题的规模B．待处理数据的初态C．A和B D．都不是 3．计算机算法指的是（①C ），它必须具备（② B ）这三个特性。 ①A．计算方法B．排序方法 C．解决问题的步骤序列D．调度方法 ②A．可执行性、可移植性、可扩充性B．可执行性、确定性、有穷性 C．确定性、有穷性、稳定性D．易读性、稳定性、安全性【南京理工大学1999 一、1（2分）【武汉交通科技大学1996 一、1（4分）】4．一个算法应该是（B ）。【中山大学1998 二、1（2分）】 A．程序B．问题求解步骤的描述 C．要满足五个基本特性D．A和C. 5．下面关于算法说法错误的是（ D ）【南京理工大学2000 一、1（1.5分）】A．算法最终必须由计算机程序实现 B.为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的 6. 下面说法错误的是（C ）【南京理工大学2000 一、2 （1.5分）】 (1）算法原地工作的含义是指不需要任何额外的辅助空间 （2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （4）同一个算法，实现语言的级别越高，执行效率就越低 A．(1) B.(1),(2) C.(1),(4) D.(3) 7．从逻辑上可以把数据结构分为（ C ）两大类。【武汉交通科技大学1996 一、4（2分）】 A．动态结构、静态结构B．顺序结构、链式结构 C．线性结构、非线性结构D．初等结构、构造型结构 8．以下与数据的存储结构无关的术语是（ D ）。【北方交通大学2000 二、1（2分）】A．循环队列 B. 链表 C. 哈希表 D. 栈 9．以下数据结构中，哪一个是线性结构（ D ）？【北方交通大学2001 一、1（2分）】 A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串 10．以下那一个术语与数据的存储结构无关？（Ａ）【北方交通大学2001 一、2（2分）】 A．栈 B. 哈希表 C. 线索树 D. 双向链表 11．在下面的程序段中，对x的赋值语句的频度为（Ｃ）【北京工商大学2001 一、10（3分）】 FOR i:=1 TO n DO 第9章排序自测卷姓名班级 一、填空题（每空1分，共24分） 1. 大多数排序算法都有两个基本的操作：比较和移动。 2. 在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7个记录60插 入到有序表时，为寻找插入位置至少需比较6 次。 3. 在插入和选择排序中，若初始数据基本正序，则选用插入；若初始数据基本反序，则选用 选择。 4. 在堆排序和快速排序中，若初始记录接近正序或反序，则选用堆排序；若初始记录基本 无序，则最好选用快速排序。 5. 对于n个记录的集合进行冒泡排序，在最坏的情况下所需要的时间是O(n2) 。若对其进行快速 排序，在最坏的情况下所需要的时间是O(n2)。 6. 对于n个记录的集合进行归并排序，所需要的平均时间是O(nlog2n)，所需要的附加空间 是O(n) 。 7．对于n个记录的表进行2路归并排序，整个归并排序需进行┌log2n┐趟（遍）。 8. 设要将序列（Q, H, C, Y, P, A, M, S, R, D, F, X）中的关键码按字母序的升序重新排列，则： 冒泡排序一趟扫描的结果是H C Q P A M S R D F X Y； 初始步长为4的希尔（shell）排序一趟的结果是P A C S Q H F X R D M Y ； 二路归并排序一趟扫描的结果是H Q C Y A P M S D R F X； 快速排序一趟扫描的结果是 F H C D P A M Q R S Y X； 堆排序初始建堆的结果是A D C R F Q M S Y P H X。 9. 在堆排序、快速排序和归并排序中， 若只从存储空间考虑，则应首先选取方法，其次选取快速排序方法，最后选取归并排序方法； 若只从排序结果的稳定性考虑，则应选取归并排序方法； 若只从平均情况下最快考虑，则应选取堆排序、快速排序和归并排序方法； 若只从最坏情况下最快并且要节省内存考虑，则应选取堆排序方法。 二、单项选择题（每小题1分，共18分） （ C ）1．将5个不同的数据进行排序，至多需要比较次。 Ａ. 8 Ｂ. 9 Ｃ. 10 Ｄ. 25 （C）2．排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为 Ａ. 希尔排序Ｂ. 冒泡排序Ｃ. 插入排序Ｄ. 选择排序（D）3．从未排序序列中挑选元素，并将其依次插入已排序序列（初始时为空）的一端的方法，称为 第3章栈和队列 一选择题 1. 对于栈操作数据的原则是（）。【青岛大学 2001 五、2（2分）】 A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序 2. 在作进栈运算时,应先判别栈是否( ① ),在作退栈运算时应先判别栈是否( ② )。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为( ③ )。 为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存空间时,应将两栈的 ( ④ )分别设在这片内存空间的两端,这样,当( ⑤ )时，才产生上溢。①, ②: A. 空 B. 满 C. 上溢 D. 下溢 ③: A. n-1 B. n C. n+1 D. n/2 ④: A. 长度 B. 深度 C. 栈顶 D. 栈底 ⑤: A. 两个栈的栈顶同时到达栈空间的中心点. B. 其中一个栈的栈顶到达栈空间的中心点. C. 两个栈的栈顶在栈空间的某一位置相遇. D. 两个栈均不空,且一个栈的栈顶到达另一个栈的栈底. 【上海海运学院 1997 二、1（5分）】【上海海运学院 1999 二、1（5分）】 3. 一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（）。 A. 不确定 B. n-i+1 C. i D. n-i 【中山大学 1999 一、9(1分)】 4. 若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j个输出元素是（）。 A. i-j-1 B. i-j C. j-i+1 D. 不确定的 【武汉大学 2000 二、3】 5. 若已知一个栈的入栈序列是1,2,3,…,n，其输出序列为p1,p2,p3，…，p N,若p N是n，则p i是( )。 A. i B. n-i C. n-i+1 D. 不确定 【南京理工大学 2001 一、1（1.5分）】 6. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（） A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 【北方交通大学 2001 一、3（2分）】 7. 设栈的输入序列是1，2，3，4,则（）不可能是其出栈序列。【中科院计算所2000一、10(2分)】 A. 1，2，4，3， B. 2，1，3，4， C. 1，4，3，2， D. 4，3，1，2， E. 3，2，1，4， 8. 一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（）。 A. 2 3 4 1 5 B. 5 4 1 3 2 C. 2 3 1 4 5 D. 1 5 4 3 2 【南开大学 2000 一、1】【山东大学 2001 二、4 (1分)】【北京理工大学 2000 一、2（2分）】 9. 设一个栈的输入序列是 1，2，3，4，5,则下列序列中，是栈的合法输出序列的是（）。 A. 5 1 2 3 4 B. 4 5 1 3 2 C. 4 3 1 2 5 D. 3 2 1 5 4 【合肥工业大学 2001 一、1（2分）】 10. 某堆栈的输入序列为a, b，c ，d,下面的四个序列中，不可能是它的输出序列的是 第八章自测题 一、单选题 1、绩效管理能够提供有关员工的工作及成果的信息，这 A 主要指绩效管理的（）。 A、反馈功能 B、甄别功能 C、补偿功能 D、管理功能 2、绩效管理的核心、关键部分是（）。C A、准备绩效考核系统 B、实施绩效考核过程 C、设计绩效考核系统 D、评估绩效考核系统 3、信度，主要指绩效考核系统所具备标准中的（）。C A、明确性 B、敏感性 C、一致性 D、准确性 4、效度，主要指绩效考核系统所具备标准中的（）。D A、明确性 B、敏感性 C、一致性 D、准确性 5、绩效考核指标设计过程的第一步为（）。C A、试用 B、归类合并筛选 C、指标内容设计 D、量化 6、绩效考核指标必须与工作内容紧密相关，而且是员工 A 能够影响和控制的，这主要指绩效考核指标的（）。 A、绩效考核指标与工作绩效一致原则 B、绩效考核指标的可 观察原则C、绩效考核指标的结构性原则D、绩效考核指标的独立性原则 7、在绩效考核过程中，可以极大的降低抵触情绪的考核 D 者是（）。 A、直接上司 B、同事 C、被考核者本人 D、下级员工 8、适用于专业性组织如大学和医院或专业性部门的考评 方法为（）。 B A、直接上司 B、同事 C、被考核者本人 D、下级员工/FONT> 9、可能会导致“穿小鞋”的一种考评方法是（）。D A、直接上司 B、同事 C、被考核者本人 D、下级员工 10、绩效考评的实施程序中的纵向程序中，考评一般先 （）。 A A、基层考评 B、中层考评 C、高层考评 D、都可以 11、要求考核者将每一个员工与其他员工进行一对一的比 较，并记录员工在每一次比较中的结果，最后，汇总员工 的优胜次数，得出员工的绩效得分，排出顺序。这主要指 （）。 C A、简单排序法 B、交替配对排序法 C、配对比较法 D、强 制分布法 12、绩效考核中，典型的成果法是（）。A A、目标管理法 B、交替配对排序法 C、评价中心技术法 D、 强制分布法 二、多选题 1、下列关于绩效管理理解正确的是（）。BCE A、绩效管理就是绩效考核 B、绩效考核只是绩效管理过程的一个组成 部分 C、绩效管理的核心是绩效考核 D、绩效管理是一个行为 E、 绩效管理可以各种形式被运用到管理决策中 2、绩效管理的职能包括（）。ABE A、反馈功能 B、甄别功能 C、补偿功能 D、激励功能 E、 管理功能 第9章排序自测卷答案姓名班级 一、填空题（每空1分,共24分) 1. 大多数排序算法都有两个基本的操作：比较(两个关键字的大小）和移动（记录或改变指向记录的 指针）。 2．在对一组记录（54，38,96，2３，１５,7２，６0,45，83)进行直接插入排序时，当把第7个记录６0插入到有序表时，为寻找插入位置至少需比较３次。(可约定为,从后向前比较) 3. 在插入和选择排序中，若初始数据基本正序,则选用插入排序(到尾部）;若初始数据基本反序,则选用 选择排序。 4．在堆排序和快速排序中,若初始记录接近正序或反序，则选用堆排序；若初始记录基本无序,则最好选用快速排序。 5. 对于n个记录的集合进行冒泡排序,在最坏的情况下所需要的时间是O(n２) 。若对其进行快速排序，在 最坏的情况下所需要的时间是O(n2) 。 6．对于n个记录的集合进行归并排序，所需要的平均时间是O(ｎloｇ2n）,所需要的附加空间是O(ｎ）。 8．设要将序列(Q，H,C, Y, P, A，Ｍ, S, R, D，F,X)中的关键码按字母序的升序重新排列,则：冒泡排序一趟扫描的结果是H, C, Q, P, A, Ｍ，S，R, D, Ｆ,X ,Ｙ; 初始步长为4的希尔（sheｌｌ)排序一趟的结果是P, A, C, S，Q, Ｄ，Ｆ, X , R, H,M,Y; 二路归并排序一趟扫描的结果是H, Q, C，Y，Ａ,Ｐ,M，S,D, R, F, X; 快速排序一趟扫描的结果是F，H, C，D,P,Ａ, M, Q, R,Ｓ, Y，X； 堆排序初始建堆的结果是A,D, C，R, F, Ｑ,M, S, Ｙ,Ｐ, H，X。 9. 在堆排序、快速排序和归并排序中, 若只从存储空间考虑，则应首先选取堆排序方法,其次选取快速排序方法，最后选取归并排序方法; 若只从排序结果的稳定性考虑,则应选取归并排序方法； 若只从平均情况下最快考虑,则应选取快速排序方法; 若只从最坏情况下最快并且要节省内存考虑，则应选取堆排序方法。 二、单项选择题（每小题１分，共１8分） ( C)1.将5个不同的数据进行排序,至多需要比较次。 A. ８Ｂ．９Ｃ．1０ D. 25 ( C)２. 排序方法中，从未排序序列中依次取出元素与已排序序列(初始时为空）中的元素进行比较，将其放 第6章树和二叉树 部分答案解释如下。 12. 由二叉树结点的公式：n=n0+n1+n2=n0+n1+(n0-1)=2n0+n1-1，因为n=1001,所以1002=2n0+n1,在完全二叉树树中，n1只能取0或1,在本题中只能取0，故n=501，因此选E。 42.前序序列是“根左右”，后序序列是“左右根”，若要这两个序列相反，只有单支树，所以本题的A和B均对，单支树的特点是只有一个叶子结点，故C是最合适的，选C。A或B 都不全。由本题可解答44题。 47. 左子树为空的二叉树的根结点的左线索为空（无前驱），先序序列的最后结点的右线索为空（无后继），共2个空链域。 52．线索二叉树是利用二叉树的空链域加上线索，n个结点的二叉树有n+1个空链域。 部分答案解释如下。 6．只有在确定何序（前序、中序、后序或层次）遍历后，遍历结果才唯一。 19．任何结点至多只有左子树的二叉树的遍历就不需要栈。 24. 只对完全二叉树适用，编号为i的结点的左儿子的编号为2i(2i<=n)，右儿子是2i+1（2i+1<=n） 37. 其中序前驱是其左子树上按中序遍历的最右边的结点（叶子或无右子女），该结点无右孩子。 38 . 新插入的结点都是叶子结点。 42. 在二叉树上，对有左右子女的结点，其中序前驱是其左子树上按中序遍历的最右边的结点（该结点的后继指针指向祖先），中序后继是其右子树上按中序遍历的最左边的结点（该结点的前驱指针指向祖先）。 44．非空二叉树中序遍历第一个结点无前驱，最后一个结点无后继，这两个结点的前驱线索和后继线索为空指针。 三.填空题 1.(1)根结点(2)左子树(3)右子树 2.(1)双亲链表表示法(2)孩子链表表示法(3)孩 子兄弟表示法 3．p->lchild==null && p->rchlid==null 4.(1) ++a*b3*4-cd (2)18 5.平衡 因子 6. 9 7. 12 8.(1)2k-1 (2)2k-1 9.(1)2H-1 (2)2H-1 (3)H=?log2N?+1 10. 用顺序存储二叉树时，要按完全二叉树的形式存储，非完全二叉树存储时，要加“虚结 点”。设编号为i和j的结点在顺序存储中的下标为s 和t ,则结点i和j在同一层上的条 件是?log2s?=?log2t?。 11. ?log2i?=?log2j?12.(1)0 (2)(n-1)/2 (3)(n+1)/2 (4) ?log2n?+1 13.n 14. N2+1 15.(1) 2K+1-1 (2) k+1 16. ?N/2? 17. 2k-2 18. 64 19. 99 20. 11 21.(1) n1-1 (2)n2+n3 22.(1)2k-2+1（第k层1个结点，总结点个数是2H-1，其双亲是2H-1/2=2k-2）(2) ?log2i?+1 23.69 24. 4 25.3h-1 26. ?n/2? 27. ?log2k?+1 28.(1)完全二叉树 (2)单枝树，树中任一结点（除最后一个结点是叶子外）,只有左子女或 只有右子女。 29.N+1 30.(1) 128(第七层满，加第八层１个) (2) 7 31. 0至多个。任意二叉树，度为１的结点个数没限制。只有完全二叉树，度为１的结点个 数才至多为1。 32．21 33.(1)2 (2) n-1 (3) 1 (4) n (5) 1 (6) n-1 34.(1) FEGHDCB (2)BEF（该二叉树转换成森林，含三棵树，其第一棵树的先根次序是 BEF） 35.(1)先序（2）中序 36. (1)EACBDGF （2）2 37.任何结点至多只有右子女 的二叉树。 38.(1)a (2) dbe (3) hfcg 39.(1) . (2) ...GD.B...HE..FCA 40.DGEBFCA 41．(1)5 （2）略 42.二叉排序树 43.二叉树 44. 前序 45.(1)先根次序（2）中根次序46.双亲的右子树中最左下的叶子结点47.2 48.(n+1)/2 49.31（x的后继是经x的双亲y的右子树中最左下的叶结点） 50.(1)前驱 (2)后 继 51.(1)1 (2)y^.lchild (3)0 (4)x (5)1 (6) y (7)x(编者注：本题按 中序线索化) 52.带权路径长度最小的二叉树，又称最优二叉树 53.69 54.(1)6 (2)261 55.(1)80 (2)001（不唯一）56.2n0-1 57.本题①是表达式求值，②是在二叉排序树中删除值为x的结点。首先查找x，若没有x， 则结束。否则分成四种情况讨论：x结点有左右子树；只有左子树；只有右子树和本身是叶 子。 (1)Postoder_eval(t^.Lchild) (2) Postorder_eval(t^.Rchild) (3)ERROR(无此运 算符)(4)A (5)tempA^.Lchild (6)tempA=NULL(7)q^.Rchild (8)q (9)tempA^.Rchild (10)tempA^.Item 第9章排序 一、填空题（每空1分，共24分） 1. 大多数排序算法都有两个基本的操作：和。 2. 在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置至少需比较次。 3. 在插入和选择排序中，若初始数据基本正序，则选 用；若初始数据基本反序，则选用。 4. 在堆排序和快速排序中，若初始记录接近正序或反序，则选用；若初始记录基本无序，则最好选用。 5. 对于n个记录的集合进行冒泡排序，在最坏的情况下所需要的时间是。若对其进行快速排序，在最坏的情况下所需要的时间是。 6. 对于n个记录的集合进行归并排序，所需要的平均时间是，所需要的附加空间是。 7．对于n个记录的表进行2路归并排序，整个归并排序需进行趟（遍）。 8. 设要将序列（Q, H, C, Y, P, A, M, S, R, D, F, X）中的关键码按字母序的升序重新排列，则： 冒泡排序一趟扫描的结果是； 初始步长为4的希尔（shell）排序一趟的结果是； 二路归并排序一趟扫描的结果是； 快速排序一趟扫描的结果是； 堆排序初始建堆的结果是。9. 在堆排序、快速排序和归并排序中， 若只从存储空间考虑，则应首先选取方法，其次选取方法，最后选取方法； 若只从排序结果的稳定性考虑，则应选取方法； 若只从平均情况下最快考虑，则应选取方法； 若只从最坏情况下最快并且要节省内存考虑，则应选取方法。 二、单项选择题（每小题1分，共18分） 1．将5个不同的数据进行排序，至多需要比较次。 Ａ. 8 Ｂ. 9 Ｃ. 10 Ｄ. 25 2．排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为 Ａ. 希尔排序Ｂ. 冒泡排序Ｃ. 插入排序Ｄ. 选择排序3．从未排序序列中挑选元素，并将其依次插入已排序序列（初始时为空）的一端的方法，称为 Ａ. 希尔排序Ｂ. 归并排序Ｃ. 插入排序Ｄ. 选择排序4．对ｎ个不同的排序码进行冒泡排序，在下列哪种情况下比 第 5 章数组和广义表 一、选择题 1.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其 存储地址为1，每个元素占一个地址空间，则a85的地址为（）。【燕山大学 2001 一、2 （2分）】 A. 13 B. 33 C. 18 D. 40 2. 有一个二维数组A[1:6，0:7] 每个数组元素用相邻的6个字节存储，存储器按字节编址， 那么这个数组的体积是（①）个字节。假设存储数组元素A[1，0]的第一个字节的地址是0， 则存储数组A的最后一个元素的第一个字节的地址是（②）。若按行存储，则A[2，4]的第 一个字节的地址是（③）。若按列存储，则A[5，7]的第一个字节的地址是（④）。就一般情 况而言，当（⑤）时，按行存储的A[I，J]地址与按列存储的A[J，I]地址相等。供选择的 答案：【上海海运学院 1998 二、2 （5分）】 ①-④： A．12 B. 66 C. 72 D. 96 E. 114 F. 120 G. 156 H. 234 I. 276 J. 282 K. 283 L. 288 ⑤： A．行与列的上界相同 B. 行与列的下界相同 C. 行与列的上、下界都相同 D. 行的元素个数与列的元素个数相同 3. 设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1 到8 ，j的值为1 到10， 数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为( )。 A. BA+141 B. BA+180 C. BA+222 D. BA+225 【南京理工大学 1997 一、8 （2分）】 4. 假设以行序为主序存储二维数组A=array[1..100，1..100]，设每个数据元素占2个存 储单元，基地址为10，则LOC[5，5]=（）。【福州大学 1998 一、10 (2分)】 A. 808 B. 818 C. 1010 D. 1020 5. 数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000 的内存单元中，则元素A[5，5]的地址是( )。【南京理工大学 2001 一、13 （1.5分）】 A. 1175 B. 1180 C. 1205 D. 1210 6. 有一个二维数组A[0:8,1:5],每个数组元素用相邻的4个字节存储，存储器按字节编址， 假设存储数组元素A[0,1]的第一个字节的地址是0，存储数组A的最后一个元素的第一个字 节的地址是（①）。若按行存储，则A[3,5]和 A[5,3]的第一个字节的地址是（②） 和（③）。若按列存储，则A[7,1]和A[2,4]的第一个字节的地址是（④）和（⑤）。【上海海运学院 1996 二、1 （5分）】 ①-⑤:A.28 B.44 C.76 D.92 E.108 F.116 G.132 H.176 I.184 J.188 7. 将一个A[1..100，1..100]的三对角矩阵，按行优先存入一维数组B[1‥298]中，A中元 素A6665（即该元素下标i=66，j=65），在B数组中的位置K为（）。供选择的答案： A. 198 B. 195 C. 197 【北京邮电大学 1998 二、5 （2分）】 8. 二维数组A的元素都是6个字符组成的串，行下标i的范围从0到8，列下标j的范圈 从1到10。从供选择的答案中选出应填入下列关于数组存储叙述中（）内的正确答案。（1）存放A至少需要（）个字节； （2）A的第8列和第5行共占（）个字节； （3）若A按行存放，元素A[8，5]的起始地址与A按列存放时的元素（）的起始地 第10 章排序练习题答案 一、填空题 1. 大多数排序算法都有两个基本的操作：比较和移动。 2. 在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7 个记录60 插 入到有序表时，为寻找插入位置至少需比较 3 次。 3.在插入和选择排序中，若初始数据基本正序，则选用插入；若初始数据基本反序，则选用 选择。 正序时两种方法移动次数均为0，但比较次数量级不同，插入法：n-1 即O(n)，选择法：O(n2) 反序时两种方法比较次数量级相同，均为O(n2)，但移动次数不同，插入法：O(n2)，选择法：3(n-1)即O(n) 4.在堆排序和快速排序中，若初始记录接近正序或反序，则选用堆排序；若初始记录基本无 序，则最好选用快速排序。 5.对于n 个记录的集合进行冒泡排序，在最坏的情况下所需要的时间是O(n2) 。若对其进行快速 排序，在最坏的情况下所需要的时间是O(n2) 。 6.对于n 个记录的集合进行归并排序，所需要的平均时间是O(nlog2n) ，所需要的附加空间是O(n) 。 7.对于n 个记录的表进行2 路归并排序，整个归并排序需进行┌log2n┐趟（遍）。 8.设要将序列（Q, H, C, Y, P, A, M, S, R, D, F, X）中的关键码按字母序的升序重新排列，则： 冒泡排序一趟扫描的结果是 H C Q P A M S R D F X Y ； 二路归并排序一趟扫描的结果是H Q C Y A P M S D R F X； 快速排序一趟扫描的结果是 F H C D P A M Q R S Y X； 堆排序初始建堆的结果是Y S X R P C M H Q D F A 。（大根堆） 9.在堆排序、快速排序和归并排序中， 若只从存储空间考虑，则应首先选取堆排序方法，其次选取快速排序方法，最后选取归并排序方法；若只从排序结果的稳定性考虑，则应选取归并排序方法； 若只从平均情况下最快考虑，则应选取快速排序方法； 若只从最坏情况下最快并且要节省内存考虑，则应选取堆排序方法。 二、单项选择题 （ C ）1．排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为 Ａ. 归并排序Ｂ. 冒泡排序Ｃ. 插入排序Ｄ. 选择排序 （ D ）2．从未排序序列中挑选元素，并将其依次插入已排序序列（初始时为空）的一端的方法，称为Ａ. 冒泡排序Ｂ. 归并排序Ｃ. 插入排序Ｄ. 选择排序 （ B ）3．对ｎ个不同的排序码进行冒泡排序，在下列哪种情况下比较的次数最多。 Ａ. 从小到大排列好的Ｂ. 从大到小排列好的Ｃ. 元素无序Ｄ. 元素基本有序 （ D ）4．对ｎ个不同的排序码进行冒泡排序，在元素无序的情况下比较的次数为 第十章：内部排序练习题 一、选择题 1、下述几种排序方法中，平均查找长度最小的是（）。 A、插入排序 B、选择排序 C、快速排序 D、归并排序 2、设关键字序列为（3，7，6，9，7，1，4，5，20），对其进行排序的最小交换次数为（）。 A、6 B、7 C、8 D、20 3、下列排序算法中不稳定的有（）。 A、直接选择排序 B、直接插入排序 C、冒泡排序 D、二叉排序 E、Shell排序 F、快速排序 G、归并排序 H、堆排序 I、基数排序 4、内部排序多个关键字的文件，最坏情况下最快的排序方法是（），相应的时间复杂度为（），该算法是（）排序方法。 A、快速排序 B、插入排序 C、归并排序 D、简单选择排序 E、O(nlog2n) F、O(n2) G、O(n2log2n) H、O(n) I、稳定J、不稳定 5、对初始状态为递增的表按递增顺序排序，最省时间的是（）算法，最费时间的算法是（）。 A、堆排序 B、快速排序 C、插入排序 D、归并排序 6、下述几种排序方法中，要求内存量最大的是（）。 A、插入排序 B、选择排序 C、快速排序 D、归并排序 7、在下面的排序方法中，关键字比较的次数与记录的初始排列次序无关的是（）。 A、希尔排序 B、冒泡排序 C、插入排序 D、选择排序 8、下列排序中，排序速度与数据的初始排列状态没有关系的是（）。 A、直接选择排序 B、基数排序 C、堆排序 D、直接插入排序 9、若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法为（）。 A、快速排序 B、堆排序 C、归并排序 D、直接插入排序 10、排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列正确位置上的方法，称为（）。 A、希尔排序 B、冒泡排序 C、插入排序 D、选择排序 11、每次把待排序的元素划分为左右两个子区间，其中左区间中元素的关键字均小于等于基准元素的关键字，右区间中元素的关键字均大于基准元素的关键字，则此排序方法为（）。 A、堆排序 B、快速排序 C、冒泡排序 D、Shell排序 12、排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为（）。 A、希尔排序 B、归并排序 C、插入排序 D、选择排序 13、n个记录的直接插入排序所需记录关键码的最大比较次数为（）。 A、nlog2n B、n2/2 C、(n+2)(n-1)/2 D、n-1 14、n个记录的直接插入排序所需的记录最小移动次数为（）。 A、2(n-1) B、n2/2 C、(n+3)(n-2)/2 D、2n 15、快速排序在（）情况下最不利于发挥其长处，在（）情况下最易发挥其长处。 A、被排序的数据量很大 B、被排序的数据已基本有序 C、被排序的数据完全有序 D、被排序的数据中最大与最小值相差不大 E、要排序的数据中含有多个相同值。 第八章排序（答案） 一、选择题 1．一组记录的排序码为47,78,57,39,41,85.,则利用堆排序的方法建立的初始推为。 A).78,47,57,39,41,85 B).85,78,57,39,41,47 C).85,78,57,47,41,39 D).85,57,78,41,47,39 2．一组记录的关键码为48,79,52,38,40,84.,则利用快速排序的方法,以第一个记录为基准得到的一次划分结果为。 A).38,40, 48, 52,79,84 B).40,38, 48,79, 52,84 C).40,38, 48, 52,79,84 D).40,38, 48,84, 52,79 3．一组记录的排序码为26,48,16,35,78,82,22,40,37,72.,其中含有5个长度为2的有序表,按归并排序的方法对该序列进行一趟归并后的结果为。 A).16, 26,35,48, 22,40, 78,82, 37,72 B).16, 26,35,48, 78,82, 22, 37,40,72 C).16, 26,48,35, 78,82, 22, 37,40,72 D).16, 26,35,48, 78, 22, 37,40,72,82 4.以下序列不是堆的是 A.105,85,98,77,80,61,82,40,22,13,66 B.105,98,85,82,80,77,66,61,40,22,13 C.13,22,40,61,66,77,80,82,85,98,105 D.105，85,40,77,80,61,66,98,82,13,22 5 A.直接插入排序 B.冒泡排序 C.归并排序 6、对下列4在第1趟划分过程中，元素移动次数最多的是序列 A.71,75,82,90, 24,18,10,68 B.71,75,68,23,10,18,90,82 C.82,75,71,18,10,90,68,24 D.24,10,18,71,82,75,68,90 7.下列排序算法中，___________算法可能在初始数据有序时，花费的时间反而最多。 A 堆排序 B 冒泡排序 C 快速排序 D 插入排序 8.对包含N个元素的散列表进行检索，平均查找长度为_________. A .O(log2N) B. O(N) C.不直接依赖于N D. 上述说法都不对 9.在各种排序方法中,从未排序序列中挑选元素,并将其依次放入已排序序列(初始时为空)的一端的方法是________________ A. 插入排序 B. 希尔排序 C. 选择排序 D. 归并排序 10.一组记录的关键字为(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 11.对具有8个元素的序列(49,38,65,97,76,13,27,50),按升序排序,采用快速排序法第一趟的结果为_________ 答案：27，38，13，49，76，97，65，50 A) 13,65,38,97,76,49,27,50 B) 13,27,38,49,50,65,76,97 C) 97,76,65,50,49,38,27,13 D) 13,38,65,97,76,49,27,50 12.下列哪个排序属于稳定排序_________ 第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. 归并排序，冒泡排序 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．如果待排序序列中两个数据元素具有相同的值，在排序前后它们的相互位置发生颠倒，则称该排序算法是不稳定的。（）就是不稳定的排序方法。【清华大学 1998 一、3 (2分）】 A．起泡排序 B．归并排序 C．Shell排序 D．直接插入排序 E．简单选择排序 8．若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选（）排序为宜。 A．直接插入 B．直接选择 C．堆 D．快速 E．基数【中科院计算所 2000 一、5（2分）】 9．若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）。 A. 快速排序 B. 堆排序 C. 归并排序 D. 直接插入排序【中国科技大学 1998 二、4（2分）】【中科院计算所 1998 二、4（2分）】 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< 第8章怎样研究算法:排序算法示例 1、排序算法是最基本的算法，很多复杂算法都是以排序为基础进行构造的。关于排序算法，下列说法不正确的是_____。 (A)大规模数据集合中查找有无某些元素的问题，有序数据集合比无序数据集合的查找要快得多； (B)大规模数据集合中按元素分组进行计算的问题，有序数据集合比无序数据集合的计算要快得多； (C)对无序数据集合，两个算法X和Y：X采用无序数据处理，Y采用先将无序数据排序成有序数据，然后进行处理；则对前述(A)、(B)两类问题，Y算法一定比X算法慢； (D)上述说法有不正确的； 答案：C 解释： 本题考核排序算法的研究 在大规模数据集合中查找，有序数据集合有利算法进行和判断，要比无序数据集合查找的快，对于（C）选项，Y算法尽管需要排序后再处理，但排序处理后的数据查找更加快捷，因此可能Y算法比X算法更快。 具体内容请参考排序算法以及第八章课件。 2、下列三个算法是关于“大规模数据集合中查找有无某些元素”问题的算法：针对一个“学生”数据表，如下示意，找出“成绩”为某一分数的所有学生。 【算法A1】 Start of algorithm A1 Step 1. 从数据表的第1条记录开始，直到其最后一条记录为止，读取每一条记录，做Step 2。Step 2. 对每一条记录，判断成绩是否等于给定的分数：如果是，则输出；如果不是，则不输出。 End of algorithm A1 【算法A2】 Start of algorithm A2 Step 1. 从数据表的第1条记录开始，直到其最后一条记录为止，读取每一条记录，做Step 2和Step 3。 Step 2. 对每一条记录，判断成绩是否等于给定的分数：如果等于，则输出；如果不等于，则不输出。 Step 3. 判断该条记录的成绩是否小于给定的分数：如果不是，则继续；否则，退出循环，算法结束。 End of algorithm A2 【算法A3】 Start of algorithm A3 Step 1. 假设数据表的最大记录数是n，待查询区间的起始记录位置Start为1，终止记录位置Finish为n； Step 2. 计算中间记录位置I = (Start+Finish)/2，读取第I条记录。 Step 3. 判断第I条记录的成绩与给定查找分数： (3.1)如果是小于关系，则调整Finish = I-1；如果Start >Finish则结束，否则继续做Step 2； (3.2)如果是大于关系，则调整Start = I+1；如果Start>Finish则结束，否则继续做Step 2； (3.3)如果是等于关系，则输出，继续读取I周围所有的成绩与给定查找条件相等的记录并输出，直到所有相等记录查询输出完毕则算法结束。 End of algorithm A3 针对上述三个算法，回答下列问题： (1)关于算法A1, A2, A3的快慢问题，下列说法正确的是_____。 (A)算法A1快于算法A2，算法A2快于算法A3； (B)算法A2快于算法A1，算法A2快于算法A3； (C)算法A3快于算法A2，算法A2快于算法A1； (D)算法A1快于算法A3，算法A3快于算法A2； (E)上述都不正确。 答案：C 解释： 本题考核排序算法的研究 首先，数据是有序排列的，从大到小。 算法A1依次搜索，穷举。 算法A2与A1一样，穷举，不同的是它利用数据是从大到小排序的特点，因此，如果当前数据比如果小于目标数，那么说明只有的也一定小于，则目标不在序列中。因此，A2比A1快。 算法A3利用数据有序特点，采用二分查找，每次将目标数与中间值比较，缩小搜索范围，因此A3比A2快。 综上，答案选（C）。 具体内容请参考排序算法以及第八章课件。 第1章绪论 一、选择题 1. 算法的计算量的大小称为计算的（）。【北京邮电大学2000 二、3 （20/8分）】 A．效率 B. 复杂性 C. 现实性 D. 难度 2. 算法的时间复杂度取决于（）【中科院计算所 1998 二、1 （2分）】 A．问题的规模 B. 待处理数据的初态 C. A和B 3.计算机算法指的是（1），它必须具备（2）这三个特性。 (1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法 (2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性 【南京理工大学 1999 一、1（2分）【武汉交通科技大学 1996 一、1（ 4分）】4．一个算法应该是（）。【中山大学 1998 二、1（2分）】 A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和 C. 5. 下面关于算法说法错误的是（）【南京理工大学 2000 一、1（1.5分）】 A．算法最终必须由计算机程序实现 B.为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的 6. 下面说法错误的是（）【南京理工大学 2000 一、2 （1.5分）】 (1）算法原地工作的含义是指不需要任何额外的辅助空间 （2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （4）同一个算法，实现语言的级别越高，执行效率就越低 A．(1) B.(1),(2) C.(1),(4) D.(3) 7．从逻辑上可以把数据结构分为（）两大类。【武汉交通科技大学 1996 一、4（2分）】A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构 8．以下与数据的存储结构无关的术语是（）。【北方交通大学 2000 二、1（2分）】A．循环队列 B. 链表 C. 哈希表 D. 栈 9．以下数据结构中，哪一个是线性结构（）？【北方交通大学 2001 一、1（2分）】A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串 10．以下那一个术语与数据的存储结构无关？（）【北方交通大学 2001 一、2（2分）】A．栈 B. 哈希表 C. 线索树 D. 双向链表 11．在下面的程序段中，对x的赋值语句的频度为（）【北京工商大学 2001 一、10（3分）】 FOR i:=1 TO n DO FOR j:=1 TO n DO x:=x+1; A． O(2n) B．O(n) C．O(n2) D．O(log2n) 12．程序段 FOR i:=n-1 DOWNTO 1 DO FOR j:=1 TO i DO 第八章排序 习题及答案 一、基础知识题 1.以关键字序列(265，301，751，129，937，863，742，694，076，438)为例，分别写出执行以下排序算法的各趟排序结束时，关键字序列的状态。 (1) 直接插入排序(2)希尔排序(3)冒泡排序(4)快速排序 (5) 直接选择排序(6) 堆排序(7) 归并排序(8)基数排序 上述方法中，哪些是稳定的排序?哪些是非稳定的排序?对不稳定的排序试举出一个不稳定的实例。 2.上题的排序方法中，哪些易于在链表(包括各种单、双、循环链表)上实现? 3.当R[low..high]中的关键字均相同时，Partion返回值是什么?此时快速排序的的运行时间是多少?能否修改Partion,使得划分结果是平衡的(即划分后左右区间的长度大致相等)? 4.若文件初态是反序的，则直接插入，直接选择和冒泡排序哪一个更好? 5.若文件初态是反序的，且要求输入稳定，则在直接插入、直接选择、冒泡和快速排序中就选选哪种方法为宜? 6.有序数组是堆吗? 7.高度为h的堆中，最多有多少个元素?最少有多少个元素?在大根堆中，关键字最小的元素可能存放在堆的哪些地方? 8.判别下列序列是否为堆(小根堆或大根堆)，若不是，则将其调整为堆： (1) (100,86,48,73,35,39,42,57,66,21); (2) (12,70,33,65,24,56,48,92,86,33); (3) (103,97,56,38,66,23,42,12,30,52,06,20); (4) (05,56,20,23,40,38,29,61,35,76,28,100). 9.将两个长度为n的有序表归并为一个长度为2n的有序表，最小需要比较n次，最多需要比较2n-1次，请说明这两种情况发生时，两个被归并的表有何特征? 10.设关键字序列为(0.79，0.13，0.16，0.64，0.39，0.20，0.89，0.53，0.71，0.42)，给出桶排序的结果。最新版数据结构1800题含完整答案详解
第10章排序自测题答案
目前最完整的数据结构1800题包括完整答案-第三章-栈和队列范文(汇编)
中央电大第二学期期未闭卷复习题及答案人力资源第八章自测题
第九章自测题答案
目前最完整的数据结构1800题包括完整答案树和二叉树答案
数据结构(C语言)第10章排序自测题
目前最完整的数据结构1800题包括完整答案 第五章 数组和广义表
第10章排序练习题答案(可编辑修改word版)
第十章：内部排序练习题
第八章 排序练习答案
目前最完整的数据结构1800题包括完整答案 第十章 排序
第8章怎样研究算法排序算法示例练习题答案解析
考研“数据结构”复习书传说中的1800题
第八章 排 序