发布时间 : 星期三 文章数据结构课程 课后习题答案更新完毕开始阅读
练习题及参考答案 （4）有8个顶点的无向连通图最少有（ ）条边。 A.5 B.6 C.7 答：C
（5）有8个顶点的有向完全图有（ ）条边。
D.8
A.14 B.28 C.56 D.112 答：C
（6）n个顶点的强连通图中至少有（ ）条边。 A. n B. n-1 C. 2n D. n(n-1) 答：A
（7）若一个图的邻接矩阵是对称矩阵，则该图一定是（ ）。 A.有向图 B.无向图 C.连通图 D.无向图或有向图 答：D
（8）设无向图G=(V, E)和G'=(V', E' )，如果G'是G的生成树，则下面的说法中错误的是（ ）。
A.G'为G的子图 B.G'为G的连通分量 C.G'为G的极小连通子图且V=V' D.G'是G的一个无环子图 答：B
（9）用邻接表表示图进行广度优先遍历时，通常是采用（ ）来实现算法的。 A.栈 B.队列 C.树 D.图 答：B
（10）用邻接表表示图进行深度优先遍历时，通常是采用（ ）来实现算法的。 A.栈 B.队列 C.树 D.图 答：A
（11）图的广度优先遍历算法中用到辅助队列，每个顶点最多进队（ ）次。 A. 1 B. 2 C. 3 D. 不确定 答：A
（12）一个无向图中包含k个连通分量，若按深度优先搜索方法访问所有结点，则必须调用（ ）次深度优先遍历算法。
A. k B. 1 C. k-1 D. k+1 答：A
（13）已知一个图的邻接表如图7.1所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是（ ）。
0 1 2 3 v0 v1 v2 v3 1 0 0 0 2 2 1 2 ∧ ∧ 3 ∧ 3 ∧ 图7.1 一个邻接表
41
数据结构简明教程
A.0 1 3 2 B.0 2 3 1 C.0 3 2 1 D.0 1 2 3 答：D
（14）已知一个图的邻接表如图7.1所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是（ ）。
A.0 1 3 2 B.0 2 3 1 C.0 3 2 1 D.0 1 2 3 答：D
（15）深度优先遍历类似于二叉树的（ ）。 A.先序遍历 B.中序遍历 C.后序遍历 D.层次遍历 答：A
（16）广度优先遍历类似于二叉树的（ ）。 A.先序遍历 B.中序遍历 C.后序遍历 D.层次遍历 答：D
（17）最小生成树指的是（ ）。
A.由连通网所得到的边数最少的生成树
B.由连通网所得到的顶点数相对较少的生成树 C.连通网中所有生成树中权值之和为最小的生成树 D.连通网的极小连通子图 答：C
（18）任何一个无向连通图的最小生成树（ ）。 A.只有一棵 B.一棵或多棵 C.一定有多棵 D.可能不存在 答：B
（19）用Prim和Kruskal两种算法构造图的最小生成树，所得到的最小生成树（ ）。 A.是相同的 B.是不同的 C.可能相同，也可能不同 D.以上都不对 答：C
（20）对于有n个顶点e条边的有向图，求最短路径的Dijkstra算法的时间复杂度为（ ）。
A.O(n) B.O(n+e) C.O(n2) D.O(ne)
答：C （21）对于有n个顶点e条边的有向图，求最短路径的Floyd算法的时间复杂度为（ ）。 A.O(n) B.O(ne) C.O(n2) D.O(n3) 答：D
（22）若一个有向图中的顶点不能排成一个拓扑序列，则可断定该有向图 。 A.是个有根有向图 B.是个强连通图 C.含有多个入度为0的顶点 D.含有顶点数目大于1的强连通分量 答：D
（23）关键路径是事件结点网络中（ ）。 A. 从源点到汇点的最长路径 B. 从源点到汇点的最短路径 C. 最长的回路 D. 最短的回路
练习题及参考答案 答：A 2. 填空题
（1）n个顶点的连通图至少（ ）条边。 答：n-1
（2）在图的邻接矩阵和邻接表表示中，（ ① ）表示一定是唯一的，而（ ② ）表示可能不唯一。
答：①邻接矩阵 ②邻接表
（3）具有10个顶点的无向图中，边数最多为（ ）。 答：45
（4）在有n个顶点的有向图中，每个顶点的度最大可达（ ）。 答：2(n-1)。
（5）n个顶点e条边的图，若采用邻接矩阵存储，则空间复杂度为（ ）。 答：O(n2)
（6）n个顶点e条边的有向图，若采用邻接表存储，则空间复杂度为（ ）。 答：O(n+e)
（7）n个顶点e条边的有向图采用邻接矩阵存储，深度优先遍历算法的时间复杂度为（ ① ）；若采用邻接表存储时，该算法的时间复杂度为（ ② ）。
答：①O(n2) ②O(n+e)
（8）n个顶点e条边的有向图采用邻接矩阵存储，广度优先遍历算法的时间复杂度为（ ① ）；若采用邻接表存储时，该算法的时间复杂度为（ ② ）。
答：①O(n2) ②O(n+e)
（9）一个连通图的生成树是该图的一个（ ）。 答：极小连通子图
（10）用普里姆（Prim）算法求具有n个顶点e条边的图的最小生成树的时间复杂度为（ ① ）；用克鲁斯卡尔（Kruskal）算法的时间复杂度是（ ② ）。若要求一个稀疏图G的最小生成树，最好用（ ③ ）算法来求解；若要求一个稠密图G的最小生成树，最好用（ ④ ）算法来求解。
答：①O(n2) ②O(elog2e) ③Kruskal ④Prim
3. 简答题
（1）从占用的存储空间来看，对于稠密图和稀疏图，采用邻接矩阵和邻接表哪个更好些？
答：设图的顶点个数和边数分别为n和e。邻接矩阵的存储空间大小为O(n2)，与e无关，因此适合于稠密图的存储。邻接表的存储空间大小为O(n+e)（有向图）或O(n+2e)（无向图），与e有关，因此适合于稀疏图的存储。
（2）对于图7.2所示的带权有向图，求从顶点0到其他各顶点的最短路径。
43
数据结构简明教程
7 0 11 4 6 6 7 3 10 15 10 3 5 9 1 8 2 图7.2 一个有向带权图
答：求解过程如下：
S
0 0 0 0 0 0 0 0
1 ∞ 22 22 22 22 22 22
dist 2 ∞ ∞ ∞ ∞ 25 25 25
3 ∞ 13 13 13 13 13 13
4 11 11 11 11 11 11 11
5 ∞ ∞ ∞ 16 16 16 16
6 7 7 7 7 7 7 7
0 0 0 0 0 0 0 0
1 -1 6 6 6 6 6 6
path 2 -1 -1 -1 -1 5 5 5
3 -1 6 6 6 6 6 6
4 0 0 0 0 0 0 0
5 -1 -1 -1 3 3 3 3
6 0 0 0 0 0 0 0
{0} {0,6} {0,6,4} {0,6,4,3}
{0,6,4,3,5} {0,6,4,3,5,1} {0,6,4,3,5,1,2}
求解结果如下：
从0到1的最短路径长度为:22 路径为:0,6,1 从0到2的最短路径长度为:25 路径为:0,6,3,5,2 从0到3的最短路径长度为:13 路径为:0,6,3 从0到4的最短路径长度为:11 路径为:0,4 从0到5的最短路径长度为:16 路径为:0,6,3,5 从0到6的最短路径长度为:7 路径为:0,6
（3）某带权有向图及其邻接表表示如图7.3所示，给出深度优先遍历序列，将该图作为AOE网，给出C的最早开始时间及活动FC的最迟开始时间。
始点 3 B 1 3 A 2 C 2 E 1 1 F 5 G 终点 3 D 3 A B C D E F G ∧ B 1 C 3 E 2 ∧ F 3 ∧ G 1 ∧ C 1 G 5 ∧ C 2 E 1 ∧ D 3 ∧ 图7.3 有向图及其单邻接表
答：深度优先遍历序列为：A,B,C,E,G,D,F。 求最早开始时间和最迟开始时间的过程如下： ve(A)=0，ve(D)=3，ve(F)=ve(D)+3=6，ve(B)=1， ve(C)=MAX{ve(B)=3,ve(A)+2,ve(F)+3}=7，