Campus and Interview preparation with Data Structure
Important topic of Data Structure :-
 |
| campus/interview preparation |
Objective type questions or multiple choice questions (MCQ) are often asked in various exams, including job recruitment tests. It also helps in understanding language constructs, syntax and fundamental rules.click the link given in above list to go to that topic.
Stack in Data Structure
1.
Which of the following is an application of Stack data structure?
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
(b) Function calls management
(c) Balancing of symbols
(d) All of the above
Answer
(d) All of the above
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
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
2.
What data structure would you mostly likely see in a non- recursive implementation of a recursive algorithm?
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
(b) Linked list
(c) Queue
(d) Trees
Answer
(a) Stack
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
The postfix form of X*Y+U/V is
(a) *XY/UV+
(b) XY*UV/+
(c) X*YU+/V
(d) XYUV+/*
(b) XY*UV/+
(c) X*YU+/V
(d) XYUV+/*
Answer
(b)
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/+
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
The result of evaluating the postfix expression 2, 4, 6, +, *, 2, 9, 3, /, +, * is
(a) 150
(b) 100
(c) 10
(d) 180
(b) 100
(c) 10
(d) 180
Answer
(b)100
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.
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 .
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)
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
b) Null
c) S
d) None
Answer
(a) X
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:
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
(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
(a) One stack is enough
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
(b) 213
(c) 142
(d) 71
Answer
(c) 142
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 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
(b) 4
(c) 3
(d) 2
Answer
(c) 3
f(S) = 0,
max(f(S), 0) = 0, i = 2
f(S)n = max(f(S), 0) + i = 0 + 2 = 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)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)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)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
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 ?
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
(b) Reverse of original string
(c) Length of string doubles
(d) Length of string becomes half
Answer
(b) Reverse of original string
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.
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 …….
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
(b) Garbage Collection
(c) Underflow of Stack
(d) Empty Collection
Answer
(c) Underflow of stack
This
condition is known as underflow of stack.
While the condition of pushing an element in full stack is called overflow of Stack.
While the condition of pushing an element in full stack is called overflow of Stack.
source-www.mysirg.com
If this article is helpful to you then please like share and comments.. Thank You...
Comments
Post a Comment