《清华大学课程讲义-数据结构答案8》由会员分享，可在线阅读，更多相关《清华大学课程讲义-数据结构答案8（5页珍藏版）》请在金锄头文库上搜索。
1、8-1 画出 1 个顶点、2 个顶点、3 个顶点、4 个顶点和 5 个顶点的无向完全图。试证明在 n 个顶点的无向完全图中，边的条数为 n(n-1)/2。8-2 右边的有向图是强连通的吗？请列出所有的简单路径。8-3 给出右图的邻接矩阵、邻接表和邻接多重表表示。8-4 用邻接矩阵表示图时，若图中有 1000 个顶点，1000 条边，则形成的邻接矩阵有多少矩阵元素？有多少非零元素？是否稀疏矩阵？【解答】一个图中有 1000 个顶点，其邻接矩阵中的矩阵元素有 10002 = 1000000 个。它有 1000 个非零元素（对于有向图）或 2000 个非零元素（对于无向图） ，因此是稀疏矩阵。8-5
2、 用邻接矩阵表示图时，矩阵元素的个数与顶点个数是否相关？与边的条数是否相关？【解答】用邻接矩阵表示图，矩阵元素的个数是顶点个数的平方，与边的条数无关。矩阵中非零元素的个数与边的条数有关。8-6 有 n 个顶点的无向连通图至少有多少条边？有 n 个顶点的有向强连通图至少有多少条边？试举例说明。【解答】n 个顶点的无向连通图至少有 n-1 条边，n 个顶点的有向强连通图至少有 n 条边。例如：8-7 对于有 n 个顶点的无向图，采用邻接矩阵表示，如何判断以下问题： 图中有多少条边？任意两个顶点 i 和 j 之间是否有边相连？任意一个顶点的度是多少？【解答】用邻接矩阵表示无向图时，因为是对称矩阵，对
3、矩阵的上三角部分或下三角部分检测一遍，统计其中的非零元素个数，就是图中的边数。如果邻接矩阵中 Aij 不为零，说明顶点 i 与顶点 j 之间有边相连。此外统计矩阵第 i 行或第 i 列的非零元素个数，就可得到顶点 i 的度数。8-8 对于如右图所示的有向图，试写出：(1) 从顶点出发进行深度优先搜索所得到的深度优先生成树；(2) 从顶点出发进行广度优先搜索所得到的广度优先生成树； 8-9 试扩充深度优先搜索算法，在遍历图的过程中建立生成森林的左子女-右兄弟链表。算法的首部为viod Graph:DFS ( const int v, int visited , TreeNode * t ) 其中
4、，指针t 指向生成森林上具有图顶点 v 信息的根结点。 （提示：在继续按深度方向从根 v 的某一未访问过的邻接顶点 w 向下遍历之前，建立子女结点。但需要判断是作为根的第一个子女还是作为其子女的右兄弟链入生成树。 ）8-10 用邻接表表示图时，顶点个数设为 n，边的条数设为 e，在邻接表上执行有关图的遍历操作时，时间代价是 O(n*e)？还是 O(n+e)？或者是 O(max(n,e)？【解答】在邻接表上执行图的遍历操作时，需要对邻接表中所有的边链表中的结点访问一次，还需要对所有的顶点访问一次，所以时间代价是 O(n+e)。8-15 右图是一个连通图，请画出(1) 以顶点为根的深度优先生成树；
5、(2) 如果有关节点，请找出所有的关节点。(3) 如果想把该连通图变成重连通图，至少在图中加几条边？如何加？【解答】(1) 从顶点出发的深度优先生成树为此答案不唯一(2) 8-16 试证明在一个有 n 个顶点的完全图中，生成树的数目至少有 2n-1-1。8-17 编写一个完整的程序，首先定义堆和并查集的结构类型和相关操作，再定义 Kruskal 求连通网络的最小生成树算法的实现。并以右图为例，写出求解过程中堆、并查集和最小生成树的变化。8-18 利用 Dijkstra 算法的思想，设计一个求最小生成树的算法。8-19 以右图为例，按 Dijkstra 算法计算得到的从顶点到其它各个顶点的最短路
6、径和最短路径长度。8-20 在以下假设下，重写 Dijkstra 算法：(1) 用邻接表表示带权有向图 G，其中每个边结点有 3 个域：邻接顶点 vertex，边上的权值 length 和边链表的链接指针 link。(2)用集合 T = V(G) - S 代替 S(已找到最短路径的顶点集合)，利用链表来表示集合 T。试比较新算法与原来的算法，计算时间是快了还是慢了，给出定量的比较。8-22使用 Floyd 算法计算 8-19 题所用的带权有向图的各对顶点之间的最短路径。8-23 下面是基于元素 0 到 4 的一些优先关系的集合，试问它们是否定义了一个偏序关系？为什么？0 nil dobegin
7、 w := p.adj;Gw.ind := Gw.ind - 1;if ( visitedw = 0 ) and ( Gw.ind = 0 ) then dfs ( G, w );p := p.link;end;end;主程序for i := 1 to n do visitedi := 0;count := 0;read ( i, j, w);while ( i 0 ) dobeginnew(p); p.adj := j; p.cost := w;Gj.ind := Gj.ind + 1;p.link := Gi.fout; Gi.fout := p;read ( i, j, w);end;f
8、or i := 1 to n do if ( visitedi = 0 ) and ( Gi.ind = 0 ) then dfs ( G, i );if count e 0 0 15 19 19 15 29 38l 17 0 15 27 19 27 37 38 l-e 17 0 0 8 0 12 8 0 此工程最早完成时间为 43。关键路径为8-27 若 AOE 网络的每一项活动都是关键活动。令 G 是将该网络的边去掉方向和权后得到的无向图。 (1) 如果图中有一条边处于从开始顶点到完成顶点的每一条路径上，则仅加速该边表示的活动就能减少整个工程的工期。这样的边称为桥(bridge)。证明若从连通图中删去桥，将把图分割成两个连通分量。(2) 编写一个时间复杂度为 O(n+e)的使用邻接表表示的算法，判断连通图 G 中是否有桥，若有。输出这样的桥。8.8 8.11 8.15 8.9 8.2 8.4 8.78.23 8.24 8.17 8.28 8.25 8.26 8.27
