对一个有n个顶点e条边的图采用邻接表表示时,进行DFS遍历的时间复杂度为(),空间复杂度为():
A.O(n)
B.O(e)
C.O(n+e)
D.O(1)
A.O(n)
B.O(e)
C.O(n+e)
D.O(1)
第1题
调用DFS的次数正好等于( )。
A.顶点数
B.边数
C.连通分量数
D.不确定
第2题
如图所示,在下面的5个序列中,符合深度优先遍历的序列有多少个( )。
1、aebfdc2、acfdeb3、aedfcb4、aefdbc5、aecfdb
A.5
B.4
C.3
D.2
第3题
如果从无向图的任一顶点出发进行一次深度优先遍历即可访问所有顶点,则该图一定是( )。
A.完全图
B.连通图
C.有回路
D.一棵树
第4题
开始进行深度优先遍历,得到的顶点序列正确的是( )。
A.a,b,e,c,d,f
B.a,c,f’e,b,d
C.a,e,b,c,f,d
D.a,e,d,f,c,b
第6题
关于图的存储结构,( )是错误的。
A.使用邻接矩阵存储一个图时,在不考虑压缩存储的情况下,所占用的存储空间大小只与图中的顶点数有关,与边数无关
B.邻接表只用于有向图的存储,邻接矩阵适用于有向图和无向图
C.若一个有向图的邻接矩阵,对角线以下元素为0,则该图的拓扑序列必定存在
D.存储无向图的邻接矩阵是对称的,故只需存储邻接矩阵的下(或上)三角部分即可
第7题
对邻接表的叙述中,( )是正确的。
A.无向图的邻接表中,第i个顶点的度为第i个链表中结点数的两倍
B.邻接表比邻接矩阵的操作更简便
C.邻接矩阵比邻接表的操作更简便
D.求有向图结点的度,必须遍历整个邻接表
为了保护您的账号安全,请在“上学吧”公众号进行验证,点击“官网服务”-“账号验证”后输入验证码“”完成验证,验证成功后方可继续查看答案!