第九章习题
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 编写一个双向起泡的排序算法，即相邻两遍向相反方向起泡。 9.7 编写算法，对n个关键字取整数值的记录序列进行整理，以使所有关键字为负值的记录 排在关键字为非负值的记录之前，要求： 采取顺序存储结构，至多使用一个记录的辅助存储空间； 算法的时间复杂度O(n)； 讨论算法中记录的最大移动次数。 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=?√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.13 插入排序中找插入位置的操作可以通过二分查找的方法来实现。试据此写一个改进后 的插入排序算法。 9.14 一个线性表中的元素为正整数或负整数。设计一个算法，将正整数和负整数分开，使 线性表的前一半为负整数，后一半为正整数。不要求对元素排序，但要尽量减少交换次数。 9.15 为什么通常使用一维数组作为堆的存放形式？ 9.16 已知（k1,k2,…，kn）是堆，写一个算法将（k1,k2,…，kn，kn+1）调整为堆。按此思想 写一个从空堆开始一个一个添入元素的建堆算法。 9.17 试比较直接插入排序、简单选择排序、快速排序、堆排序、归并排序、希尔排序和基 数排序的时空性能、稳定性和适用情况。 9.18 在供选择的答案中填入正确答案： (1)、排序（分类）的方法有许多种：__A__法从未排序序列中依次取出元素，与排序序 列（初始为空）中的元素作比较，将其放入已排序列的正确位置上；__B__法从未排序序列中挑选元素，并将其依次放入已排序序（初始时为空）的一端；交换排序法是对序列中元素进行一系列的比较，当被比较的两元素逆序时进行交换。__C___和__D__是基于这类方法的两种排序方法，而__D__是比__C__效率更高的方法，利用某种算法，根据元素的关键值计算出排序位置的方法是__E__。 供选择答案 ① 选择排序 ② 快速排序 ③ 插入排序 ④ 冒泡排序 ⑤ 归并排序 ⑥ 二分排序 ⑦ 哈希排序 ⑧ 基数排序 (2)、一组记录的关键字为（46，79，56，38，40，84），利用快速排序的方法，以第一个记录为基准得到的一次划分结果为 。 A、38，40，46，56，79，84 B、40，38，46，79，56，84 C、40，38，46，56，79，84 D、40，38，46，84，56，79 (3)、下列排序算法中， 算法可能会出现下面情况：初始数据有序时，花费时间反而最多。 A、堆排序 B、冒泡排序 C、快速排序 D、SHELL 排序 9.19 判断正误： （ ）在一个大堆中，最小元素不一定在最后。 （ ）对n个记录采用快速排序方法进行排序，最坏情况下所需时间是o（nlog2n）。 （ ）在执行某排序算法过程中，出现了排序码朝着与最终排序序列相反方向移动的现 象，则称该算法是不稳定的。 实习题 一、 随机生成30个数，试比较直接插入排序、简单选择排序、起泡排序、快速排序、堆排 序和希尔排序的时空性能和稳定性。 二、 统计成绩。 给出n个学生的考试成绩表，每条信息由姓名与分数组成。 (1)按分数高低次序，打印出每个学生在考试中获得的名次，分数相同的为同一名次； (2)按名次列出每个学生的姓名与分数。 9.1 (1)无序表：顺序查找不成功时，查找长度为n+1；成功时，平均查找长度为1/(n+1)*(1+2+…+(n+1))=(n+2)/2；两者不相同。 （2）表中只有一个关键字等于给定值k的记录，无序表、有序表：顺序查找成功时，平均查找长度均为1/(n)*(1+2+…+n)=(n+1)/2；两者相同。 （3）表中只有m个关键字等于给定值k的记录，无序表：ASL=n+1；有序表：ASL=（n+1）/2+m；两者不相同。 5 2 1 3 4 9.3 ASL=1/10（1+2*2+4*3+3*4）=2.9 9.11 9.14 6 7 8 9 10 30 20 20 30 20 50 30 52 30 20 50 52 20 50 60 52 30 52 30 68 20 60 68 50 50 20 删除50后 60 70 52 68 20 30 60 70 52 20 30 60 70 删除68后 9.19 22 67 41 30 53 46 13 01 0 1 2 3 4 5 6 7 8 9 10 ASL=（4*1+2*2+3+6）/8=17/8 9.25 int Search-Seq(SSTable ST, KeyType key){ //在顺序表ST中顺序查找其关键字等于key的数据元素，ST按关键字自大至小有序， //若找到，则函数值为该元素在表中的位置，否则为0 ST.elem[ST.length+1].key=key; for (i=1; ST.elem[i].key>key; ++i); if (ST.elem[i].key==key)&&(i<=ST.length) return i else return 0 ; }//Search-Seq 9.31 TelemType Maxv(Bitree T){ //返回二叉排序树T中所有结点的最大值 for (p=T; p->rchild; p=p->rchild); return p->data; }//Maxv TelemType Minv(Bitree T){ //返回二叉排序树T中所有结点的最小值 for (p=T; p->lchild; p=p->lchild); return p->data; }//Minv Status IsBST(Bitree T){ //判别T是否为二叉排序树 if (!T) return OK; else if ((!T->lchild)||((T->lchild)&&(IsBST(T->lchild)&&(Maxv(T->lchild) &&((!T->rchild)||((T->rchild)&&(IsBST(T->rchild)&&(Minv(T->rchild)>T->data))) return OK else return ERROR; }//IsBST 9.33 Status OutputGEx(Bitree T, TelemType x){ //从大到小输出给定二叉排序树T中所有值不小于x的数据元素 if (T) { if (OutputGEx(T->rchild, x)) if (T->data>=x) { print(T->data); if (OutputGEx(T->lchild, x)) return OK; } else return OK; } else return OK; }//OutputGEx 第九章 查找 9.25 int Search_Sq(SSTable ST,int key)//在有序表上顺序查找的算法,监视哨设在高下标端 { ST.elem[ST.length+1].key=key; for(i=1;ST.elem[i].key>key;i++); if(i>ST.length||ST.elem[i].key 分析:本算法查找成功情况下的平均查找长度为ST.length/2,不成功情况下为ST.length.