中国铁道出版社数据结构（第二版）单元10练习参考答案

7． 已知数据序列{10，18，4，3，6，12，9，15}，写出二路归并排序的每一趟排序结果。

[10] [18] [4] [3] [6] [12] [9] [15]

[10 18] [3 4] [6 12] [9 15] 第一趟排序结果

[3 4 10 18] [6 9 12 15] 第二趟排序结果

[3 4 6 9 10 12 15 18] 第三趟排序结果

8． 已知数据序列{53，36，48，36，60，7，18，41}，写出采用简单选择排序的每一趟排序结果。 解： [53 36 48 36 60 7 18 41] （7） [36 48 36 60 53 18 41] （7 18） [48 36 60 53 36 41] （7 18 36） [48 60 53 36 41] （7 18 36 36） [60 53 48 41] （7 18 36 36 41） [53 48 60] （7 18 36 36 41 48） [53 60] （7 18 36 36 41 48 53） [60] （7 18 36 36 41 48 53 60 ）

9． 已知数据序列{10，1，15，18，7，15}，试画出采用快速排序法，第一趟排序的结果。 解

10 1 15 18 7 15 low high 交换

7 1 15 18 [10] 15 low high 交换

第一趟排序结果： 7 1 [10] 18 15 15 low high

10． 已知数据序列{10，1，15，18，7，15}，试写出采用快速排序法，第一趟排序的结果。 解：

7 1 10 18 15 15

五．二分插入排序程序填空

void BInsSort( ) // 按递增序对R[1]~R[ n ]进行二分插入排序 { int i, j, low, high, m; for ( i=2; i<= n ; i++) { R[0]=R[i];

low=1; high= n ；

// 设定R[0]为监视哨

while (low <= high) { m=(low+high)/2 ;

if ( R[0]

low=m+1;

}

for (j=i-1;j>=high+1;j--)

R[j+1]= R[ j ] ; // 元素后移 R[high]=R[0]; // 插入

} }

六． 算法题

1．以单链表为存储结构，写一个直接选择排序算法。 解： void selectsort(pointer h)

{ pointer p,q,r,s,t; t=NULL; while(h)

{ p=h; q=NULL; s=h; r=NULL; while (p)

{ if (p->keykey) { s=p; p=q; }

if (s==h)

h=h->link; else

h=s; s->link=t; t=s; } h=t; } }

2．以单链表作为存储结构实现直接插入排序算法。 解： void InsertList(List head)

{ Lnode *p, * pprev,q,*qprev, *current; if (!head) return; pprev=head; p=head->next;

while (p) { q=head; qprev=NULL;

while (q->key < p->key) // 查找插入位置 {qprev=q; q=q->next;}

if (q= =p) // p最大，无须插入 {pprev=p; p=p->next;} else

{ current=p; p=p->next; pprev->next=p; current->next=q;

if (q==head) // 插在表头 head=current;

else // 插在中间某个位置上 qprev->next=current;

} } }

3．设计一个算法，使得在尽可能少的时间内重排数组，将所有取负值的关键字放在所有取非负值的关键字之前。

解： void part (int a[ ])

{ i=1;j=n; // 初、终下标 while (i

{ while (i=0) // 自右向左找非负数 j--;

while (i

a[i]=a[j]; a[j]=t;

i++;

j--;

} }

}

4．设已排序的文件用单链表表示，再插入一个新记录，仍然按关键字从小到大的次序排序，试写出该算法。

void insert(lklist head;datatype x) {

s=new ( node ); s->key=x;

s->next= NULL; if (head= =NULL) head=s; else

{ p=head; q= NULL;

while (( p! =NULL) && (s->key > p->key ))

{ q=p; p=p->next; } if (q= =NULL)

{ s->next=head; head=s; }

else

{ if (p==NULL) q->next=s;

else

{ s->next=q->next; q->next=s; }

} } }

排序过程分析

1． 已知数据序列{50，60，40，20，80，15，10，45}，试画出采用快速排序法，第一趟排序的结果。

解：[45，10，40，20，15] 50 [80，60]

2． 已知数据序列{82，40，66，13，84，36，96，57，39，80，61，14}，写出二路归并排序的每一趟排序结果。 解：

[82] [40] [66] [13] [84] [36] [96] [57] [39] [80] [61] [14]

[40 82] [13 66] [36 84] [57 96] [39 80] [14 61] 第一趟排序结果 [13 40 66 82] [36 57 84 96] [14 39 61 80] 第二趟排序结果 [13 36 40 57 66 82 84 96] [14 39 61 80] 第三趟排序结果 [13 14 36 39 40 57 61 66 80 82 84 96] 第四趟排序结果

3． 已知数据序列{40，63，11，84，35，93，58，39，15}，写出采用简单选择排序的每一趟排序结果。

解： [40 63 11 84 35 93 58 39 15]

（11） [63 40 84 35 93 58 39 15] （11 15） [40 84 35 93 58 39 63] （11 15 35） [84 40 93 58 39 63] （11 15 35 39） [40 93 58 84 63] （11 15 35 39 40） [93 58 84 63] （11 15 35 39 40 58） [93 84 63]