5.3 KiB
排序习题
基本概念
例题 对任意$7$个关键字进行基于比较的排序，至少要进行()次关键字之间的两两比较。
A.13
B.14
C.15
D.6
解：$A$。对于任意序列进行基于比较的排序，求最少的比较次数应考虑最坏情况。对任意$n$个关键字排序的比较次数至少$\lceil\log_2(n!)\rceil$。将$n=7$代入公式，答案为$13$。上述公式证明如下（仅供有兴趣的同学参考）：在基于比较的排序方法中，每次比较两个关键字后，仅出现两种可能的转移。假设整个排序过程至少需要做$t$次比较，则显然会有$2^t$种情况。由于$n$个记录共有$n!$种不同的排列，因而必须有$n!$种不同的比较路径，于是有$2^t\geqslant n!$，即$t\geqslant\log_2(n!)$。考虑到$t$为整数，故为$\lceil\log_2(n!)\rceil$。
插入排序
例题 有些排序算法在每趟排序过程中，都会有一个元素被放置到其最终位置上，()算法不会出现此种情况。
$A.$希尔排序
$B.$堆排序
$C.$冒泡排序
$D.$快速排序
解：$A$。希尔排序是组间有序组内无序。
交换排序
例题 采用递归方式对顺序表进行快速排序。下列关于递归次数的叙述中，正确的是()。
$A.$递归次数与初始数据的排列次序无关
$B.$每次划分后，先处理较长的分区可以减少递归次数
$C.$每次划分后，先处理较短的分区可以减少递归次数
$D.$递归次数与每次划分后得到的分区的处理顺序无关
解：$D$。递归次数与各元素的初始排列有关。若每次划分后分区比较平衡，则递归次数少；若分区才平衡，递归次数多。递归次数与处理顺序是没有关系的。
选择排序
简单选择排序
例题 设线性表中每个元素有两个数据项$k_1$和$k_2$，现对线性表按以下规则进行排序：先看数据项$k_1$，$k_1$值小的元素在前，大的元素在后；在$k_1$值相同的情况下，再看$k_2$，$k_2$值小的在前，大的元素在后。满足这种要求的排序方法是()。
$A.$先按$k_1$进行直接插入排序，再按$k_2$进行简单选择排序
$B.$先按$k_2$进行直接插入排序，再按$k_1$进行简单选择排序
$C.$先按$k_1$进行简单选择排序，再按$k_2$进行直接插入排序
$D.$先按$k_2$进行简单选择排序，再按$k_1$进行直接插入排序
解：$D$。首先应确定$k_1$、$k_2$的排序顺序，若先排$k_1$再排$k_2$，则排序结果不符合题意，排除选项$A$、$C$。再考虑算法的稳定性，当$k_1$排好序后，再对$k_2$排序，若对$k_2$排序采用的算法是不稳定的，则对于$k_1$相同而$k_2$不同的元素可能会改变相对次序，从而不一定能满足题干中的条件“在$k_1$值相同的情况下，$k_2$值小的元素在前，大的元素在后”。直接插入排序算法是稳定的，而简单选择排序算法是不稳定的，故只能选$D$。
堆排序
例题 对关键码序列${23,17,72,60,25,8,68,71,52}$进行堆排序，输出两个最小关键码后的剩余堆是()。
A.\{23,72,60,25,68,71,52\}
B.\{23,25,52,60,71,72,68\}
C.\{71,25,23,52,60,72,68\}
D.\{23,25,68,52,60,72,71\}
解：$D$。筛选法初始建堆为${8,17,23,52,25,72,68,71,60}$，输出$8$后重建的堆为${17,25,23,52,60,72,68,71}$，输出$17$后重建的堆为${23,25,68,52,60,72,71}$。
归并排序
例题 下列排序方法中，排序过程中比较次数的数量级与序列初始状态无关的是()。
$A.$归并排序
$B.$插入排序
$c.$快速排序
$D.$冒泡排序
解：$D$。选择排序和归并排序都与序列初始状态无关。
外部排序
败者树
例题 设有$5$个初始归并段，每个归并段有$20$个记录，采用$5$路平衡归并排序，若不采用败者树，使用传统的顺序选出最小记录（简单选择排序）的方法，总的比较次数是(①)，若采用败者树最小的方法，总的比较次数是(②)。
A.20
B.300
C.396
D.500
解：$C,B$。不采用败者树时，在$5$个记录中选出最小的需要做$4$次比较，共有$5\times20=100$个记录，需要估$99$次选择最小记录的操作，所以需要的比较次数为$4\times99=396$，故选$C$。
采用败者树时，$5$路归并意味着败者树的外结点有$5$个，败者树的高$h=\lceil\log_25\rceil=3$。每次在参加比较的记录中选择一个关键字最小的记录，比较次数不超过$h$，共$100$个记录需要的比较次数不超过$100\times3=300$，故选$B$。
例题 在做$m$路平衡归并排序的过程中，为实现输入/内部归并/输出的并行处理，需要设置(①)个输入缓冲区和(②)个输出缓冲区。
A.2
B.m
C.2m-1
D.2m
解：$D,A$。增加一个输出缓冲区，当一个输出缓冲区满时，通知通道进行输出，同时归并程序向第二个输出缓冲区填充数据，这就实现了内部归并和输出的并行。增加$m$个输入缓冲区，当$m$个缓冲区正在运行时，外部可以向正在工作的$m$个缓冲区对应的第二个缓冲区（也就是增加的$m$个缓冲区）写入数据，这就实现了输入和内部归并的并行。综上两点设置$2$个输出$2m$个输入缓冲区即可实现输入/内部归并/输出的并行处理。