![](https://static.youtibao.com/asksite/comm/h5/images/m_q_title.png)
下列关于连通图的BFS和DFS生成树高度论述正确的是()。
A、BFS生成树的高度
B、BFS生成树的高度≤DFS生成树的高度
C、BFS生成树的高度≥DFS生成树的高度
D、BFS生成树的高度≥DFS生成树的高度
![](https://static.youtibao.com/asksite/comm/h5/images/solist_ts.png)
A、BFS生成树的高度
B、BFS生成树的高度≤DFS生成树的高度
C、BFS生成树的高度≥DFS生成树的高度
D、BFS生成树的高度≥DFS生成树的高度
A、生成树是遍历的产物
B、从同一顶点出发所得的生成树相同
C、生成树中不包括环
D、不同遮历方法所得的生成树不同
下列不属于生成树协议目前常见版本的是______。
A.STP生成树协议(IEEE 802.1D)
B.RSTP快速生成树协议(IEEE 802.1W)
C.MSTP多生成树协议(IEEE 802.1S)
D.VSTP超生成树协议(IEEE 802.1K)
具有n个顶点的连通图,其最小生成树具有________条边。
A.n/2
B.n-1
C.n
D.n+1
以下叙述中正解的是()。
A.只要无向连通图中没有权值相同的边,则其最小生成树唯一
B.只要无向图中有权值相同的边,则其最小生成树一定不唯一
C.从n个顶点的连通图中选取n-1条权值最小的边,即可构成最小生成树
D.设连通图G含有n个顶点,则含有n个顶点n-1条边的子图一定是G的生成树
以下说法中正确的是(49)。
A.带权连通图的某最小生成树的权值之和一定小于其他生成树的权值之和
B.从源点到终点的最短路径是惟一的
C.任意一个AOV网不一定存在拓扑序列
D.任意一个AOE网中的关键路径是惟一的
●对于n个顶点e条边的无向连通图,利用Prim算法生成最小生成树的时间复杂度为 (24) ,利用Kruskal算法生成最小生成树的时间复杂度为 (25) 。
(24) A.O((n+1)2 )
B.O(n2 )
C.O(n2-1)
D.(n2+1)
(25) A.O(log2e)
B.O(log2e-1)
C.O(elog2e)
D.以上都不对
任何一个无向连通图的最小生成树()。
A.只有一棵
B.一棵或多棵
C.一定有多棵
D.可能不存在