This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Towers of Hanoi using Recursion”.

1. What is the objective of tower of hanoi puzzle?

a) To move all disks to some other rod by following rules

b) To divide the disks equally among the three rods by following rules

c) To move all disks to some other rod in random order

d) To divide the disks equally among three rods in random order

View Answer

Explanation: Objective of tower of hanoi problem is to move all disks to some other rod by following the following rules-1) Only one disk can be moved at a time. 2) Disk can only be moved if it is the uppermost disk of the stack. 3) No disk should be placed over a smaller disk.

2. Which of the following is NOT a rule of tower of hanoi puzzle?

a) No disk should be placed over a smaller disk

b) Disk can only be moved if it is the uppermost disk of the stack

c) No disk should be placed over a larger disk

d) Only one disk can be moved at a time

View Answer

Explanation: The rule is to not put a disk over a smaller one. Putting a smaller disk over larger one is allowed.

3. The time complexity of the solution tower of hanoi problem using recursion is _________

a) O(n^{2})

b) O(2^{n})

c) O(n log n)

d) O(n)

View Answer

Explanation: Time complexity of the problem can be found out by solving the recurrence relation: T(n)=2T(n-1)+c. Result of this relation is found to be equal to 2

^{n}. It can be solved using substitution.

4. Recurrence equation formed for the tower of hanoi problem is given by _________

a) T(n) = 2T(n-1)+n

b) T(n) = 2T(n/2)+c

c) T(n) = 2T(n-1)+c

d) T(n) = 2T(n/2)+n

View Answer

Explanation: As there are 2 recursive calls to n-1 disks and one constant time operation so the recurrence relation will be given by T(n) = 2T(n-1)+c.

5. Minimum number of moves required to solve a tower of hanoi problem with n disks is __________

a) 2^{n}

b) 2^{n}-1

c) n^{2}

d) n^{2}-1

View Answer

Explanation: Minimum number of moves can be calculated by solving the recurrence relation – T(n)=2T(n-1)+c. Alternatively we can observe the pattern formed by the series of number of moves 1,3,7,15…..Either way it turn out to be equal to 2

^{n}-1.

6. Space complexity of recursive solution of tower of hanoi puzzle is ________

a) O(1)

b) O(n)

c) O(log n)

d) O(n log n)

View Answer

Explanation: Space complexity of tower of hanoi problem can be found out by solving the recurrence relation T(n)=T(n-1)+c. Result of this relation is found out to be n. It can be solved using substitution.

7. Which of the following functions correctly represent the solution to tower of hanoi puzzle?

a)

void ToH(int n,int a,int b,int c) { If(n>0) { ToH(n-1,a,c,b); cout<<”move a disk from” <<a<<” to”<< c; ToH(n-1,b,a,c); } }

b)

void ToH(int n,int a,int b,int c { If(n>0) { ToH(n-1,a,b,c); cout<<”move a disk from” <<a<<” to”<< c; ToH(n-1,b,a,c); } }

c)

void ToH(int n,int a,int b,int c) { If(n>0) { ToH(n-1,a,c,b); cout<<”move a disk from” <<a<<” to”<< c; ToH(n-1,a,b,c); } }

d)

void ToH(int n,int a,int b,int c) { If(n>0) { ToH(n-1,b,a,c); cout<<”move a disk from” <<a<<” to”<< c; ToH(n-1,a,c,b); } }

Explanation: The first recursive call moves n-1 disks from a to b using c. Then we move a disk from a to c. Finally the second recursive call moves n-1 disks from b to c using a.

8. Recursive solution of tower of hanoi problem is an example of which of the following algorithm?

a) Dynamic programming

b) Backtracking

c) Greedy algorithm

d) Divide and conquer

View Answer

Explanation: The recursive approach uses divide and conquer algorithm as we break the problem into smaller parts and then solve the smaller parts and finally combine their results to get the overall solution.

9. Tower of hanoi problem can be solved iteratively.

a) True

b) False

View Answer

Explanation: Iterative solution to tower of hanoi puzzle also exists. Its approach depends on whether the total numbers of disks are even or odd.

10. Minimum time required to solve tower of hanoi puzzle with 4 disks assuming one move takes 2 seconds, will be __________

a) 15 seconds

b) 30 seconds

c) 16 seconds

d) 32 seconds

View Answer

Explanation: Number of moves = 2

^{4}-1=16-1=15

Time for 1 move = 2 seconds

Time for 15 moves = 15×2 = 30 seconds.

**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__.