This section contains carefully selected MCQs and Previous Year Questions with explanations to help students understand concepts and prepare effectively for examinations, interviews, and competitive tests.
Q: 1Which data structure is used for implementing recursion?
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: 2Consider 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:
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: 3A stack is useful for
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: 4Which 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
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: 5Stack can be implemented using _______ and _______?
Option D
A stack can be implemented using Array or Linked List.
Q: 6Which data structure is required to covert the infix to prefix notation?
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: 7The process of inserting new element and removing an existing element to/from stack is called, respectively.
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: 8What is the outcome of the prefix expression
+, - , *, 3, 2, /, 8, 4, 1 ?
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: 9Here 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?
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: 10Which of the following data structure is the best suited to match parenthesis in evaluating an arithmetic expression?
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: 11Stack cannot be used to
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: 12Which of the following is the prefix form of A+B*C?
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: 13Which data structure is used to convert infix notation to postfix notation?
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: 14If 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.
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: 15The postfix expression equivalent of the prefix expression * + ab – cd is
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- *
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 |
|---|