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