13 在下列排序方法中，( )方法可能出现这种情况：在最后一趟开始之前，所有的元素都不在其最终应在的正确位置上。【武汉理工大学2003一、10(26／12分)】
（A）快速排序
（B）冒泡排序
（C）堆排序
（D）插入排序
14 用直接插入排序方法对下面四个序列进行排序(由小到大)，元素比较次数最少的是( )。【北方交通大学2001一、15(2分)】
（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
15 直接插入排序在最好情况下的时间复杂度为( )。【北京邮电大学1999一、5(2分)】
（A）O(logn)
（B）O(n)
（C）O(n*logn)
（D）O(n2)
二、填空题
答案见麦多课文库
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分
17 堆是一种有用的数据结构。堆排序是一种(1)排序，堆实质上是一棵(2)结点的层次序列。对含有n个元素的序列进行排序时，堆排序的时间复杂度是(3)，所需的附加存储结点是(4)。关键字序列05，23，16，68，94，72，71，73是否满足堆的性质(5)。【山东工业大学1996三、1(5分)】
18 每次使两个有序表合并成一个有序表，这种排序方法叫做__________排序。【哈尔滨工业大学2005一、6(1分)】
19 按LSD进行多关键字排序，除最次位关键字之外，对每个关键字进行排序时，只能用__________的排序方法。【北京交通大学2004二、5(2分)】
20 分别采用堆排序、快速排序、冒泡排序和归并排序，对初态为有序的表，则最省时间的是__________算法，最费时间的是__________算法。【福州大学1998二、10(2分)】
21 不受待排序初始序列的影响，时间复杂度为O(N2)的排序算法是__________，在排序算法的最后一趟开始之前，所有元素都可能不在其最终位置上的排序算法是__________。 【中国人民大学2001一、3(2分)】
三、判断题
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）错误
四、综合题
28 在堆排序、快速排序和合并排序中：
29 若只从存储空间考虑，则应首先选取哪种排序方法，其次选取哪种排序方法，最后选取哪种排序方法?
30 若只从排序结果的稳定性考虑，则应选取哪种排序方法?
31 若只从平均情况下排序最快考虑，则应选取哪种排序方法?
32 若只从最坏情况下排序最快并且要节省内存考虑，则应选取哪种排序方法?【吉林大学2001一、5(6分)】
32 已知关键字集合为{32，6，50，27，97，1 5，92，29，20)，要求按关键字递增排序
33 若采用快速排序，请给出第一趟、第二趟的排序结果。
34 若采用(小根)堆排序，请给出初始堆。
35 若给定待排序记录的关键字基本有序时，应采用快速排序还是堆排序?为什么?
36 快速排序属于稳定排序吗?堆排序属于稳定排序吗?【厦门大学2005 4(15分)】
答案见麦多课文库
相关推荐：
loading