同步综合练及参考答案.doc

《同步综合练及参考答案.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、同步综合练习及参考答案（一）基础知识题7．1在图7.23所是的各无向图中：（1）找出所有的简单环。（2）那些图是连通图？对非连通图给出其连通分量。（3）那些图是自由树（或森林）？//自由树的概念见7.4节解：（1）简单环（a）(1231)(b)无(c)（1231）（2342）（12431）(d)无（2）连通图（a）（c）（d）非连通图（b）的连通分量为（3）自由树（d）森林（b）7．2在图7.24所是的有向图中：（1）该图是强连通的码？若不是，则给出其强连通分量。（2）请给出所有简单路径及有向环。（3）请给出每个顶点的度、入度和出度。（4）请给

2、出其邻接表、邻接矩阵及逆邻接表。解：（1）图是强连通的。（2）所有简单路径（重复环未计算）（v1）（v2）（v3）（v4）(v1v2)(v2v3)(v3v1)(v1v4)(v4v3)(v1v2v3)(v2v3v1)(v3v1v4)(v3v1v2)(v1v4v3)(v4v3v1)（v1v2v3v1）（v2v3v1v4）（v3v1v4v3）（v4v3v1v2）有向环（v1v2v4v1）（v4v1v4v4）(3)各顶点的度、入度、和出度。(4)①邻接表①邻接矩阵集。②逆邻接表7．3假设图的顶点是A,B,…,请根据下属的邻接矩阵画出相应的无向图或有向图

3、。解：7．4假设一颗完全二叉树包含A,B,…,G第七个结点，写出其邻接表和邻接矩阵。解：①完全二叉树②邻接矩阵③邻接表7．5对n各顶点的无向图和有向图，采用邻接矩阵和邻接表表示，如何判别下列有关问题：（1）图中有多少条边？（1）任意两个顶点I和j是否有边相连？（2）任意一个顶点的度是多少？解：①对于无向图（1）图中边数等于邻接矩阵中1的各数的一半；邻接表中的边表中结点各数的一半。（2）若邻接矩阵中A[i,j]≠0则I和j两个顶点有边相连。（3）顶点I的度为第I行中1的个数；邻接表中I的边表结点个数j.②对于有向图（1）图中边树等于邻接矩阵中的个

4、数；邻接表中的出边表中结点数。（2）若邻接矩阵中A[i,j]>0则I和j两个顶点有边相连；邻结表中I得出边表是否有结点j，决定I和j两个顶点有边相连。（3）顶点I的度为第I行中1的个数加上第I列中1的个数之和；邻接表中i得出边表结点个数加上边表中结点I的个数之和。7．6n个顶点的连通图至少有几条边？强连通图呢？解：①n个顶点的连通图至少有n-1条边。②n个顶点的强连通图至少有n条边。7．7DFS和BFS遍历采用什么样的数据结构来暂存顶点？当要求连通图的生成树的高度最小，应采用何种遍历？解：①DFS采用了栈；BFS采用了队列。②采用BFS。7．8

5、画出以顶点v1为初始源点遍历图7。25所示的有向图所得到的DFS和BFS生成森林。解：7．9按顺序输入顶点对：（1，2），（1，6），（2，6），（1，4），（6，4），（1，3），（3，4），（6，5），（4，5），（1，5），（3，5），根据第7.2.2节中算法CreateALGraph画出相应的邻接表，并写出在该邻接表上，从顶点4开始搜索所得的DFS和BFS序列，及DFS和BFS生成树。解：依题意构造有向图：①邻接表②DFS和BFS序列DFS序列：453162BFS序列：453612③DFS和BFS生成树DFS生成树BFS生成树7.10什

6、么样的图其最小生成树是唯一的？用Prim和Kruskal求最小生成数的时间各为多少？他们分别适合于哪个图？解：①具有n的结点，n-1条边的连通图其生成树是唯一的。①的结点，e条边的无向连通图求最小生成树的时间分别为Prim:O(n2);Kruskal:O(e*log2e)①Prim适应于稠密图（点少边多）；Kruskal适应于稀疏图（点多边少）。7．11对图7.26所示的连通图，请分别用Pirm和Kruskal算法构造其最小生成树。解：①Pirm算法构造的生成树。②Kruskal算法构造的生成树。7．12对图7.27所示的有向网，试利用Dijk

7、stra算法求出从源点1到其它各顶点的最短路径，并写出执行短发过程中扩充红点集的每天次循环状态（类似表7.2）.解：7．13是写出图7.28所示有向图的所有拓扑序列，并指出应用教材中NonPrefirtTopSort算法求得的是哪个序列，设邻接表的边表结点中的邻接点序号是递增的。解：NonPreFirtTopSort算法求得的序列是：V0V1V5V2V6V3V4其余序列有多种（略）。7．14什么样的DAG的拓扑序列是唯一的？解：设DAG中有n个结点，则当DAG中有至少n-1个不同的后继结点且至少有n-1个前缀结点时其拓扑序列是唯一的。7．15以

8、V4为源点，给出用DFS搜索7.28的道德你拓扑序列。V4V3V2V0V1V5V6.（二）算法设计题7．16试在无向图的邻接矩阵和邻接表上实现如下算法