CS Free MCQ Bank

[ 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.

[ 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.

[ Option D ]

A stack can be implemented using Array or Linked List.

[ 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.

[ 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.

[ 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.

[ 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.

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.

[ 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.

[ 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.

[ Option A ]

Therefore, the sequence of popped out values are 2 2 1 1 2.

[ Option A ]

To convert prefix notation expression into postfix form then the following mechanism is used:

1. Read or scan the prefix expression from right to left.
2. When operand is encountered then push it onto stack.
3. When an operator is encountered then:
   1. Pop two operands from the stack. Where operand1 is top element and operand2 is next to top element and combine them as operand1 operand2 operator.
   2. Push the result back onto stack.
4. Repeat until all symbols are processed.
5. Finally, the stack top will have the Postfix Form.

Given infix notation expression : * + a b - c d

The postfix notation expression : ab+ cd- *

[ Option A ]

To convert the infix expression a+b*c−d^e^f into postfix, we must follow operator precedence and associativity rules.

• The precedence order (from highest to lowest) : ^, /, *, + , −.
• The ^ is Right-Associative, while /, * , + , − are Left-Associative.

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^^-

[ 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.

[ 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.

[ 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:

• String Reversal, by pushing each character onto a stack and popping them, the string is reversed.
• Backtracking, used in algorithms like maze solving, depth-first search, and recursion to keep track of choices.
• Expression Evaluation and Conversion, evaluating postfix and prefix expressions or converting infix expressions.
• Undo Sequence, in the text editors the facility to undo the last instruction is provided. Stack is used to implement it. The actions are stored in the stack and if undo is executed the topmost instruction is deleted from the stack.
• Pass Parameters, in the programming environment when the values of the parameters passed are stored in a data structure of stack and then these arguments are fetched in the LIFO manner from the stack.
• History in Web Browser, the pages visited from the web browser are stored in the stack. The most visited page is kept on the top and the least on the bottom of the stack.

[ 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.

[ 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.

[ 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+

[ 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.

[ Option C ]

Expression: ( A + B ) * ( C * D - E ) * F / G

[ Option B ]

The stack size never exceeds 5, and no invalid operation occurs. Therefore, all stack operations are performed smoothly.

[ 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.

[ 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.

[ Option C ]

Given postfix expression:
10 5 + 60 6 / * 8 –

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).

[ 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.