已知无向连通图 G 中各边的权值均为 1,下列算法中一定能够求出图 G 中从某顶点到其余各个顶点最短路径的是【 】
Ⅰ.普利姆算法;Ⅱ.克鲁斯卡尔算法;Ⅲ.图的广度优先搜索
A、仅Ⅰ
B、仅Ⅲ
C、仅Ⅰ、Ⅱ
D、Ⅰ、Ⅱ和Ⅲ
已知无向连通图 G 中各边的权值均为 1,下列算法中一定能够求出图 G 中从某顶点到其余各个顶点最短路径的是【 】
Ⅰ.普利姆算法;Ⅱ.克鲁斯卡尔算法;Ⅲ.图的广度优先搜索
A、仅Ⅰ
B、仅Ⅲ
C、仅Ⅰ、Ⅱ
D、Ⅰ、Ⅱ和Ⅲ
B
【解析】
无向连通图 G 中各边的权值均为 1 ,G 可以视为无权图,可以用广度优先搜索求单源最短路径,在求无权图的单源最短路径问题中,广度优先搜索比Dijkstra算法更加高效。
普利姆算法和克鲁斯卡尔算法是图的最小生成树算法。
已知一棵二叉树的树形如图,若其后序遍历为 f、d、b、e、c、a,则其先序列为【 】
在有 6 个字符组成的字符集 S 中,各个字符出现的频次分别为 3、4、5、6、8、10,为 S 构造的哈夫曼树的加权平均长度为【 】
若采用三元组表存储结构存储系数矩阵 M.则除三元组外,下列数据中还需要保存的是【 】Ⅰ. M 的行数;Ⅱ. M 中包含非零元素的行数;Ⅲ. M 的列数;Ⅳ. M 中包含非零元素的列数.
下列对顺序存储的有序表 (长度为 n)实现给定操作的算法中平均时间复杂度为 O(1)的是【 】
对于下面的有向图,采用邻接链表存储时,顶点 0的表结点个数为2,顶点3的表结点个数为0,顶点1的表结点个数为【 】。
对于一个具有n个结点的连通无向图,如果它有且只有一个简单回路,那么此图有__________条边。
n个顶点的连通图用邻接矩阵表示时,该矩阵至少有__________个非零元素。
如果G是一个具有n个顶点的连通无向图,那么G最多有__________条边,最少有__________条边。
已知某带权图G的邻接表如下所示,其中表结点的结构为:以下关于该图的叙述中,正确的是【 】。
对于下图,从顶点1进行深度优先遍历时,不可能得到的遍历序列是【 】
对于下图,若采用邻接矩阵存储,则矩阵中的非0元素数目为【 】。
某图G的邻接表如下所示。以下关于图G的叙述中,正确的是【 】。