ELEVATE SKILLS!
Q: 1 Which data structure is used for implementing recursion?
Queue
Linked List
Stack
Array
[ Option C ]
Recursion is when a function calls itself to solve smaller subproblems. Every time a function is called: its parameters, local variables, return address, must be saved before the function can call itself again. This saving and restoring is managed by a stack.
Q: 2 Consider the following postfix notation expression:
P: 8 2 3 ^ / 2 3 * + 5 1 * -
The top two elements of the stack after the first * is evaluated are:
6,1
5,7
3,2
1,5
[ Option A ]
Given postfix expression:
8 2 3 ^ / 2 3 * + 5 1 * -
We evaluate the expression using a stack, scanning from left to right until the first * is encountered.
| Scanned Symbol | Action | Stack (Top → Bottom) |
|---|---|---|
| 8 | Push in Stack. | 8 |
| 2 | Push in Stack. | 2, 8 |
| 3 | Push in Stack. | 3, 2, 8 |
| ^ | Pop top two i.e., 2^3 = 8 and Push result back to Stack. | 8, 8 |
| / | Pop top two i.e., 8/8 = 1 and Push result back to Stack. | 1 |
| 2 | Push in Stack. | 2, 1 |
| 3 | Push in Stack. | 3, 2, 1 |
| * | Pop top two i.e., 2*3 = 6 and Push result back to Stack. | 6, 1 |
Q: 3 A stack is useful for
Breadth First Search
Recursion
Queue in a Ticket Counter
Accessing Element Using Index
[ Option B ]
A Stack is a data structure that follows the LIFO (Last In, First Out) principle, where the last inserted element is the first to be removed. It is widely used in situations where operations need to be performed in Reverse Order.
One of the most important applications of a stack is Recursion. When a function calls itself, each function call is stored in a call stack, which keeps track of function execution. After completing a function, control returns to the previous function using this stack.
| Term | Explanation |
|---|---|
| Breadth First Search | Uses a queue. |
| Queue in a Ticket Counter | Follows FIFO, so uses a queue. |
| Accessing Element Using Index | Done using arrays. |
Q: 4 Which of the following permutations can be obtained in the same order using a stack assuming that the input is the sequence 5,6,7,8,9 in that order
(i) 7,8,9,6,5
(ii) 5,9,6,7,8
(iii) 9,8,7,5,6
(iv) 7,6,9,8,5
(i) and (iv)
(ii) and (iii)
(iii) and (iv)
(ii) and (iv)
[ Option A ]
A Stack works on LIFO (Last In First Out) principle. Elements must be pushed in the given order (5,6,7,8,9), and we can pop only from the top. A permutation is valid only if it follows stack push–pop rules.
| Permutation | Valid/Invalid | Explanation |
|---|---|---|
| (i) 7,8,9,6,5 | Valid | Possible by pushing 5,6,7 then pop 7 then push 8 then pop 8 then push 9 then pop 9 then pop 6,5. |
| (ii) 5,9,6,7,8 | Invalid | After popping 5 and then 9, 6 cannot come before 7 and 8. |
| (iii) 9,8,7,5,6 | Invalid | After popping 9,8,7, stack has 5,6. Cannot pop 5 before 6. |
| (iv) 7,6,9,8,5 | Valid | Push 5,6,7 then pop 7,6 then push 8,9 then pop 9,8, finally pop 5. |
Q: 5 Stack can be implemented using _______ and _______?
Array and Binary Tree
Array and Graph
Graph and Tree
None of these
[ Option D ]
A stack can be implemented using Array or Linked List.
Q: 6 Which data structure is required to covert the infix to prefix notation?
Queue
Stack
Linked List
More than one of the above
[ Option B ]
To convert an infix expression to a prefix expression, we need a data structure that can temporarily hold operators while respecting their precedence and associativity. A stack is ideal for this purpose because it follows the LIFO (Last In First Out) principle.
Q: 7 The process of inserting new element and removing an existing element to/from stack is called, respectively.
Pop, Push
Insert, Delete
Push, Pop
Add, Delete
[ Option C ]
In a stack, the operation used to insert a new element is called Push, and the operation used to remove an existing element is called Pop. These are standard stack operations based on the LIFO (Last In, First Out) principle.
Q: 8 What is the outcome of the prefix expression
+, - , *, 3, 2, /, 8, 4, 1 ?
12
11
5
4
[ Option C ]
To evaluate a prefix expression, also known as Polish notation, the operator precedes its operands. The evaluation process involves scanning the expression from right to left. When an operand is encountered, it is pushed onto a stack. When an operator is found, the two most recent operands are popped from the stack, the operator is applied to these operands, and the result is pushed back onto the stack.
This continues until the entire expression has been scanned. The final result of the expression is the sole remaining value on the stack.
Q: 9 Here is an infix expression: A+B*(C*D-E). Suppose that we are using the usual stack algorithm to convert the expression from infix to postfix notation. The maximum number of symbols that will appear on the stack At One Time during the conversion of this expression?
7
4
6
3
[ Option B ]
The step-by-step stack status while converting the infix expression A+B*(C*D-E) to postfix using the standard stack algorithm.
| Scanned Symbol | Action | Stack Status (Top → Bottom) | Output (Postfix P) |
|---|---|---|---|
| A | Operand (Add to P) | Empty | P : A |
| + | Push + to Stack | + | P : A |
| B | Operand (Add to P) | + | P : AB |
| * | Pop Higher or Equal Precedence and Push * to Stack | * + | P : AB |
| ( | Push ( to Stack | ( * + | P : AB |
| C | Operand (Add to P) | ( * + | P : ABC |
| * | Pop Higher or Equal Precedence and Push * to Stack | * ( * + | P : ABC |
| D | Operand (Add to P) | * ( * + | P : ABCD |
| - | Pop Higher or Equal Precedence and Push - to Stack | - ( * + | P : ABCD* |
| E | Operand (Add to P) | - ( * + | P : ABCD*E |
| ) | Pop until ( | * + | P : ABCD*E- |
| End | Pop remaining operators | Empty | P : ABCD*E-*+ |
When we perform the conversion from infix to postfix expression * ( * + (Top to Bottom) symbols are placed inside the stack. A maximum of 4 symbols is identified during the entire conversion.
Q: 10 Which of the following data structure is the best suited to match parenthesis in evaluating an arithmetic expression?
Linked List
List
Queue
Stack
[ Option D ]
A Stack follows the LIFO (Last In First Out) principle, which makes it ideal for checking balanced parentheses in arithmetic expressions. Application of stack are:
Q: 11 Stack cannot be used to
Evaluate an arithmetic expression in postfix form
Implement recursion
Convert a given arithmetic expression in infix form to its equivalent postfix form
Allocate CPU resource by operating system
[ Option D ]
A Stack is used for things like expression evaluation, recursion, and converting infix to postfix because all of these need LIFO order. The last item pushed is the first one removed, which matches how function calls and operators are handled.
CPU Scheduling is handled by the operating system scheduler, using queues like ready queue, not stack.
Q: 12 Which of the following is the prefix form of A+B*C?
+A*BC
ABC+*
+AB*C
None of the above
[ Option A ]
Prefix notation (Polish notation) places the operator before its operands. Operator precedence is handled by position, no parentheses needed.
To convert an infix expression to its prefix form, we first need to understand operator precedence. The given expression is A+B*C. Since multiplication (*) has higher precedence than addition (+), B*C is evaluated first. Converting B*C to prefix gives *BC. Then combining it with A+ gives the full prefix expression +A*BC.
Q: 13 Which data structure is used to convert infix notation to postfix notation?
Stack
Queue
Tree
More than one of the above
[ Option A ]
To convert an infix expression into postfix form, we need a data structure that can temporarily hold operators and help manage precedence and parentheses. A Stack is used for this purpose because it allows operators to be pushed and popped in a LIFO (Last-In-First-Out) manner, which perfectly matches the needs of the conversion process.
Q: 14 If the sequence of operations: push(1), push(2), pop, push(1), push(2), pop, pop, pop, push(2), pop are performed on a stack, the sequence of popped out values.
2,2,1,1,2
2,2,1,2,2
2,1,2,2,1
2,1,2,2,2
[ Option A ]
| Operation | Stack Status (Top → Bottom) | Popped Value |
|---|---|---|
| push(1) | 1 | — |
| push(2) | 2, 1 | — |
| pop | 1 | 2 |
| push(1) | 1, 1 | — |
| push(2) | 2, 1, 1 | — |
| pop | 1, 1 | 2 |
| pop | 1 | 1 |
| pop | — | 1 |
| push(2) | 2 | — |
| pop | — | 2 |
Therefore, the sequence of popped out values are 2 2 1 1 2.
Q: 15 The postfix expression equivalent of the prefix expression * + ab – cd is
ab + cd - *
abcd + - *
ab + cd * -
None of the above
[ Option A ]
To convert prefix notation expression into postfix form then the following mechanism is used:
Given infix notation expression : * + a b - c d
| SYMBOL | ACTION | STACK STATUS |
|---|---|---|
| d | Operand, push it onto stack. | d |
| c | Operand, push it onto stack. | d, c |
| - | Operator, pop c, d and form cd-. Push result back onto stack. | cd- |
| b | Operand, push it onto stack. | cd-, b |
| a | Operand, push it onto stack. | cd-, b, a |
| + | Operator, pop a, b and form ab+. Push result back onto stack. | cd-, ab+ |
| * | Operator, pop ab+, cd- and form ab+ cd- *. Push result back onto stack. | ab+ cd- * |
The postfix notation expression : ab+ cd- *
Q: 16 The postfix expression corresponding to the infix expression a+b*c-d^e^f is?
abc*+def^^-
abc*+de^f^-
ab+c*d-e^f^
-+a*bc^^def
[ Option A ]
To convert the infix expression a+b*c−d^e^f into postfix, we must follow operator precedence and associativity rules.
Infix : a+b*c-d^e^f
Postfix : a+b*c-d^ ef^
Postfix : a+b*c- def^^
Postfix : a+bc*- def^^
Postfix : abc*+ - def^^
Postfix : abc*+def^^-
Q: 17 Reverse polish notation for infix expression
(A+B)*C-D/E will be –
-*+ABC/DE
AB+CD-*E/
AB+C*DE-/
AB+C*DE/-
[ Option D ]
Reverse Polish Notation (RPN), also known as Postfix Notation, is a way of writing arithmetic expressions where the operator placed after the operands. For example, the infix expression A+B is written as AB+in RPN.
Besides RPN, there are two other common notations, Infix Notation and Prefix (Polish) Notation. In infix notation, operators are placed between operands like A+B and prefix notation (Polish Notation), operators precede the operands like +AB. In Polish Notation and Reverse Polish Notation (RPN), there is no need of parentheses.
Q: 18 What is the postfix expression for the corresponding infix expression?
a+b*c+(d*e)
abc*+de*+
abc+*de*+
a+bc*de+*
None of the above
[ Option A ]
To convert an infix expression to postfix, we must remember the basic rule of operator precedence and associativity. The operator * and / has higher precedence than + and -.
Infix to postfix conversion for a + b * c + ( d * e ) using a stack, and display the stack state after every step.
| READ SYMBOL | ACTION | STACK (BOTTOM TO TOP) | POSTFIX (P) |
|---|---|---|---|
| a | Operand. Append to output. | (Empty) | P : a |
| + | Push + onto Stack. | + | P : a |
| b | Operand. Append to output. | + | P : ab |
| * | * has higher precedence than top +. So, push * onto Stack. | + , * | P : ab |
| c | Operand. Append to output. | + , * | P : abc |
| + | Pop while top has ≥ precedence than read operator. Finally pushed read operator + onto stack. | + | P : abc*+ |
| ( | Push onto Stack. | + , ( | P : abc*+ |
| d | Operand. Append to output. | + , ( | P : abc*+d |
| * | Push * onto Stack because stack top is (. | + , ( , * | P : abc*+d |
| e | Operand. Append to output. | + , ( , * | P : abc*+de |
| ) | Pop until ( is not encountered then ignore both ( and ). | + | P : abc*+de* |
| End. | Pop remaining operators. | (Empty) | P : abc*+de*+ |
Q: 19 Which among the following is a postfix expression?
*xy
x+y/z
xyz*+ab+-
x/y*(a+b)
[ Option C ]
In expression notations, Postfix (Reverse Polish Notation) means the operator is written after the operands. It does not require parentheses and follows the order of evaluation directly.
The expression xyz*+ab+- follows postfix rules, operands come first, then operators are applied step by step. Hence, it is a valid Postfix Expression.
Q: 20 The time complexity for evaluating a postfix expression is _________.
O(log2n)
O(n)
O(nlog2n)
O(n2)
[ Option B ]
Evaluating a Postfix Expression (Reverse Polish Notation) is done using a stack. The algorithm scans the expression from left to right and performs operations accordingly.
Each token is processed exactly once, and each stack operation either push or pop takes constant time. So, the total time is proportional to the number of tokens in the expression.
Hence the time complexity for evaluating a postfix expression is O(n), where n is the number of Tokens (Operands and Operators).
Q: 21 Which one of the following is not the application of the stack data structure?
Asynchronous data transfer
String Reversal
Backtracking
None of the above
[ Option A ]
A stack is a linear data structure that follows the LIFO (Last In, First Out) principle, meaning the last element inserted is the first one to be removed. Some applications of stacks are:
Q: 22 What would be the prefix notation for the given equation?
(a+(b/c)*(d^e)-f)
+-a*/^bcdef
-+a*b/c^def
-+a*/bc^def
-+fa*/bc^de
[ Option C ]
The given infix expression is a + (b/c) * (d^e) - f. To convert it into prefix form, we first look at the inner brackets. The term (b/c) in prefix becomes / b c, and the term (d^e) becomes ^ d e.
Next, these two are multiplied, so (b/c) * (d^e) becomes * / b c ^ d e. Now, this result is added to a, so the expression a + ((b/c) * (d^e)) becomes + a * / b c ^ d e. Finally, we subtract f from this whole result, so the complete prefix form becomes - + a * / b c ^ d e f.
Q: 23 How many parentheses are left in the stack when an algorithm is analyzing the parentheses string ((() (()) (()))?
0
1
2
3
[ Option B ]
In Parentheses Matching (Balanced Parentheses), a stack is used to check whether the brackets are balanced or not.
Every time an opening parenthesis ‘(’ is encountered, it is pushed into the stack. When a closing parenthesis ‘)’ is found, one element is popped from the stack. After processing the entire string, if any elements are left in the stack, it means those parentheses are unmatched.
| POSITION | CHAR | STACK BEFORE | ACTION | STACK AFTER | STACK SIZE |
|---|---|---|---|---|---|
| 1 | ( | [] | Push | [ (] | 1 |
| 2 | ( | [ (] | Push | [ ( , (] | 2 |
| 3 | ( | [ ( , (] | Push | [ ( , ( , (] | 3 |
| 4 | ) | [ ( , ( , (] | Pop | [ ( , (] | 2 |
| 5 | space | [ ( , (] | Ignore | [ ( , (] | 2 |
| 6 | ( | [ ( , (] | Push | [ ( , ( , (] | 3 |
| 7 | ( | [ ( , ( , (] | Push | [ ( , ( , ( , (] | 4 |
| 8 | ) | [ ( , ( , ( , (] | Pop | [ ( , ( , (] | 3 |
| 9 | ) | [ ( , ( , (] | Pop | [ ( , (] | 2 |
| 10 | space | [ ( , (] | Ignore | [ ( , (] | 2 |
| 11 | ( | [ ( , (] | Push | [ ( , ( , (] | 3 |
| 12 | ( | [ ( , ( , (] | Push | [ ( , ( , ( , (] | 4 |
| 13 | ) | [ ( , ( , ( , (] | Pop | [ ( , ( , (] | 3 |
| 14 | ) | [ ( , ( , (] | Pop | [ ( , (] | 2 |
| 15 | ) | [ ( , (] | Pop | [ (] | 1 |
Final Stack: [ ( ] : 1 Unmatched Left Parenthesis.
Q: 24 Consider the following stack implemented using stack-
#define SIZE 11
struct STACK
{
int arr[SIZE];
int top=-1;
}
What would be the maximum value of top that does not cause the overflow of the stack?
8
9
11
10
[ Option D ]
In the given stack implementation, the size of the array is defined as 11, which means the stack can hold elements from index 0 to 10. Initially, the value of top is -1, and each time an element is pushed, the value of top increases by one.
When the stack is completely filled, the top will point to the last valid index, which is 10. At this stage, the stack contains 11 elements in total, and if we try to push one more element, it will cause an overflow. Therefore, the maximum value of top that does not cause overflow is 10.
Q: 25 Convert the following infix expression into its equivalent postfix expression.
(A+B^D)/(E–F)+G
ABD+^EF/– G+
ABD^+EF–/G+
ABD^+EF/–G+
ABD+^EF–/G+
[ Option B ]
To convert the infix expression (A+B^D)/(E−F)+G into postfix, we follow operator precedence and parentheses rules. The exponent operator ^ has the highest precedence, followed by division /, and then addition + and subtraction -.
Infix : (A + B ^ D) / (E − F) + G
Postfix : (A+BD^) / (E - F) + G
Postfix : ABD^+ / (E - F) + G
Postfix : ABD^+ / EF- + G
Postfix : ABD^+EF-/ + G
Postfix : ABD^+EF-/G+
Q: 26 What data structure would you choose to implement "undo" feature in a word processor?
Queue
Stack
Dequeue
None of these
[ Option B ]
The stack is most suitable data structure since it works in LIFO (Last-In-First-Out) ordering. All these actions are pushed into stack and whatever action has to be reversed (undoed) can be just popped off the top of the stack.
Q: 27 The postfix form of the expression
(A+B)*(C*D-E)*F/G, is –
AB+CD*E-FG/**
AB+CD*E-F**G/
AB+CD*E-*F*G/
AB+CDE*-*F*G/
[ Option C ]
Expression: ( A + B ) * ( C * D - E ) * F / G
| Scanned Symbol | Action | Stack Status (Top → Bottom) | Output (Postfix P) |
|---|---|---|---|
| ( | Push ( | ( | P : |
| A | Operand (Add to P) | ( | P : A |
| + | Push + | + ( | P : A |
| B | Operand (Add to P) | + ( | P : AB |
| ) | Pop until ( | # (Empty) | P : AB+ |
| * | Push * | * | P : AB+ |
| ( | Push ( | (* | P : AB+ |
| C | Operand (Add to P) | (* | P : AB+C |
| * | Push * | *(* | P : AB+C |
| D | Operand (Add to P) | *(* | P : AB+CD |
| - | Pop Higher or Equal Precedence | -(* | P : AB+CD* |
| E | Operand (Add to P) | -(* | P : AB+CD*E |
| ) | Pop until ( | * | P : AB+CD*E- |
| * | Push * | * | P : AB+CD*E-* |
| F | Operand (Add to P) | * | P : AB+CD*E-*F |
| / | Pop Higher or Equal Precedence | / | P : AB+CD*E-*F* |
| G | Operand (Add to P) | / | P : AB+CD*E-*F*G |
| End | Pop Remaining. | # (Empty) | P : AB+CD*E-*F*G/ |
Q: 28 Consider the following operations performed on a stack of size 5: push(a); pop(); push(b); push(c); pop(); push(d); pop(); pop(); push(e); which of the following statements is correct?
Underflow occurs
Stack operations are performed smoothly
Overflow occurs
None of these
[ Option B ]
| Operation | Stack Status (Top → Bottom) | Remark |
|---|---|---|
| Initial | — | Empty Stack |
| push(a) | a | Ok |
| pop() | — | Ok (Removes a) |
| push(b) | b | Ok |
| push(c) | c, b | Ok |
| pop() | b | Ok (Removes c) |
| push(d) | d, b | Ok |
| pop() | b | Ok (Removes d) |
| pop() | — | Ok (Removes b) |
| push(e) | e | Ok |
The stack size never exceeds 5, and no invalid operation occurs. Therefore, all stack operations are performed smoothly.
Q: 29 Stack data structure uses
FIFO
LIFO
LILO
None of the above
[ Option B ]
A stack works on the LIFO (Last In, First Out) principle. This means the element inserted last will be removed first, just like stacking plates, the last plate placed on top is the first one you take off.
Q: 30 Which condition causes a stack underflow?
Removing from an empty stack
Reading beyond the top
Allocating too much memory
Inserting into a full stack
[ Option A ]
A stack is a linear data structure that follows the LIFO (Last In, First Out) principle. In stack the last element inserted is the first one to be removed. Stack Underflow occurs when an attempt is made to pop (remove) an item from an empty stack, where no elements exist to remove.
Q: 31 Following sequence of operations is performed on a stack:
PUSH(32), PUSH(4), POP, PUSH(56), POP, POP
The sequence of values popped out is
4, 56, 32
56, 32, 4
32, 56, 4
4, 32, 56
[ Option A ]
A Stack follows the LIFO (Last In First Out) principle, meaning the last element pushed into the stack is the first one to be removed.
| OPERATION | STACK STATUS (BOTTOM TO TOP) | POPPED VALUE |
|---|---|---|
| PUSH(32) | 32 | - |
| PUSH(4) | 32, 4 | - |
| POP | 32 | 4 |
| PUSH(56) | 32, 56 | - |
| POP | 32 | 56 |
| POP | (Empty) | 32 |
Sequence of values popped out, 4, 56, 32.
Q: 32 Most appropriate data structure for implementing recursive procedure is
Queue
Trie
Stack
Linked List
[ Option C ]
Recursion is a programming technique where a function calls itself. During recursion, each function call must store its state such as parameters, return address, local variables, so that it can resume correctly after execution. This storage follows the Last In First Out (LIFO) principle.
A Stack perfectly supports this behavior. Each recursive call is pushed onto the stack, and when the function returns, the last call is popped first. That is why recursion is internally implemented using a call stack.
Q: 33 The expression a b c + - is written in which of the following form?
Infix
Postfix
Prefix
Lastfix
[ Option B ]
In Expression Notations:
Remember,
Q: 34 The result evaluating the postfix expression 10 5 + 60 6 / * 8 – is?
124
284
142
248
[ Option C ]
Given postfix expression:
10 5 + 60 6 / * 8 –
| Scanned Symbol | Action | Stack Status (Top → Bottom) |
|---|---|---|
| 10 | Push in Stack. | 10 |
| 5 | Push in Stack. | 5, 10 |
| + | Pop top two i.e., 10+5 = 15 and Push result back to Stack. | 15 |
| 60 | Push in Stack. | 60, 15 |
| 6 | Push in Stack. | 6, 60, 15 |
| / | Pop top two i.e., 60/6 = 10 and Push result back to Stack. | 10, 15 |
| * | Pop top two i.e., 15*10 = 150 and Push result back to Stack. | 150 |
| 8 | Push in Stack. | 8, 150 |
| – | Pop top two i.e., 150−8 = 142 and Push result back to Stack. | 142 |
NOTE:
In postfix evaluation, operand1 operator operand2, where operand1 is second popped value (next to top element) while operand2 is first popped value (top element).
Q: 35 Which one of the following is the process of inserting an element in the stack?
Insert
Add
Push
None of the above
[ Option C ]
A stack is a linear data structure that follows the LIFO (Last In, First Out) principle, where elements are added or removed only from one end called TOP of the stack.
The process of adding or inserting new element at the top of stack is called Push Operation. The process of deleting or removing an existing element from top of stack is called Pop Operation.
Thank you so much for taking the time to read my Computer Science MCQs section carefully. Your support and interest mean a lot, and I truly appreciate you being part of this journey. Stay connected for more insights and updates! If you'd like to explore more tutorials and insights, check out my YouTube channel.
Don’t forget to subscribe and stay connected for future updates.
| Student Name | |
|---|---|
| College |
| What's Say |
|---|