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

Please login before attempting the quiz

Question 1

What is the time complexity of the A* search algorithm in the worst case, assuming a consistent heuristic?

It depends on the heuristic function and can be exponential in the worst case.
O(V + E), where V is the number of vertices and E is the number of edges
O(V^2), where V is the number of vertices
O(E log V), where V is the number of vertices and E is the number of edges

Question 2

Which of the following data structures is commonly used to implement the priority queue in A* search?

Queue
Stack
Linked list
Binary heap

Question 3

In a directed graph, what is the necessary and sufficient condition for the existence of an Eulerian path?

At most two vertices have a difference of 1 between their in-degree and out-degree, and all other vertices have equal in-degree and out-degree.
The graph has no cycles.
The graph is strongly connected.
All vertices have the same in-degree and out-degree.

Question 4

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?

Cannot be determined
12 units
11 units
10 units

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

How does the Bellman-Ford algorithm handle negative weight cycles when determining shortest paths?

It detects and reports the existence of negative weight cycles, indicating that a shortest path may not exist.
It modifies the edge weights to eliminate negative cycles before finding the shortest path.
It ignores negative weight cycles and finds the shortest path regardless.
It utilizes a separate algorithm to handle negative weight cycles after executing the main algorithm.

Question 7

Which of the following statements is NOT TRUE about a graph with a Hamiltonian cycle?

The graph is connected.
The number of vertices is greater than or equal to 3.
Every vertex has a degree of at least 2.
The graph is planar.

Question 8

If a graph has negative edge weights but no negative weight cycles, which algorithm can still find the shortest path?

Both Dijkstra's and Bellman-Ford algorithm
Only Bellman-Ford algorithm
Only Dijkstra's algorithm
Neither algorithm can find the shortest path

Question 9

Johnson's algorithm improves the efficiency of finding all-pairs shortest paths in which type of graph?

Directed acyclic graphs (DAGs)
Sparse graphs with negative edge weights
Unweighted graphs
Dense graphs with positive edge weights

Question 10

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

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

Please login before attempting the quiz

Question 1

What is the time complexity of the A* search algorithm in the worst case, assuming a consistent heuristic?

It depends on the heuristic function and can be exponential in the worst case.
O(V + E), where V is the number of vertices and E is the number of edges
O(V^2), where V is the number of vertices
O(E log V), where V is the number of vertices and E is the number of edges

Question 2

Which of the following data structures is commonly used to implement the priority queue in A* search?

Queue
Stack
Linked list
Binary heap

Question 3

In a directed graph, what is the necessary and sufficient condition for the existence of an Eulerian path?

At most two vertices have a difference of 1 between their in-degree and out-degree, and all other vertices have equal in-degree and out-degree.
The graph has no cycles.
The graph is strongly connected.
All vertices have the same in-degree and out-degree.

Question 4

Cannot be determined
12 units
11 units
10 units

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

How does the Bellman-Ford algorithm handle negative weight cycles when determining shortest paths?

It detects and reports the existence of negative weight cycles, indicating that a shortest path may not exist.
It modifies the edge weights to eliminate negative cycles before finding the shortest path.
It ignores negative weight cycles and finds the shortest path regardless.
It utilizes a separate algorithm to handle negative weight cycles after executing the main algorithm.

Question 7

Which of the following statements is NOT TRUE about a graph with a Hamiltonian cycle?

The graph is connected.
The number of vertices is greater than or equal to 3.
Every vertex has a degree of at least 2.
The graph is planar.

Question 8

If a graph has negative edge weights but no negative weight cycles, which algorithm can still find the shortest path?

Both Dijkstra's and Bellman-Ford algorithm
Only Bellman-Ford algorithm
Only Dijkstra's algorithm
Neither algorithm can find the shortest path

Question 9

Johnson's algorithm improves the efficiency of finding all-pairs shortest paths in which type of graph?

Directed acyclic graphs (DAGs)
Sparse graphs with negative edge weights
Unweighted graphs
Dense graphs with positive edge weights

Question 10

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

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

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