Data Structures & Algorithms Multiple Choice Questions on “Backtracking”.
1. Which of the problems cannot be solved by backtracking method? Answer: d 2. Backtracking algorithm is implemented by constructing a tree of choices called as? 3. What happens when the backtracking algorithm reaches a complete solution? Answer: b 4. A node is said to be ____________ if it has a possibility of reaching a complete solution. Answer: b 5. In what manner is a state-space tree for a backtracking algorithm constructed? Answer: a 6. The leaves in a state-space tree represent only complete solutions. Answer: b 7. In general, backtracking can be used to solve? Answer: c 8. Which one of the following is an application of the backtracking algorithm? Answer: d 9. Backtracking algorithm is faster than the brute force technique Answer: a 10. Which of the following logical programming languages is not based on backtracking? Answer: d 11. The problem of finding a list of integers in a given specific range that meets certain conditions is called? Answer: b 12. Who coined the term ‘backtracking’? Answer: a 13. ___________ enumerates a list of promising nodes that could be computed to give the possible solutions of a given problem. 14. The problem of finding a subset of positive integers whose sum is equal to a given positive integer is called as? Answer: b 15. The problem of placing n queens in a chessboard such that no two queens attack each other is called as? Answer: a
a) n-queen problem
b) subset sum problem
c) hamiltonian circuit problem
d) travelling salesman problem
Clarification: 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.
a) State-space tree
b) State-chart tree
c) Node tree
d) Backtracking tree
Answer: a
Clarification: 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.
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
Clarification: When we reach a final solution using a backtracking algorithm, we either stop or continue searching for other possible solutions.
a) Non-promising
b) Promising
c) Succeeding
d) Preceding
Clarification: If a node has a possibility of reaching the final solution, it is called a promising node. Otherwise, it is non-promising.
a) Depth-first search
b) Breadth-first search
c) Twice around the tree
d) Nearest neighbour first
Clarification: 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.
a) true
b) false
Clarification: The leaves in a state space tree can either represent non-promising dead ends or complete solutions found by the algorithm.
a) Numerical problems
b) Exhaustive search
c) Combinatorial problems
d) Graph coloring problems
Clarification: Backtracking approach is used to solve complex combinatorial problems which cannot be solved by exhaustive search algorithms.
a) Finding the shortest path
b) Finding the efficient quantity to shop
c) Ludo
d) Crossword
Clarification: Crossword puzzles are based on backtracking approach whereas the rest are travelling salesman problem, knapsack problem and dice game.
a) true
b) false
Clarification: Backtracking is faster than brute force approach since it can remove a large set of answers in one test.
a) Icon
b) Prolog
c) Planner
d) Fortran
Clarification: Backtracking algorithm form the basis for icon, planner and prolog whereas fortran is an ancient assembly language used in second generation computers.
a) Subset sum problem
b) Constraint satisfaction problem
c) Hamiltonian circuit problem
d) Travelling salesman problem
Clarification: Constraint satisfaction problem is the problem of finding a list of integers under given constraints. Constraint satisfaction problem is solved using a backtracking approach.
a) Lehmer
b) Donald
c) Ross
d) Ford
Clarification: D.H. Lehmer was the first person to coin the term backtracking. Initially, the backtracking facility was provided using SNOBOL.
a) Exhaustive search
b) Brute force
c) Backtracking
d) Divide and conquer
Answer: c
Clarification: Backtracking is a general algorithm that evaluates partially constructed candidates that can be developed further without violating problem constraints.
a) n- queen problem
b) subset sum problem
c) knapsack problem
d) hamiltonian circuit problem
Clarification: Subset sum problem is the problem of finding a subset using the backtracking algorithm when summed, equals a given integer.
a) n-queen problem
b) eight queens puzzle
c) four queens puzzle
d) 1-queen problem
Clarification: 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.