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