第六章测试1.
任何一个无向连通图的最小生成树
A:一定有多棵
B:可能不存在
C:只有一棵 D:一棵或多棵
答案:D
2.
用邻接表表示图进行广度优先遍历时，通常是采用 来实现算法的。
A:栈
B:图 C:队列 D:树 3.
在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 倍。
A:2 B:1 C:4 D:1/2 4.
已知有向图G = (V, E)，其中V={V1，V2，V3，V4，V5，V6，V7},E={<V1，V2>，<V1，V3>,<V1，V4>,<V2，V5>,<V3，V5>,<V3，V6>,<V4，V6>,<V5，V7>,<V6，V7>}，G的拓扑有序序列是（）。
A:V1，V3，V2，V6，V4，V5，V7 B:V1，V3，V4，V5，V2，V6，V7 C: V1，V3，V4，V6，V2，V5，V7 D:V1，V2，V5，V3，V4，V6，V7 5.
对于含有n个顶点的带权连通图，它的最小生成树是指图中任意一个（）。
A:由n-1条权值之和最小的边构成的子图 B: 由n-1条权值最小的边构成的子图 C:由n个顶点构成的边的权值之和最小的连通子图 D:由n-1条权值之和最小的边构成的连通子图 6.
用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间与图中结点的个数有关，而与图的边数无关。
A:对 B:错 7.
如果有向图的所有顶点可以构成一个拓扑排序，则说明该有向图存在回路。
A:对 B:错 8.
一个非空图可以没有边，但不能没有顶点。
A:对 B:错 9.
有n-1条边的图肯定都是生成树。
A:对 B:错 10.
n个顶点的完全有向图含有边的数目是（）。
A:n * n B:n(n+1) C:n(n-1) D:n/2 11.
在有向图的邻接表存储结构中，顶点v在链表中出现的次数是（）。
A:依附于顶点v的边数 B:顶点v的出度
C:顶点v的度 D:顶点v的入度 12.
对一个无向图进行深度优先搜索时，得到的搜索序列是唯一的。
A:对 B:错 13.
G是一个非连通无向图，有28条边，则G至少有（）个顶点。
A:7 B:9 C:8 D:10 14.
对于一个有n个顶点，e条边的有向图，采用邻接表存储，对其进行广度优先搜索，算法的时间复杂度是（）。
A:O(n+e) B:O(e) C:O(n) D:O(n*e) 15.
下列关于无向连通图的叙述中，正确的是（）。
所有顶点的度数之和是偶数
边数大于顶点数减1
至少有一个顶点的度是1
A:a和b B:只有c C:a和c D:只有a 16.
在TopSort（拓扑排序）函数中，如果外循环还没结束，就已经找不到“未输出的入度为0的顶点”，则说明
A: 图中可能有回路
B: 图中必定存在回路
C: 该图有顶点不连通
D: 算法错误 17.
使用克鲁斯卡尔（Kruskal）算法求图 G 的最小生成树，加入到最小生成树中的边依次是（）
A: (a,e), (b,e), (c,e), (b,d), (b,f)
B: (b,f), (b,d), (b,e), (a,e), (c,e)
C: (a,e), (c,e), (b,e), (b,f), (b,d) D: (b,f), (b,d), (a,e), (c,e), (b,e)
18.
下列选项中，不是如下有向图的拓扑序列的是
A: 5, 1, 2, 3, 6, 4
B:5, 1, 2, 6, 3, 4 C: 5, 2, 1, 6, 3, 4
D: 1, 5, 2, 3, 6, 4
19.
如果无向完全图G中有78条边，则G的生成树有（ ）条边。
A:77 B:14 C:32 D:12 20.
在一个有权无向图中，如果顶点b到顶点a的最短路径长度是10，顶点c与顶点b之间存在一条长度为3的边。那么下列说法中有几句是正确的？
I. c与a的最短路径长度就是13
II. c与a的最短路径长度就是7
III. c与a的最短路径长度不超过13
IV. c与a的最短路径不小于7
A:3句 B:1句 C:2句 D:4句
