Computer Science 101 Practice Exam — Free

Trace upward from the base cases rather than expanding the whole call tree. The base case covers $n = 0$ and $n = 1$, both returning 1.

• $f(2) = f(1) + 2f(0) = 1 + 2 = 3$
• $f(3) = f(2) + 2f(1) = 3 + 2 = 5$
• $f(4) = f(3) + 2f(2) = 5 + 6 = 11$
• $f(5) = f(4) + 2f(3) = 11 + 10 = 21$

Check with the closed form: the recurrence $a_n = a_{n-1} + 2a_{n-2}$ has characteristic equation $r^2 - r - 2 = (r-2)(r+1) = 0$, so $a_n = \alpha 2^n + \beta(-1)^n$. The base cases give $\alpha + \beta = 1$ and $2\alpha - \beta = 1$, so $\alpha = 2/3$ and $\beta = 1/3$, and $a_5 = \tfrac{2}{3}(32) + \tfrac{1}{3}(-1) = \tfrac{64 - 1}{3} = 21$.

Option B (11) is the most tempting error: it is $f(4)$, the result of stopping one level early, and it is also what you get by wrongly taking $f(0) = 0$. Option C (8) is the plain Fibonacci value obtained by dropping the factor of 2. Option D (43) is $f(6)$, one level too far.

Note that the call count grows quickly: $f(5)$ makes 15 calls in total, because every call with $n \ge 2$ spawns two more, which is why memoization matters for recurrences like this one.

f(5) = 21 (option A).

range(1, 20) produces the integers 1 through 19; the upper bound 20 is excluded. For each $i$ the first test asks whether $i$ is a multiple of 3 and odd; only when that test fails does the elif ask whether $i$ is a multiple of 7.

Multiples of 3 in range: 3, 6, 9, 12, 15, 18. The odd ones are 3, 9 and 15, so the first branch adds $3+9+15 = 27$. The even multiples 6, 12 and 18 fail the first test and then fail the elif (none is a multiple of 7), so they contribute nothing.

Multiples of 7 in range: 7 and 14. Neither is a multiple of 3, so each reaches the elif and is subtracted: $27-7-14 = 6$. The value 21 would satisfy both tests, but it lies outside the range.

So the program prints 6.

Check by running the loop in order and watching total: after $i = 3$ it is 3; after 7 it is −4; after 9 it is 5; after 14 it is −9; after 15 it is 6; no later value of $i$ changes it.

Common slips: including $i = 20$ (the range is exclusive at the top), forgetting the != 0 odd test and adding all six multiples of 3 (which would give 42), or subtracting 21.

6

The pivot is a[6] = 6, and i starts at −1. The loop invariant is that a[lo..i] holds keys at most the pivot and a[i+1..j-1] holds keys greater than it.

• j = 0: 7 ≤ 6 is false; no swap.
• j = 1: 2 ≤ 6 is true; i becomes 0; swap a[0] and a[1]: [2, 7, 9, 4, 3, 8, 6].
• j = 2: 9 ≤ 6 is false.
• j = 3: 4 ≤ 6 is true; i becomes 1; swap a[1] and a[3]: [2, 4, 9, 7, 3, 8, 6].
• j = 4: 3 ≤ 6 is true; i becomes 2; swap a[2] and a[4]: [2, 4, 3, 7, 9, 8, 6].
• j = 5: 8 ≤ 6 is false.

After the loop, swap a[i+1] = a[3] with the pivot at a[6]: [2, 4, 3, 6, 9, 8, 7], and the function returns 3. Check the invariant: everything left of index 3 (2, 4, 3) is at most 6 and everything right of it (9, 8, 7) is greater, so 6 is in its final sorted position.

(b) The loop runs for j = 0 to j = 5, one comparison each: 6 comparisons, which is $n-1$ for $n = 7$ elements.

(c) Quicksort recurses on a[0..2] = [2, 4, 3] and a[4..6] = [9, 8, 7]. If the input is already sorted (or reverse sorted), the last element is always the largest (or smallest) key, so every partition splits the array into $n-1$ elements and 0 elements. The comparisons then total $(n-1) + (n-2) + \dots + 1 = n(n-1)/2$, which is $O(n^2)$, versus the $O(n \log n)$ average when the pivots split the array roughly evenly.

(a) Final array [2, 4, 3, 6, 9, 8, 7], returned index 3; (b) 6 comparisons; (c) subarrays [2, 4, 3] and [9, 8, 7]; sorted or reverse-sorted input gives $O(n^2)$.