Skip to content
GATEiit

GATE DA 2024 Q44: BFS versus DFS expansions to reach state 6

Question

Consider a state space where the start state is number 1. The successor function for the state numbered n returns two states numbered n+1 and n+2. Assume that the states in the unexpanded state list are expanded in the ascending order of numbers and the previously expanded states are not added to the unexpanded state list.

Which ONE of the following statements about breadth-first search (BFS) and depth-first search (DFS) is true, when reaching the goal state number 6?

Try it: multiple choice: exactly one correct option

Select one option
Wrong answer costs 2/3 mark in GATE.
Show answer and explanation

Answer: C (official GATE 2024 final answer key)

Concept used: Simulate BFS (queue) and DFS (stack) with duplicate detection.

First step: Because the smallest-numbered state is always expanded first, both searches expand states 1, 2, 3, 4, 5 before reaching 6.

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

WhatsAppDownload image

Source: official GATE 2024 DA question paper and final answer key, organised by IISc Bangalore. Question paper · Answer key

More Artificial Intelligence PYQs

PracticePractise Artificial Intelligence questions →Full paperAll GATE DA 2024 questions →