数据结构课后习题答案（修订版）(7)

{

int I;

R[Max].key=key;

for(I=0;R[I].key

return –1; }

函数SeqSearch返回值为-1时，表示查找失败;否则是查找到的关键字在表中的位置（下标值）。等概率情况下，查找成功的平均查找长度为（1/n）(1+2+…+n)=(n+1)/2;查找失败的平均查找长度为：(1/(n+1)) (1+2+3+…+n+(n+1))=(n+2)/2。

(2) 答：若查找成功返回指向关键字为x的结点的指针，否则查找失败返回NULL。 node *sqsearch(node *head,int x) {

node *p=head; while(p!=NULL) if (x>p->key) p=p->link;

else if(x==p->key) return p; else { p=NULL;

return p; }}

虽然链表中的结点是按从小到大的顺序排序的，但是其存储结构为单链表，查找结点时只能从头指针开始逐步进行搜索，故不能用折半查找。

习题十答案

1． 填空题

(1)D (2) L2 (3) 15 , 21 , 21 ,13

2．答：(1) flag=0 (2) 从0到n-I , R[j+1].key , R[j]=R[j+1] （3）flag=0 3．答：（1）直接插入排序

初始序列：[138] {219 365 513 206 211 511 276 868 641} 一趟结果：[138 219] {365 513 206 211 511 276 868 641} 二趟结果：[138 219 365] {513 206 211 511 276 868 641} 三趟结果：[138 219 365 513] {206 211 511 276 868 641} 四趟结果：[138 206 219 365 513] {211 511 276 868 641} 五趟结果：[138 206 211 219 365 513] {511 276 868 641} 六趟结果：[138 206 211 219 365 511 513] {276 868 641} 七趟结果：[138 206 211 219 276 365 511 513] {868 641} 八趟结果：[138 206 211 219 276 365 511 513 868] {641}

九趟结果：[138 206 211 219 276 365 511 513 641 868]

一趟结果d=5 : 138 219 276 513 206 211 511 365 868 641 d=2 {138 276 206 511 868}

{219 513 211 365 641} 二趟结果d=2: 138 211 206 219 276 365 511 513 868 641 d=1 {138 211 206 219 276 365 511 513 868 641} 三趟结果d=1: 138 206 211 219 276 365 511 513 641 868 4．答：用完全二叉树表示 从?n/2」=3开始

结点3大于结点6、7中的较大者，所以不交换，再比较上一个结点2，结点2小于结点4、5的值中的较大者结点4的值100，所以交换结点2、4.

结点1的值25小于结点3、4的值中的较大者结点4的值100，所以交换结点1、4，再接着检查结点1，因结点1的值小于结点2、5中的较大者结点2的值50，所以交换结点1、2。 生成了一个大根堆。

输出结点和调整过程如下：

输出100 调整 输出70 调整 输出50 调整 输出43 调整

输出25

接着输出结点7（12）、结点6（7）。这样得到一个从大到小的序列 （100 70 50 43 25 12 7）

5．答：过程如下：

初始状态：{72}{73}{71}{23}{94}{16}{05}{68}{48}{19}{26}

一趟归并：{72 73}{23 71}{16 94}{05 68}{19 48}{26}

二趟归并：{23 71 72 73}{05 16 68 94}{19 26 48}

三趟归并：{05 16 23 68 71 72 73 94}{19 26 48}

四趟归并：{05 16 19 23 26 48 68 71 72 73 94} 6．答：（1）快速排序： ①15为基准：

第一趟快速排序后：{7 2 12 5 9 }15{30 38 22 17 19} ②分别以7为基准，以30为基准：

第二趟快速排序后：{5 2}7{12 9}15{19 17 22}30{38} ③分别以5为基准，以12为基准，以19为基准： 第三趟快速排序后：{2 5 7 9 12 15 17 19 22 30 38} （2）归并排序：

初始状态： {15}{2}{17}{38}{9}{30}{5}{12}{22}{7}{19} 第一趟归并后：{2 15} {17 38} {9 30} {5 12} {7 22} {19} 第二趟归并后：{2 15 17 38} {5 9 12 30} {7 19 22} 第三趟归并后：{2 5 9 12 15 17 30 38} {7 19 22} 第四趟归并后：{2 5 7 9 12 15 17 19 22 30 38} （3）基数排序： 初始状态：

15→2→17→38→9→30→5→12→22→7→19 第一趟分配：

r[0] r[1] r[2] r[3] r[4] r[5] r[6] r[7] r[8] r[9] ↓ 22 ↓ 12 5 7 ↓ ↓ ↓ 30 2 15 17 38 19 第一趟收集：

30→2→12→22→15→5→17→7→38→19 第二趟分配：

r[0] r[1] r[2] r[3] r[4] r[5] r[6] r[7] r[8] r[9] ↓ 19 ↓ 7 17 ↓ ↓ 5 15 38 ↓ ↓ ↓ 2 12 22 30 第二趟收集：

2→5→7→12→15→17→19→22→30→38 7．答：在冒泡排序过程中，对相邻的两个关键字R[i]和R[i+1]进行比较，只有当R[i]>R[i+1]时，才把R[i]和R[i+1]交换，即R[i]原值向后移动一个位置，而R[i+1]的原值向前移动一个位置。若R[k]与R[m]相等且m>k，那么，要把R[k]移到R[m]右边去，首先要通过移动R[k]（或R[m]）使R[k]与R[m]相邻dmj比较R[k]gn R[m]值时，由于它们相等，故不会进行位置交换。这就是说R[k]的原值不可能移动到R[m]原值的右边。也就是说，冒泡排序是稳定的。

快速排序是不稳定的。例如10 10 2进行快速排序后得到的序列是2 10 10 ，10与10的相对位置发生了变化，所以快速排序是不稳定的。

直接插入排序的方法是顺序地取下一个待排序的关键字k，从后向前与已排好序的关键字序列中的关键字逐一比较，当k值大于或等于某个关键字key时，则停止比较，且把k插到key之后。若待排序的关键字ki与kj的相等且ki在kj之前，则一定是先把ki插入到已排好序的子序列中。当插入kj时，从后向前逐个比较，比较到ki时有ki=kj，于是停止比较，并且把kj插到ki之后，这就保持了ki与kj的相对次序与排序之前是一致的。所以直接插入排序是稳定的。

堆排序是不稳定的。例如，对关键字序列2 10 10经过堆排序后，得到的序列是2 10 10，显然，10与10的相对次序与排序之前不一致。

希尔排序是不稳定的。例如，对关键字序列4 4 2 8进行希尔排序时，第一次把这些关键字分成两组，各组排序后，再合成一组，继续排序，最后得到的序列为2 4 4 8，显然，4和4的相对次序在排序后发生了变化，所以，希尔排序是不稳定的。

选择排序是不稳定的。例如，43 89 21 43 28 15经过选择排序后结果为15 21 28 43 43 89，显然，43和43的相对次序发生了变化，所以选择排序是不稳定的。

折半插入排序是稳定的。在算法中，WHILE的循环结束条件是low=r[m].key时，是移动low，low=m+1,使得low>high而循环结束;而当x.key

是移动high，即high=m-1，使得low>high而循环结束。由于x.key=r[m].key时需作low=m+1操作，这样就不会将具有相同关键字的记录插入到其记录的前面。所以折半插入排序是稳定的。

归并排序是稳定的。例如，对43 89 21 43 28 15经过归并排序后结果为15 21 28 43 43 89，43 43的相对位置没有发生变化，所以说基数排序是稳定的。

基数排序是稳定的。例如，对43 89 21 43 28 15经过基数排序后 …… 此处隐藏：4445字，全部文档内容请下载后查看。喜欢就下载吧 ……