鏁版嵁缁撴瀯璇惧悗浣滀笟绛旀�� - 鐧惧害鏂囧簱

克鲁斯卡尔算法生成最小生成树过程：

4 试列出下图中全部可能的拓扑有序序列。

解：全部的拓扑有序序列如下：

1 2 5 6 3 4 （1）1 -5- 2 -3 -6- 4 （2）1 -5 -6 -2- 3- 4 （3）1 -5 -2 -6 -3 -4 （4）5 -6 -1 -2 -3- 4 （5）5 -1 -2 -3 -6 -4 （6）5 -1 -2 -6 -3 -4 （7）5 -1 -6 -2 -3 -4

5

试利用Dijkstra算法求图中从顶点a到其他各顶点间的最短路径，

写出执行算法过程中各步的状态。

终点 b c d e f g Vj S

i=1 15 (a,b) 2 (a,c) 12 (a,d) ∞ ∞ ∞ c 从a到各终点的D值和最短路径的求解过程 i=2 i=3 i=4 i=5 15 (a,b) 12 (a,d) 10 (a,c,e) 6 (a,c,f) ∞ f 15 (a,b) 11 (a,c,f,d) 10 (a,c,e) 16 (a,c,f,g) e 15 (a,b) 11 (a,c,f,d) 16 (a,c,f,g) d 15 (a,b) 14 (a,d,g) g {a,c} {a,c,f} {a,c,f,e} {a,c,f,e,d} {a,c,f,e,d,b} S是已求得最短路径的终点的集合，则下一条最短路径（设其为终点为x）或者是弧（v,x）,或者是中间只经过S中的顶点而最后达到x的路径。 第十章 排序练习题

1、以关键字序列（503,087,512,061,908,170,897,275,653,426）为例，手工执行以下排序算法，写出每一趟排序结束时的关键字状态： （1）直接插入排序；（2）希尔排序（增量d[1]=5） （3）快速排序； （4）堆排序； （5）归并排序； （6）基数排序。

2、判别以下序列是否为堆（小顶堆或大顶堆）。如果不是，则把它调整为堆（要求记录交换次数最小）。 （1）（100,86,48,73,35,39,42,57,66,21） （2）(12,70,33,65,24,56,48,92,86,33)。

3、试以L.r[k+1]作为监视哨改写直接插入排序算法。其中，L.r[1…k]为待排序记录且k

4、编写一个双向起泡的排序算法，即相邻两遍向相反方向起泡。

?n?5、序列的“中值记录”指的是：如果将此序列排序后，它是第??个记录。试

?2?写一个求中值记录的算法。