Stacks Questions and Answers

Answer: A

O will be at the top. A stack removes items from the top, last in and first out. The stack from top to bottom is L, M, N, O, P, Q. Removing three items takes away L, then M, then N, and O is left at the top. L is the item removed first, N is removed third and P lies below O, so none of them is on top. Elements are added and removed only at the top, so the order of removal is the reverse of the order of addition.

Answer: A

Only keeping, with every record, a pointer to the record with the smallest key below it works.

On PUSH, compare the new key with the minimum stored in the current top record and save a pointer to whichever is smaller (the new record itself if it is smaller): O(1). On POP, simply discard the top record; the record beneath already holds the minimum of everything below it. MIN reads the top record's pointer: O(1). No standard operation becomes slower.

A single pointer to the minimum fails when the minimum is popped: finding the new minimum then needs a scan of the stack, O(n). A sorted auxiliary array makes PUSH and POP O(n), since an element must be inserted or removed in the middle. A min-heap gives O(1) MIN but makes PUSH and POP O(log n), increasing their complexity.

Answer: B

The postfix notation is 95 - 2 +.

In postfix each operator follows its two operands. Convert the inner expression first, then the outer one:

\[ \begin{aligned} (9 - 5) &\to 9\ 5\ - \\ (9 - 5) + 2 &\to 9\ 5\ -\ 2\ + \end{aligned} \]

Evaluating it on a stack gives 9 - 5 = 4 and then 4 + 2 = 6, as the original does. '59 -' would compute 5 - 9, the operands reversed, '2 + 95 -' puts an operator before its operands, and '92 + 5 -' computes 9 + 2 - 5, a different expression.

Answer: D

The answer is All of the mentioned.

A parentheses-balancing program pushes each opening bracket and pops on each closing one; the expression is balanced if every pop matches and the stack ends empty. At run time, local variables live in activation records on the call stack, pushed on a function call and popped on return. A compiler's syntax analyser, such as an LR or LL parser, keeps grammar symbols and states on a parsing stack.

Since each of the three uses a stack, choosing any one alone would be incomplete.

Answer: C

The stack holds at most 3 parentheses.

The algorithm pushes each '(' and pops one for each ')'. The maximum stack size is the deepest nesting. For ( ( ) ( ( ) ) ( ( ) ) ): the outer '(' gives depth 1, the next pairs reach depth 2, and the inner '(' of each '( ( ) )' group reaches depth 3. The stack never holds more than three at once.

12 is the total number of characters, and 6 the number of '(' symbols, neither of which is ever on the stack at the same time. 4 would need one more level of nesting.

Answer: C

The prefix form is * - A / B C - / A K L.

Convert each part, giving / priority over -:

• A - B / C: B / C becomes / B C, so the whole is - A / B C.
• A / K - L: A / K becomes / A K, so the whole is - / A K L.

The two bracketed parts are multiplied, so * goes in front: * - A / B C - / A K L.

The option A B C A K L * - / - / is a postfix-style string with the operators gathered at the end, and the other two options place the operators in an order that does not reproduce the expression when read back.

Answer: B

The postfix form is A B * C D / +.

Multiplication and division bind more tightly than addition, so the expression is (A*B) + (C/D). Converting each part to postfix puts the operator after its operands:

\[ \begin{aligned} A*B &\rightarrow A\ B\ * \\ C/D &\rightarrow C\ D\ / \\ (A*B)+(C/D) &\rightarrow A\ B\ *\ C\ D\ /\ + \end{aligned} \]

Option A puts the operators first, which is closer to prefix form. Options C and D change the grouping, applying + before * and /, which is not what the expression means.

Answer: C

The postfix form is def + / bc * +.

Convert by precedence: the parenthesised e + f becomes ef+; dividing d by it gives def+/; b * c becomes bc*; finally the two parts are added.

\[ d / (e + f) + b * c \;\to\; d\,e\,f + /\ b\,c * + \]

Option B, def+/bc+*, evaluates to (d / (e + f)) * (b + c): it adds b and c and then multiplies, the reverse of the given expression. Options A and D are not valid for this expression at all; in A the division is applied to b and c, and D runs out of operands for its second +.

Answer: D

Stacks are used in all of the above.

Function calls are managed on a call stack that holds return addresses, parameters and local variables. Arithmetic expressions are converted from infix to postfix and evaluated with a stack. In large number arithmetic, digits can be pushed onto stacks so that addition proceeds from the least significant digit with carries.

Since each listed use is a genuine stack application, no single option is complete on its own.

Answer: A

The most appropriate structure is a stack.

To evaluate a postfix expression, read it left to right. Push each operand on the stack. When an operator arrives, pop the top two operands, apply the operator (the first one popped is the right operand) and push the result. At the end the single value left on the stack is the answer. For 2 3 4 * +: push 2 and 3 and 4, then * gives 12, then + gives 14.

A queue is first-in first-out, so it would give operands back in the wrong order. A priority queue or an AVL tree orders items by value, which is irrelevant to evaluating postfix, where operator precedence is already settled by position.