CSS Computer Science Algorithms & Data Structures Flashcards

24 sample cards from the Algorithms & Data Structures deck

Sampled from the end of the deck, so these are different cards from the ones shown on the syllabus page.

1. When is linear search preferable to binary search?

   When the data is unsorted, the list is very small, or the data structure does not allow random access (e.g. a linked list).

2. How many comparisons does binary search need in the worst case for n elements?

   ⌊log₂ n⌋ + 1 comparisons, i.e. O(log n).

3. State the time complexity (best/average/worst) and space of Bubble Sort.

   Best O(n) with optimization, average and worst O(n²); space O(1). Stable, in-place.

4. State the time complexity and key property of Selection Sort.

   O(n²) in all cases (best/average/worst); space O(1); in-place; generally NOT stable; performs the minimum number of swaps (O(n)).

5. State the time complexity of Insertion Sort and when it performs best.

   Best O(n) (nearly sorted data), average and worst O(n²); space O(1); stable, in-place. Efficient for small or almost-sorted arrays.

6. State Merge Sort's time complexity, space, stability, and core technique.

   O(n log n) in all cases; space O(n) (needs auxiliary array); stable; uses divide-and-conquer by splitting, recursively sorting, and merging.

7. State Quick Sort's average and worst time complexity, and what causes the worst case.

   Average O(n log n), worst O(n²); space O(log n) for recursion. Worst case occurs with poor pivot choices (e.g. already-sorted data with first/last pivot). In-place, typically not stable.

8. State Heap Sort's time complexity, space, and stability.

   O(n log n) in all cases; space O(1) (in-place); NOT stable. Builds a max-heap then repeatedly extracts the max.

9. What makes a sorting algorithm 'stable'?

   It preserves the relative order of records with equal keys. Examples: Merge Sort, Insertion Sort, Bubble Sort. Unstable: Quick Sort, Heap Sort, Selection Sort.

10. What is the lower bound for comparison-based sorting and why?

    Ω(n log n) comparisons in the worst case, because a comparison sort's decision tree must have n! leaves and a binary tree of n! leaves has height ≥ log₂(n!) = Ω(n log n).

11. What is a hash table and what is its average-case lookup time?

    A data structure mapping keys to values using a hash function to compute an index into a bucket array. Average-case insert/search/delete is O(1); worst case O(n).

12. What is a collision in hashing and name two general resolution strategies.

    A collision occurs when two distinct keys hash to the same index. Resolution: separate chaining (linked lists per bucket) and open addressing (probing for another slot).

13. Compare separate chaining and open addressing for collision resolution.

    Chaining stores colliding elements in a linked list at each bucket (handles high load factors, uses extra pointers). Open addressing stores all elements in the array itself and probes for empty slots (better cache use, but degrades as it fills).

14. Name three open-addressing probing techniques.

    Linear probing (check next slot sequentially), quadratic probing (offsets grow as i²), and double hashing (use a second hash function for the step size).

15. Define the load factor of a hash table and its significance.

    Load factor α = n/m (number of stored elements / number of buckets). Higher α increases collisions; tables are typically resized/rehashed when α exceeds a threshold (e.g. 0.7).

16. What properties make a good hash function?

    It should be deterministic, fast to compute, distribute keys uniformly across buckets, and minimize collisions (avalanche effect).

17. Define a binary tree and the maximum number of nodes at level i (root at level 0).

    A tree where each node has at most two children (left and right). Maximum nodes at level i is 2^i; a tree of height h has at most 2^(h+1) − 1 nodes.

18. What is the defining ordering property of a Binary Search Tree (BST)?

    For every node, all keys in its left subtree are smaller and all keys in its right subtree are larger than the node's key.

19. Which BST traversal yields keys in sorted ascending order, and what is its order of visiting?

    In-order traversal (Left, Root, Right) yields keys in ascending sorted order.

20. Give the time complexity of search/insert/delete in a BST for balanced vs degenerate trees.

    Balanced: O(log n). Degenerate (skewed, like a linked list): O(n). Average for random insertion: O(log n).

21. What is a balanced tree and why is balancing needed?

    A tree whose height is kept O(log n) by limiting the height difference between subtrees. Balancing prevents degeneration into a linked list, guaranteeing O(log n) operations.

22. What is the balance condition of an AVL tree and how is balance restored?

    For every node the heights of its left and right subtrees differ by at most 1 (balance factor ∈ {-1,0,1}). Balance is restored by single or double rotations (LL, RR, LR, RL) after insert/delete.

23. List the key properties of a Red-Black tree.

    1) Every node is red or black. 2) The root is black. 3) Red nodes cannot have red children (no two reds in a row). 4) Every root-to-NULL path has the same number of black nodes (equal black-height). This guarantees O(log n) height.

24. Compare AVL trees and Red-Black trees.

    AVL trees are more strictly balanced, giving faster lookups but more rotations on insert/delete. Red-Black trees are less rigidly balanced, allowing faster insertions/deletions with fewer rotations—preferred when modifications are frequent (e.g. C++ std::map).

What this deck covers

Algorithms & Data Structures flashcards FAQ