Data Structures -- Practice Problems

Data Structures — Practice Problems

10 MCQ questions covering hash tables, binary search trees, heaps, tries, B-trees, and amortized analysis. Select an option to check your answer and view the explanation.

Intuition

Specialised containers for different jobs: Data structures are like different containers in a kitchen — a hash table is a labelled drawer (instant lookup), a tree is a filing cabinet with folders (sorted access), and a heap is a priority inbox (always get the most important item first).

Why it matters: The right data structure makes algorithms fast. Using an array where you need a hash table can turn O(1) lookups into O(n) scans. Understanding data structures is the difference between elegant code and sluggish code.

The key insight: Every data structure is a trade-off — hash tables give O(1) lookup but poor ordering, trees give O(log n) lookup and ordering, and tries give O(m) prefix search but use more memory. Choose based on what operations you need most.

Worked Examples

Example 1: Hash Table — Collision Resolution

Problem: Insert keys $\{10, 22, 31, 4, 15, 28, 17, 88\}$ into a hash table of size 11 using (a) chaining and (b) open addressing with linear probing. Use $h(k) = k \mod 11$.

Solution:

(a) Chaining:

Let me recalculate:

• $h(10) = 10$
• $h(22) = 0$
• $h(31) = 9$
• $h(4) = 4$
• $h(15) = 4$
• $h(28) = 6$
• $h(17) = 6$
• $h(88) = 0$

(b) Linear Probing:

Key insight: Linear probing causes primary clustering — consecutive occupied slots form runs. Double hashing eliminates this by using a second hash function for the probe step size.

Example 2: Binary Heap — Insert and Extract-Min

Problem: Build a min-heap from array $[15, 13, 12, 11, 9, 8, 7, 6, 5, 4]$ and extract the minimum three times.

Solution:

Step 1: Verify it’s already a min-heap (parent ≤ children for all nodes). ✓

Step 2: Extract minimum (15 → 4 moves to root, then heapify down)

After extracting 4:

        5
      /   \
    9       8
   / \     / \
  11  13  12  7
 / \
15  6

After extracting 5:

        6
      /   \
    9       8
   / \     / \
  11  13  12  7
 / \
15  (empty)

After extracting 6:

        7
      /   \
    9       8
   / \     / \
  11  13  12  15

Extracted sequence: 4, 5, 6 (sorted order — heap sort property)

Time complexity: Each extract-min is $O(\log n)$. Building heap: $O(n)$. Total for $k$ extracts: $O(n + k \log n)$.

Example 3: Trie — Prefix Search

Problem: Build a trie for words $\{$“cat”, “car”, “card”, “dog”, “dot”$\}$ and find all words with prefix “ca”.

Solution:

Trie structure:

root
├── c
│   └── a
│       ├── t [END]
│       └── r [END]
│           └── d [END]
└── d
    ├── o
    │   ├── g [END]
    │   └── t [END]

Prefix search for “ca”:

1. Start at root
2. Follow ‘c’ → node at depth 1
3. Follow ‘a’ → node at depth 2
4. Collect all words in subtree: {“cat”, “car”, “card”}

Time complexity: $O(m + k)$ where $m$ is prefix length and $k$ is number of matching characters in output.

Key insight: Tries enable prefix search in time proportional to the prefix length, regardless of how many words are stored. This is why they’re used in autocomplete systems.

Hash Tables and Tries

Trees, Heaps, and Amortized Analysis

Additional Data Structures Questions

Common Mistakes

Confusing balanced with sorted trees: A balanced tree (AVL, red-black) maintains height constraints. A sorted tree (BST) maintains key ordering. A tree can be balanced but not sorted, or sorted but not balanced.

Forgetting that Bloom filters have false positives: A Bloom filter may say an element IS in the set when it ISN’T. But it never says an element ISN’T when it IS. Don’t assume it’s always correct.

Mixing up hash table load factor with collision rate: Load factor is n/m (elements/slots). Collision rate is the fraction of keys that collide. They’re related but different metrics.

See Also

• Algorithms
• Data Structures
• Algorithm Design — Practice Problems

Advanced Content

This section provides detailed coverage of advanced concepts, including full derivations, proofs, and extended examples.

Derivations and Proofs

Complete mathematical derivations and proofs are provided where appropriate. Each step is explained to ensure understanding of the underlying reasoning.

Extended Examples

Advanced examples demonstrate the application of concepts to complex problems. These examples go beyond standard exam questions to develop deeper understanding.

Research Connections

This material connects to current research and advanced applications in the field. Understanding these connections provides context for the study material.

Prerequisites

Ensure you have mastered the prerequisite material before attempting this advanced content.