Engineering Questions with Answers - Multiple Choice Questions

# Data Structure MCQ – Towers of Hanoi

1 - Question

The optimal data structure used to solve Tower of Hanoi is _________
a) Tree
b) Heap
c) Priority queue
d) Stack

Explanation: The Tower of Hanoi involves moving of disks ‘stacked’ at one peg to another peg with respect to the size constraint. It is conveniently done using stacks and priority queues. Stack approach is widely used to solve Tower of Hanoi.

2 - Question

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: First transfer all the diska to the auxiliary and then to the end peg, this is achieved by making auxiliary peg as the end peg in the first recursive call, in the second recursive call, the auxiliary becomes the start peg from where the disks are transferred to the end peg.

3 - Question

Which among the following is not a palindrome?
c) Malayalam

Explanation: A palindrome is a string that reads the same forward and backward, Madam, Dad and Malayalam are palindromes where as Maadam is not a palindrome.

4 - Question

Which data structure can be used to test a palindrome?
a) Tree
b) Heap
c) Stack
d) Priority queue

Explanation: Stack is a convenient option as it involves pushing and popping of characters.

5 - Question

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: Push all the characters in the input string to a stack, now pop them and append to a new string which is checked for equality with the original string.

6 - Question

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: Tracing of the moves in the above ToH problem will prove this result, instead you can simply add a count for each recursive call to check the number of moves.

7 - Question

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;
}```