第10章 排序

　　云南大学信息学院计算机科学与工程系《数据结构》课后作业

　　第2套第10章排序

　　一、选择题

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

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

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

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

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

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

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

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

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

　　（1）8447251521（2）1547258421

　　（3）1521258447（4）1521254784

　　则采用的排序是()。

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

　　6．下列排序算法中(

　　A.选择)排序在一趟结束后不一定能选出一个元素放在其最终位置上。B.冒泡C.归并D.堆

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

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

　　8.对初始状态为递增序列的表按递增顺序排序，最省时间的是（

　　是（）算法。

　　A.堆排序B.快速排序C.插入排序D.归并排序D.归并排序）算法，最费时间的

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

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

　　10．在待排序列“局部有序”或序列长度较小的情况下，最佳内部排序的方法是（

　　A．直接插入排序B．冒泡排序C．简单选择排序

　　11.若用冒泡排序方法对序列{10,14,26,29,41,52}从大到小排序，需进行（

　　A.3B.10C.15D.25）））次比较。

　　12．下列四个序列中，哪一个是堆（

　　A.75,65,30,15,25,45,20,10

　　C.75,45,65,30,15,25,20,10）。B.75,65,45,10,30,25,20,15D.75,45,65,10,25,30,20,15

　　13.归并排序中，归并的趟数是()。

　　A．O（n）B．O(logn)C．O(nlogn)D．O(n*n)

　　二、判断题：

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

　　）

　　）

　　）2．排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。（3．两分法插入排序所需比较次数与待排序记录的初始排列状态相关。（4．在用堆排序算法排序时，如果要进行增序排序，则需要采用“大根堆”。（

　　三、填空题

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

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

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

　　selectsort(head)

　　p=head;

　　while{q=p;while((3)______)

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

　　}

　　tmp=q-q-data=p-p-data=tmp;p=;

　　}

　　4．设有字母序列{Q,D,F,X,A,P,N,B,Y,M,C,W},请写出按2路归并排序方法对该序列进行一趟扫描后的结果_______。

　　5．关键码序列（Q，H，C，Y，Q，A，M，S，R，D，F，X），要按照关键码值递增的次序进行排序，若采用初始步长为4的Shell排序法，则一趟扫描的结果是_____；若采用以第一个元素为分界元素的快速排序法，则扫描一趟的结果是______。2

　　四、应用题

　　1.在各种排序方法中，哪些是稳定的？哪些是不稳定的？并为每一种不稳定的排序方法举出一个不稳定的实例。

　　2．对一个由n个关键字不同的记录构成的序列，能否用比2n-3少的次数选出该序列中关键字取最大值和关键字取最小值的记录？请说明如何实现？在最坏的情况下至少进行多少次比较？

　　3.设LS是一个线性表，LS=(a1,a2,…,an),若采用顺序存储结构，则在等概率的前提下，插入一个元素需要平均移动的元素个数是多少？若元素插在ai与ai+1之间(0=n-1)的概率为(n-i)/(n*(n+1)/2)，则插入一个元素需要平均移动的元素个数又是多少？

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

　　5．我们知道，对于n个元素组成的线性表进行快速排序时，所需进行的比较次数与这n个元素的初始排序有关。问：

　　（1）当n=7时，在最好情况下需进行多少次比较？请说明理由。

　　（2）当n=7时，给出一个最好情况的初始排序的实例。

　　（3）当n=7时，在最坏情况下需进行多少次比较？请说明理由。

　　（4）当n=7时，给出一个最坏情况的初始排序的实例

　　6.给出一组关键字：29，18，25，47，58，12，51，10，分别写出按下列各种排序方法进行排序时的变化过程：

　　(1)归并排序

　　(2)快速排序

　　(3)堆排序每归并一次书写一个次序。每划分一次书写一个次序。先建成一个堆，然后每从堆顶取下一个元素后，将堆调整一次。

　　五、算法设计题：

　　1.有一种简单的排序算法，叫做计数排序（countsorting）。这种排序算法对一个待排序的表(用数组表示)进行排序，并将排序结果存放到另一个新的表中。必须注意的是，表中所有