Towers of Hanoi | Data Structure MCQs

1.

Which data structure can be used suitably to solve the Tower of Hanoi problem?

   A.) Tree
   B.) Heap
   C.) Priority queue
   D.) Stack

Answer: Option 'D'

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,
although it is also possible using priority queues. Since stack approach is widely used, the more suitable option would be ‘d’ stack.

2.

Which among the following is not a palindrome?

   A.) Madam
   B.) Dad
   C.) Malayalam
   D.) Maadam

Answer: Option 'D'

By definition, a palindrome is a string which is the same forward and backward, here, option d doesn’t adhere to this definition.

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.) None of these

Answer: Option 'A'

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.

4.

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

Answer: Option 'B'

Although, it is possible to reverse the string without using stack, it is done by looping through the string from the end character by character.
In Java, it is also possible to use the StringBuilder and StringBuffer classes which have a built-in method ‘reverse’.
Note its similarity to PalindromeTest.

5.

What is the number of moves required in the Tower of Hanoi problem for k disks?

   A.) 2k – 1
   B.) 2k + 1
   C.) 2k + 1
   D.) 2<Sup>k</sup>&nbsp; -  1

Answer: Option 'D'

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.

6.

Which data structure can be used to test a palindrome?

   A.) Tree
   B.) Heap
   C.) Stack
   D.) Priority queue

Answer: Option 'C'

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

Towers of Hanoi | Data Structure MCQs Download Pdf