Question 1
Which of the following is true about a directed graph?
1
All edges are bidirectional.
2
All vertices are connected
3
Every vertex has an outgoing edge.
4
Every edge has a direction, i.e. it has a start vertex and an end vertex.
Question 2
Which of the following is the correct time complexity for Depth-First Search (DFS) and Breadth-First Search (BFS) for a graph with 'V' vertices and 'E' edges?
1
O(E)
2
O(V)
3
O(V * E)
4
O(V + E)
Question 3
Which of the following algorithms is used for finding the shortest path in a graph with non-negative weights?
1
Kruskal’s Algorithm
2
Bellman-Ford Algorithm
3
Dijkstra’s Algorithm
4
Floyd-Warshall Algorithm
Question 4
Which of the following is true about a complete graph?
1
There is no direct edge between any pair of vertices.
2
Every vertex has exactly one edge.
3
Every pair of vertices is connected by exactly one edge.
4
All edges are directed.
Question 5
What is the time complexity of finding the connected components of an undirected graph using Depth-First Search (DFS)?
1
O(E)
2
O(V + E)
3
O(V)
4
O(V * E)
Question 6
Which of the following algorithms is used for finding the Minimum Spanning Tree (MST) of a graph?
1
Floyd-Warshall Algorithm
2
Bellman-Ford Algorithm
3
Prim’s Algorithm
4
Dijkstra’s Algorithm
Question 7
How would you implement the A* search algorithm for pathfinding in a graph?
1
Use a priority queue to store nodes
2
Use recursion to explore all paths
3
Use a simple list to store nodes
4
Use a stack to store nodes