1. The optimal data structure used to solve Tower of Hanoi is _________
a) Tree
b) Heap
c) Priority queue
d) Stack
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.
erting an infix expression to a postfix expression, when an operand is read, it is placed on to the output. When an operator is read, it is placed in the operator stack.
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)
Subscribe Now: Data Structure Newsletter | Important Subjects Newsletters
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)
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);
}
} 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
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.
4. Which data structure can be used to test a palindrome?
a) Tree
b) Heap
c) Stack
d) Priority queue
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 stk = new Stack();
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 stk = new Stack();
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 stk = new Stack();
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 stk = new Stack();
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");
} 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
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;
} Answer: a
Explanation:
Stack is used to postfix expression to infix expression. And to convert we follow the following steps: (i) Scan the expression from left to right. (ii) If operand is found, push it on stack.(iii) If operator is found, the two operands are popped and the combined infix expression is formed and pushed onto the stack.
8. Which of the following is valid reverse polish expression?
a) a op b
b) op a b
c) a b op
d) both op a b and a b op
Answer: c
Explanation:
The postfix expression is also known as the reverse polish expression. In postfix expressions, the operators come after the operands. So, the correct expression is a b op and hence a b op is correct.
9. The result of the postfix expression 5 3 * 9 + 6 / 8 4 / + is _____________
a) 8
b) 6
c) 10
d) 9
Answer: b
Explanation:
Given postfix expression: 5 3 * 9 + 6 / 8 4 / +
Result = 5 3 * 9 + 6 / 8 4 / +
= (5 * 3) 9 + 6 / (8 / 4) +
= ((5 * 3) + 9) / 6 + ( 8 / 4) = ( 24 / 6) + 2 = 4 + 2 = 6.
10. Which of the following statement is incorrect with respect to infix to postfix conversion algorithm?
a) operand is always placed in the output
b) operator is placed in the stack when the stack operator has lower precedence
c) parenthesis are included in the output
d) higher and equal priority operators follow the same condition
Answer: c
Explanation:
Parentheses are not included in the output. They are placed in the operator stack and then discarded.
11. In infix to postfix conversion algorithm, the operators are associated from?
a) right to left
b) left to right
c) centre to left
d) centre to right
Answer: b
Explanation:
In infix, prefix and postfix expressions, the operators are associated from left to right and not right to left.
12. What is the corresponding postfix expression for the given infix expression? a*(b+c)/d
a) ab*+cd/
b) ab+*cd/
c) abc*+/d
d) abc+*d/
Answer: d
Explanation:
Using the infix to postfix conversion algorithm, the corresponding postfix expression is obtained as abc+*d/.
13. What is the corresponding postfix expression for the given infix expression? a+(b*c(d/e^f)*g)*h)
a) ab*cdef/^*g-h+
b) abcdef^/*g*h*+
c) abcd*^ed/g*-h*+
d) abc*de^fg/*-*h+
Answer: b
Explanation:
Using the infix to postfix expression conversion algorithm using stack, the corresponding postfix expression is found to be abcdef^/*g*h*+.
14. What is the correct postfix expression for the following expression? a+b*(c^d-e)^(f+g*h)-i
a) abc^de-fg+*^*+i-
b) abcde^-fg*+*^h*+i-
c) abcd^e-fgh*+^*+i-
d) ab^-dc*+ef^gh*+i-
Answer: c
Explanation:
The postfix expression for the given infix expression is found to be abcd^e-fgh*+^*+i- when we use infix to postfix conversion algorithm.
15. From the given Expression tree, identify the correct postfix expression from the list of options. The postfix expression is ab*cd-+ from the given Expression tree
a) ab*cd*+
b) ab*cd-+
c) abcd-*+
d) ab*+cd-
Answer: b
Explanation:
From the given expression tree, the infix expression is found to be (a*b)+(c-d). Converting it to postfix, we get, ab*cd-+.
