سوال ۶۳ کنکور ارشد مهندسی کامپیوتر ۱۴۰۰

Check each requested data structure independently. The hard constraint is that every listed operation must run in $\Theta(1)$ (worst-case constant time).

Structure 1 — $\text{Push}$, $\text{Pop}$, $\text{FindMin}$, $\text{FindMax}$ all $\Theta(1)$. Achievable. Keep the data in a stack and maintain two auxiliary stacks, one tracking the running minimum and one the running maximum. On $\text{Push}(x)$ also push $\min(x,\text{top}_{\min})$ and $\max(x,\text{top}_{\max})$; on $\text{Pop}$ pop all three; $\text{FindMin}/\text{FindMax}$ just read the tops. Every operation is $\Theta(1)$. So this one can be built.

Structure 2 — $\text{Push}$, $\text{Pop}$, $\text{DeleteMin}$ all $\Theta(1)$. Impossible. $\text{DeleteMin}$ removes the minimum element (not the top), so the min may sit in the middle and the auxiliary-stack trick collapses. More fundamentally, suppose both $\text{Push}$ and $\text{DeleteMin}$ ran in $\Theta(1)$. Then inserting $n$ keys costs $\Theta(n)$ and calling $\text{DeleteMin}$ $n$ times also costs $\Theta(n)$, yielding the keys in sorted order in total $\Theta(n)$ time:

$\underbrace{n\cdot\Theta(1)}_{\text{Push}}+\underbrace{n\cdot\Theta(1)}_{\text{DeleteMin}}=\Theta(n).$

That contradicts the comparison-sort lower bound $\Omega(n\log n)$. So this one cannot be built.

Structure 3 — $\text{Push}$, $\text{Pop}$ all $\Theta(1)$. Achievable. This is just an ordinary stack (array- or list-backed): both operations are $\Theta(1)$. So this one can be built.

Only one of the three (Structure 2) is impossible, so the answer is one.

Exam trick: Whenever a structure must support Insert and ExtractMin (or DeleteMin) both in $O(1)$, it is impossible — the $\Omega(n\log n)$ comparison-sort bound forbids it. Plain FindMin/FindMax (read-only, no removal) is fine in $O(1)$.