CS 205 Shared Quiz Plan

1. int arr = new int(10);
2. int[] arr = new int[10];
3. int arr[] = int[10];
4. array int[10] = new array;

Answer: B — int[] arr = new int[10];

Square brackets on the type (int[]), allocated with new and size in brackets. Option A uses parentheses. Option C is missing 'new'.

1. An IndexOutOfBoundsException is thrown
2. The element is added to a separate overflow area
3. A new array of larger capacity is created, all elements are copied, then the new element is added
4. The array automatically grows by exactly one slot

Answer: C

Dynamic arrays typically double capacity when full. All elements are copied — O(n) operation, amortized O(1).

1. O(1)
2. O(log n)
3. O(n)
4. O(n²)

Answer: C — O(n)

Inserting at index 0 requires shifting all n elements one position right. Arrays are poor for front insertions — linked lists handle this in O(1).

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        System.out.println(i + j);
    }
}

1. O(n)
2. O(n log n)
3. O(n²)
4. O(2n)

Answer: C — O(n²)

Outer loop runs n times × inner loop runs n times = n² total iterations.

int[] doubleArray(int[] arr) {
    int[] result = new int[arr.length];
    for (int i = 0; i < arr.length; i++) {
        result[i] = arr[i] * 2;
    }
    return result;
}

1. O(1)
2. O(log n)
3. O(n)
4. O(n²)

Answer: C — O(n)

Allocates a new array of size n. The loop variable is O(1) extra. Total additional space: O(n).

1. Set C.next = null
2. Set B.next = D
3. Set D.next = B
4. Set A.next = D

Answer: B — Set B.next = D

To remove C, bypass it by pointing its predecessor (B) to its successor (D). This is why deletion in a singly linked list requires access to the previous node.

1. Faster access to elements by index
2. Less memory usage per element
3. O(1) insertion at the front without shifting
4. Better cache performance

Answer: C

Inserting at the front of a linked list is O(1) — just create a new node and point it to the old head. Arrays require shifting all elements. Arrays win on index access, memory density, and cache performance.

1. Insert at front
2. Get the first element
3. Remove the last element
4. Check if the list is empty

Answer: C

Removing the last element requires updating the second-to-last node's next pointer. In a doubly linked list, tail.prev gives you that node in O(1). A singly linked list must traverse the entire list to find it.

int f(int n) {
    if (n == 0) return 0;
    return n + f(n - 1);
}

1. 4
2. 6
3. 10
4. 24

Answer: C — 10

f(4) = 4 + f(3) = 4 + 3 + f(2) = 4 + 3 + 2 + f(1) = 4 + 3 + 2 + 1 + f(0) = 4+3+2+1+0 = 10. This computes the sum 1+2+...+n.

int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}

1. 15
2. 24
3. 120
4. 720

Answer: C — 120

factorial(5) = 5 × 4 × 3 × 2 × 1 = 120.

void countdown(int n) {
    System.out.println(n);
    countdown(n - 1);
}

1. Prints 5, 4, 3, 2, 1, 0 and stops
2. Prints 5, 4, 3, 2, 1 and stops
3. Prints 5 once and stops
4. Prints numbers until a StackOverflowError occurs

Answer: D — StackOverflowError

There is no base case to stop the recursion. The method keeps calling itself forever (5, 4, 3, … 0, -1, -2, …) until the call stack overflows. Every recursive method needs a base case.

int power(int base, int exp) {
    if (exp == 0) return 1;
    return base * power(base, exp - 1);
}

1. 10
2. 25
3. 32
4. 64

Answer: C — 32

power(2,5) = 2 × power(2,4) = 2 × 2 × power(2,3) = … = 2⁵ = 32. Each recursive call multiplies base one more time, and the base case (exp == 0) returns 1.

int fib(int n) {
    if (n <= 1) return n;
    return fib(n-1) + fib(n-2);
}

1. 2
2. 3
3. 5
4. 8

Answer: C — 5 times

Drawing the recursion tree: fib(5) branches into fib(4)+fib(3), which further branches. The base cases (n=0 or n=1) are reached 5 times total: fib(1) is called 3 times, fib(0) is called 2 times.

1. O(n)
2. O(n²)
3. O(2ⁿ)
4. O(n log n)

Answer: C — O(2ⁿ)

Each call branches into two recursive calls, creating a binary tree of calls. The tree has roughly 2ⁿ nodes. This is why memoization or dynamic programming is essential for Fibonacci.

1. Encapsulation
2. Memoization
3. Polymorphism
4. Garbage collection

Answer: B — Memoization

Memoization stores the results of expensive function calls and returns the cached result when the same inputs occur again. It converts the exponential Fibonacci into O(n) by avoiding redundant computation.

1. Recursion is always faster than iteration
2. Any recursive solution can be rewritten iteratively (and vice versa)
3. Recursion uses less memory than iteration
4. Iteration cannot solve problems that recursion can

Answer: B

Recursion and iteration are equally powerful — any recursive algorithm can be converted to an iterative one (often using an explicit stack) and vice versa. Recursion is often more elegant for problems with recursive structure (trees, divide-and-conquer), but iteration typically uses less memory since it avoids call stack overhead.

1. Queue
2. Stack
3. Array
4. Linked List

Answer: B — Stack

Push each opening paren onto the stack. When you see a closing paren, pop and check for a match. If the stack is empty at the end with no mismatches, the expression is balanced. LIFO order naturally matches nested structures.

1. A
2. B
3. C
4. E

Answer: B

After push A,B,C,D: stack = [A,B,C,D] (D on top). Pop twice removes D, C: stack = [A,B]. Push E: stack = [A,B,E]. Pop once removes E: stack = [A,B]. Top = B.

1. Push: O(1), Pop: O(n)
2. Push: O(n), Pop: O(1)
3. Push: O(1), Pop: O(1)
4. Push: O(n), Pop: O(n)

Answer: C — Both O(1)

With a linked list, push adds a node at the head (O(1)) and pop removes the head node (O(1)). No shifting or resizing needed.

1. 9
2. 10
3. 14
4. 24

Answer: C — 14

Push 3, push 4. See +: pop 4 and 3, compute 3+4=7, push 7. Push 2. See *: pop 2 and 7, compute 7*2=14, push 14. Result = 14.

1. Last In, First Out (LIFO)
2. First In, First Out (FIFO)
3. Highest priority first
4. Random access

Answer: B — FIFO

A queue processes elements in the order they arrive, like a line at a store. LIFO describes a stack. Highest priority first describes a priority queue.

1. A
2. B
3. C
4. D

Answer: C

FIFO: enqueue A,B,C,D (front=A, rear=D). Dequeue removes A, then B. Front is now C.

1. 2
2. 4
3. 3
4. 6

Answer: B — 4

Elements at indices 4, 5, 0, 1 (wrapping around). Count = (2 - 4 + 6) % 6 = 4. The formula (rear - front + capacity) % capacity handles the wrap-around.

1. Undo/redo in a text editor
2. Print jobs waiting to be processed
3. Evaluating a mathematical expression
4. Browser back button history

Answer: B

Print jobs are processed in the order received (FIFO) — a perfect queue application. Undo/redo and browser history are stacks (LIFO). Expression evaluation uses a stack.

1. Root
2. Internal node
3. Leaf
4. Subtree

Answer: C — Leaf

A leaf node has no children (both left and right child are null). An internal node has at least one child. The root is the topmost node.

      5
     / \
    3   8
   / \
  1   4

1. 1, 3, 4, 5, 8
2. 5, 3, 1, 4, 8
3. 1, 4, 3, 8, 5
4. 5, 3, 8, 1, 4

Answer: B — 5, 3, 1, 4, 8

Pre-order visits: root, left subtree, right subtree. So: 5 (root), then 3, 1, 4 (left subtree), then 8 (right subtree). Option A is in-order.

1. 2
2. 3
3. 4
4. 6

Answer: A — 2

A complete binary tree minimizes height. Height 2 gives 3 levels (0, 1, 2) with a maximum of 1 + 2 + 4 = 7 nodes — exactly 7. A perfectly complete binary tree of height 2 fits all 7 nodes. Height 1 can hold at most 3 nodes, so height 2 is the minimum.

1. Pre-order
2. In-order
3. Post-order
4. Level-order

Answer: B — In-order

In-order (left, root, right) visits BST nodes in ascending sorted order. This is a key property of BSTs and one of the most important things to know about tree traversals.

1. 5 (first inserted)
2. 1 (lowest priority value)
3. 8 (highest priority value)
4. 4 (last inserted)

Answer: B — 1

A min-priority queue always removes the element with the smallest priority value, regardless of insertion order. Unlike a regular queue (FIFO), priority determines the exit order.

1. O(1)
2. O(log n)
3. O(n)
4. O(n log n)

Answer: B — O(log n)

Insert adds the element at the bottom of the heap, then "bubbles up" to restore the heap property. The maximum number of swaps is the height of the tree = log n.

1. Customers waiting in a checkout line
2. Emergency room patients triaged by severity
3. Undo history in a text editor
4. Browsing web pages in order visited

Answer: B

ER patients are seen based on severity (priority), not arrival order. A checkout line is a regular queue (FIFO). Undo history is a stack. Web browsing history is a stack.

1. O(1)
2. O(log n)
3. O(n)
4. O(n log n)

Answer: A — O(1)

The minimum element is always at the root of a min-heap. You simply read the first element of the array. Removing it is O(log n), but just finding it is O(1).

1. [1, 3, 5, 7, 9, 8, 6]
2. [1, 5, 3, 7, 8, 9, 6]
3. [3, 1, 5, 7, 9, 8, 6]
4. [1, 3, 5, 4, 7, 8, 6]

Answer: A

In a min-heap, every parent must be ≤ its children. For index i: left child = 2i+1, right child = 2i+2. Option A: 1≤3, 1≤5, 3≤7, 3≤9, 5≤8, 5≤6 — all valid. Option C fails because 3 > 1 (root is not minimum).

1. Bubble up from the root
2. Bubble down (sift down) from the root
3. Sort the entire array
4. Rebuild the heap from scratch

Answer: B — Bubble down from the root

After removal, the last element is moved to the root, then "bubbled down" by swapping with its smaller child until the heap property is restored. This takes O(log n). Rebuilding from scratch would be O(n) — unnecessary.

1. O(n log n)
2. O(n²)
3. O(n)
4. O(log n)

Answer: C — O(n)

The bottom-up heapify approach starts from the last non-leaf and sifts down each node. Although it seems like it should be O(n log n), the mathematical analysis shows most nodes are near the bottom and require few swaps. The total work sums to O(n).

1. i / 2
2. (i - 1) / 2
3. 2 * i + 1
4. i - 1

Answer: B — (i - 1) / 2

For 0-based indexing: parent = (i-1)/2 (integer division), left child = 2i+1, right child = 2i+2. For 1-based indexing, parent = i/2. This is a fundamental heap formula.

1. Slot 0
2. Slot 1
3. Slot 3
4. Slot 5

Answer: C — Slot 3

10 % 7 = 3, 17 % 7 = 3, 24 % 7 = 3. All three hash to slot 3. With chaining, they form a linked list at that slot.

1. Performance improves because more slots are utilized
2. Performance degrades because collisions become more frequent
3. Performance is unaffected by load factor
4. The hash table automatically prevents high load factors

Answer: B

Higher load factor = more elements per slot on average = more collisions = longer chains (or more probing). This is why hash tables resize when load factor exceeds a threshold (typically 0.75 in Java).

1. O(1)
2. O(log n)
3. O(n)
4. O(n log n)

Answer: C — O(n)

In the worst case, all keys hash to the same bucket, creating one long chain of length n. Searching that chain is O(n). (Java 8+ converts long chains to balanced trees, making worst case O(log n), but the classic answer is O(n).)

1. ArrayList of student-grade pairs
2. Sorted array with binary search
3. HashMap
4. LinkedList of student-grade pairs

Answer: C — HashMap

HashMap provides O(1) average-case lookup by key. An ArrayList or LinkedList would require O(n) linear search. A sorted array gives O(log n) with binary search but O(n) for insertions.

1. 3
2. 7
3. 4
4. 1

Answer: B — 7

5 becomes the root. 3 < 5, goes left. 7 > 5, goes right. So the right child of the root (5) is 7. Then 1 and 4 go into the left subtree under 3.

1. O(1)
2. O(log n)
3. O(n)
4. O(n log n)

Answer: C — O(n)

If elements are inserted in sorted order (e.g., 1,2,3,4,5), the BST degenerates into a linked list (all right children). Search becomes O(n). Balanced BSTs (AVL, Red-Black) guarantee O(log n) worst case.

1. Faster average lookup time
2. Keys are stored in sorted order
3. Uses less memory
4. Handles collisions better

Answer: B — Keys are stored in sorted order

TreeMap is backed by a Red-Black tree, so keys are always sorted. This allows operations like finding the smallest key, range queries, and ordered iteration. HashMap is faster for lookup (O(1) vs O(log n)) but doesn't maintain order.

1. Its parent's value
2. The in-order successor (smallest value in right subtree)
3. The largest value in the tree
4. The average of its two children

Answer: B

The in-order successor (smallest value in the right subtree) maintains the BST property because it's larger than everything in the left subtree and smaller than everything else in the right subtree. The in-order predecessor (largest in left subtree) also works.

1. Sorted input and constant space
2. Optimal substructure and overlapping subproblems
3. Linear time and logarithmic space
4. Divide-and-conquer and greedy choice

Answer: B

Optimal substructure means the optimal solution contains optimal solutions to subproblems. Overlapping subproblems means the same subproblems are solved repeatedly. When both exist, DP avoids redundant computation by storing results.

1. It uses too much memory
2. It recalculates the same subproblems many times
3. It has too many base cases
4. The recursive calls are too deep

Answer: B

Naive recursion recomputes fib(k) many times for each k. For example, fib(3) is computed multiple times when calculating fib(5). DP stores each result once, eliminating this redundancy.

1. The final answer and working backward
2. The base cases and building up to the final answer
3. Random entries in any order
4. The middle of the table outward

Answer: B

Bottom-up DP starts from the smallest subproblems (base cases) and iteratively builds up to the desired answer. This contrasts with top-down (memoized recursion), which starts from the final problem and recurses down to base cases.

1. 2 coins (5 + 6)
2. 3 coins (5 + 5 + 1)
3. 6 coins (all 1s + one 5)
4. 11 coins (all 1s)

Answer: A — 2 coins (5 + 6)

A greedy approach (always pick the largest coin) would choose 6 + 5 = 11 in 2 coins, which happens to be optimal here. But greedy doesn't always work for coin change — DP systematically finds the true minimum by building up from smaller amounts.