MCQs

Disclaimer:

Educational Use Only:

The website links provided are to be used strictly for educational and knowledge-gaining purposes only.

No Misuse:

Do not misuse the links or the information contained therein for any commercial, illegal, or unethical activities.

Respect for Websites and Businesses:

Respect the intellectual property and business interests of the websites and their owners. Do not attempt to alter, copy, or redistribute content without proper authorization.

Acknowledge Value of Knowledge:

Recognize and value the knowledge and resources shared by these websites. Use the information responsibly and ethically.

No Endorsement:

The provision of these links does not imply endorsement of the linked sites, their content, or their products and services. Users are responsible for evaluating the suitability and accuracy of the information.

User Responsibility:

By accessing these links, you agree to use the information at your own risk and to comply with all applicable laws and website terms of use.

Overall MCQs for Reference

Which algorithm is most widely used for finding the shortest path from a single source to all other vertices in a graph?
a. Kruskal’s Algorithm
b. Prim’s Algorithm
c. Dijkstra’s Algorithm
d. Floyd-Warshall Algorithm
Answer: c. Dijkstra’s Algorithmgeeksforgeeks+2
What is the major advantage of the Bellman-Ford algorithm over Dijkstra’s algorithm?
a. Handles negative edge weights
b. Faster computation time
c. Simpler implementation
d. Works only for undirected graphs
Answer: a. Handles negative edge weightstestbook+2
Which algorithm is suitable for finding shortest paths between every pair of vertices in a weighted graph?
a. DFS
b. Floyd-Warshall Algorithm
c. Prim’s Algorithm
d. BFS
Answer: b. Floyd-Warshall Algorithmgeeksforgeeks+2
The complexity of Dijkstra’s algorithm using a min-priority queue (e.g., binary heap) is:
a. O(V^2)
b. O(V)
c. O(Elog(V))
d. O(V^3)
Answer: c. O(Elog(V))geeksforgeeks+1
Which shortest path algorithm uses dynamic programming to solve the all-pairs shortest path problem?
a. Dijkstra’s Algorithm
b. Bellman-Ford Algorithm
c. Floyd-Warshall Algorithm
d. DFS
Answer: c. Floyd-Warshall Algorithmgetsdeready+2
What happens if Dijkstra’s algorithm is used on a graph with negative edge weights?
a. It fails to find any path
b. It may produce incorrect results
c. It ignores negative weights
d. Performs optimally
Answer: b. It may produce incorrect resultstestbook+1
A* algorithm is an example of:
a. Uninformed search
b. Informed search
c. Dynamic search
d. Backtracking search
Answer: b. Informed searchfrontiersin+2
Which method guarantees the shortest path even in the presence of negative cycles?
a. BFS
b. DFS
c. Bellman-Ford Algorithm
d. Dijkstra’s Algorithm
Answer: c. Bellman-Ford Algorithm (but only detects, not solves negative cycles)geeksforgeeks+2
The purpose of the heuristic function in the A* algorithm is to:
a. Estimate path length from start node only
b. Guide search toward the goal efficiently
c. Guarantee completeness only
d. Sort the queue
Answer: b. Guide search toward the goal efficientlyacm+2
Which search algorithm will find the shortest path in an unweighted graph?
a. BFS
b. DFS
c. A*
d. Kruskal’s
Answer: a. BFSgetsdeready+2
In Dijkstra’s algorithm, what determines which vertex is explored next?
a. Random choice
b. LIFO order
c. Minimum tentative distance
d. Maximum outgoing edge
Answer: c. Minimum tentative distancegeeksforgeeks+1
Floyd-Warshall Algorithm’s time complexity is:
a. O(V^3)
b. O(VE)
c. O(Elog(V))
d. O(V)
Answer: a. O(V^3)testbook+2
Johnson’s algorithm is used for:
a. Minimum spanning trees
b. All pairs shortest paths in sparse graphs
c. Maximum flow calculation
d. Topological sorting
Answer: b. All pairs shortest paths in sparse graphsgeeksforgeeks+1
Which algorithm can be optimized using a priority queue or heap data structure?
a. DFS
b. Topological Sort
c. Dijkstra’s Algorithm
d. Floyd-Warshall Algorithm
Answer: c. Dijkstra’s Algorithmtestbook+2
What is the principle behind the greedy choice in Dijkstra’s algorithm?
a. Select longest edge
b. Select node with largest current distance
c. Select node with smallest tentative distance
d. Select node processed last
Answer: c. Select node with smallest tentative distancegeeksforgeeks+2
Which algorithm finds the shortest path in a weighted directed acyclic graph (DAG) in linear time?
a. Dijkstra’s Algorithm
b. Topological Sort based algorithm
c. Floyd-Warshall Algorithm
d. Kruskal’s Algorithm
Answer: b. Topological Sort based algorithmgetsdeready+1
Main disadvantage of Bellman-Ford algorithm is:
a. Can’t handle negative weights
b. Inefficient for large graphs
c. Only for undirected graphs
d. Can’t detect cycles
Answer: b. Inefficient for large graphsgeeksforgeeks+2
The A* Search Algorithm combines which two values?
a. Path length and number of neighbors
b. Path cost and heuristic estimate
c. Degree and out-degree
d. Number of vertices and edges
Answer: b. Path cost and heuristic estimatefrontiersin+2
Which algorithm quickly finds the shortest path but requires non-negative weights and is typically used in navigation systems?
a. DFS
b. Dijkstra’s Algorithm
c. Prim’s Algorithm
d. DFS with stack
Answer: b. Dijkstra’s Algorithmijeijournal+2
In which scenario does the A* algorithm reduce to Dijkstra’s algorithm?
a. When heuristic is zero
b. When goal node is unreachable
c. When all edge weights are zero
d. When heuristic overestimates
Answer: a. When heuristic is zerowikipedia+2
In a breadth-first search applied on an unweighted undirected graph, the first time a vertex is discovered means:
a. It is part of a cycle
b. It is reached via a shortest path
c. It has the highest degree
d. It is the source
Answer: b. It is reached via a shortest pathgetsdeready+1
Which algorithm is most suitable for real-time vehicle or game navigation (due to efficiency and use of heuristics)?
a. Bellman-Ford
b. Kruskal’s
c. A*
d. Prim’s
Answer: c. A*ijeijournal+2
If a graph contains negative cycles, which algorithm can be used to detect them?
a. Dijkstra’s
b. Johnson’s
c. Bellman-Ford
d. BFS
Answer: c. Bellman-Fordtestbook+2
For which data structure does Dijkstra’s algorithm yield O(V^2) time complexity?
a. Min-heap
b. Binary tree
c. Array
d. BST
Answer: c. Arraygeeksforgeeks+1
Heuristic search algorithms such as A* are especially effective in:
a. Sparse graphs without weights
b. Graphs with known heuristic to target
c. Cyclic graphs only
d. Highly connected regular graphs
Answer: b. Graphs with known heuristic to targetacm+2
What is the main limitation of Dijkstra’s algorithm?
a. Does not return shortest paths all pairs
b. Handles only negative weights
c. Cannot detect negative cycles
d. Works only for undirected graphs
Answer: c. Cannot detect negative cyclesgeeksforgeeks+1
Which of the following searches always finds the shortest path in unweighted graphs?
a. Depth-first search
b. Breadth-first search
c. Greedy search
d. Best-first search
Answer: b. Breadth-first searchgraphable+2
What distinguishes the Floyd-Warshall algorithm from Dijkstra’s algorithm?
a. Handles nonlinear graphs
b. Computes all-pairs shortest paths
c. Requires negative weights
d. Ignores cycles
Answer: b. Computes all-pairs shortest pathsgeeksforgeeks+1
Which statement about bidirectional search is correct?
a. It works only in trees
b. Reduces search space by searching from both start and goal
c. Only for weighted graphs
d. Does not require graph representation
Answer: b. Reduces search space by searching from both start and goalwikipedia
The time complexity of Bellman-Ford algorithm is:
a. O(V^2)
b. O(Elog(V))
c. O(VE)
d. O(V^3)
Answer: c. O(V*E)geeksforgeeks+1
What is the role of the priority queue in Dijkstra’s Algorithm?
a. To store visited nodes
b. To track nodes in LIFO order
c. To efficiently select node with least tentative distance
d. To remove cycles
Answer: c. To efficiently select node with least tentative distancegeeksforgeeks+1
Which pathfinding algorithm is the basis for many heuristics in real-world transportation?
a. DFS
b. BFS
c. Dijkstra’s Algorithm
d. DFS with backtracking
Answer: c. Dijkstra’s Algorithmsciencedirect+1
When does the Bellman-Ford algorithm terminate?
a. After V-1 iterations
b. As soon as the goal is reached
c. When all cycles are visited
d. After finding minimum spanning tree
Answer: a. After V-1 iterationstestbook+2
Which algorithm is most commonly used for navigation in Google Maps?
a. DFS
b. A*
c. Prim’s Algorithm
d. Kruskal’s Algorithm
Answer: b. A*ijeijournal+2
Uninformed search for the shortest path includes:
a. DFS
b. BFS
c. Backtracking
d. Recursive search
Answer: b. BFSfrontiersin+2
Why is BFS not suitable for graphs with high branching factor and weights?
a. Only works for unweighted
b. Slower than Dijkstra’s
c. Handles only minimum spanning trees
d. Ignores visited nodes
Answer: a. Only works for unweightedgetsdeready+2
Which algorithm updates the costs for each neighboring node using ‘relaxation’?
a. Prim’s
b. Kruskal’s
c. Dijkstra’s
d. DFS
Answer: c. Dijkstra’ssiteforinfotech+1
What is a main characteristic of the BFS algorithm in context of shortest paths?
a. Finds paths only if graph is weighted
b. Finds shortest in terms of number of edges
c. Always finds minimum cost
d. Ignores cycles
Answer: b. Finds shortest in terms of number of edgesgetsdeready+2
The main logic behind the A* algorithm is combining:
a. Random search and DFS
b. Path cost so far and heuristic to goal
c. Size of connected components
d. Cycle length and degree
Answer: b. Path cost so far and heuristic to goalacm+2
If the heuristic in A* overestimates the cost, the result will be:
a. Algorithm remains optimal
b. May fail to find shortest path
c. Faster execution
d. Infinite loop
Answer: b. May fail to find shortest pathfrontiersin+1
Which algorithm uses principle of dynamic programming for shortest paths in dense graphs?
a. Prim’s
b. Floyd-Warshall
c. Kruskal’s
d. DFS
Answer: b. Floyd-Warshallgeeksforgeeks+1
Johnson’s algorithm is used when:
a. Graph is sparse and requires all-pairs shortest
b. Unweighted path needed
c. For cyclic graphs only
d. For negative cycles
Answer: a. Graph is sparse and requires all-pairs shortestgeeksforgeeks+1
Which algorithm is the fastest for single-source shortest path in graphs without negative edge weights?
a. Prim’s
b. Kruskal’s
c. Dijkstra’s
d. Floyd-Warshall
Answer: c. Dijkstra’sfrontiersin+2
ALT, Arc flags, and Hub labeling are advanced techniques for:
a. Minimum spanning tree
b. Maximum matching
c. Fast shortest path computation
d. Cycle detection
Answer: c. Fast shortest path computationwikipedia
Why does the A* algorithm often outperform uninformed approaches?
a. Ignores graph structure
b. Leverages information to guide search
c. Always finds all possible paths
d. Uses heavy computation
Answer: b. Leverages information to guide searchacm+2
In Dijkstra’s algorithm, if all edge weights are equal, the algorithm behaves like:
a. DFS
b. BFS
c. Topological sort
d. Kruskal’s
Answer: b. BFSgetsdeready+2
The main computational resource bounded in the shortest-path problem is:
a. Time
b. Coloring
c. Memory usage
d. Graph topology
Answer: a. Timegeeksforgeeks+2
Which shortest-path algorithm is most memory efficient for sparse graphs?
a. Floyd-Warshall
b. Johnson’s
c. Dijkstra’s with heap
d. DFS recursion
Answer: b. Johnson’sgeeksforgeeks+1
A practical application of shortest path algorithms is:
a. Network routing
b. Graph coloring
c. Array sorting
d. Cache replacement
Answer: a. Network routingijeijournal+2
Heuristic algorithms are particularly important in shortest path AI when:
a. Graphs are weighted and dynamic
b. No weights exist
c. Graphs are linear
d. Number of edges is constant
Answer: a. Graphs are weighted and dynamicsciencedirect+1

Blog

Systemethic Technologies

Leave a Reply Cancel reply

Useful links

Other Terms & Policies

Contact Info