数据结构书本习题答案(续).doc

《数据结构书本习题答案(续).doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、7.5对n个顶点的无向图和有向图，采用邻接矩阵和邻接表表示时，如何判别下列有关问题? (1)图中有多少条边? (2)任意两个顶点i和j是否有边相连? (3)任意一个顶点的度是多少?答：对于n个顶点的无向图和有向图，用邻接矩阵表示时： (1)设m为矩阵中非零元素的个数 　　　无向图的边数=m/2　　　有向图的边数=m　(2)无论是有向图还是无向图，在矩阵中第i行,第j列的元素若为非零值，则该两顶点有边相连。　(3)对于无向图，任一顶点i的度为第i行中非零元素的个数。　　对于有向图，任一顶点i的入度为第i列中非零元素的个数，出度为第i行中非零元素的个数，度为入度出度之和。　　当用邻接

2、表表示时：　(1)对于无向图，图中的边数=边表中结点总数的一半。　　　对于有向图，图中的边数=边表中结点总数。　(2)对于无向图，任意两顶点间是否有边相连，可看其中一个顶点的邻接表，若表中的adjvex域有另一顶点位置的结点，则表示有边相连。　　　对于有向图，则表示有出边相连。　(3)对于无向图，任意一个顶点的度则由该顶点的边表中结点的个数来决定。　　对于有向图，任意一个顶点的出度由该顶点的边表中结点的个数来决定，入度则需遍历各顶点的边表。(用逆邻接表可容易地得到其入度。)7.6n个顶点的连通图至少有几条边?强连通图呢?答：n个顶点的连通图至少有n-1条边，强连通图至少有2(n-

3、1)条边。7.7DFS和BFS遍历各采用什么样的数据结构来暂存顶点?当要求连通图的生成树的高度最小，应采用何种遍历?答：DFS遍历采用栈来暂存顶点。BFS采用队列来暂存顶点。当要求连通图的生成树的高度最小时，应采用BFS遍历。7．87.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节中算法CreatALGraph画出相应的邻接表。并写出在该邻接表上，从顶点4开始搜索所得的DFS和BFS序列，及DFS和BFS生成树。 答：相应的邻接表如下：　　┌─┬─┐ ┌─┬

4、─┐ ┌─┬─┐ ┌─┬─┐ ┌─┬─┐ ┌─┬─┐　　1│1│　─→│5│　─→│3│　─→│4│　─→│6│　─→│2│∧│　　├─┼─┤ ├─┼─┤ ├─┼─┤ └─┴─┘ └─┴─┘ └─┴─┘   2│2│　─→│6│　─→│1│∧│    ├─┼─┤ ├─┼─┤ ├─┼─┤ ┌─┬─┐   3│3│　─→│5│　─→│4│　─→│1│∧│    ├─┼─┤ ├─┼─┤ ├─┼─┤ ├─┼─┤ ┌─┬─┐   4│4│　─→│5│　─→│3│　─→│6│　─→│1│∧│    ├─┼─┤ ├─┼─┤ ├─┼─┤ ├─┼─┤ ├─┼─┤   5│5│　─→│3│　─→│1

5、│　─→│4│　─→│6│∧│    ├─┼─┤ ├─┼─┤ ├─┼─┤ ├─┼─┤ ├─┼─┤   6│6│　─→│5│　─→│4│　─→│2│　─→│1│∧│    └─┴─┘ └─┴─┘ └─┴─┘ └─┴─┘ └─┴─┘   根据上面的邻接表画出的图见下图:        从顶点4开始搜索所得的DFS序列是：   从顶点4开始搜索所得的BFS序列是：   相应的生成树见上图。7.10什么样的图其最小生成树是唯一的?用PRIM和Kruskal求最小生成树的时间各为多少?它们分别适合于哪类图?答：当候选轻边集中的轻边数始终等于1条时，其最小生成树是唯一的。用Prim和Krus

6、kal求最小生成树的时间复杂度分别为O(n2)和O(elge),前者适合于稠密图，后者适合于稀疏图.7.11对图7.26（下图）所示的连通图，请分别用Prim和Kruskal算法构造其最小生成树。 　　　答：　　7.13试写出图7.28(下图)所示有向图的所有拓扑序列，并指出就用7.6节给出的NonPreFirstTopSort算法求得的是哪个序列，设邻接表的边表结点中的邻接点序号是递增有序的。    答：上图中所有拓扑序列如下： v0v1v5v2v3v6v4* v0v1v5v2v6v3v4 v0v1v5v6v2v3v4 v1v0v5v6v2v3v4 v1v0v5v2v3v6v4

7、 v1v0v5v2v6v3v4 v1v5v0v2v3v6v4 v1v5v0v2v6v3v4 v1v5v0v6v2v3v4 v5v1v0v2v3v6v4 v5v1v0v2v6v3v4 v5v1v0v6v2v3v4 v5v0v1v2v3v6v4 v5v0v1v2v6v3v4 v5v0v1v6v2v3v4 v0v5v6v1v2v3v4 v1v5v6v0v2v3v4 v5v6v1v0v2v3v4 v5v6v0v1v2v3v4 v5v0v6v1v2v3v4 v5v1v6v0v2v3v4