1. 画出下图所示的无向图的邻接表。

列出深度优先和广度优先搜索
遍历该图所的顶点序列和边的序列。

邻接表：
深度优先搜索：顶点序列：1 -2 -3- 4- 5 -6
边的序列：（1，2） （2，3） （3，4） （4，5） （5，6）
广度优先搜索：顶点序列：1 -2 -3 -6 -5-4
边的序列：（1，2） （1，3） （1，6） （1，5） （5，4）
2 已知以二维数组表示的图的邻接矩阵如下图所示。

试分别画出自顶点1出发进
行遍历所得的深度优先生成树和广度优先生成树。

1 2 3 4 5 6 7 8 9 10
1 0 0 0 0 0 0 1 0 1 0
2 0 0 1 0 0 0 1 0 0 0
3 0 0 0 1 0 0 0 1 0 0
4 0 0 0 0 1 0 0 0 1 0
5 0 0 0 0 0 1 0 0 0 1
6 1 1 0 0 0 0 0 0 0 0 7
0 0 1 0 0 0 0 0 0 1
1
5
2
4
6 3
8 1 0 0 1 0 0 0 0 1 0
9 0 0 0 0 1 0 1 0 0 1
10 1 0 0 0 0 1 0 0 0 0 解：邻接矩阵所表示的图如下：
自顶点1出发进行遍历所得的深度优先生成树：
自顶点1出发进行遍历所得的广度优先生成树：
3
请对下图的无向带权图
（1）写出它的邻接矩阵，并按普里母算法求其最小生成树。

（2）写出它的邻接表，并按克鲁斯卡尔算法求其最小生成树。

解：（1） 邻接矩阵：
∞ 4 3 ∞ ∞ ∞ ∞ ∞ 4 ∞ 5 5 9 ∞ ∞ ∞ 3 5 ∞ 5 ∞ ∞ ∞ 5 ∞ 5 5 ∞ 7 6 5 4 ∞ 9 ∞ 7 ∞ 3 ∞ ∞ ∞ ∞ ∞ 6 3 ∞ 2 ∞ ∞ ∞ ∞ 5 ∞ 2 ∞ 6 ∞
∞
5
4 ∞ ∞ 6 ∞
普里母算法求得的最小生成树：
7
5
9
6
4
5
6
3
5 5
3
4 e
d
2
5
c
b
h
f
g
a
（2）邻接表：
克鲁斯卡尔算法生成最小生成树过程：
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 到其他各顶点间的最短路径，
写出执行算法过程中各步的状态。

4
6
3
5
1
2
终点 从a 到各终点的D 值和最短路径的求解过程 i=1 i=2 i=3 i=4 i=5 b 15 15 15 15 15 (a,b) (a,b) (a,b) (a,b) (a,b) c 2 (a,c) d 12 12 11 11 (a,d) (a,d) (a,c,f,d) (a,c,f,d)
e ∞ 10 10 (a,c,e) (a,c,e)
f ∞ 6 (a,c,f)
g ∞ ∞ 16 16 14 (a,c,f,g) (a,c,f,g) (a,d,g) Vj c
f
e
d
g
S
{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<MAXSIZE 。

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

5、序列的“中值记录”指的是：如果将此序列排序后，它是第⎥⎥
⎤
⎢⎢⎡2n 个记录。

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