8.2　习题解答

一、选择题

1. 在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是( )。

A. 希尔排序 B. 起泡排序 C. 插入排序 D. 选择排序

【解答】 D

分析：由选择排序的定义可知。

2. 对初始状态为递增有序的序列进行排序，最省时间的是( )，最浪费时间的是( )。已知待排序序列中每个元素距其最终位置不远，则采用( )方法最节省时间。

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

【解答】 (1)(B)　(2)(C)　(3)(B)

分析：待排序序列中每个元素距其最终位置不远意味着该序列基本有序，由各种排序的定义可知。

3. 堆是一个键位序列｛k₁，k₂，k,…，k₁…，k₀｝，对i＝1，2,…，[n/2]，满足( )。

A.k_i≤k_2i≤k_2i＋1　　B.k_i＜k_2i＜k_2i＋1

C.k_i≤k_2i且k_i≤k_2i+1(2i+1n)　　D.k_i≤k_2i或k_i≤k_2i+1(2i+1≤n)

【解答】 C

分析：满足k_i≤k_2i且k_i≤k_2i+1(2i+1≤n)条件的完全二叉树为堆。这个堆中根结点的关键字最小，称为小根堆。反之，如果这棵完全二叉树中任意结点的关键字大于或者等于其左孩子和右孩子的关键字(当有左孩子或右孩子时)，对应的堆为大根堆。所以正确答案为C。

4. 快速排序方法在( )情况下最不利于发挥其长处。

A. 要排序的数据量太大　　　　B. 要排序的数据中含有多个相同值

C. 要排序的数据已基本有序　　D. 要排序的数据个数为奇数

【解答】 C

分析：由快速排序的定义和特性易知。

5. 将上万个一组无序并且互不相等的正整数序列，存放于顺序存储结构中，采用( )方法能够最快地找出其中最大的正整数。

A. 快速排序　　　　B. 插入排序

C. 选择排序　　　　D. 归并排序

【解答】 C

分析：由于选择排序每趟从待排序的记录中选出关键字最小的记录，每个记录都要进行比较，不考虑已排好序的子文件，因此，关键字比较的次数与记录的初始排列无关。常用的选择排序方法是直接选择排序和堆排序。由于堆排序一趟排好一个记录，如果要找出其中最大的元素，使用堆排序最好。所以正确答案为C。

6. 内部排序的方法有许多种，( )方法是从未排序序列中依次取出元素，与已排序序列中的元素作比较，将其放入已排序序列的正确位置上。

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

【解答】 B

分析：插入排序的基本思想是：在一个已排好序的记录子集的基础上，每一步将下一个待排序的记录插入到已排好序的记录子集中，直到将所有待排序记录全部插入为止。所以正确答案为B。

二、填空

1. 内部排序的方法可以分为五类：( )、( )、( )、( )、( )。

【解答】 内部排序的方法分为五类：插入排序、选择排序、交换排序、归并排序、分配排序。

2. 在具有24个元素的有序上进行折半(二分查找)，则比较一次查找成功的结点数为，比较二次查找成功的结点数为，比较三次查找成功的结点数为，比较四次查找成功的结点数为，比较五次查找成功的结点数为。总的平均查找长度为。

【解答】 折半查找过程可以与一棵二叉树相对应，那么第一层上有1个结点，第二层上有2个结点，第三层上有4个结点，第四层上有8个结点，第五层上有9个结点。

平均查找长度为：ASL=(1×1+2×2+3×4+4×8+5×9)/24≈3.92

三、如果只想得到一个序列中第k个最小元素之前的部分排序序列，最好采用什么排序方法？为什么？如由这样的一个序列：{57，40，38，11，13，34，48，75，25，6，19，9，7}得到其第4个最小元素之前的部分序列{6，7，9，11}，使用所选择的算法实现时，要执行多少次比较？

【解答】 采用堆排序最适合，依题意可知只需取得第k个最小元素之前的排序序列时，堆排序的时间复杂度是O(n+klog₂n)，若k≤n/log₂n，则可得到的时间复杂度是O(n)。

对于序列：{57,40,38,11,13,34,48,75,25,6,19,9,7}得到其4个最小元素之前的部分序列{6，7，9，11}，使用所选择的算法实现时，其执行比较次数如下：

建堆　　　20次　　　　得到 6

调整　　　5次　　　　得到 7

调整　　　4次　　　　得到 9

调整　　　5次　　　　得到11

共计执行34次比较。

四、已知下列各种初始状态(长度为n)的元素，试问当利用直接插入法进行排序时，至少需要进行多少次比较(要求排序后的文件按关键字从小到大顺序排列)。

(1) 关键字自小至大有序(key₁＜key₂＜…＜key_n)。

(2) 关键字自大至小逆序(key₁＞key₂＞…＞key_n)。

(3) 奇数关键字顺序有序，偶数关键字顺序有序(key₁＜key₃＜…＜key₂＜key₄)。

(4) 前半部分元素按关键字顺序有序，后半部分元素关键字顺序逆序。

(key₁＜key₂＜…＜key_m，key_m+1＜key_m+2＜…＜key_n这里的m是中间位置)

【解答】 依题意，各种情况下的最好的比较次数即为最少比较次数。

(1) 这种情况下，插入第i(2≤i≤n)个元素的比较次数为1，因此总的比较次数为：

1+1+…+1=n-1

(2) 这种情况下，插入第i(2≤i≤n)个元素的比较次数为i，因此总的比较次数为：

2+3+…+n=[(n-1)(n+2)]/2

(3) 这种情况下，比较次数最少的情况是所有记录关键字均按升序排列，此时，总的比较次数为：n-1

(4)在后半部分的关键字均大于前半部分的关键字时需要的比较次数最少，此时前半部分的比较次数=m-1，后半部分的比较次数=(n-m-1)(n-m+2)/2,因此，比较次数为：m-1+(n-m+1)(n-m+2)/2=(n-2)(n+8)/8 (假设n为偶数，m=n/2)

五、已知有一关键字序列为{486，79，596，34，900，120，789，179，703，307}，如果我们采用基数排序方法对此序列进行排序 (按照升序排列)，请给出每一趟的排序结果。

【解答】 基数排序的基本思想是：从低位到高位依次对k^j(j=d-1，d-2,…,0)进行箱排序，根据基数排序法的基本方法，我们得到如下的排序结果：

初始：486，596，34，900，120，789，179，703，307

第1趟：(按个位进行排序)：120，900，703，34，486，596，307，79，179，389

第2趟：(按十位进行排序)：307，703，900，120，34，79，179，486，789，596

第3趟：(按百位进行排序)：34，79，120，307，486，596，703，789，900

六、已知有一关键字序列为｛372，81，437，96，205，732，821，634，572，495，264｝，如果采用归并排序方法对此序列进行升序排列，请给出每一趟的排序结果。

【解答】 归并排序的基本思想是：第1趟归并排序是，将待排序的文件R[1,…,n]看作是n个长度为1的有序子文件，将这些文件两两归并，若n是偶数，则得到n/2个长度为2的有序文件；若n为奇数，则最后一个文件轮空，此时得到[n/2]-1个有序文件长度为2，最后一个文件长度为1，第2趟是将第1趟得到的各个有序子文件进行两两归并。这样依次类推，直到得到一个长度是n的有序文件为止。按照上述规则，我们得到各趟归并的结果如下：

初始：372，81，437，96，205，732，21，634，572，495，264

第1趟归并后：[81，372][96，437][205，732][634，821][495，572][264]

第2趟归并后：[81，96，372，437][205，634，732，821][264，495，572]

第3趟归并后：[81，96 ，205，372，437，634，732，821][264，495，572]

第4趟归并后：[81，96，205，264，372，437，495，572，634，732，821]

七、已知奇偶转换排序如下所述；第一趟对所有奇数的i，将a[i]和a[j]进行比较，第二趟对所有偶数的i，将a[i]与a[i+1]进行比较，每次比较时若a[i] ＞a[i+1], 则将二者交换，以后重复上述二趟过程交换进行，直至整个数组有序。

(1) 试问排序结束的条件是什么？

(2) 编写一个实现上述排序过程的算法。

【解答】 (1) 排序结束条件为没有交换元素时为止。

(2) 实现本题奇偶转换排序函数如下：

八、算法设计(用C++代码实现)：

(1) 编写一个递归函数实现归并排序。

【解答】 根据题意，归并排序的递归模型为：

归并排序的递归函数如下，其中r[l，h]经排序后放在r₁[l，h]之中，r₂[l，h]为辅助空间：

合并函数如下，其中r[l,m](s1)及r[m+1,h](s2)分别有序，归并后置于r2中：

(2) 直接插入排序中寻找插入位置的操作可以通过折半查找来实现。据此写一个改进的插入排序的算法。

【解答】 插入排序的基本思想是：每趟从无序区中取出一个元素，按键值大小插入到有序区中，对于有序区，当然可以采用折半查找来确定插入位置。算法如下：

(3) 采用单链表作存储结构，编写一个采用选择排序方法进行升序排序的函数。

【解答】