Backtracking Multiple choice Questions and Answers (MCQs)
Click on any option to know the CORRECT ANSWERS
Which of the problems cannot be solved by backtracking method?
subset sum problem
hamiltonian circuit problem
travelling salesman problem
Question 1 Explanation:
N-queen problem, subset sum problem, Hamiltonian circuit problems can be solved by backtracking method whereas travelling salesman problem is solved by Branch and bound method.
Backtracking algorithm is implemented by constructing a tree of choice s called as?
Question 2 Explanation:
Backtracking problem is solved by constructing a tree of choice s called as the state-space tree. Its root represents an initial state before the search for a solution begins.
What happens when the backtracking algorithm reaches a complete solution?
It backtracks to the root
It continues searching for other possible solutions
It traverses from a different route
Recursively traverses through the same route
Question 3 Explanation:
When we reach a final solution using a backtracking algorithm, we either stop or continue searching for other possible solutions.
A node is said to be ..... if it has a possibility of reaching a complete solution.
Question 4 Explanation:
If a node has a possibility of reaching the final solution, it is called a promising node. Otherwise, it is non-promising.
In what manner is a state-space tree for a backtracking algorithm constructed?
Twice around the tree
Nearest neighbour first
Question 5 Explanation:
A state-space tree for a backtracking algorithm is constructed in the manner of depth-first search so that it is easy to look into.
There are 5 questions to complete.