# Towers of Hanoi – Data Structure Questions and Answers

This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on “Towers of Hanoi”.

1. Which among the following is not a palindrome?
A) Madam
B) Dad
C) Malayalam
D) Maadam

Explanation: A palindrome is a string that reads the same both forward and backward; Madam, Dad, and Malayalam are all palindromes, but Maadam is not.

2. Which data structure can be used to test a palindrome?
A) Tree
B) Heap
C) Stack
D) Priority queue

Explanation: Since it requires pressing and popping of characters, stack is a convenient choice.

3. Select the appropriate code which tests for a palindrome.
A)

```public static void main(String[] args)
{
System.out.print("Enter any string:");
Scanner in=new Scanner(System.in);
String input = in.nextLine();
Stack<Character> stk = new Stack<Character>();
for (int i = 0; i < input.length(); i++)
{
stk.push(input.charAt(i));
}
String reverse = "";
while (!stk.isEmpty())
{
reverse = reverse + stk.pop();
}
if (input.equals(reverse))
System.out.println("palindrome");
else
System.out.println("not a palindrome");
}```

B)

```public static void main(String[] args)
{
System.out.print("Enter any string:");
Scanner in=new Scanner(System.in);
String input = in.nextLine();
Stack<Character> stk = new Stack<Character>();
for (int i = 0; i < input.length(); i++)
{
stk.push(input.charAt(i));
}
String reverse = "";
while (!stk.isEmpty())
{
reverse = reverse + stk.peek();
}
if (input.equals(reverse))
System.out.println("palindrome");
else
System.out.println("not a palindrome");
}```

C)

```public static void main(String[] args)
{
System.out.print("Enter any string:");
Scanner in=new Scanner(System.in);
String input = in.nextLine();
Stack<Character> stk = new Stack<Character>();
for (int i = 0; i < input.length(); i++)
{
stk.push(input.charAt(i));
}
String reverse = "";
while (!stk.isEmpty())
{
reverse = reverse + stk.pop();
stk.pop();
}
if (input.equals(reverse))
System.out.println("palindrome");
else
System.out.println("not a palindrome");
}```

D)

```public static void main(String[] args)
{
System.out.print("Enter any string:");
Scanner in=new Scanner(System.in);
String input = in.nextLine();
Stack<Character> stk = new Stack<Character>();
for (int i = 0; i < input.length(); i++)
{
stk.push(input.charAt(i));
}
String reverse = "";
while (!stk.isEmpty())
{
reverse = reverse + stk.pop();
stk.pop();
}
if (!input.equals(reverse))
System.out.println("palindrome");
else
System.out.println("not a palindrome");
}```

Explanation: All the characters in the input string are moved to a stack, then popped and appended to a new string that is compared to the original string.

4. What is the number of moves required to solve Tower of Hanoi problem for k disks?
A) 2k – 1
B) 2k + 1
C) 2k + 1
D) 2k – 1

Explanation: Instead of tracing the moves in the above ToH problem, you can simply add a count for each recursive call to calculate the number of moves.

5. Select the appropriate code which reverses a word.
A)

```public String reverse(String input)
{
for (int i = 0; i < input.length(); i++)
{
stk.push(input.charAt(i));
}
String rev = "";
while (!stk.isEmpty())
{
rev = rev + stk.peek();
}
return rev;
}```

B)

```public String reverse(String input)
{
for (int i = 0; i < input.length(); i++)
{
stk.push(input.charAt(i));
}
String rev = "";
while (!stk.isEmpty())
{
rev = rev + stk.pop();
}
return rev;
}```

C)

```public String reverse(String input)
{
for (int i = 0; i < input.length(); i++)
{
stk.push(input.charAt(i));
}
String rev = "";
while (!stk.isEmpty())
{
rev = rev + stk.pop();
}
}```

D)

```public String reverse(String input)
{
for (int i = 0; i < input.length(); i++)
{
stk.push(input.charAt(i));
}
String rev = "";
while (!stk.isEmpty())
{
rev = rev + stk.pop();
stk.pop();
}
return rev;
}```

Explanation:

Although it is possible to reverse the string without using stack, this is accomplished by looping through the string character by character from the beginning.
In Java, you can use the StringBuilder and StringBuffer classes, which have a built-in reverse process.
It’s worth remembering how close it is to PalindromeTest.

6. The optimal data structure used to solve Tower of Hanoi is _________
A) Tree
B) Heap
C) Priority queue
D) Stack

Explanation: With respect to the size constraint, the Tower of Hanoi entails transferring discs ‘stacked’ at one peg to another peg. It’s easy to do with stacks and priority queues. Tower of Hanoi is often solved using the stack technique.

7. Select the appropriate code for the recursive Tower of Hanoi problem.(n is the number of disks)
A)

```public void solve(int n, String start, String auxiliary, String end)
{
if (n == 1)
{
System.out.println(start + " -> " + end);
}
else
{
solve(n - 1, start, end, auxiliary);
System.out.println(start + " -> " + end);
solve(n - 1, auxiliary, start, end);
}
}```

B)

```public void solve(int n, String start, String auxiliary, String end)
{
if (n == 1)
{
System.out.println(start + " -> " + end);
}
else
{
solve(n - 1, auxiliary, start, end);
System.out.println(start + " -> " + end);
}
}```

C)

```public void solve(int n, String start, String auxiliary, String end)
{
if (n == 1)
{
System.out.println(start + " -> " + end);
}
else
{
System.out.println(start + " -> " + end);
solve(n - 1, auxiliary, start, end);
}
}```

D)

```public void solve(int n, String start, String auxiliary, String end)
{
if (n == 1)
{
System.out.println(start + " -> " + end);
}
else
{
solve(n - 1, start, end, auxiliary);
System.out.println(start + " -> " + end);
}
}```

Explanation: Move all the discs to the auxiliary first, then to the end peg. This is accomplished by having the auxiliary peg the end peg in the first recursive call, then the auxiliary being the start peg in the second recursive call, from which the discs are moved to the end peg.

The Tower of Hanoi (also known as Brahma Tower or Lucas’ Tower, and also referred to as Towers or simply pyramid puzzle) is a mathematical game or puzzle. It is made up of three rods and a variety of discs of various diameters that can be slipped onto any rod. The discs are stacked on one rod in decreasing size order, with the smallest at the top, to approximate a conical shape.