《数据结构 - C语言描述》习题及答案 耿国华 下载本文

第九章 内部排序

习 题

9.1 以关键码序列(503,087,512,061,908,170,897,275,653,426)为例,手

工执行以下排序算法,写出(前三趟)每一趟排序结束时的关键码状态:

(1)直接插入排序; (2)希尔排序(增量d[1]=5); (3)快速排序; (4)堆排序; (5)归并排序; (6)基数排序。

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

序结果。

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

个元素的初始排列。

n=7时在最好情况下需进行多少次比较?请说明理由。 对n=7给出一个最好情况的初始排列实例。 (保证每个基准记录都是中间记录)

9.4 假设序列由n个关键字不同的记录构成,要求不经排序而从中选出关键字从大到小顺序

的前k(k<

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

的插入排序算法。

9.6 编写一个双向起泡的排序算法,即相邻两遍向相反方向起泡。 [提示]:(1)参快速排序(2)“水底”、“水面”相遇时结束。

9.7 编写算法,对n个关键字取整数值的记录序列进行整理,以使所有关键字为负值的记录

排在关键字为非负值的记录之前,要求:

采取顺序存储结构,至多使用一个记录的辅助存储空间; 算法的时间复杂度O(n); 讨论算法中记录的最大移动次数。

[提示]:r[0]=r[1],以0为分界值,参快速排序划分过程,但不要求对元素排序。

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

9.9 假设含n个记录的序列中,其所有关键字为值介于v和w 之间的整数,且其中很多关

键字的值是相同的。则可按如下方法排序:另设数组number[v...w]且令number[i]为统计关键字取整数I 的记录数,之后按number 重排序列以达到有序,编写算法实现上述排序方法,并讨论此方法的优缺点。

9.10 已知两个有序序列(a1, a2 ,..., am)和(am+1 , am+2 ,..., an),并且其中一个序列的记录个数

少于s,且s= floor ( sqrt (n) ). 试写一个算法,用O(n)时间和O(1)附加空间完成这两个有序序列的归并。

9.11 偶交换排序如下所述:第一趟对所有奇数i,将a[i]和a[i+1]进行比较;第二趟对所有偶

数i,将a[i]和a[i+1]进行比较,若a[i]>a[i+1],则将两者交换;第一趟对所有奇数i, 第二趟对所有偶数i,…,依次类推直至整个序列有序为止。 (1)这种排序方法的结束条件是什么?

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

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

9.12 设计一个用链表表示的直接选择排序算法。(与9.8重)

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

的插入排序算法。(与9.5重复)

9.14 一个线性表中的元素为正整数或负整数。设计一个算法,将正整数和负整数分开,使

线性表的前一半为负整数,后一半为正整数。不要求对元素排序,但要尽量减少交换次数。(与9.7类似)

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

9.16 已知(k1,k2,…,kn)是堆,写一个算法将(k1,k2,…,kn,kn+1)调整为堆。按此思想

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