Consider the following pseudo code. Assume that IntQueue is an integer queue.…
2023
Consider the following pseudo code. Assume that IntQueue is an integer queue. What does the function fun do?
void fun(int n)
{
IntQueue q = new IntQueue();
q.enqueue(0);
q.enqueue(1);
for (int i = 0; i < n; i++)
{
int a = q.dequeue();
int b = q.dequeue();
q.enqueue(b);
q.enqueue(a + b);
print(a);
}
}- A.
Prints numbers from 0 to n-1
- B.
Prints numbers from n-1 to 0
- C.
Prints first n Fibonacci numbers
- D.
Prints first n Fibonacci numbers in reverse order.
Show answer & explanation
Correct answer: C
Concept: A queue that always holds exactly the two most recent terms of a sequence can generate that sequence by, in every round, dequeuing the front term to print it, then re-enqueuing the OTHER dequeued term unchanged together with the sum of the two dequeued terms — this reproduces the recurrence F(k) = F(k-1) + F(k-2), the defining rule of the Fibonacci sequence, while keeping the queue holding exactly the next two consecutive terms.
Iteration i | Queue before | a = dequeue() | b = dequeue() | Printed value | Queue after |
|---|---|---|---|---|---|
0 | [0, 1] | a = 0 | b = 1 | 0 | [1, 1] |
1 | [1, 1] | a = 1 | b = 1 | 1 | [1, 2] |
2 | [1, 2] | a = 1 | b = 2 | 1 | [2, 3] |
3 | [2, 3] | a = 2 | b = 3 | 2 | [3, 5] |
4 | [3, 5] | a = 3 | b = 5 | 3 | [5, 8] |
Cross-check: The five printed values 0, 1, 1, 2, 3 are exactly F(0) through F(4) of the standard Fibonacci sequence (0, 1, 1, 2, 3, 5, 8, ...), so after n iterations the loop has printed precisely the first n Fibonacci numbers — matching the option describing that behaviour, not a plain count-up/count-down or a reversed Fibonacci output.