Data Structures Graphs 3

Question 1

What is the time complexity of Dijkstra's algorithm when implemented with a binary min-heap?

Accepted Answer

O((V + E) log V)

Answer

With a binary min-heap, each extract-min operation costs O(log V) and each decrease-key costs O(log V), resulting in O((V + E) log V) overall.

Question 2

Which of the following is NOT a valid graph traversal algorithm?

Accepted Answer

Inorder Traversal

Answer

Inorder traversal is specific to binary trees, not general graphs; BFS, DFS, and best-first search all work on graphs.

Question 3

What is the key difference between Prim's and Kruskal's algorithms for finding a minimum spanning tree?

Accepted Answer

Prim's grows the tree from a starting vertex, Kruskal's adds the globally cheapest edge each time

Answer

Prim's builds the MST incrementally from a single vertex, while Kruskal's sorts all edges and greedily adds the cheapest non-cycle-forming edge.

Question 4

In a graph with V vertices and E edges, what is the maximum number of edges possible in an undirected simple graph?

Accepted Answer

V(V - 1) / 2

Answer

In an undirected simple graph, each pair of distinct vertices can share at most one edge, giving V(V-1)/2 maximum edges.

Question 5

Which algorithm is commonly used to find all strongly connected components in a directed graph?

Accepted Answer

Kosaraju's algorithm

Answer

Kosaraju's algorithm uses two passes of DFS (one on the original graph and one on its transpose) to identify all strongly connected components.

Data Structures Practice Test