CS 205 Research Instruments Guide

for (int i = 1; i < n; i = i * 2) {
    System.out.println(i);
}

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

Answer: C — O(log n)

The loop variable doubles each iteration (i = i * 2), so it takes log₂(n) iterations to reach n. Distractor A is tempting because students often assume all single loops are O(n).

1. For all input sizes n > 0
2. For sufficiently large n (beyond some threshold)
3. Only when n > 1000
4. Never — Big-O doesn't predict actual running time

Answer: B

Big-O describes asymptotic behavior — it guarantees the relationship holds for sufficiently large n, but not for all n (constant factors matter for small inputs). Distractor D is partially true but overstates the case.

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

Answer: B — O(log n)

Binary search on a sorted array runs in O(log n). Distractor C (linear search) ignores that the array is sorted. Distractor A would only apply to direct index access.

1. ArrayList (dynamic array)
2. Singly linked list with head pointer
3. Sorted array
4. Binary search tree

Answer: B

A singly linked list with a head pointer supports O(1) insert and remove at the front. An ArrayList requires O(n) shifting for front insertions. This tests whether students understand the cost tradeoffs, not just definitions.

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

Answer: B

Stack is LIFO. After pushing 1-5, the stack top-to-bottom is 5,4,3,2,1. Three pops remove 5, 4, 3. Top is now 2. Tests basic LIFO understanding through tracing.

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

Answer: B — 3 elements

Elements are at indices 3, 4, 0 (wrapping around). Count = (1 - 3 + 5) % 5 = 3. This is a common point of confusion for students learning circular arrays.

1. Insert at front
2. Insert at back
3. Remove from back
4. Access the first element

Answer: C

Removing from the back of a singly linked list requires traversing to the second-to-last node (O(n)), since there's no previous pointer. A doubly linked list can follow tail.prev in O(1). Both A, B, and D are O(1) for both structures with head+tail pointers.

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

1. 5
2. 15
3. 120
4. 25

Answer: C — 120

This computes n! (factorial). 5! = 5 × 4 × 3 × 2 × 1 = 120. Tests ability to trace recursion. Distractor B (15) might come from adding instead of multiplying.

1. It returns 0
2. It runs forever without any error
3. It causes a StackOverflowError
4. The compiler rejects it

Answer: C

Each recursive call adds a frame to the call stack. Without a base case, calls never stop, and the stack eventually overflows. Distractor B is wrong because the stack is finite. Distractor D is wrong because missing a base case is a runtime error, not a compile error.

        8
       / \
      3   10
     / \    \
    1   6    14

1. 8, 3, 1, 6, 10, 14
2. 1, 3, 6, 8, 10, 14
3. 1, 6, 3, 14, 10, 8
4. 8, 3, 10, 1, 6, 14

Answer: B — 1, 3, 6, 8, 10, 14

In-order traversal of a BST visits nodes in sorted order (left, root, right). Distractor A is pre-order. Distractor D is level-order. This tests both traversal knowledge and BST properties.

1. Left child of 6
2. Right child of 6
3. Left child of 8
4. Right child of 3

Answer: A — Left child of 6

5 < 8 (go left to 3), 5 > 3 (go right to 6), 5 < 6 (go left — empty slot). Tests BST insertion logic by tracing the path.

1. h + 1
2. 2h
3. 2^h+1 - 1
4. 2^h

Answer: C — 2^h+1 - 1

A complete binary tree of height h has 2^h+1 - 1 nodes (assuming height of root = 0). Distractor A is the minimum for a "stick" tree. Tests understanding of tree structure bounds.

1. In a min-heap, every node is smaller than its children; in a BST, left child < parent < right child
2. A min-heap is always balanced; a BST is always balanced
3. A min-heap supports O(1) search; a BST supports O(log n) search
4. They are the same data structure with different names

Answer: A

The heap property (parent ≤ children) is different from the BST property (left < parent < right). Distractor B is wrong — BSTs are not always balanced. Distractor C is wrong — heap search is O(n). Tests understanding of structural vs. ordering properties.

1. 1
2. 2
3. 3
4. 0

Answer: C — 3

12 % 10 = 2, 22 % 10 = 2, 32 % 10 = 2. All three hash to index 2. With chaining, they form a linked list at that slot. Tests collision understanding.

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

Answer: A — O(1)

With a good hash function and low load factor, collisions are rare, giving average O(1) lookup. The question specifies "average-case" and "good hash function" to be precise. Distractor C is the worst case (all keys in one bucket).

1. Depth-First Search (DFS)
2. Breadth-First Search (BFS)
3. Either DFS or BFS — both find shortest paths
4. Neither — you need Dijkstra's algorithm

Answer: B — BFS

BFS explores nodes level by level, so the first time it reaches a node, that's the shortest path (in an unweighted graph). DFS may find a path, but not necessarily the shortest. Dijkstra is for weighted graphs. This is a critical conceptual distinction.

1. A sparse graph
2. A complete graph
3. A tree
4. An impossible graph

Answer: B — A complete graph

A complete undirected graph with n vertices has n(n-1)/2 edges = 6×5/2 = 15. A tree with 6 vertices would have exactly 5 edges. Tests knowledge of graph properties and formulas.

1. O(V)
2. O(E)
3. O(V²)
4. O(V + E)

Answer: C — O(V²)

An adjacency matrix is a V × V 2D array, regardless of how many edges exist. O(V + E) is the space for an adjacency list. Tests understanding of representation tradeoffs.

1. QuickSort
2. MergeSort
3. Bubble Sort
4. Insertion Sort

Answer: B — MergeSort

MergeSort is O(n log n) in all cases (best, average, worst). QuickSort's worst case is O(n²) — a critical distinction that students often miss. Bubble Sort and Insertion Sort are O(n²) worst case.

1. MergeSort
2. QuickSort (random pivot)
3. Insertion Sort
4. Selection Sort

Answer: C — Insertion Sort

Insertion Sort runs in O(n) on nearly-sorted data because almost no shifting is needed. MergeSort and QuickSort still do O(n log n) regardless. This tests understanding of best-case behavior, not just worst-case.