清华大学课程讲义-数据结构答案第9章.doc

清华大学课程讲义-数据结构答案第9章.doc

《清华大学课程讲义-数据结构答案第9章.doc》由会员分享，可在线阅读，更多相关《清华大学课程讲义-数据结构答案第9章.doc（7页珍藏版）》请在冰点文库上搜索。

清华大学课程讲义-数据结构答案第9章

9-1什么是内排序?

什么是外排序?

什么排序方法是稳定的?

什么排序方法是不稳定的?

【解答】

9-2设待排序的关键码序列为{12,2,16,30,28,10,16*,20,6,18},试分别写出使用以下排序方法每趟排序后的结果。

并说明做了多少次关键码比较。

（1）直接插入排序

（2）希尔排序（增量为5,2,1） （3）起泡排序

（4）快速排序 （5）直接选择排序 （6）锦标赛排序

（7）堆排序 （8）二路归并排序 （9）基数排序

【解答】

9-3在起泡排序过程中，什么情况下关键码会朝向与排序相反的方向移动，试举例说明。

在快速排序过程中有这种现象吗？

【解答】

如果在待排序序列的后面的若干关键码比前面的关键码小，则在起泡排序的过程中，关键码可能向与最终它应移向的位置相反的方向移动。

例如，

574038111334487561997如9向相反方向移动

657403811133448757199如19向相反方向移动

675740381113344875919 如9向最终方向移动

679 574038111334487519 如13向相反方向移动

679115740381319344875如13向最终方向移动

679111357403819344875如34向相反方向移动

679111319574038344875

679111319345740384875

67911131934

9-4试修改起泡排序算法，在正反两个方向交替进行扫描，即第一趟把关键码最大的对象放到序列的最后，第二趟把关键码最小的对象放到序列的最前面。

如此反复进行。

【解答】

templatevoiddataList:

:

shake_Sort（）{

//奇数趟对表Vector从前向后,比较相邻的关键码,遇到逆序即交换,直到把参加比较关键码序列

//中最大的关键码移到序列尾部。

偶数趟从后向前,比较相邻的关键码,遇到逆序即交换,直到把

//参加比较关键码序列中最小的关键码移到序列前端。

inti=1,j;intexchange;

while（i

exchange=0; //假定元素未交换

for（j=CurrentSize-i;j>=i;j--） //逆向起泡

if（Vector[j-1]>Vector[j]）{ //发生逆序

Swap（Vector[j-1],Vector[j]）; //交换,最小关键码放在Vector[i-1]处

exchange=1; //做“发生了交换”标志

}

if（exchange==0）break; ////当exchange为0则停止排序

for（j=i;j<=CurrentSize-i-1;j++） //正向起泡

if（Vector[j]>Vector[j+1]）{ //发生逆序

Swap（Vector[j],Vector[j+1]）; //交换,最大关键码放在Vector[n-i]处

exchange=1; //做“发生了交换”标志

}

if（exchange==0）break; ////当exchange为0则停止排序

i++;

}

}

9-5如果待排序的关键码序列已经按非递减次序有序排列，试证明函数QuickSort（）的计算时间将下降到O（n2）。

9-6在实现快速排序的非递归算法时，可根据基准对象，将待排序关键码序列划分为两个子序列。

若下一趟首先对较短的子序列进行排序，试证明在此做法下，快速排序所需要的栈的深度为O（log2n）。

9-7在实现快速排序算法时，可先检查位于两端及中点的关键码，取三者之中的数值不是最大也不是最小的关键码作为基准对象。

试编写基于这种思想的快速排序算法，并证明对于已排序的关键码序列，该算法的计算时间为O（nlog2n）。

9-8在使用非递归方法实现快速排序时,通常要利用一个栈记忆待排序区间的两个端点。

那么能否用队列来代替这个栈?

为什么?

【解答】

可以用队列来代替栈。

在快速排序的过程中，通过一趟划分，可以把一个待排序区间分为两个子区间，然后分别对这两个子区间施行同样的划分。

栈的作用是在处理一个子区间时，保存另一个子区间的上界和下界，待该区间处理完成后再从栈中取出另一子区间的边界，对其进行处理。

这个功能利用队列也可以实现，只不过是处理子区间的顺序有所变动而已。

9-9试设计一个算法,使得在O（n）的时间内重排数组,将所有取负值的关键码排在所有取正值（非负值）的关键码之前。

【解答】

9-10奇偶交换排序是另一种交换排序。

它的第一趟对序列中的所有奇数项i扫描，第二趟对序列中的所有偶数项i扫描。

若A[i]>A[i+1]，则交换它们。

第三趟有对所有的奇数项，第四趟对所有的偶数项，…，如此反复，直到整个序列全部排好序为止。

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

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

（3）当待排序关键码序列的初始排列是从小到大有序，或从大到小有序时，在奇偶交换排序过程中的关键码比较次数是多少？

【解答】

9-11请编写一个算法，在基于单链表表示的待排序关键码序列上进行简单选择排序。

【解答】

9-12若参加锦标赛排序的关键码有11个，为了完成排序，至少需要多少次关键码比较？

【解答】

9-13试给出适用于锦标赛排序的胜者树的类型声明。

并写一个函数，对n个参加排序的对象，构造胜者树。

设n是2的幂。

【解答】

9-14手工跟踪对以下各序列进行堆排序的过程。

给出形成初始堆及每选出一个关键码后堆的变化。

（1）按字母顺序排序：

Tim,Dot,Eva,Rom,Kim,guy,Ann,Jim,Kay,Ron,Jan

（2）按数值递增顺序排序：

26,33,35,29,19,12,22

（3）同样7个数字，换一个初始排列，再按数值的递增 顺序排序：

12,19,33,26,29,35,22

【解答】

9-15如果只想在一个有n个元素的任意序列中得到其中最小的第k（k<

为什么?

例如有这样一个序列:

{503,017,512,908,170,897,275,653,612,154,509,612*,677,765,094},要得到其第4个元素之前的部分有序序列:

{017,094,154,170},用所选择的算法实现时,要执行多少次比较?

【解答】

一般来讲，当n比较大且要选的数据k<

但当n比较小时，采用锦标赛排序方法更好。

例如，对于序列{57,40,38,11,13,34,48,75,6,19,9,7}，选最小的数据6，需形成初始堆，进行18次数据比较；选次小数据7时，需进行4次数据比较；再选数据9时，需进行6次数据比较；选数据11时，需进行4次数据比较。

但如果选用锦标赛排序，对于有n个数据的序列，选最小数据需进行n-1次数据比较，以后每选一个数据，进行数据比较的次数，均需ëlog2nû次。

例如，同样12个数据，第一次选最小的数据6，需进行11次数据比较，以后选7、9、11时，都是ëlog212û=3次数据比较。

9-16希尔排序、简单选择排序、快速排序和堆排序是不稳定的排序方法,试举例说明。

【解答】

（1）希尔排序 {512 275 275* 061}增量为2

{275* 061 512 275} 增量为1

{061 275*275 512}

（2）直接选择排序 {275 275*512 061}i=1

{061 275*512 275}i=2

{061 275*512 275}i=3

{061 275*275 512}

（3）快速排序 {512 275 275*}

{275* 275 512}

（4）堆排序 {275275*061170}已经是最大堆，交换275与170

{170275*061275}对前3个调整

{275*170061275}前3个最大堆，交换275*与061

{061170275*275}对前2个调整

{170061275*275}前2个最大堆，交换170与061

{061170275*275}

9-17设有n个待排序元素存放在一个不带表头结点的单链表中,每个链表结点只存放一个元素,头指针为r。

试设计一个算法,对其进行二路归并排序,要求不移动结点中的元素,只改各链结点中的指针,排序后r仍指示结果链表的第一个结点。

（提示：

先对待排序的单链表进行一次扫描,将它划分为若干有序的子链表,其表头指针存放在一个指针队列中。

当队列不空时重复执行,从队列中退出两个有序子链表,对它们进行二路归并,结果链表的表头指针存放到队列中。

如果队列中退出一个有序子链表后变成空队列,则算法结束。

这个有序子链表即为所求。

）

【解答】

（1）两路归并算法

proceduremerge（ha,hb:

pointer;varhc:

pointer）;

varpa,pb,pc:

pointer;

begin

ifha↑.data<=hb↑.data

thenbeginhc:

=ha;pa:

=ha↑.next;pb:

=hb;end

elsebeginhc:

=hb;pb:

=hb↑.next;pa:

=ha;end;

pc:

=hc;

while（pa<>nil）and（pb<>nil）do

ifpa↑.data<=pb↑.data

thenbegin

pc↑.next:

=pa;pc:

=pa;pa:

=pa↑.next;

end

elsebegin

pc↑.next:

=pb;pc:

=pb;pb:

=pb↑.next;

end;

ifpa<>nilthenpc↑.next:

=pa

elsepc↑.next:

=pb;

end;

（2）归并排序主程序

proceduremergesort（varr:

pointer）;

vars,t:

pointer;varQ:

Queue;

begin

ifr=nilthenreturn;

SetEmpty（Q）;s:

=r;Enqueue（Q,r）;

whiles<>nildo

begin

t:

=s↑.next;

while（t<>nil）and（s↑.data<=t↑.data）do

begins:

=t;t:

=t↑.next;end;

ift<>nilthen

begins↑.next:

=nil;s:

=t;EnQueue（Q,s）;end;

end;

whilenotIsEmpty（Q）do

begin

r:

=DlQueue（Q）;

ifIsEmpty（Q）thenbreak;

s:

=DlQueue（Q）;

merge（r,s,t）;EnQueue（Q,t）;

end

end;

9-18若设待排序关键码序列有n个关键码，n是一个完全平方数。

将它们划分为块，每块有个关键码。

这些块分属于两个有序表。

下面给出一种O

（1）空间的非递归归并算法：

step1:

在两个待归并的有序表中从右向左总共选出个具有最大值的关键码；

step2:

若设在step1选出的第2个有序表中的关键码有s个，则从第1个有序表选出的关键码有-s个。

将第2个有序表选出的s个关键码与第1个有序表选出的关键码左边的同样数目的关键码对调；

step3:

交换具有最大个关键码的块与最左块（除非最左块就是具有最大个关键码的块）。

对最右块进行排序；

step4:

除去具有最大个关键码的块以外，对其它的块根据其最后的关键码按非递减顺序排序；

step5:

设置3个指针，分别位于第1块、第2块和第3块的起始位置，执行多次substep，直到3个指针都走到第块为止。

此时前块已经排好序。

FsubStep所做的工作是比较第2个指针与第3个指针所指关键码，将值小的与第1个指针所指关键码对调，相应指针前进1个关键码位置。

step6:

对最后第块中最大的个关键码进行排序。

（1）设有16个关键码，分别存放于两个有序表{10,12,14,16,18,20,22,25}和{11,13,15,17,19,21,23,24}中，试根据上面的描述，写出排序的全过程，并说明它具有时间复杂度O（n）和空间复杂度O

（1）。

（2）编写相应的算法。

要求两个待排序有序表的长度可以不同，但每一个表的长度都是的倍数。

（3）假设两个有序表分别为（x1,…,xm）和（xm+1,…,xn），编写一个算法归并这两个有序表，得到（x1,…,xn）。

设s=。

9-19试编写一个算法，将对象序列（x1,x2,…,xn）循环右移p个位置，0£p£n。

要求该算法的时间复杂度为O（n）而空间复杂度为O

（1）。

【解答】

9-20在什么条件下，MSD基数排序比LSD基数排序效率更高？

【解答】

9-21在已排好序的序列中，一个对象所处的位置取决于具有更小关键码的对象的个数。

基于这个思想，可得计数排序方法。

该方法在声明对象时为每个对象增加一个计数域count，用于存放在已排好序的序列中该对象前面的对象数目，最后依count域的值，将序列重新排列，就可完成排序。

试编写一个算法，实现计数排序。

并说明对于一个有n个对象的序列，为确定所有对象的count值，最多需要做n（n-1）/2次关键码比较。

待排序的表

【解答】

35661428

14283566

0

0

0

0

初始状态

2

1

0

0

第1趟排序结果

3

0

0

第2趟排序结果

0

1

第3趟排序结果

存放结果的表

templatevoiddatalist:

:

count_sort（）{

//initList是待排序表，resultList是结果表

inti,j;

int*c=newdatalist; //c是存放计数排序结果的临时表

for（i=0;i

for（i=0;i

for（j=i+1;j

if（Vector[j].key

elseVector[j].count++; //统计

for（i=0;iVector[]中各就各位

c->Vector[Vector[i].count]=Vector[i];

for（i=0;iVector[i]; //结果复制回当前表对象中

deletec;

}

9-22试证明对一个有n个对象的序列进行基于比较的排序，最少需要执行nlog2n次关键码比较。

【解答】

9-23如果某个文件经内排序得到80个初始归并段，试问

（1）若使用多路归并执行3趟完成排序，那么应取的归并路数至少应为多少？

（2）如果操作系统要求一个程序同时可用的输入/输出文件的总数不超过15个，则按多路归并至少需要几趟可以完成排序？

如果限定这个趟数，可取的最低路数是多少？

【解答】

（1）设归并路数为k，初始归并段个数m=80，根据归并趟数计算公式S=élogkmù=élogk80ù=3得：

k3≥80。

由此解得k≥3，即应取的归并路数至少为3。

（2）设多路归并的归并路数为k，需要k个输入缓冲区和1个输出缓冲区。

1个缓冲区对应1个文件，有k+1=15，因此k=14，可做14路归并。

由S=élogkmù=élog1480ù=2。

即至少需2趟归并可完成排序。

若限定这个趟数，由S=élogk80ù=2，有80≤k2，可取的最低路数为9。

即要在2趟内完成排序，进行9路排序即可。

9-24假设文件有4500个记录，在磁盘上每个页块可放75个记录。

计算机中用于排序的内存区可容纳450个记录。

试问：

（1）可以建立多少个初始归并段？

每个初始归并段有多少个记录？

存放于多少个页块中？

（2）应采用几路归并？

请写出归并过程及每趟需要读写磁盘的页块数。

【解答】

（1）文件有4500个记录，计算机中用于排序的内存区可容纳450个记录，可建立的初始归并段有4500∕450=10个。

每个初始归并段中有450个记录，存于450∕75=6个页块中。

（2）内存区可容纳6个页块，可建立6个缓冲区，其中5个缓冲区用于输入，1个缓冲区用于输出，因此，可采用5路归并。

归并过程如下：

450450450450450450450450450450

22502250

4500

共做了2趟归并，每趟需要读60个磁盘页块，写出60个磁盘页块。

9-25设初始归并段为（10,15,31,¥）,（9,20,¥）,（22,34,37,¥）,（6,15,42,¥）,（12,37,¥）,（84,95,¥）,试利用败者树进行k路归并，手工执行选择最小的5个关键码的过程。

【解答】做6路归并排序，选择最小的5个关键码的败者树如下图所示。

输出10（0号段）

0

输出9（1号段）

1

4

输出6（4号段）

5

5

1

1

1

4

4

0

0

5

1

0

0

84

0

10

20

10

3

6

6

9

3

9

10

3

6

4

6

4

3

6

3

5

5

6

5

4

3

22

15递补

15

20递补

15

84

1

22

12

12

22

6

84

12

15递补

输出15（4号段）

输出12（5号段）

4

5

0

0

4

1

0

5

3

6

5

12

6

22

9

5

1

1

4

1

0

1

0

15

20

15

20

6

3

3

6

6

4

3

6

4

3

5

5

15

15

84

84

22

37

12

22

42递补

37递补

9-26设输入文件包含以下记录：

14,22,7,24,15,16,11,100,10,9,20,12,90,17,13,19,26,38,30,25,50,28,110,21,40。

现采用败者树生成初始归并段，请画出选择的过程。

9-27给出12个初始归并段，其长度分别为30,44,8,6,3,20,60,18,9,62,68,85。

现要做4路外归并排序，试画出表示归并过程的最佳归并树，并计算该归并树的带权路径长度WPL。

13

9.69.99.149.19

9.119.17

9.89.129.15

14

9.239.259.27

9.199.21

9.249.26