《数据结构 》排序试题附答案_比较次数与初始元素序列的排列无关

《数据结构 》排序试题附答案

 

一、选择题

1．某内排序方法的稳定性是指(    )。

A．该排序算法不允许有相同的关键字记录      B．该排序算法允许有相同的关键字记录

C．平均时间为0（n log n）的排序方法        D．以上都不对

2．下面给出的四种排序法中(    )排序法是不稳定性排序法。

    A. 插入           B. 冒泡              C. 二路归并        D. 堆积

3．下列排序算法中，其中（    ）是稳定的。

A. 堆排序，冒泡排序              B. 快速排序，堆排序  

 C. 直接选择排序，归并排序       D. 归并排序，冒泡排序

4．稳定的排序方法是（    ）

A．直接插入排序和快速排序       B．折半插入排序和起泡排序

C．简单选择排序和四路归并排序   D．树形选择排序和shell排序

5．下列排序方法中，哪一个是稳定的排序方法？（ 　）

A．直接选择排序      B．二分法插入排序      C．希尔排序        D．快速排序

6．若要求尽可能快地对序列进行稳定的排序，则应选（A．快速排序 B．归并排序 C．冒泡排序）。

7．如果待排序序列中两个数据元素具有相同的值，在排序前后它们的相互位置发生颠倒，则称该排序算法是不稳定的。（    ）就是不稳定的排序方法。

A．起泡排序    B．归并排序    C．Shell排序    D．直接插入排序    E．简单选择排序

8．若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选（    ）排序为宜。

A．直接插入 B．直接选择 C．堆 D．快速 E．基数 

9．若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（    ）。

 A. 快速排序        B. 堆排序        C. 归并排序         D. 直接插入排序

10．下面的排序算法中，不稳定的是（    ）

       A.起泡排序   B.折半插入排序   C.简单选择排序    D.希尔排序     E.基数排序   F.堆排序。

11．下列内部排序算法中：

A．快速排序   B.直接插入排序 C. 二路归并排序 D. 简单选择排序 E. 起泡排序   F. 堆排序

（1） 其比较次数与序列初态无关的算法是（    ）    （2）不稳定的排序算法是（    ）

（3）在初始序列已基本有序（除去n个元素中的某k个元素后即呈有序，k<<n）的情况下，排序效率最高的算法是（    ）

（4）排序的平均时间复杂度为O(n•logn)的算法是（    ）为O(n•n)的算法是（    ）

12．排序趟数与序列的原始状态有关的排序方法是(    )排序法。

   A．插入            B. 选择              C. 冒泡            D. 快速

13．下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是。(    )

A．选择排序法      B. 插入排序法       C. 快速排序法        D. 堆积排序法

14．对下列四种排序方法，在排序中关键字比较次数同记录初始排列无关的是(    )。

A．直接插入       B. 二分法插入        C. 快速排序         D. 归并排序   

15．在下列排序算法中,哪一个算法的时间复杂度与初始排序无关（ ）。

A． 直接插入排序   B. 气泡排序     C. 快速排序     D. 直接选择排序

16．比较次数与排序的初始状态无关的排序方法是(     )。

A．直接插入排序       B．起泡排序      C．快速排序       D．简单选择排序

17．数据序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中的(    )的两趟排序后的结果。

A．选择排序        B.冒泡排序         C.插入排序         D.堆排序

18．数据序列（2，1，4，9，8，10，6，20）只能是下列排序算法中的(    )的两趟排序后的结果。

A. 快速排序         B. 冒泡排序          C. 选择排序         D. 插入排序

19．对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为

（1） 84 47 25 15 21 （2） 15 47 25 84 21 （3） 15 21 25 84 47 （4） 15 21 25 47 84

则采用的排序是 (     )。

A. 选择            B. 冒泡           C. 快速            D. 插入

20．对序列{15，9，7，8，20，-1，4}进行排序，进行一趟后数据的排列变为{4，9，-1，8，20，7，15}；则采用的是（    ）排序。

A. 选择           B. 快速           C. 希尔            D. 冒泡

21．若上题的数据经一趟排序后的排列为{9，15，7，8，20，-1，4}，则采用的是（    ）排序。

A．选择      B. 堆      C. 直接插入    D. 冒泡

22．下列排序算法中(    )不能保证每趟排序至少能将一个元素放到其最终的位置上。

A.快速排序 B. shell排序 C. 堆排序   D.冒泡排序 

23．下列排序算法中(    )排序在一趟结束后不一定能选出一个元素放在其最终位置上。

A. 选择           B. 冒泡           C. 归并        D. 堆

24．下列序列中，（    ）是执行第一趟快速排序后所得的序列。

    A. [68，11，18，69]   [23，93，73]       B. [68，11，69，23]   [18，93，73]

    C. [93，73]   [68，11，69，23，18]       D. [68，11，69，23，18]   [93，73]

25．有一组数据（15，9，7，8，20，-1，7，4） 用快速排序的划分方法进行一趟划分后数据的排序为 (    )（按递增序）。

A．下面的B，C，D都不对。        B．9，7，8，4，-1，7，15，20

C．20，15，8，9，7，-1，4，7     D. 9，4，7，8，7，-1，15，20

26．一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（    ）。

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)

27. 在下面的排序方法中，辅助空间为O（n）的是(    ) 。

      A．希尔排序       B. 堆排序         C. 选择排序        D. 归并排序    

28．下列排序算法中，在待排序数据已有序时，花费时间反而最多的是(     )排序。

     A． 冒泡 B. 希尔 C. 快速 D. 堆

29.下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的是：（    ）。

A. 直接插入排序     B. 快速排序     C. 直接选择排序      D. 堆排序

30. 对初始状态为递增序列的表按递增顺序排序，最省时间的是（    ）算法，最费时间的是（    ）算法。

    A. 堆排序    B. 快速排序    C. 插入排序     D. 归并排序 

31. 就平均性能而言，目前最好的内排序方法是(    )排序法。

A. 冒泡   B. 希尔插入   C. 交换 D. 快速

32．如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用（    ）方法最快。

A．起泡排序   B．快速排列 C．Shell排序 D．堆排序 E．简单选择排序

答案： 

 

 

部分答案解释如下：

18. 对于后三种排序方法两趟排序后，序列的首部或尾部的两个元素应是有序的两个极值，而给定的序列并不满足。

20. 本题为步长为3的一趟希尔排序。             24.枢轴是73。 

49. 小根堆中，关键字最大的记录只能在叶结点上，故不可能在小于等于n/2的结点上。

64. 因组与组之间已有序，故将n/k个组分别排序即可，基于比较的排序方法每组的时间下界为O(klog2k),全部时间下界为O(nlog2k)。

 

 

二、判断题：

1．当待排序的元素很大时，为了交换元素的位置，移动元素要占用较多的时间，这是影响时间复杂度的主要因素。（    ）

2．内排序要求数据一定要以顺序方式存储。 （    ）

3．排序算法中的比较次数与初始元素序列的排列无关。（）

4．排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。（    ）

5．在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的。（ ）

6．直接选择排序算法在最好情况下的时间复杂度为O（N）。（ ）

7．两分法插入排序所需比较次数与待排序记录的初始排列状态相关。（）

8．在初始数据表已经有序时，快速排序算法的时间复杂度为O(nlog2n )。（    ）

9．在待排数据基本有序的情况下，快速排序效果最好。（    ）

10．当待排序记录已经从小到大排序或者已经从大到小排序时，快速排序的执行时间最省。（    ）

11．快速排序的速度在所有排序方法中为最快,而且所需附加空间也最少。（    ）

12．堆肯定是一棵平衡二叉树。（    ）

13．堆是满二叉树。（    ）【

14．（101，88，46，70，34，39，45，58，66，10）是堆。（ ）

15．在用堆排序算法排序时，如果要进行增序排序，则需要采用“大根堆”。（    ）

16．堆排序是稳定的排序方法。（    ）

17．归并排序辅助存储为O（1）。（    ）

18．在分配排序时，最高位优先分配法比最低位优先分配法简单。（ ）

19． 冒泡排序和快速排序都是基于交换两个逆序元素的排序方法,冒泡排序算法的最坏时间复杂性是O(n*n),而快速排序算法的最坏时间复杂性是O(nlog2n),所以快速排序比冒泡排序算法效率更高。 （    ）

20．交换排序法是对序列中的元素进行一系列比较，当被比较的两个元素逆序时，进行交换，冒泡排序和快速排序是基于这类方法的两种排序方法，冒泡排序算法的最坏时间复杂性是O（n*n） ，（    ）而快速排序算法的最坏时间复杂性是O（nlog2n）；所以快速排序比冒泡排序效率更高。

21．快速排序和归并排序在最坏情况下的比较次数都是O(nlog2n)。（   ）

22．在任何情况下，归并排序都比简单插入排序快。（   ）

23．归并排序在任何情况下都比所有简单排序速度快。（   ）

24．快速排序总比简单排序快。（   ）

25. 中序周游（遍历）平衡的二叉排序树，可得到最好排序的关键码序列。（    ）

三、填空题

1．若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的______和记录的_____。

2. 外排序的基本操作过程是_______和_______。

3. 属于不稳定排序的有__________。

4．分别采用堆排序，快速排序，冒泡排序和归并排序，对初态为有序的表，则最省时间的是_____算法，最费时间的是______算法。

5. 不受待排序初始序列的影响，时间复杂度为O(N2)的排序算法是_____，在排序算法的最后一趟开始之前，所有元素都可能不在其最终位置上的排序算法是_____。

6．直接插入排序用监视哨的作用是_______。

7．对n个记录的表r[1..n]进行简单选择排序，所需进行的关键字间的比较次数为_______。

8. 用链表表示的数据的简单选择排序，结点的域为数据域data ，指针域 next ；链表首指针为head ，链表无头结点。

selectsort(head)

    p=head;

while (p(1)_______)

{q=p; r=(2)_______

       while((3)______ )

{if ((4)_______ ) q=r;

          r=(5)_______ ;

}

      tmp=q->data; q->data=p->data; p->data=tmp; p= (6)_______ ;

      } 

9．下面的c函数实现对链表head进行选择排序的算法,排序完毕,链表中的结点按结点值从小到大链接。请在空框处填上适当内容,每个空框只填一个语句或一个表达式：

#include <stdio.h>

typedef struct node {char data; struct node *link; }node;

node *select(node *head)

{node *p,*q,*r,*s;

p=(node *)malloc(sizeof(node));

   p->link=head; head=p;

while(p->link!=null)

     {q=p->link; r=p;

      while ((1)____)

         { if (q->link->data<r->link->data) r=q;

           q=q->link;

 }

      if ((2)____) {s=r->link; r->link=s->link; s->link= ((3)_____); ((4)_____);}

      ((5)____) ;

     }

p=head; head=head->link; free(p); return(head);

}

10．下面的排序算法的思想是：第一趟比较将最小的元素放在r[1]中，最大的元素放在r[n]中，第二趟比较将次小的放在r[2]中，将次大的放在r[n-1]中，…,依次下去，直到待排序列为递增序。（注：<-->）代表两个变量的数据交换）。

void sort(SqList &r,int n) {

         i=1;

while((1)__)   {

min=max=1;

for (j=i+1;(2)____ ;++j) 

{if((3)____) min=j; else if(r[j].key>r[max].key) max=j; }

if((4)_____) r[min] < ---- >r[j];

if(max!=n-i+1){if ((5)___) r[min] < ---- > r[n-i+1]; else ((6)__); }

i++;

}

}//sort

 

 

 

 

习题答案：

 

二、判断题

 

 

部分答案解释如下：

5. 错误。例如冒泡排序是稳定排序，将4,3,2,1按冒泡排序排成升序序列，第一趟变成3,2,1,4，此时3就朝向最终位置的相反方向移动。      12. 错误。堆是n个元素的序列，可以看作是完全二叉树，但相对于根并无左小右大的要求，故其既不是二叉排序树，更不会是平衡二叉树。

22. 错误。待排序序列为正序时，简单插入排序比归并排序快。

 

三、填空题

1. 比较,移动    2.生成有序归并段（顺串）,归并    3.希尔排序、简单选择排序、快速排序、堆排序等

4. 冒泡,快速    5. (1)简单选择排序     (2)直接插入排序（最小的元素在最后时）

6. 免去查找过程中每一步都要检测整个表是否查找完毕，提高了查找效率。        7. n(n-1)/2

8.题中p指向无序区第一个记录，q指向最小值结点，一趟排序结束，p和q所指结点值交换，同时向后移p指针。(1)!=null        (2)p->next (3)r!=null (4)r->data<q->data (5)r->next (6)p->next

9. 题中为操作方便，先增加头结点（最后删除），p指向无序区的前一记录，r指向最小值结点的前驱，一趟排序结束，无序区第一个记录与r所指结点的后继交换指针。

(1)q->link!=NULL (2)r!=p    (3)p->link (4)p->link=s       (5)p=p->link

10.(1)i<n-i+1 (2)j<=n-i+1 (3)r[j].key<r[min].key (4)min!=i (5)max==i (6)r[max]<-->r[n-i+1]