Prepare for Graphs Data Structure Interview with iQwizz | Difficulty Level: Advance | Rating: 4

Please login before attempting the quiz

Question 1

What is the purpose of the heuristic function in the A* search algorithm?

To determine the order in which nodes are visited during the search.
To calculate the exact cost of the path from the start node to the current node.
To store the visited nodes to avoid cycles.
To estimate the cost of the cheapest path from the current node to the goal node.

Question 2

Johnson's algorithm leverages which two algorithms to efficiently find all-pairs shortest paths in a graph with both positive and negative edge weights?

Bellman-Ford algorithm and Floyd-Warshall algorithm
Dijkstra's algorithm and Bellman-Ford algorithm
Depth-First Search and Breadth-First Search
A* search algorithm and Dijkstra's algorithm

Question 3

What is the minimum number of edges that need to be removed from a complete graph with 'n' vertices to make it acyclic (i.e., having no cycles)?

n
1
n - 1
n/2

Question 4

What is an advantage of using a Fibonacci heap implementation for Dijkstra's algorithm?

It improves the time complexity for sparse graphs.
It allows the algorithm to handle negative edge weights.
It reduces the space complexity of the algorithm.
It simplifies the implementation of the algorithm.

Question 5

What is the time complexity of the Edmonds-Karp algorithm when using a Breadth-First Search (BFS) to find augmenting paths in a network flow graph with 'V' vertices and 'E' edges?

O(E^2 * V)
O(V * E)
O(V^2 * E)
O(V + E)

Question 6

In the context of shortest path algorithms, what is 'relaxation'?

Transforming a directed graph into an undirected graph.
Updating the distance to a node if a shorter path is found.
Reducing the priority of a node in the priority queue.
Removing edges that cannot contribute to the shortest path.

Question 7

Consider a network flow graph with a source 's' and sink 't'. Applying the Ford-Fulkerson algorithm results in a maximum flow of 10 units. Now, we increase the capacity of an edge on the shortest augmenting path by 2 units. What is the maximum possible flow after this modification?

12 units
10 units
Cannot be determined
11 units

Question 8

What is the relationship between A* search and Dijkstra's algorithm?

A* and Dijkstra's algorithm are entirely unrelated.
A* is only applicable to unweighted graphs, while Dijkstra's algorithm works for weighted graphs.
Dijkstra's algorithm is a special case of A* search.
A* is a generalization of Dijkstra's algorithm.

Question 9

In the worst-case scenario, what is the time complexity of the Floyd-Warshall algorithm for a graph with 'V' vertices?

O(V log V)
O(V^2)
O(V^3)
O(E log V)

Question 10

Which of the following scenarios would likely benefit most from using the A* search algorithm?

Finding all possible paths between two vertices in a graph.
Determining if a graph is connected.
Finding the shortest path in an unweighted, undirected graph.
Finding the shortest path in a weighted graph with a known heuristic estimate to the goal.

Please login before attempting the quiz

Question 1

What is the purpose of the heuristic function in the A* search algorithm?

To determine the order in which nodes are visited during the search.
To calculate the exact cost of the path from the start node to the current node.
To store the visited nodes to avoid cycles.
To estimate the cost of the cheapest path from the current node to the goal node.

Question 2

Johnson's algorithm leverages which two algorithms to efficiently find all-pairs shortest paths in a graph with both positive and negative edge weights?

Bellman-Ford algorithm and Floyd-Warshall algorithm
Dijkstra's algorithm and Bellman-Ford algorithm
Depth-First Search and Breadth-First Search
A* search algorithm and Dijkstra's algorithm

Question 3

What is the minimum number of edges that need to be removed from a complete graph with 'n' vertices to make it acyclic (i.e., having no cycles)?

n
1
n - 1
n/2

Question 4

What is an advantage of using a Fibonacci heap implementation for Dijkstra's algorithm?

It improves the time complexity for sparse graphs.
It allows the algorithm to handle negative edge weights.
It reduces the space complexity of the algorithm.
It simplifies the implementation of the algorithm.

Question 5

What is the time complexity of the Edmonds-Karp algorithm when using a Breadth-First Search (BFS) to find augmenting paths in a network flow graph with 'V' vertices and 'E' edges?

O(E^2 * V)
O(V * E)
O(V^2 * E)
O(V + E)

Question 6

In the context of shortest path algorithms, what is 'relaxation'?

Transforming a directed graph into an undirected graph.
Updating the distance to a node if a shorter path is found.
Reducing the priority of a node in the priority queue.
Removing edges that cannot contribute to the shortest path.

Question 7

12 units
10 units
Cannot be determined
11 units

Question 8

What is the relationship between A* search and Dijkstra's algorithm?

A* and Dijkstra's algorithm are entirely unrelated.
A* is only applicable to unweighted graphs, while Dijkstra's algorithm works for weighted graphs.
Dijkstra's algorithm is a special case of A* search.
A* is a generalization of Dijkstra's algorithm.

Question 9

In the worst-case scenario, what is the time complexity of the Floyd-Warshall algorithm for a graph with 'V' vertices?

O(V log V)
O(V^2)
O(V^3)
O(E log V)

Question 10

Which of the following scenarios would likely benefit most from using the A* search algorithm?

Finding all possible paths between two vertices in a graph.
Determining if a graph is connected.
Finding the shortest path in an unweighted, undirected graph.
Finding the shortest path in a weighted graph with a known heuristic estimate to the goal.

Graphs Data Structure Questions

Please login before attempting the quiz

Question 1

Question 2

Question 3

Question 4

Question 5

Question 6

Question 7

Question 8

Question 9

Question 10

Please login before attempting the quiz

Question 1

Question 2

Question 3

Question 4

Question 5

Question 6

Question 7

Question 8

Question 9

Question 10

Login Account