《数据结构》期末复习题及参考答案- 第10章排序一、选择题1、n个记录进行直接插入排序时，记录最小的比较次数是( )A.(n-1)B.0C.(n+3)(n-2)/2D.n2/22、对n个记录进行希尔排序，所需要的辅助存储空间为（）。

A.O（1og2n）B.O（n）C.O（1）D.O（n2）3、就平均性能而言，目前最好的内排序方法是( )排序法。

A.冒泡B.希尔插入C.交换D.快速4、直接插入排序在最好情况下的时间复杂度为（）A．O(logn) B．O(n) C．O(n*logn) D．O(n2)5、以下算法思路分别出自什么排序算法：取当前最小的数，插入到已经排好序的数据末尾：（）；取当前要排序的数，插入到已经排好序的数据中适当位置：（）；相邻两个数比较，如果大小顺序颠倒就把两者交换过来：（）。

6、设一组初始关键字记录关键字为(20，15，14，18，21，36，40，10)，则以20为基准记录的一趟快速排序结束后的结果为( )。

(A) 10，15，14，18，20，36，40，21(B) 10，15，14，18，20，40，36，21(C) 10，15，14，20，18，40，36，2l(D) 15，10，14，18，20，36，40，217、下列四种排序算法中，哪一个需要采用递归调用的方式实现A、直接插入排序B、快速排序C、冒泡排序D、折半插入排序8、从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为( )排序法。

A.插入B.选择C.希尔D.快速9、快速排序方法在（）情况下最不利于发挥其长处。

A.要排序的数据量太大B.要排序的数据中含有多个相同值C.要排序的数据个数为奇数D.要排序的数据已基本有序10、对一组数据（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. 插入11、在希尔排序算法中，需要借助（）实现A、直接插入排序B、快速排序C、冒泡排序D、折半插入排序12、若用冒泡排序方法对序列{10,14,26,29,41,52}从大到小排序，需进行（）次比较。

A. 3B. 10C. 15D. 2513、在下列排序算法中，哪一个算法的时间复杂度与初始排序无关（）。

A.直接插入排序B.起泡排序C. 快速排序D.选择排序14、对下列四种排序方法，在排序中关键字比较次数同记录初始排列无关的是( )。

A．直接插入 B. 起泡排序 C. 快速排序 D. 二分法插入15、若采用希尔排序法对序列{ 12,36,21,7,2,19,6,31,49,13,27,38,5 }进行排序，增量分别为5、3、1。

那么当增量为3时，排序结束后的序列是哪一个A. { 5, 2, 19, 6, 27, 21, 7, 31, 38, 12, 36, 49, 13 }B. { 12,6, 5, 7,2,19, 36, 21,49,13,27,38, 31 }C. { 7, 2, 5, 12, 6, 19, 13, 21, 38, 31, 27, 49, 36 }D. { 2, 6, 5, 7, 12, 13, 27, 21,31, 19, 36, 38, 49 }二、填空题1、直接插入排序、折半插入排序、起泡排序都属于稳定排序。

希尔排序、快速排序、选择排序都属于不稳定排序。

2、直接插入排序用监视哨的作用是免去查找过程中每一步都要检测整个表是否查找完毕，提高了查找效率。

3、对有限个记录进行起泡排序，第n趟起泡排序的排序结束位置应为上一趟排序中最后一次发生记录交换的位置。

4、对n个记录的表r[1..n]进行简单选择排序，所需进行的关键字间的比较次数为n(n-1)/2 , 若进行起泡排序，则最多需要n(n-1)/2次的比较。

5、假设存放在计算机内存中的含n个记录的序列为{ R1, R2, …，R n }，其相应的关键字序列为{ K1, K2, …，K n }，这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系Ks1≤Ks2≤…≤Ks n，按此固有关系将n个记录序列重新排列为{ Rs1, Rs2, …，Rs n }。

若整个排序过程都在内存中完成，不需要访问外存，则称此类排序问题为内部排序。

6、对于排序算法，其基本思想是不断扩大有序序列区，同时不断缩小无序序列区。

7、判定起泡排序的结束条件是：当至多进行n-1趟起泡排序，或一趟起泡排序中未发生交换（即已有序）时，结束排序。

三、简答题1、(1)请简单叙述希尔排序的基本思想。

(2)写出初始数列{49，38，65，97，76，13，27，49，55，4 }在希尔排序下的状态变化过程（假设增量d=5、3、1）。

(1)希尔排序是对直接插入排序算法的改进，它从“记录个数少”和“基本有序”出发，将待排序的记录划分成几组（缩小增量分组），从而减少参与直接插入排序的数据量，当经过几次分组排序后，记录的排列已经基本有序，这个时候再对所有的记录实施直接插入排序。

(2)：2、(1)别。

(2)设待排序的记录共7个，排序码分别为8，3，2，5，9，1，6。

分别写出用直接插入排序和选择排序下序列的状态变化过程。

要求以排序码序列的变化描述形式说明排序全过程（动态过程）要求按递减顺序排序。

(1)直接插入排序的基本思想是基于插入，开始假定第一个记录有序，然后从第二个记录开始，依次插入到前面有序的子文件中。

即将记录R[i](2<=i<=n)插入到有序子序列R[1..i-1]中，使记录的有序序列从R[1..i-1]变为R[1..i] ，最终使整个文件有序。

共进行n-1趟插入。

最坏时间复杂度是0(n2)，平均时间复杂度是0(n2)，空间复杂度是O(1)，是稳定排序。

选择排序的基本思想是基于选择，开始有序序列长度为零，第i(1<=i<n)趟选择排序是，从无序序列R[i..n]的n-i+1记录中选出关键字最小的记录，和第i个记录交换，使有序序列逐步扩大，最后整个文件有序。

共进行n-1趟选择。

最坏时间复杂度是0(n2)，平均时间复杂度是0(n2)，空间复杂度是O(1)，是不稳定排序。

(2)直接插入排序：第一趟(3)[8,3],2,5,9,1,6第二趟(2)[8,3,2],5,9,1,6第三趟(5)[8,5,3,2],9,1,6第四趟(9)[9,8,5,3,2],1,6第五趟(1)[9,8,5,3,2,1],6第六趟(6)[9,8,6,5,3,2,1]直接选择排序：（第六趟后仅剩一个元素，是最小的，直接选择排序结束）第一趟(9)[9],3,2,5,8,1,6第二趟(8)[9,8],2,5,3,1,6第三趟(6)[9,8,6],5,3,1,2第四趟(5)[9,8,6,5],3,1,2第五趟(3)[9,8,6,5,3],1,2第六趟(2)[9,8,6,5,3,2],13、(1) 请简述快速排序的算法思想。

(2)已知一组关键字：29，18，25，47，58，12，51，10，请写出按快速排序方法进行排序时的变化过程：(1)快速排序思想：首先将待排序记录序列中的所有记录作为当前待排序区域，以第一个记录的关键字作为枢轴（或支点）（pivot），凡其关键字不大于枢轴的记录均移动至该记录之前，凡关键字不小于枢轴的记录均移动至该记录之后。

致使一趟排序之后，记录的无序序列R[s..t]将分割成两部分：R[s..i-1]和R[i+1..t],且R[j].key≤R[i].key≤R[k].key(s≤j<i,i<k≤t),然后再递归地将R[s..i-1]和R[i+1..t]进行快速排序。

快速排序在记录有序时蜕变为冒泡排序，可用“三者取中”法改善其性能，避免最坏情况的出现。

具体排序实例不再解答。

(2) 快速排序：每划分一次书写一个次序，选择第一个元素29开始进行划分。

第一趟:10,18,25,12,29,58,51,47；第二趟:10,18,25,12,29,47,51,88；第三趟:10,12,18,25,29,47,51,88四、算法分析题1、阅读下列直接插入排序算法代码，并完成填空。

void InsertSort(SqList *L){ //对顺序表L作直接插入排序。

int i, j;for( i=2; i<=(*L).length; ++i)if LT( (*L).r[i].key, (*L).r[i-1].key ) //当<时, 将L.r[i]插入到有序区{ (*L).r[0]=(*L).r[i];for( j=i-1; LT( (*L).r[0].key, (*L).r[j].key ); --j)(*L).r[j+1] = (*L).r[j]; //记录后移(*L).r[j+1] = (*L).r[0]; //插入到正确位置}}2、阅读下列起泡排序法代码，并完成填空。

voidBubbleSort(Elem R[ ], int n){ Elem tmp;i = n;while (i>1){ lastExchangeIndex = 1;for (j = 1; j <i; j++)if ( R[j].key> R[j+1].key){ tmp=R[j]; R[j]=R[j+1]; R[j+1]=temp;lastExchangeIndex = j; //记下进行交换的记录位置}i = lastExchangeIndex; //本趟进行过交换的最后一个记录的位置}}3、阅读下面的一趟快速排序算法的代码，并完成填空。

int Partition (RedType R[], int low, int high){ R[0] = R[low];pivotkey = R[low].key; // 枢轴while (low<high){ while(low<high&& R[high].key>=pivotkey) --high;R[low] = R[high];while (low<high && R[low].key<=pivotkey) ++low;R[high] = R[low];}R[low] = R[0];return low;}五、算法描述题输入50个学生的记录（每个学生的记录包括学号和成绩），组成记录数组，然后按成绩由高到低的次序输出（每行10个记录）。

排序方法采用选择排序。