数据结构课后作业答案

1、1. 152463画出下图所示的无向图的邻接表。列出深度优先和广度优先搜索遍历该图所的顶点序列和边的序列。邻接表：深度优先搜索：顶点序列：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出发进行遍历所得的深度优先生成树和广度优先生成树。123456789101000000101020010001000300010001004000010001050000

2、01000161100000000700100000018100100001090000101001101000010000解：邻接矩阵所表示的图如下：自顶点1出发进行遍历所得的深度优先生成树：自顶点1出发进行遍历所得的广度优先生成树：3 请对下图的无向带权图（1）写出它的邻接矩阵，并按普里母算法求其最小生成树。（2）写出它的邻接表，并按克鲁斯卡尔算法求其最小生成树。925cbhfgae3457d5635465解：（1）邻接矩阵：4345593555557654973632526546普里母算法求得的最小生成树：（2）邻接表：克鲁斯卡尔算法生成最小生成树过程：4 试列出下图中全部可能的拓扑有序

3、序列。463512解：全部的拓扑有序序列如下：（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 -45 试利用Dijkstra算法求图中从顶点a到其他各顶点间的最短路径，写出执行算法过程中各步的状态。终点从a到各终点的D值和最短路径的求解过程i=1i=2i=3i=4i=5b1515151515(a,b)(a,b)(a,b)(a,b)(a,b)c2(a,c)d12121111(a

4、,d)(a,d)(a,c,f,d)(a,c,f,d)e1010(a,c,e)(a,c,e)f6(a,c,f)g161614(a,c,f,g)(a,c,f,g)(a,d,g)VjcfedgSa,ca,c,fa,c,f,ea,c,f,e,da,c,f,e,d,bS是已求得最短路径的终点的集合，则下一条最短路径（设其为终点为x）或者是弧（v,x）,或者是中间只经过S中的顶点而最后达到x的路径。第十章 排序练习题1、以关键字序列（503,087,512,061,908,170,897,275,653,426）为例，手工执行以下排序算法，写出每一趟排序结束时的关键字状态：（1）直接插入排序；（2）希尔排序（增量d1=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.rk+1作为监视哨改写直接插入排序算法。其中，L.r1k为待排序记录且kMAXSIZE。