Stacks
Question 1 
The following postfix expression with single digit operands is evaluated using a stack:
8 2 3 ^ / 2 3 * + 5 1 * Note that ^ is the exponentiation operator. The top two elements of the stack after the first * is evaluated are:
6, 1
 
5, 7
 
3, 2  
1, 5 
Question 1 Explanation:
8 2 3 ^ / 2 3 * + 5 1 * 
After the * is evaluated at the time elements in the stack is 1, 6.
After the * is evaluated at the time elements in the stack is 1, 6.
Question 2 
Consider the following C program:
#include #define EOF 1 void push (int); /* push the argument on the stack */ int pop (void); /* pop the top of the stack */ void flagError (); int main () { int c, m, n, r; while ((c = getchar ()) != EOF) { if (isdigit (c) ) push (c); else if ((c == '+')  (c == '*')) { m = pop (); n = pop (); r = (c == '+') ? n + m : n*m; push (r); } else if (c != ' ') flagError (); } printf("% c", pop ()); }What is the output of the program for the following input ? 5 2 * 3 3 2 + * +
15  
25  
30  
150 
Question 2 Explanation:
push 5
push 2
pop 2
pop 5
5 * 2 = 10
push 10
push 3
push 3
push 2
pop 2
pop 3
3 + 2 = 5
push 5
pop 5
pop 3
3 * 5 = 15
push 15
pop 15
pop 10
10 + 15 = 25
push 25
Finally, pop 25 and print it.
push 2
pop 2
pop 5
5 * 2 = 10
push 10
push 3
push 3
push 2
pop 2
pop 3
3 + 2 = 5
push 5
pop 5
pop 3
3 * 5 = 15
push 15
pop 15
pop 10
10 + 15 = 25
push 25
Finally, pop 25 and print it.
Question 3 
A single array A[1..MAXSIZE] is used to implement two stacks. The two stacks grow from opposite ends of the array. Variables top1 and top2 (topl < top2) point to the location of the topmost element in each of the stacks. If the space is to be used efficiently, the condition for “stack full” is
(top1 = MAXSIZE/2) and (top2 = MAXSIZE/2+1)
 
top1 + top2 = MAXSIZE
 
(top1 = MAXSIZE/2) or (top2 = MAXSIZE)
 
top1 = top2 – 1

Question 3 Explanation:
Since the stacks are growing from opposite ends, so initially top1=1 and top2=Max_size. Now to make the efficient use of space we should allow one stack to use the maximum possible space as long as other stack doesn't need it. So any of the stack can grow towards each other until there is space available in the array. Hence, the condition must be top1=top2  1.
Question 4 
The best data structure to check whether an arithmetic expression has balanced parentheses is a
queue
 
stack  
tree
 
list 
Question 4 Explanation:
Stack is the best data structure to validate the arithmetic expression.
While evaluating when left parentheses occur then it push in to the stack, when right parentheses occur pop from the stack.
While at the end there is empty in the stack.
While evaluating when left parentheses occur then it push in to the stack, when right parentheses occur pop from the stack.
While at the end there is empty in the stack.
Question 5 
Assume that the operators +, , ×, are left associative and ^ is right associative. The order of precedence (from highest to lowest) is ^, x , +, . The postfix expression corresponding to the infix expression a + b×cd^e^f is
abc×+def^^
 
abc×+de^f^
 
ab+c×de^f^
 
+a×bc^^def

Question 5 Explanation:
a+b×cd^e^f
Note: When low precedence operator enters into stack then pop.
Note: When low precedence operator enters into stack then pop.
Question 6 
Let S be a stack of size n ≥1. Starting with the empty stack, suppose we push the first n natural numbers in sequence, and then perform n pop operations. Assume that Push and Pop operations take X seconds each, and Y seconds elapse between the end of one such stack operation and the start of the next operation. For m ≥1, define the stacklife of m as the time elapsed from the end of Push(m) to the start of the pop operation that removes m from S. The average stacklife of an element of this stack is
n(X + Y)  
3Y + 2X
 
n(X + Y)  X
 
Y + 2X 
Question 6 Explanation:
Life time of last element present in the stack = Y
(After push into stack then immediately popped)
Life time of (n1) element = Y + X + Y + X + Y = 2X + 3Y
Life time of (n2) element = (n1) + 2X + 2Y = 2X + 3Y + 2X + 2Y = 4X + 5Y
Life time of 1's element = 2(n1)X + (2n1)Y
Life time of all elements is ⇒
2X(1+2+3+...+n1)+Y(1+3+5+...+(2n1))
⇒ 2X(n(n1) /2) +Y((n/2)(1+2n1))
⇒ n(n(X+Y)X))
Avg. of n numbers = n(n(X+Y)X)/n = n(X+Y)X
(After push into stack then immediately popped)
Life time of (n1) element = Y + X + Y + X + Y = 2X + 3Y
Life time of (n2) element = (n1) + 2X + 2Y = 2X + 3Y + 2X + 2Y = 4X + 5Y
Life time of 1's element = 2(n1)X + (2n1)Y
Life time of all elements is ⇒
2X(1+2+3+...+n1)+Y(1+3+5+...+(2n1))
⇒ 2X(n(n1) /2) +Y((n/2)(1+2n1))
⇒ n(n(X+Y)X))
Avg. of n numbers = n(n(X+Y)X)/n = n(X+Y)X
Question 7 
To evaluate an expression without any embedded function calls
One stack is enough  
Two stacks are needed  
As many stacks as the height of the expression tree are needed  
A Turning machine is needed in the general case 
Question 7 Explanation:
To evaluate an expression or converting prefix to postfix, postfix to prefix only one stack is enough.
Question 8 
Which of the following is essential for converting an infix expression to the postfix
form efficiently?
An operator stack  
An operand stack  
An operand stack and an operator stack  
A parse tree

Question 8 Explanation:
An operator stack ⇒ Infix to (Postfix or Prefix)
An operand stack ⇒ Postfix to Prefix
Operator & operand stack ⇒ We don't use two stacks
Parse tree ⇒ No use
An operand stack ⇒ Postfix to Prefix
Operator & operand stack ⇒ We don't use two stacks
Parse tree ⇒ No use
Question 9 
Which of the following permutations can be obtained in the output (in the same order) using a stack assuming that the input is the sequence 1, 2, 3, 4, 5 in that order?
3, 4, 5, 1, 2  
3, 4, 5, 2, 1  
1, 5, 2, 3, 4  
5, 4, 3, 1, 2 
Question 9 Explanation:
Push 1 Push 2 Push 3 Pop 3 Push 4 Pop 4 Push 5 Pop 5 Pop 2 Pop 1.
→ Remaining options are not possible.
→ Remaining options are not possible.
Question 10 
20, 10, 20, 10, 20  
20, 20, 10, 10, 20  
10, 20, 20, 10, 20  
20, 20, 10, 20, 10 
Question 10 Explanation:
PUSH(10), PUSH(20), POP = 20 (i)
→ PUSH(10), PUSH(10), PUSH(20), POP = 20 (ii)
→ PUSH(10), PUSH(10), POP = 10 (iii)
→ PUSH(10), POP = 10 (iv)
→ PUSH(20)
→ PUSH(20), POP = 20 (v)
⇒ 20, 20, 10, 10, 20
→ PUSH(10), PUSH(10), PUSH(20), POP = 20 (ii)
→ PUSH(10), PUSH(10), POP = 10 (iii)
→ PUSH(10), POP = 10 (iv)
→ PUSH(20)
→ PUSH(20), POP = 20 (v)
⇒ 20, 20, 10, 10, 20
There are 10 questions to complete.