1. The optimal data structure used to solve Tower of Hanoi is _________
a) Tree
b) Heap
c) Priority queue
d) Stack
Discussion
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. Which among the following is not a palindrome?
a) Madam
b) Dad
c) Malayalam
d) Maadam
Discussion
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.
3. Which data structure can be used to test a palindrome?
a) Tree
b) Heap
c) Stack
d) Priority queue
Discussion
Explanation: Stack is a convenient option as it involves pushing and popping of characters.
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
Discussion
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.
5. What is the time complexity of balancing parentheses algorithm?
a) O (N)
b) O (N log N)
c) O (M log N)
d) O (N2)
Discussion
Explanation: The time complexity of balancing parentheses algorithm is mathematically found to be O (N).
6. Which application of stack is used to ensure that the pair of parentheses is properly nested?
a) Balancing symbols
b) Reversing a stack
c) Conversion of an infix to postfix expression
d) Conversion of an infix to prefix expression
Discussion
Explanation: Balancing symbols application ensures that the pair of parentheses are properly nested while reversing stack reverses a stack.
7. In balancing parentheses algorithm, the string is read from?
a) right to left
b) left to right
c) center to right
d) center to left
Discussion
Explanation: Any string is read by the compiler from left to right and not from right to left.
8. Which is the most appropriate data structure for applying balancing of symbols algorithm?
a) stack
b) queue
c) tree
d) graph
Discussion
Explanation: Stack is the most appropriate data structure for balancing symbols algorithm because stack follows LIFO principle (Last In First Out).
9. Which of the following does the balancing symbols algorithm include?
a) balancing double quotes
b) balancing single quotes
c) balancing operators and brackets
d) balancing parentheses, brackets and braces
Discussion
Explanation: The balancing symbols algorithm using stack only includes balancing parentheses, brackets and braces and not any other symbols.
10. Which of the following statement is incorrect with respect to balancing symbols algorithm?
a) {[()]}
b) ([ )]
c) {( )}
d) { [ ] }
Discussion
Explanation: ([ )] is incorrect because’)’ occurs before the corresponding ‘]’ is encountered.