# Backtracking Multiple Choice Questions and Answers (MCQs)

This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Backtracking”.

1. Which of the problems cannot be solved by backtracking method?
a) n-queen problem
b) subset sum problem
c) hamiltonian circuit problem
d) travelling salesman problem

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.

2. Backtracking algorithm is implemented by constructing a tree of choices called as?
a) State-space tree
b) State-chart tree
c) Node tree
d) Backtracking tree

Explanation: Backtracking problem is solved by constructing a tree of choices called as the state-space tree. Its root represents an initial state before the search for a solution begins.

3. What happens when the backtracking algorithm reaches a complete solution?
a) It backtracks to the root
b) It continues searching for other possible solutions
c) It traverses from a different route
d) Recursively traverses through the same route

Explanation: When we reach a final solution using a backtracking algorithm, we either stop or continue searching for other possible solutions.

4. A node is said to be ____________ if it has a possibility of reaching a complete solution.
a) Non-promising
b) Promising
c) Succeeding
d) Preceding

Explanation: If a node has a possibility of reaching the final solution, it is called a promising node. Otherwise, it is non-promising.

5. In what manner is a state-space tree for a backtracking algorithm constructed?
a) Depth-first search
c) Twice around the tree
d) Nearest neighbour first

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.

6. The leaves in a state-space tree represent only complete solutions.
a) true
b) false

Explanation: The leaves in a state space tree can either represent non-promising dead ends or complete solutions found by the algorithm.

7. In general, backtracking can be used to solve?
a) Numerical problems
b) Exhaustive search
c) Combinatorial problems
d) Graph coloring problems

Explanation: Backtracking approach is used to solve complex combinatorial problems which cannot be solved by exhaustive search algorithms.

8. Which one of the following is an application of the backtracking algorithm?
a) Finding the shortest path
b) Finding the efficient quantity to shop
c) Ludo
d) Crossword

Explanation: Crossword puzzles are based on backtracking approach whereas the rest are travelling salesman problem, knapsack problem and dice game.

9. Backtracking algorithm is faster than the brute force technique
a) true
b) false

Explanation: Backtracking is faster than brute force approach since it can remove a large set of answers in one test.

10. Which of the following logical programming languages is not based on backtracking?
a) Icon
b) Prolog
c) Planner
d) Fortran

Explanation: Backtracking algorithm form the basis for icon, planner and prolog whereas fortran is an ancient assembly language used in second generation computers.

11. The problem of finding a list of integers in a given specific range that meets certain conditions is called?
a) Subset sum problem
b) Constraint satisfaction problem
c) Hamiltonian circuit problem
d) Travelling salesman problem

Explanation: Constraint satisfaction problem is the problem of finding a list of integers under given constraints. Constraint satisfaction problem is solved using a backtracking approach.

12. Who coined the term ‘backtracking’?
a) Lehmer
b) Donald
c) Ross
d) Ford

Explanation: D.H. Lehmer was the first person to coin the term backtracking. Initially, the backtracking facility was provided using SNOBOL.

13. ___________ enumerates a list of promising nodes that could be computed to give the possible solutions of a given problem.
a) Exhaustive search
b) Brute force
c) Backtracking
d) Divide and conquer

Explanation: Backtracking is a general algorithm that evaluates partially constructed candidates that can be developed further without violating problem constraints.

14. The problem of finding a subset of positive integers whose sum is equal to a given positive integer is called as?
a) n- queen problem
b) subset sum problem
c) knapsack problem
d) hamiltonian circuit problem

Explanation: Subset sum problem is the problem of finding a subset using the backtracking algorithm when summed, equals a given integer.

15. The problem of placing n queens in a chessboard such that no two queens attack each other is called as?
a) n-queen problem
b) eight queens puzzle
c) four queens puzzle
d) 1-queen problem

Explanation: The problem of placing n-queens in a chessboard such that no two queens are vertical or horizontal or diagonal to each other is an n-queen problem. The problem only exists for n = 1, 4, 8.

Sanfoundry Global Education & Learning Series – Data Structures & Algorithms.

To practice all areas of Data Structures & Algorithms, here is complete set of 1000+ Multiple Choice Questions and Answers.

If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]