数据结构课后作业答案

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出发进行遍历所得的深度优先生成树和广度优先生成树。12345678910100000010102001000100030001000100400001000105000001000161100000000700100000011524638100100001090000101001101000010000解：邻接矩阵所表示的图如下：自顶点1出发进行遍历所得的深度优先生成树：自顶点1出发进行遍历所得的广度优先生成树：3请对下图的无向带权图（1）写出它的邻接矩阵，并按普里母算法求其最小生成树。（2）写出它的邻接表，并按克鲁斯卡尔算法求其最小生成树。解：（1）邻接矩阵：∞43∞∞∞∞∞4∞559∞∞∞35∞5∞∞∞5∞55∞7654∞9∞7∞3∞∞∞∞∞63∞2∞∞∞∞5∞2∞6∞∞54∞∞6∞普里母算法求得的最小生成树：759645635534ed25cbhfga（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-45试利用Dijkstra算法求图中从顶点a到其他各顶点间的最短路径，写出执行算法过程中各步的状态。463512终点从a到各终点的D值和最短路径的求解过程i=1i=2i=3i=4i=5b1515151515(a,b)(a,b)(a,b)(a,b)(a,b)c2(a,c)d12121111(a,d)(a,d)(a,c,f,d)(a,c,f,d)e∞1010(a,c,e)(a,c,e)f∞6(a,c,f)g∞∞161614(a,c,f,g)(a,c,f,g)(a,d,g)VjcfedgS{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]为待排序记录且kMAXSIZE。4、编写一个双向起泡的排序算法，即相邻两遍向相反方向起泡。5、序列的“中值记录”指的是：如果将此序列排序后，它是第2n个记录。试写一个求中值记录的算法。