Q. If a graph is represented using an adjacency matrix, what is the time complexity of BFS?
-
A.
O(V + E)
-
B.
O(V^2)
-
C.
O(E)
-
D.
O(V log V)
Solution
For an adjacency matrix representation, BFS has a time complexity of O(V^2) due to the need to check all possible edges.
Correct Answer:
B
— O(V^2)
Learn More →
Q. What is the primary disadvantage of using DFS?
-
A.
It cannot handle cycles
-
B.
It may get stuck in deep paths
-
C.
It is slower than BFS
-
D.
It requires more memory
Solution
DFS may get stuck in deep paths, especially in graphs with long branches.
Correct Answer:
B
— It may get stuck in deep paths
Learn More →
Q. What is the space complexity of BFS in a graph with V vertices?
-
A.
O(V)
-
B.
O(E)
-
C.
O(V + E)
-
D.
O(1)
Solution
BFS requires O(V) space for the queue to store the vertices at the current level.
Correct Answer:
A
— O(V)
Learn More →
Q. What is the worst-case time complexity of DFS for a graph represented as an adjacency list?
-
A.
O(V + E)
-
B.
O(V^2)
-
C.
O(E)
-
D.
O(V log V)
Solution
The worst-case time complexity of DFS is O(V + E) for an adjacency list representation.
Correct Answer:
A
— O(V + E)
Learn More →
Q. Which traversal method is guaranteed to visit all vertices in a connected graph?
-
A.
BFS
-
B.
DFS
-
C.
Both BFS and DFS
-
D.
Neither BFS nor DFS
Solution
Both BFS and DFS will visit all vertices in a connected graph.
Correct Answer:
C
— Both BFS and DFS
Learn More →
Showing 1 to 5 of 5 (1 Pages)
