1.
Which of the following is an application of Stack data structure?
(a) Evaluation of postfix expression
(b) Function calls management
(c) Balancing of symbols
(d) All of the above
Answer
All the above listed are applications of Stack. Stack is a data structure in which insertion and deletion are done from one end only.
Some of the applications are:
i) Tower of Hanoi solution
ii) Evaluation of Arithmetic expressions
iii) Syntax parsing (Balancing of symbols)
iv) Function call management
What data structure would you mostly likely see in a non- recursive implementation of a recursive algorithm?
(a) Stack
(b) Linked list
(c) Queue
(d) Trees
Answer
Function calling itself is called recursion.Everytime a function is called with some data,then again the same function is called with some smaller data. In this way, at some point it reaches at base condition and then returns the value to the function that called it.This continues until this reaches from where it started. So it is like putting function state in a data structure while moving ahead and removing them while returning back. This requirement needs last-in-first-out condition and thus Stack data structure is used.
3.
The postfix form of X*Y+U/V is
(a) *XY/UV+
(b) XY*UV/+
(c) X*YU+/V
(d) XYUV+/*
Answer
In postfix notation, operators are written after operand.
For ex: X*Y in postfix notation — XY*
We can easily examine that the given expression is an infix expression. Following BODMAS rule, this expression is (X*Y) + (U/V).
Firstly converting X*Y into postfix expression, we get XY* and then U/V, we get UV/.Now individually we have XY* + UV/. Now solving it, we get XY*UV/+
4.
The result of evaluating the postfix expression 2, 4, 6, +, *, 2, 9, 3, /, +, * is
(a) 150
(b) 100
(c) 10
(d) 180
Answer
Evaluation of postfix expression using stack
i. Scan the expression from left to right.
ii. Create an empty stack.
iii. Now while traversal, if the character is operand, then push it onto stack.
iv. Otherwise if the character is binary operator, pop 2 operands from the stack ( in case of unary operator, pop one operand only).
Let the operator be “opr”, first removed operand be “b” and second removed operand be “a”.
Push the result “a opr b” onto stack again.(Note that the second removed element is kept first according to this algorithm).
v. When complete expression is traversed, we will get a single element in stack, which is the result of evaluation of postfix expression.
Step 1: 2 (Stack content)
Step 2: 2, 4 (Stack content)
Step 3: 2, 4, 6 (Stack content)
Step 4: “+” is an operator. Popping 6 and then 4 and then pushing 4+6=10.Stack is 2, 10.
Step 5: Again “*” is an operator. Push 2*10=20 onto stack. Stack is 20.
Step 6: 20, 2
Step 7: 20, 2, 9
Step 8: 20, 2, 9, 3
Step 9: “/” is an operator. Push 9/3 onto stack. Stack is 20, 2, 3
Step 10: “+” is an operator. Push 2+3. Stack is 20, 5.
Step 11: “*” is an operator. Push 20*5 = 100. Stack is 100.
Since we have traversed the complete expression.We will pop out the result from stack, which is 100 .
5.
What is the result of the following operation
Top (Push (S, X)).
Where Top() function returns the element at the top of the stack(provided as input) and Push() function takes a Stack and an element to push in that stack. Push() function returns the current stack (after changes)
a) X
b) Null
c) S
d) None
Firstly inner function Push(S,X) gets solved. So X is pushed onto stack and then S’ (stack after changes) is passed as an input to Top() function. Then Top() returns the element at the top of Stack S’, which is X.
6.
To evaluate an expression without any embedded function calls:
(a) One stack is enough
(b) Two stacks are needed
(c) As many stacks as the height of the expression tree are needed
(d) A Turing machine is needed in the general case
Answer
Any infix expression can be converted to postfix expression. And postfix expression can be evaluated using only one stack.
7. The result evaluating the postfix expression 10 5 + 60 6 / * 8 – is
(a) 284
(b) 213
(c) 142
(d) 71
Answer
Procedure of evaluation has already been discussed in above question.
8.
A function f defined on stacks of integers satisfies the following properties. f(∅) = 0 and f (push (S, i)) = max (f(S), 0) + i for all stacks S and integers i.
If a stack S contains the integers 2, -3, 2, -1, 2 in order from bottom to top, what is f(S)?
(a) 6
(b) 4
(c) 3
(d) 2
Answer
f(S) = 0, max(f(S), 0) = 0, i = 2
f(S)n = max(f(S), 0) + i = 0 + 2 = 2
f(S) = 2, max(f(S), 0) = 2, i = -3
f(S)n= max(f(S), 0) + i = 2 – 3 = -1
f(S) = -1, max(f(S), 0) = 0, i = 2
f(S)n= max(f(S), 0) + i = 0 + 2 = 2
f(S) = 2, max(f(S), 0) = 2, i = -1
f(S)n= max(f(S), 0) + i = 2 – 1 = 1
f(S) = 1, max(f(S), 0) = 1, i = 2
f(S)n= max(f(S), 0) + i = 1 + 2 = 3
9.
If a string of characters is inserted onto the empty stack one by one until all the elements are inserted. Now characters are popped out of it and each character is appended to a string(initially empty string), then what changes we observe in the new string ?
(a) Same as the original string
(b) Reverse of original string
(c) Length of string doubles
(d) Length of string becomes half
Answer
You can try with a simple string say “ABC”.
After pushing contents of stack will be
C B
A
So the string made by appending an initially empty string is CBA.
10.
The condition when user tries to remove from an empty stack is called …….
(a) Overflow of Stack
(b) Garbage Collection
(c) Underflow of Stack
(d) Empty Collection
Answer
This condition is known as underflow of stack.
While the condition of pushing an element in full stack is called overflow of Stack.