知到答案数据结构（宁夏大学）智慧树答案_2022年

第七章

具有n个顶点的无向完全图的边数为（）。
 n(n-1)
n²
n(n-1)/2
答案:n(n-1)/2
对含有n个顶点e条边的有向图，Floyd算法的时间复杂度为（ ）
O(n)
O(ne)
O(n³)如果从无向图的任一顶点出发进行一次深度优先搜索可访问所有顶点，则该图一定是（）。带权有向图G用邻接矩阵A存储，则顶点i的入度等于A中（ ）。以下对AOV网的描述中，错误的是（ ）。设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有（）条有向边。设某无向图中有n个顶点e条边，则建立该图邻接表的时间复杂度为（）。
O(n²)
O(n+e)
O(n³)用邻接表存储图所用的空间大小（）。深度优先遍历类似于二叉树的（）。用Prim和Kruskal两种算法构造同一连通图的最小生成树，所得的最小生成树（）。任一AOV网中至少有一条关键路径，且是从源点到汇点的路径中最长的一条。（ ）若图G的最小生成树不唯一，则G的边数一定多于n-1，并且权值最小的边有多条（其中n为G的顶点数）。邻接表比邻接矩阵更节省空间。任意一个AOV网都可以有拓扑排序。图的广度优先遍历算法中用到的辅助队列，每个顶点最多进队的次数不确定。