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