计算机专业基础综合数据结构（排序）历年真题试卷汇编1(总分：72.00，做题时间：90分钟)一、单项选择题(总题数：15，分数：30.00)1.下列序列中，( )是执行第一趟快速排序后所得的序列。
【福州大学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]枢轴是73。
2.适合并行处理的排序算法是( )。
【西安电子科技大学2005一、8(1分)】【电子科技大学2005一、8(1分)】A.选择排序B.快速排序√C.希尔排序D.基数排序3.一组记录的关键字为(46，79，56，38，40，84)，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为( )。
【北京交通大学2005一、8(2分)【燕山大学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)如何对一趟快速排序的结果在最短的时间内做出正确判断，这里给出建议：首先84应该不动，所以D排除了；接着40应调到序列首，所以A排除了；接着79应调到移走40的空位上，B排除了。
选择答案C，不必再继续做了(假定确有唯一正确答案)。
4.下列排序算法中，( )算法可能会出现下面的情况：初始数据有序时，花费的时间反而最多。
【中南大学2005一、4(2分)】A.快速排序√B.堆排序C.希尔排序D.冒泡排序5.将一组无序的数据重新排列成有序序列，其方法有：( )。
【武汉理工大学2004一、8(3分)】A.拓扑排序B.快速排序√C.堆排序√D.基数排序√6.就平均性能而言，目前最好的内排序方法是( )排序法。
【西安电子科技大学1998一、9(2分)】A.冒泡B.希尔插，AC.交换D.快速√7.如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用( )方法最快。
【清华大学1998一、2(2分)】A.起泡排序B.快速排列C.Shell排序D.堆排序√E.简单选择排序本题相当于从n个元素选取k(k＜＜n)个元素用什么排序方法最好。
起泡排序和简单选择排序第1趟比较n 一1次选出最小／最大元素，第2趟比较n一2次，选出次小／次大元素，因此，这两种排序方法不予考虑。
若选最小，快速排序和起泡排序差不多。
希尔排序只有等排序结束才能有最后结果，这里不予考虑。
堆排序建堆选出最小／最大元素，比较了至多不超过4n次，以后每选出一个元素需要logn次的比较。
由此，本题的答案应该选D。
但是编者还有另外的分析。
若先用快速排序选出第k个最小元素，则比较次数在O(n)级，算法见下面“五、27”。
对前面k-1个记录可以采用任何简单(不使用适合大数据量的堆排序等)排序方法，即使再用快速排序，也是可以的。
这里n大到什么程度，k小到什么程度，会有个阈值。
8.若要从1000个元素中选出前10个最小的元素，( )是最适合的算法。
【北京理工大学2005一、9(1分)】A.直接插入排序B.归并排序C.堆排序√D.快速排序9.对数据序列(8，9，10，4，5，6，20，1，2)采用(由后向前次序的)冒泡排序，需要进行的趟数(遍数)至少是( )。
【中国科学技术大学2005】A.3B.4C.5 √D.810.下列排序算法中，占用辅助空间最多的是：( )。
【厦门大学2002五、2(8分)】A.归并排序√B.快速排序C.希尔排序D.堆排序11.在下面的排序方法中，辅助空间为O(m)的是( )。
【南京理工大学1999一、17(1分)】A.希尔排序B.堆排序C.选择排序D.归并排序√12.从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为( )排序法。
【北京航空航天大1999一、8(2分)】A.插入√B.选择C.希尔D.二路归并是叙述直接插入排序特征的，要认真领会。
13.在下列排序方法中，( )方法可能出现这种情况：在最后一趟开始之前，所有的元素都不在其最终应在的正确位置上。
【武汉理工大学2003一、10(26／12分)】A.快速排序B.冒泡排序C.堆排序D.插入排序√14.用直接插入排序方法对下面四个序列进行排序(由小到大)，元素比较次数最少的是( )。
【北方交通大学2001一、15(2分)】A.94，32，40，90，80，46，21，69B.32，40，21，46，69，94，90，80C.21，32，46，40，80，69，90，94 √D.90，69，80，46，21，32，94，4015.直接插入排序在最好情况下的时间复杂度为( )。
【北京邮电大学1999一、5(2分)】A.O(logn)B.O(n) √C.O(n*logn)D.O(n 2 )二、填空题(总题数：6，分数：12.00)16.堆是一种有用的数据结构。
试判断下面的关键字序列中哪一个是堆__________。
①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分__________________________________________________________________________________________正确答案：(正确答案：④是堆 (1)选择 (2)筛选法 (3)O(nlog 2 n) (4)1个)17.堆是一种有用的数据结构。
堆排序是一种(1)排序，堆实质上是一棵(2)结点的层次序列。
对含有n个元素的序列进行排序时，堆排序的时间复杂度是(3)，所需的附加存储结点是(4)。
关键字序列05，23，16，68，94，72，71，73是否满足堆的性质(5)。
【山东工业大学1996三、1(5分)】__________________________________________________________________________________________正确答案：(正确答案：(1)选择 (2)完全二叉树 (3)O(nlog 2 n) (4)1个 (5)满足堆的性质)18.每次使两个有序表合并成一个有序表，这种排序方法叫做__________排序。
【哈尔滨工业大学2005一、6(1分)】__________________________________________________________________________________________正确答案：(正确答案：归并)19.按LSD进行多关键字排序，除最次位关键字之外，对每个关键字进行排序时，只能用__________的排序方法。
【北京交通大学2004二、5(2分)】__________________________________________________________________________________________正确答案：(正确答案：稳定)20.分别采用堆排序、快速排序、冒泡排序和归并排序，对初态为有序的表，则最省时间的是__________算法，最费时间的是__________算法。
【福州大学1998二、10(2分)】__________________________________________________________________________________________正确答案：(正确答案：冒泡，快速)21.不受待排序初始序列的影响，时间复杂度为O(N 2 )的排序算法是__________，在排序算法的最后一趟开始之前，所有元素都可能不在其最终位置上的排序算法是__________。
【中国人民大学2001一、3(2分)】__________________________________________________________________________________________正确答案：(正确答案：简单选择排序，直接插入排序(最小的元素在最后时))三、判断题(总题数：7，分数：14.00)22.归并排序要求的辅助空间最多。
( )【中国海洋大学2007二、15(1分)】A.正确√B.错误23.在分配排序时，最高位优先分配法比最低位优先分配法简单。
( )【上海交通大学1998一、20(1分)】A.正确B.错误√24.快速排序是排序算法中最快的一种。
( )【暨南大学2010三、1(1分)】A.正确B.错误√25.在任何情况下，归并排序都比简单插入排序快。
( )【北京邮电大学2000一、4(1分)2002一、9(1分)】A.正确B.错误√待排序序列为正序时，简单插入排序比归并排序快。
26.基数分类只适用于以数字为关键字的情况，不适用于以字符串为关键字的情况。
( )【哈尔滨工业大学2003二、8(1分)】A.正确B.错误√27.外部排序是把外存文件调入内存，可利用内部排序的方法进行排序，因此排序所花的时间取决于内部排序的时间。
( )【北京邮电大学1998一、8(2分)】A.正确B.错误√都是外部排序问题。
外部排序指待排序文件很大，不能一次调入内存所进行的排序方法。
外部排序分成生成顺串和归并顺串两个阶段。
外部排序的效率主要取决于读写外存的次数，即归并的趟数。
减少归并趟数就可以减少读写次数，提高效率。
28.在外排序过程中，对长度为n的初始序列进行“置换一选择”排序时，可以得到的最大初始有序段的长度不超过n／2。
( )【大连海事大学2001一、3(1分)】A.正确B.错误√四、综合题(总题数：2，分数：16.00)在堆排序、快速排序和合并排序中：（分数：8.00）(1).若只从存储空间考虑，则应首先选取哪种排序方法，其次选取哪种排序方法，最后选取哪种排序方法? __________________________________________________________________________________________ 正确答案：(正确答案：堆排序，快速排序，归并排序)(2).若只从排序结果的稳定性考虑，则应选取哪种排序方法?__________________________________________________________________________________________ 正确答案：(正确答案：归并排序)(3).若只从平均情况下排序最快考虑，则应选取哪种排序方法?__________________________________________________________________________________________ 正确答案：(正确答案：快速排序)(4).若只从最坏情况下排序最快并且要节省内存考虑，则应选取哪种排序方法?【吉林大学2001一、5(6分)】__________________________________________________________________________________________ 正确答案：(正确答案：堆排序)已知关键字集合为{32，6，50，27，97，1 5，92，29，20)，要求按关键字递增排序（分数：8.00）(1).若采用快速排序，请给出第一趟、第二趟的排序结果。