Advanced DataStructures

What is the primary difference between an adjacency matrix and an adjacency list?

• Adjacency matrix is space-efficient for sparse graphs

• Adjacency list is faster for checking if two nodes are connected

• Adjacency matrix requires O(V^2) space, while adjacency list requires O(|V|+|E|) space

• Adjacency list is slower for graph traversal

What type of graph is required to perform a topological sort?

• Directed Cyclic Graph

• Undirected Graph

• Directed Acyclic Graph

• Weighted Graph

In topological Sort, which vertex is chosen first?

• A vertex with highest indegree

• A vertex with negative values

• Any vertex

• A vertex with zero indegree

What is the time complexity of Topological sort in a graph with V vertex and E edges

• O(V^2)

• O( |V| + |E| )

• O( V log V)

• O( E^2)

Dijkstra's Algorithm is used to find the shortest path between

• All pair of vertices in a graph

• A single source vertex to all other vertices in a graph

• All vertices to a single destination vertex in a graph

• All edges in a graph

Dijkstra's algorithm does not work correctly if the graph contains

• Positive Edge Weights

• Self - Loops

• Zero Edge Weights

• Negative Edge Weights

In Dijkstra's Algorithm, What value is assigned to the source vertex at the beginning?

• -1

• Infinity

• 0

• The maximum weight of the graph

What happens if a vertex is revisited in Dijkstra's Algorithm with a shorter path then previously recorded?

• It is ignored

• The shortest path value is updated

• The algorithm terminates

• The shortest path value is incremented

Which of the following algorithms is an alternative to Dijkstra’s Algorithm for graphs with negative weights?

• Kruskal's Algorithm

• Floyd - Warshall Algorithm

• Bellman - Ford Algorithm

• Prim's Algorithm

22. In topological sorting, a vertex with in-degree 0 represents:

• A vertex that can be visited after all other vertices

• A vertex that has no outgoing edges

• A vertex that has no incoming edges

• A vertex that is part of a cycle