QuizzesIntermediate Graph Traversal Techniques: A* and Dijkstra's Algorithm
intermediate
dsa

Intermediate Graph Traversal Techniques: A* and Dijkstra's Algorithm

Explore the intricacies of A* and Dijkstra's algorithms in graph traversal.

18 minutes 12 questions Pass at 70%
Time Limit
18 minutes - timer starts when you begin
Change Answers Freely
Revisit and change any answer before submitting
Full Review After Submit
Correct answers and explanations shown for every question
Auto-submit on timeout
Quiz submits automatically when time runs out

Questions in this quiz

12 questions on Intermediate Graph Traversal Techniques: A* and Dijkstra's Algorithm. Work through them here, then start the quiz to answer them and see your score.

  1. 1.What is the primary difference between Dijkstra's Algorithm and A* Algorithm?

    • ADijkstra's uses a heuristic, A* does not
    • BNeither use heuristics
    • CA* uses a heuristic, Dijkstra's does not
    • DBoth use heuristics
  2. 2.In Dijkstra's algorithm, what data structure is commonly used to select the next node to process?

    • AStack
    • BQueue
    • CLinked List
    • DPriority Queue
  3. 3.Which of the following is true about A* algorithm's heuristic function?

    • AIt can be any arbitrary function
    • BIt must underestimate the true cost
    • CIt must overestimate the true cost
    • DIt must be linear
  4. 4.What is the time complexity of Dijkstra's algorithm using a binary heap?

    • AO(V^2)
    • BO(E log V)
    • CO(E + V)
    • DO(V log V)
  5. 5.In A* algorithm, what does the 'f(n)' function represent?

    • AThe estimated total cost from start to goal through n
    • BThe cost from the start node to the goal
    • CThe cost from the start node to node n
    • DThe heuristic cost from node n to the goal
  6. 6.Which of the following is a requirement for Dijkstra's algorithm to work correctly?

    • AAll edge weights must be non-negative
    • BGraph must be connected
    • CGraph must be acyclic
    • DGraph must be directed
  7. 7.What is the main advantage of A* over Dijkstra's algorithm?

    • AA* is faster due to the heuristic
    • BA* can handle negative weights
    • CA* uses less memory
    • DA* guarantees the shortest path
  8. 8.Which of the following is NOT a characteristic of Dijkstra's algorithm?

    • AIt finds the shortest path
    • BIt can handle negative weights
    • CIt uses a priority queue
    • DIt explores all nodes
  9. 9.In A* algorithm, if the heuristic is perfect, what is the result?

    • AA* will not find the shortest path
    • BA* will explore fewer nodes
    • CA* will be slower than Dijkstra's
    • DA* will not terminate
  10. 10.What happens if the heuristic function in A* overestimates the cost?

    • AA* will be faster
    • BA* will run indefinitely
    • CA* may not find the shortest path
    • DA* will still find the shortest path
  11. 11.Which algorithm is more suitable for finding the shortest path in a game map with obstacles?

    • AA* Algorithm
    • BDijkstra's Algorithm
    • CDepth-First Search
    • DBreadth-First Search
  12. 12.What is the role of the heuristic function in A* algorithm?

    • ATo estimate the cost to the goal
    • BTo determine the next node to explore
    • CTo calculate the cost from the start
    • DTo calculate the exact cost to the goal