Data Structure Questions and Answers – Towers of Hanoi

«
»

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

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

Answer: d
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.
advertisement

2. 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)

advertisement
advertisement
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)

advertisement
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)

advertisement
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);
       }
}
View Answer
Answer: a
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. Which among the following is not a palindrome?
a) Madam
b) Dad
c) Malayalam
d) Maadam
View Answer

Answer: d
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.
advertisement

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

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

5. 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");
}
View Answer
Answer: a
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. 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
View Answer

Answer: d
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. 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;
}
View Answer
Answer: b
Explanation: 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.

Sanfoundry Global Education & Learning Series – Data Structure.

To practice all areas of Data Structure, here is complete set of 1000+ Multiple Choice Questions and Answers.

Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

advertisement
advertisement
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn | Youtube | Instagram | Facebook | Twitter