全国自考数据结构导论（内部排序）模拟试卷1

34． 插入排序中找插入位置的操作可以通过二分查找的方法来实现。试据此写一个改进后的插入排序算法。

35． 写出非递归调用的快速排序算法。

32． 设计一个用链表表示的直接选择排序算法。

33． 设计一个用链表表示的直接插入排序算法。

31． 采用单链表作存储结构，编写一个采用选择排序方法进行升序排序的函数。

29． 设有10000个无序的数据元素，可供选择的排序方法有：二路归并排序、堆排序、希尔排序和快速排序。现在希望用最快速度挑选出前10个最大的数据元素，问采用什么方法最好?为什么?

30． 试比较直接插入排序、直接选择排序、快速排序、堆排序、二路归并排序的时空性能。

27． 举例说明本章介绍的各排序方法中哪些是不稳定的?

28． 对于给定的一组键值：83，40，63，13，84，35，96，57，39，79，61，15，分别画出应用直接插入排序、希尔排序、冒泡排序、快速排序、直接选择排序、二路归并排序对上述序列进行排序中各趟的结果。

24． 设表中元素的初始状态是按键值递增的，分别用堆排序、快速排序、冒泡排序和二路归并排序方法对其仍按递增顺序进行排序，则______最省时间______最费时间。

26． 在执行某种排序算法的过程中出现了关键字朝着最终排序序列相反的方向移动，从而认为该排序算法是不稳定的，这种说法对吗?为什么?请举一例说明。

25． 对快速排序来讲，其最好情况下的时间复杂度是_______，其最坏情况下的时间复杂度是________。

22． 常用的选择排序方法有_______和_______。

23． 设有字母序列{P，D，F，Z，E，P，N，B，X，M，G，w}，请写出按二路归并排序方法对该序列进行一趟扫描后的结果_______。

21． 对于堆排序和快速排序，若待排序序列基本有序，则选用______较好；若待排序序列无序，则选用_____较好。

20． 若堆中某一数据元素在数组中的下标为30，则它的左孩子的下标为_______，右孩子的下标为________。

18． 对于直接插入排序和直接选择排序，若待排序序列基本有序，则选用______较好；若待排序序列为逆序，则选用______较好。

19． 直接插入排序在最好情况下的时间复杂度为_______，在最坏情况下的时间复杂度为_______。

17． 常用的插入排序有________和________。

16． 根据在排序过程中使用的存储器将排序方法分为：________和________。

15． 当文件局部有序或文件长度较小的情况下，最佳的排序方法是₂。

13． 以下______排序方法是不稳定的排序方法。

14． 快速排序在最坏情况下昀时间复杂度是______。

12． 若有关键字序列{20，80，10，50，60，95，15，55，30，40}，并且该序列是由5个长度为2的子序列组成，则用二路归并排序方法对该序列进行一趟二路归并后的结果为______。

11． 以下四种排序方法中，要求附加的内存空量最大的是______。

10． 以下排序方法中，不能保证每趟排序至少能将一个数据元素放到其最终位置上的排序方法是______。

8． 将上万个一组无序并且互不相等的正整数序列，存放于顺序存储结构中，采用______方法能够最快地找出其中最大的正整数。

9． 在排序过程中，键值比较的次数与初始序列的排列顺序无关的是______。

7． 以下______序列不是堆。

6． 用某种排序方法对线性表(35，90，15，50，10，30，75，28，13)进行排序时得到以下中间结果，则所采用的排序方法是______。

13，28， 15， 30， 10， 35， 75， 50， 90

10， 13， 15， 30， 28， 35， 50， 75， 90

10， 13， 15， 28， 30， 35， 50， 75， 90

5． 快速排序方法在______情况下最不利于发挥其长处。

3． 在对一组关键字序列{70，55，100，15，33，65，50，40，95)进行直接插人排序时，把65插入到有序序列需要比较______次。

4． 若有关键字序列{42，70，50，33，40，80}，则利用快速排序的方法，以第一个关键字为基准元素得到的一次划分结果为______。

1． 排序方法的稳定性是指______。

2． 排序的目的是为了以后对已排序的数据元素进行______操作。