练习题9参考答案

3. 简答题

（1）简要叙述如何选择好的内排序方法。

答：没有哪一种内排序方法是绝对好的。每一种排序方法都有其优缺点，适合于不同的环境。因此，在实际应用中，应根据具体情况做选择。首先考虑排序对稳定性的要求，若要求稳定，则只能在稳定方法中选取，否则可以在所有方法中选取；其次要考虑待排序结点数n的大小，若n较大，则可在改进方法中选取，否则在简单方法中选取；然后再考虑其他因素。下面给出综合考虑了以上几个方面所得出的大致结论：

① 当待排序的结点数n较大，关键字的值分布比较随机，并且对排序稳定性不作要求时，宜选用快速排序法。

② 当待排序的结点数n较大，内存空间又允许，并且要求排序稳定时，宜采用归并排序法。

③ 当待排序的结点数n较大，关键字的值的分布可能出现升序或者逆序的情况，并且对排序稳定性不作要求时，宜采用堆排序方法或者归并排序方法。

④ 当待排序的结点数n较小，关键字的值基本有序（升序）或者分布比较随机，并且有排序稳定性要求时，宜采用插入排序法。

⑤ 当待排序的结点数n较小，对排序稳定性不作要求时，宜采用选择排序方法，若关键字的值不接近逆序，亦可采用直接插入排序法。

⑥ 已知两个有序表，若要将它们组合成一个新的有序表，最好的方法是归并排序方法。 （2）给出关键字序列{4,5,1,2,8,6,7,3,10,9}的希尔排序过程。 答：希尔排序过程如图9.1所示。

排序前:4,5,1,2,8,6,7,3,10,9 gap=5: 4,5,1,2,8,6,7,3,10,9 gap=2: 1,2,4,3,7,5,8,6,10,9 gap=1: 1,2,3,4,5,6,7,8,9,10 排序后:1,2,3,4,5,6,7,8,9,10 图9.1 希尔排序各趟排序结果

（3）一个有n个整数的数组R[1..n]，其中所有元素是有序的，将其看成是一棵完全二叉树，该树构成一个堆吗？若不是，请给一个反例，若是，请说明理由。

答：该数组一定构成一个堆，递增有序数组构成一个小根堆，递减有序数组构成一个大根堆。

以递增有序数组为例，假设数组元素为k1、k2、…、kn是递增有序的，从中看出下标越大的元素值也越大，对于任一元素ki，有ki

（4）已知序列{75,23,98,44,57,12,29,64,38,82}，给出采用冒泡排序法对该序列作升序排序时的每一趟的结果。

答：采用冒泡排序法排序的各趟的结果如下：

初始序列:

75 23 98 44 57 12 29 64 38 82

练习题及参考答案 i=0(归位元素:12):12 75 23 98 44 57 29 38 64 82 i=1(归位元素:23):12 23 75 29 98 44 57 38 64 82 i=2(归位元素:29):12 23 29 75 38 98 44 57 64 82 i=3(归位元素:38):12 23 29 38 75 44 98 57 64 82 i=4(归位元素:44):12 23 29 38 44 75 57 98 64 82 i=5(归位元素:57):12 23 29 38 44 57 75 64 98 82 i=6(归位元素:64):12 23 29 38 44 57 64 75 82 98

（5）已知序列{75,23,98,44,57,12,29,64,38,82}，给出采用快速排序法对该序列作升序排序时的每一趟的结果。

答：采用快速排序法排序的各趟的结果如下：

初始序列:

75 23 98 44 57 12 29 64 38 82 38 23 64 44 57 12 29 75 98 82 29 23 12 38 57 44 64 75 98 82 12 23 29 38 57 44 64 75 98 82 12 23 29 38 57 44 64 75 98 82 12 23 29 38 44 57 64 75 98 82 12 23 29 38 44 57 64 75 82 98

区间:0-9 基准:75: 区间:0-6 基准:38: 区间:0-2 基准:29: 区间:0-1 基准:12: 区间:4-6 基准:57: 区间:8-9 基准:98:

（6）已知序列{75,23,98,44,57,12,29,64,38,82}，给出采用简单选择排序法对该序列作升序排序时的每一趟的结果。

答：采用直接选择法排序的各趟的结果如下：

初始序列:

75 23 98 44 57 12 29 64 38 82

i=0 归位元素:12 12 23 98 44 57 75 29 64 38 82 i=1 归位元素:23 12 23 98 44 57 75 29 64 38 82 i=2 归位元素:29 12 23 29 44 57 75 98 64 38 82 i=3 归位元素:38 12 23 29 38 57 75 98 64 44 82 i=4 归位元素:44 12 23 29 38 44 75 98 64 57 82 i=5 归位元素:57 12 23 29 38 44 57 98 64 75 82 i=6 归位元素:64 12 23 29 38 44 57 64 98 75 82 i=7 归位元素:75 12 23 29 38 44 57 64 75 98 82 i=8 归位元素:82 12 23 29 38 44 57 64 75 82 98

（7）已知序列{75,23,98,44,57,12,29,64,38,82}，给出采用堆排序法对该序列升序排序时的每一趟的结果。

答：采用堆排序法排序的各趟的结果如下：

初始序列: 初始堆:

75 23 98 44 57 12 29 64 38 82 98 82 75 64 57 12 29 44 38 23 82 64 75 44 57 12 29 23 38 98 75 64 38 44 57 12 29 23 82 98 64 57 38 44 23 12 29 75 82 98 57 44 38 29 23 12 64 75 82 98 44 29 38 12 23 57 64 75 82 98 38 29 23 12 44 57 64 75 82 98 29 12 23 38 44 57 64 75 82 98 23 12 29 38 44 57 64 75 82 98

归位元素:98 调整成堆[1..9]: 归位元素:82 调整成堆[1..8]: 归位元素:75 调整成堆[1..7]: 归位元素:64 调整成堆[1..6]: 归位元素:57 调整成堆[1..5]: 归位元素:44 调整成堆[1..4]: 归位元素:38 调整成堆[1..3]: 归位元素:29 调整成堆[1..2]:

2

归位元素:23 调整成堆[1..1]:

练习题及参考答案 12 23 29 38 44 57 64 75 82 98

（8）已知序列{75,23,98,44,57,12,29,64,38,82}，给出采用归并排序法对该序列作升序排序时的每一趟的结果。

答：采用归并排序法排序的各趟的结果如下：

初始序列:

75 23 98 44 57 12 29 64 38 82

length=1: 23 75 44 98 12 57 29 64 38 82 length=2: 23 44 75 98 12 29 57 64 38 82 length=4: 12 23 29 44 57 64 75 98 38 82 length=8: 12 23 29 38 44 57 64 75 82 98

（10）如果在106个记录中找前10个最小的记录，你认为采用什么样的排序方法所需的关键字比较次数最少？为什么？

答：采用堆排序方法，建立初始堆时间为4n，每次选取一个最小记录后再筛选的时间为log2n，找前10个最小的记录的时间=4n+9log2n。而冒泡排序和简单选择排序需10n的时间。而直接插入排序、希尔排序和二路归并排序等必须全部排好序后才能找前10个最小的记录，显然不能采用。

（11）设有11个长度（即包含记录个数）不同的初始归并段，它们所包含的记录个数为{25,40,16,38,77,64,53,88,9,48,98}。试根据它们做4路平衡归并，要求：

① 指出总的归并趟数； ② 构造最佳归并树；

③ 根据最佳归并树计算每一趟及总的读记录数。 答：① 总的归并趟数=?log411?=2。

② m=11，k=4，(m-1) MOD (k-1)=1≠0，需要附加k-1-(m-1) MOD (k-1)=2个长度为0的虚归并段，最佳归并树如图9.2所示。

0 0 9 16 25 25 38 40 48 53 64 77 128 88 242 98 556 图9.2 最佳归并树

③ 根据最佳归并树计算每一趟及总的读记录数： 第1趟的读记录数=9+16=25

第2趟的读记录数=25+25+38+40+48+53+64+77=370 第3趟的读记录数=128+88+242+98=556 总的读记录数=25+370+556+951。

3

练习题及参考答案 4. 算法设计题

（1）设计一个直接插入算法：设元素为R[0..n-1]，其中R[i-1..n-1]为有序区，R[0..i]为无序区，对于元素R[i]，将其关键字与有序区元素（从头开始）进行比较，找到一个刚好大于R[i].key的元素R[j]，将R[i..j-1]元素前移，然后将原R[i]插入到R[j-1]处。要求给出每趟结束后的结果。

解：对应的算法如下：

void InsertSort3(SqType R[],int n) { }

int i,j,k; SqType tmp;

for (i=n-2;i>=0;i--) { }

tmp=R[i]; j=i+1;

while (jR[j].key)

j++;

//在有序区找到一个刚大于tmp.key的位置R[j] //R[i..j-1]元素前移,以便腾出一个位置插入tmp //在j-1位置处插入tmp

for (k=i;k

R[k]=R[k+1];

R[j-1]=tmp;

printf(\for (k=0;k

printf(\printf(\

（2）有一种简单的排序算法，叫做计数排序。这种排序算法对一个待排序的表（用数

组表示）进行排序，并将排序结果存放到另一个新的表中。必须注意的是，表中所有待排序的关键字互不相同，计数排序算法针对表中的每个元素，扫描待排序的表一趟，统计表中有多少个元素的关键字比该元素的关键字小。假设对某一个元素，统计出数值为c，那么这个元素在新的有序表中的合适的存放位置即为c。

① 设计实现计数排序的算法。

② 对于有n个元素的表，比较次数是多少？

③ 与简单选择排序相比，这种方法是否更好？为什么？ 解：① 对应的计数排序的算法如下：

void CountSort(SqType A[],SqType B[],int n) {

int i,j,count; for (i=0;i

count=0;

//统计A中小于A[i].key的元素个数

for (j=0;j

if (A[j].key

count++;

B[count]=A[i];

4

}

练习题及参考答案 ② 对于有n个元素的表，每个元素都要与n个元素（含自身）进行比较，关键字比较的总次数是n2。

③ 简单选择排序比这种计数排序好，因为对有n个元素的数据表进行简单排序只需进行1+2+…+(n-1)=n(n-1)/2次比较，且可在原地进行排序。

（3）设计一个算法，判断一个数据序列是否构成一个大根堆。 解：当数据个数n为偶数时，最后一个分支结点（编号为n/2）只有左孩子（编号为n），其余分支结点均为双分支结点；当n为奇数时，所有分支结点均为双分支结点。对每个分支结点进行判断，只有一个分支结点不满足小根堆的定义，返回0；如果所有分支结点均满足小根堆的定义，返回1。对应的算法如下：

int IsHeap(SqType R[],int n) { }

int i;

if (n%2==0) //n为偶数时,最后一个分支结点(编号为n/2)只有左孩子(编号为n) { } else { }

return(1);

//n为奇数时,所有分支结点均为双分支结点

//判断所有双分支结点

if (R[i].key>R[2*i].key || R[i].key>R[2*i+1].key)

return(0);

for (i=n/2;i>=1;i--) if (R[n/2].key>R[n].key)

return(0);

if (R[i].key>R[2*i].key || R[i].key>R[2*i+1].key)

return(0);

for (i=n/2-1;i>=1;i--) //判断所有双分支结点

上机实验题9

有一个整型数组A[0..n-1]，前m（0

（1）要求算法的时间复杂度为O(n)，设计相应的算法Sort1(A,m,n)。 （2）要求算法的空间复杂度为O(1)，设计相应的算法Sort2(A,m,n)。

解：Sort1算法采用二路归并思想，Sort2算法采用直接插入思想。对应的程序如下：

#include #include #define MaxSize 100

void Sort1(int A[],int m,int n)

//将A[0..m-1]和A[m..n-1]两个相邻的有序表归并为一个有序表A[0..n-1]

5

本文来源：https://www.bwwdw.com/article/jnqv.html