ITPEC FE Morning October 2020 Question 9
There are three stacks, A, B, and C, each having an initial state [1, 2, 3], respectively. When the recursively defined function, f(), below, is called and terminates, what is the state of stack B? Here, [a0, a1, …, an-1] represent the state of a stack. When an is pushed into this stack, the state becomes [a0, a1, …, an-1, an].
f() {
if A is empty {
do nothing
} else {
pop a value from A, then push it into C
call f()
pop a value from C, then push it into B
}
}
Explanation
[1, 2, 3, 1, 2, 3] — the values are reversed once going from A into C and reversed back going from C into B.
Top of each stack is the rightmost value. Each call pops A into C, recurses, and only after the recursive call returns pops C into B:
- •Descent: 3, then 2, then 1 are moved from A to C, so C = [1, 2, 3, 3, 2, 1] and A is empty
- •Return, innermost call first: C's top 1 goes to B, then 2, then 3
- •B = [1, 2, 3] + [1, 2, 3] = [1, 2, 3, 1, 2, 3]
Answer (a)
Why not others:
- •(b) [1, 2, 3, 3, 2, 1] — the order values leave A (3, 2, 1): it reverses once, as if A were popped straight into B, missing the second reversal through C
- •(c) [3, 2, 1, 1, 2, 3] and (d) [3, 2, 1, 3, 2, 1] — change the bottom of B, but f only pushes onto B, so its original [1, 2, 3] stays underneath
Key rule: Every transfer through a stack reverses the order, so two transfers restore it; work that follows a recursive call runs in reverse order of the calls.
Algorithm and Programming · AI-written, may contain errors
This question comes from an official ITPEC past paper. ITPEC Practice is an independent study tool and is not affiliated with ITPEC. See the official FE past-paper collection or Report an issue.