MCQs on Graph Representation and Traversal

What is the correct way to initialize an adjacency list for 5 vertices?

• ArrayList graph = new ArrayList<>(5);

• int[] graph = new int[5];

• ArrayList[] graph = new ArrayList[5];

• LinkedList[] graph = new LinkedList[5];

What does this code create? graph[0].add(1); graph[1].add(0);

• Directed edge from 0 to 1

• Undirected edge between 0 and 1

• Weighted edge

• Cycle

Why do we initialize each element of the graph? for(int i = 0; i < graph.length; i++) graph[i] = new ArrayList<>();

• To make a deep copy

• To avoid null pointer exception

• To create adjacency matrix

• To sort the vertices

Which of the following is NOT a correct way to represent an undirected edge between two nodes?

• graph[a].add(b); graph[b].add(a);

• graph[a].add(b);

• graph[b].add(a); graph[a].add(b);

• Both A and C

What is the purpose of using ArrayList[] over ArrayList[]?

• To store edge weights

• To track edge types

• To reduce memory

• To make the graph connected

Which data structure does DFS use internally (recursion)?

• Queue

• Stack

• Array

• Heap

What will be the DFS output for this graph starting at 0? 0 - 1 | 2 Code: dfs(graph, 0, visited);

• 0 1 2

• 0 2 1

• 0

• 2 0 1

DFS explores all __________ before backtracking.

• adjacent vertices

• connected components

• leaf nodes

• neighbors of the neighbors

What happens if visited[curr] = true is removed in DFS?

• DFS won't run

• It will run infinitely or revisit nodes

• It will skip nodes

• It will throw an error

What is the time complexity of DFS using adjacency list?

• O(V)

• O(E)

• O(V + E)

• O(V²)