第九章习题分析和总结.docx

第九章习题

9.1 以关键码序列（503，087，512，061，908，170，897，275，653，426）为例，手工执行以下排序算法，写出每一趟排序结束时的关键码状态：

（1）直接插入排序； （2）希尔排序（增量d[1]=5）；

（3）快速排序； （4）堆排序；

（5）归并排序； （6）基数排序。

一组关键字码，40，27，28，12，15，50，7，采用快速排序或堆排序，写出每趟排序结果。

不难看出，对长度为n的记录序列进行快速排序时，所需进行的比较次数依赖于这n

个元素的初始排列。

n=7时在最好情况下需进行多少次比较？请说明理由。对n=7给出一个最好情况的初始排列实例。

假设序列由n个关键字不同的记录构成，要求不经排序而从中选出关键字从大到小顺序的前k(kn)个记录。试问如何进行才能使所作的关键字间比较次数达到最小？

插入排序中找插入位置的操作可以通过二分查找的方法来实现。试据此写一个改进后的插入排序算法。

编写一个双向起泡的排序算法，即相邻两遍向相反方向起泡。

编写算法，对n个关键字取整数值的记录序列进行整理，以使所有关键字为负值的记录排在关键字为非负值的记录之前，要求：

采取顺序存储结构，至多使用一个记录的辅助存储空间；算法的时间复杂度O(n)；

讨论算法中记录的最大移动次数。

试以单链表为存储结构实现简单选择排序的算法

假设含n个记录的序列中，其所有关键字为值介于v和w之间的整数，且其中很多关键字的值是相同的。则可按如下方法排序：另设数组number[v...w]且令number[i]为统计关键字取整数I的记录数，之后按number重排序列以达到有序，编写算法实现上述排序方法，并讨论此方法的优缺点。

已知两个有序序列(a,a,...,a)和(a

,a ,...,a),并且其中一个序列的记录

1 2 m

m+1

m+2 n

个数少于s,且s=?√n?. 试写一个算法,用O(n)时间和O(1)附加空间完成这两个

有序序列的归并。

偶交换排序如下所述：第一趟对所有奇数i,将a[i]和a[i+1]进行比较；第二趟对所有偶数i,将a[i]和a[i+1]进行比较，若a[i]a[i+1],则将两者交换；第一趟对所有奇数i,第二趟对所有偶数i，…,依次类推直至整个序列有序为止。

这种排序方法的结束条件是什么？

分析当初始序列为正序或逆序两种情况下，奇偶交换排序过程中所需进行的关键字比较的次数。

写出奇偶交换排序的算法。

设计一个用链表表示的直接选择排序算法。

插入排序中找插入位置的操作可以通过二分查找的方法来实现。试据此写一个改进后的插入排序算法。

一个线性表中的元素为正整数或负整数。设计一个算法，将正整数和负整数分开，使线性表的前一半为负整数，后一半为正整数。不要求对元素排序，但要尽量减少交换次数。

为什么通常使用一维数组作为堆的存放形式？

已知（k,k,…，k）是堆，写一个算法将（k,k,…，k，k ）调整为堆。按此思想

1 2 n

1 2 n

n+1

写一个从空堆开始一个一个添入元素的建堆算法。

试比较直接插入排序、简单选择排序、快速排序、堆排序、归并排序、希尔排序和基数排序的时空性能、稳定性和适用情况。

在供选择的答案中填入正确答案：

、排序（分类）的方法有许多种：A法从未排序序列中依次取出元素，与排序序列（初始为空）中的元素作比较，将其放入已排序列的正确位置上；B法从未排序序列中挑选元素，并将其依次放入已排序序（初始时为空）的一端；交换排序法是对

序列中元素进行一系列的比较，当被比较的两元素逆序时进行交换。 C 和 D

是基于这类方法的两种排序方法，而

D 是比

C 效率更高的方法，利用某种算法，

根据元素的关键值计算出排序位置的方法是 E 。供选择答案

①

选择排序

②

快速排序

③

插入排序

④

冒泡排序

⑤

归并排序

⑥

二分排序

⑦

哈希排序

⑧

基数排序

、一组记录的关键字为（46，79，56，38，40，84），利用快速排序的方法，以第一个记录为基准得到的一次划分结果为 。

A、38，40，46，56，79，84B、40，38，46，79，56，84C、40，38，46，56，79，84D、40，38，46，84，56，79

、下列排序算法中， 算法可能会出现下面情况：初始数据有序时，花费时间反而最多。

A、堆排序 B、冒泡排序 C、快速排序 D、SHELL排序

判断正误：

（）在一个大堆中，最小元素不一定在最后。

（）对n个记录采用快速排序方法进行排序，最坏情况下所需时间是o（nlogn）。

2

（）在执行某排序算法过程中，出现了