Data Structures MCQs - Graphs (Set 4)

Q1. What is the space complexity of an adjacency matrix for a graph with V vertices and E edges?

a) O(V)

b) O(E)

c) O(V + E)

d) O(V^2)

Q2. For a sparse graph, which representation usually uses less memory?

a) Adjacency matrix

b) Adjacency list

c) Incidence matrix

d) Both use the same memory

Q3. Depth-First Search (DFS) is naturally implemented using:

a) A queue

b) A stack (or recursion)

c) A min-heap

d) A hash table only

Q4. What is the time complexity of BFS or DFS on a graph stored as an adjacency list?

a) O(V)

b) O(E)

c) O(V + E)

d) O(V * E)

Q5. A topological ordering exists only for which kind of graph?

a) Any undirected graph

b) A directed acyclic graph (DAG)

c) A complete graph

d) A graph with exactly one cycle

Q6. Directed edges are A->B, A->C, B->D and C->D. Which of these is a valid topological order?

a) D, B, C, A

b) A, D, B, C

c) A, C, B, D

d) B, A, C, D

Q7. Dijkstra's algorithm may give wrong answers when the graph has:

a) Cycles

b) Negative edge weights

c) More than 100 vertices

d) Undirected edges

Q8. Which algorithm finds single-source shortest paths even when some edge weights are negative, and can also detect negative cycles?

a) Prim's algorithm

b) Kruskal's algorithm

c) Bellman-Ford algorithm

d) Breadth-First Search

Q9. Floyd-Warshall computes shortest paths between all pairs of vertices in:

a) O(V^2)

b) O(V^3)

c) O(V + E)

d) O(E log V)

Q10. How many edges does a minimum spanning tree of a connected graph with V vertices have?

a) V

b) V - 1

c) V + 1

d) E - V

Q11. Kruskal's algorithm uses which data structure to check efficiently whether adding an edge would create a cycle?

a) Stack

b) Disjoint set (Union-Find)

c) Trie

d) Circular queue

Q12. Prim's algorithm builds a minimum spanning tree by:

a) Sorting all edges and adding the cheapest ones that do not form a cycle

b) Growing one tree from a start vertex, always adding the cheapest edge leaving the tree

c) Removing the heaviest edge from every cycle in any order

d) Running BFS from every vertex

Q13. The sum of the degrees of all vertices in an undirected graph with E edges is:

a) E

b) 2E

c) E / 2

d) E^2

Q14. What is the maximum number of edges in a simple undirected graph with n vertices?

a) n - 1

b) n

c) n(n - 1) / 2

d) n^2

Q15. In a DFS of a directed graph, finding a back edge means the graph:

a) Is disconnected

b) Contains a cycle

c) Is a tree

d) Has negative weights

Q16. A connected undirected graph with V vertices and exactly V - 1 edges is:

a) Always a tree

b) Always complete

c) Always contains a cycle

d) Always bipartite with a cycle