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
View Answer
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
View Answer
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
View Answer
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
View Answer
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
b) Breadth-first search
c) Twice around the tree
d) Nearest neighbour first
View Answer
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
View Answer
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
View Answer
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
View Answer
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
View Answer
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
View Answer
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
View Answer
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
View Answer
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
View Answer
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
View Answer
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
View Answer
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]
- Practice Programming MCQs
- Practice Computer Science MCQs
- Check Computer Science Books
- Check Programming Books
- Practice Data Structure MCQ
