[考研类试卷]计算机专业基础综合数据结构(排序)历年真题试卷汇编1.doc

（D）要排序的数据已基本有序

14 对n个元素的表做快速排序，最坏情况下，算法的时间复杂度为____。【华中科技大学2006年】

（A）O(log2n)

（B）O(nlog2n)

（C）O(n2)

（D）O(2n)

15 对以下关键字序列用快速排序算法进行排序，速度最慢的是____。【北京交通大学2002年】

（A）20，24，4，16，22，29

（B）24，22，29，16，20，4，8

（C）20，8，16，29，24，22，4

（D）4，8，16，20，24，29

16 快速排序在最坏的情况下的时间复杂度与下面哪个算法的最坏情况下的时间复杂度相同____。【北京交通大学2006年】

（A）希尔排序

（B）堆排序

（C）冒泡排序

（D）基数排序

17 根据堆的定义，下面4个序列中，构成堆的是____。【广东工业大学2002年】

答案见麦多课文库

（A）77，67，32，17，27，47，22，12

（B）77，67，47，12，32，27，22，17

（C）77，47，67，32，17，27，22，12

（D）77，47，67，12，27，32，22，17

18 有～组数据(15，9，7，8，20，一1，7，4)，用堆排序的筛选方法建立的初始堆为____。【南京理工大学1996年】

（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均不对。

19 构建n个记录的初始堆，其时间复杂度为____。【华中科技大学2006年】

（A）O(n)

（B）O(n2)

（C）O(log2n)

（D）O(nlog2n)

20 在对n个元素的序列进行排序时，堆排序所需要的附加存储空间是____。【西安电子科技大学2001年】

（A）O(log2n)

（B）O(1)

答案见麦多课文库

（C）O(n)

（D）O(nlog2n)

21 对n个记录的文件进行堆排序，最坏情况下的执行时间是____。【北京交通大学2001年

（A）O(log2n)

（B）O(n)

（C）O(nlog2n)

（D）O(n2)

22 归并排序中，归并趟数的数量级是____。【南京理工大学2000年】

（A）O(n)

（B）O(log2n)

（C）O(nlog2n)

（D）O(n2)

23 对具有n个元素的序列采用二路归并排序算法排序，算法的空间复杂度是____。【北京航空航天大学2007年】

（A）O(n)

（B）O(2n)

（C）O(n2)

（D）O(log2n)

答案见麦多课文库

24 若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是：稳定的，则可选择的排序方法是____。【北京交通大学2004年】【太原科技大学2007年】

（A）快速排序

（B）堆排序

（C）归并排序

（D）直接插入排序

25 排序趟数与序列的原始状态有关的排序方法是____排序法。【北京航空航天大学1999年】

（A）插入

（B）选择

（C）冒泡

（D）基数

26 下列排序方法中，____在待排序的数据为有序时，花费时间反而最多。【华中科技大学2007年】

（A）快速排序

（B）插入排序

（C）堆排序

（D）冒泡排序

27 当待排序序列基本有序时，下列方法中____最好。【北京邮电大学2005年】

（A）直接插入排序

答案见麦多课文库