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

（B）快速排列

（C）希尔排序

（D）堆排序

41 基于比较方法的n个数据的内部排序。最坏情况下的时间复杂度能达到的最好下界是____。【南京理工大学1996年】

（A）O(nlog2n)

（B）O(log2n)

（C）O(n)

（D）O(n2)

42 基于比较的排序算法时间复杂度最好的是O(____)。【北京邮电大学2007年】

（A）log2n

（B）n

（C）nlog2n

（D）n2

43 在最好情况下，对n个记录的顺序表作____排序，其时间复杂度为O(n)。【华中科技大学2006年】

（A）归并排序

（B）快速排序

（C）堆排序

答案见麦多课文库

（D）直接插入排序

44 对各种内部排序方法来说，____。【华南理工大学2006年】

（A）快速排序时间性能最佳

（B）基数排序和归并排序是稳定的排序方法

（C）快速排序是一种选择排序

（D）堆排序所用的辅助空间比较大

二、综合题

45 冒泡排序算法是把大的元素向上移(气泡的上浮)，也可以把小的元素向下移(气泡的下沉)请给出上浮和下沉过程交替的冒泡排序算法。【吉林大学2001年】

46 有50个学生的记录(每个学生的记录包括学号和成绩)，组成记录数组，按成绩由高到低的次序输出(每行10个记录)。排序方法采用选择排序。【北京师范大学1999年】

46 有一种简单的排序算法，叫做计数排序(CountSorting)。这种排序算法对一个待排序的表(用数组表示)进行排序，并将排序结果存放到另一个新的表中。必须注意的是，表中所有待排序的关键码互不相同，计数排序算法针对表中的每个记录，扫描待排序的表一趟，统计表中有多少个记录的关键码比该记录的关键码小，假设针对某一个记录，统计出的计数值为c，那么，这个记录在新的有序表中的合适的存放位置即为C。

47 给出适用于计数排序的数据表定义。

48 使用C语言编写实现计数排序的算法。

49 对于有n个记录的表，关键码比较次数是多少?

50 与简单选择排序相比较，这种方法是否更好?为什么?【清华大学2000年】

答案见麦多课文库

51 设有一个数组中存放了一个无序的关键序列K1、K2、…、Kn。现要求将Kn放在将元素排序后的正确位置上，试编写实现该功能的算法，要求比较关键字的次数不超过n。【南京航空航天大学1997年】

51 已知关键字序列(K1，K2，K3，…，Kn-1)是大根堆。

52 试写出一算法将(K1，K2，K3，…，Kn-1,Kn)调整为大根堆。

53 利用1)的算法写一个建大根堆的算法。【中科院软件所1999年】

54 设有顺序放置的n个桶，每个桶中装有一粒砾石，每粒砾石的颜色是红、白、蓝之一。要求重新安排这些砾石，使得所有红色砾石在前，所有白色砾石居中，所有蓝色砾石居后，重新安排时对每粒砾石的颜色只能看一次，并且只允许交换操作来调整砾石的位置。【上海大学1999年】

答案见麦多课文库