北邮数据结构第六章答案详解 图(1)

1、第六章第六章 图图 1、填空题、填空题 (1) n 个顶点的无向图，最多能有(_)条边。 解析：完全图是边数最多的图，参考完全图的定义即可。 答案：n*(n-1)/2 (2) 有 n 个顶点的连通无向图 G 至少有(_)条边。 解析：生成树是连通图中边数最少的图，参考生成树的定义即可。 答案：n-1 (3) 有 n 个顶点的强连通有向图 G 至少有(_)条弧。 答案：n (4) G 为无向图，如果从 G 的某个顶点出发，进行一次广度优先遍历，即可访问图的每 个顶点，则该图一定是(_)图。 解析：若一次遍历能访问所有的结点，说明各个结点之间都可达。 答案：连通 (5) 若采用邻接矩阵结构存储具有

2、 n 个顶点的图，则对该图进行广度优先遍历的算法时 间复杂度为_。 解析： 广度优先遍历需要遍历 n 个结点， 对于每一个结点需要遍历邻接矩阵的一行以找 出该结点的所有连接点，即循环 n 次，因此，总的时间复杂度是 O(n2)。 答案：O(n2) (6) n 个顶点的连通图的生成树有(_)条边。 答案：n-1 (7) 图的深度优先遍历类似于树的(_)遍历； 图的广度优先遍历类似于树的(_) 遍历。 答案：前序 层序 (8) 对于含有 n 个顶点 e 条边的连通图，得用 Prim 算法求最小生成树的时间复杂度为 (_)。 答案：O(n2) (9) 已知无向图 G 的顶点数为 n，边数为 e，其邻

3、接表表示的空间复杂度为(_)。 答案：O(n+e) (10) 一棵具有 n 个顶点的生成树有且仅有(_)条边。 答案：n-1 2、 单选题单选题 (1) 在一个无向图中，所有顶点的度数之和等于所有边数的( )倍 A.1/2 B.1 C.2 D.4 解析：顶点的度指的是与该顶点相连的边数，每一条边和两个顶点相连，因此该条边被 相邻的两个顶点各计算 1 次，因此图的总度数是边数的两倍。 答案：C (2) 在一个具有 n 个顶点的有向图中，若所有顶点的出度数之和为 S，则所有顶点的度 数之和为( )。 A.S B.S-1 C.S+1 D.2S 答案：A (3) 具有 n 个顶点的有向图最多有( )条

4、边。 A.n B.n(n1) C.n(n+1) D.n2 答案：B (4) 含 n 个顶点的连通图中任意一条简单路径，其长度不可能超过( ) A.1 B. n/2 C.n-1 D.n 解析：若超过 n-1，则路径中必存在重复的顶点 答案：C (5) 若一个图中包含有 k 个连通分量，若按照深度优先搜索的方法访问所有顶点，则必 须调用( )次深度优先搜索遍历的算法。 A.k B.1 C.k-1 D.k+1 解析： 一次深度优先搜索可以访问一个连通分量中的所有结点， 因此 k 个连通分量需要 调用 k 次深度优先遍历算法。 答案：A (6) 若一个图的边集为,则从顶点 1 开始对该图进 行深度优先

5、遍历，得到的顶点序列可能为( )。 A.1,2,5,4,3 B.1,2,3,4,5 C.1,2,5,3,4 D.1,4,3,2,5。 解析：根据图的边集信息可得如图 6-5 所示的有向图，因此从 1 点开始遍历的顺序可以 为 1、2、5、4、3。 图 6-5 构造有向图 答案：A (7) 若一个图的边集为(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)，则从顶点 A 开始对该图进 行广度优先遍历，得到的顶点序列可能是( )。 A. A,B,C,D,E,F B. A,B,C,F,D,E C. A,B,D,C,E,F D. A,B,C, D,F, E 解析： 根据图的边集信息

6、可得如图 6-6 所示的无向图， 从 A 点开始广度遍历则为 A、 B、 C、D、E、F。 图 6-6 构造无向图 答案：A (8) 存储无向图的邻接矩阵是( )，存储有向图的邻接矩阵是( )。 A.对称的 B.非对称的 答案：A B (9) 采用邻接表存储的图的广度优先遍历算法类似于二叉树的( )。 A.先序遍历 B.中序遍历 C.后序遍历 D.按层遍历。 答案：D (10) 设有一个无向图 G=(V,E)和 G=(V,E)如果 G为 G 的生成树，则下面不正确的说法 是( ) A.G为 G 的子图 B.G为 G 的连通分量 C.G为 G 的极小连通子图且 V=V D.G为 G 的一个无环子

7、图 解析： 连通分量的定义是极大连通子图， 即该子图包含所有的顶点和与这些顶点相连的 所有的边。生成树的定义是极小连通子图，是子图的一种，并且本书所有的图均是无环图， A D B C E F 2 1 3 5 4 因此 A、C、D 是正确的。 答案：B 3、画出图 6-7 所示的无向图 G 的邻接表（顶点按照 ASCII 排列） ，并根据所得邻接表 给出从 A 点开始的深度优先和广度优先搜索遍历该图所的顶点序列。 图 6-7 无向图 G 答案：邻接表如下图所示： A17 B0267 C136 D246 E356 F467 G123457 H0156 0 1 2 3 4 5 6 7 深度优先：AB

8、CDEFGH 广度优先：ABHCGFDE 4、分别使用普里姆算法和克鲁斯卡尔算法构造出如图 6-8 所示图 G 的一棵最小生成树 图 6-8 图 G 答案：根据不同算法构造的最小生成树如图 6-9 所示的图(a)和(b) 6 4 2 6 3 5 5 1 5 6 2 4 1 3 5 6 A G B H C F D E 1 3 65 42 1 3 65 42 (a) Prim 生成树 (b) Kruskal 生成树 图 6-9 最小生成树 5、算法设计 （1）以邻接表为存储结构，设计实现深度优先遍历的非递归算法。 答案： 参考 5.2.1 小节基于邻接矩阵实现深度优先遍历的非递归算法， 修改查找未

9、访问 过的邻接点的方法即可。实现该算法的邻接表的存储结构如下，包括顶点结点、弧结点和邻 接表类结构： struct VertexNode /顶点结点 char Vertex; /数据域：顶点信息 ArcNode *firstarc; /指针域：指向第一条弧 ; struct ArcNode /弧结点 int adjvex; /数据域：邻接顶点下标 ArcNode * next; /指针域：指向下一条弧结点 ; const int MAXSIZE =10; template class ALGraph /邻接表类 private: VertexNode adjlistMAXSIZE; /结点 i

10、nt vNum, arcNum; /顶点数目和弧的数目 ; 程序代码实现： template void AGraph:DFS(int v) int stackMAXSIZE; /定义顺序栈 int top = -1; coutvt; /访问结点 v bVisitedv = true; /设置访问标记 stack+top = v; /结点 v 入栈 adjvex nextarc vertex firstarc 顶点结点 弧结点 while (top!=-1) v=stacktop; ArcNode *p = adjlistv. firstarc; while(p!=NULL) int i = p- adjvex; if(!bVisite