CS50x: Introduction to Computer Science Data Structures Flashcards

24 sample cards from the Data Structures deck

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

1. What three fields does a BST node contain?

   A value, a pointer to the left child (struct node *left), and a pointer to the right child (struct node *right); absent children are NULL.

2. Describe the recursive procedure for searching a BST for a value $x$.

   If the current node is NULL, return false (not found). If $x$ equals the node's value, return true. If $x$ is less than the value, recursively search the left subtree; if greater, recursively search the right subtree — discarding half the remaining tree at each step (when balanced).

3. What is the search time complexity of a balanced BST with $n$ nodes, and why?

   $O(\log n)$, because a balanced tree of $n$ nodes has height about $\log_{2} n$, and each comparison descends one level, halving the search space.

4. What is the worst-case shape of a BST, when does it arise, and what is search time then?

   A degenerate (unbalanced) tree that is effectively a linked list — e.g., when keys are inserted in already-sorted order, every node has only one child. Search degrades to $O(n)$.

5. Which traversal of a BST visits the values in sorted (ascending) order, and what is its recursive pattern?

   In-order traversal: recursively visit the left subtree, then the current node, then the right subtree. The BST property guarantees this yields the values in ascending order.

6. Compare a BST to a sorted array for the combination of searching and inserting.

   Both search in $O(\log n)$ (balanced BST vs. binary search on the array). But insertion into a balanced BST is $O(\log n)$, while inserting into a sorted array is $O(n)$ because elements must shift; the BST keeps data dynamic without wholesale copying.

7. What is a trie, and where does its name come from?

   A trie is a tree in which each key is stored implicitly as a path of characters from the root, one character per level — a tree of arrays of pointers. The name comes from 'retrieval' (pronounced 'try').

8. In a CS50-style trie storing lowercase English words, what does each node contain?

   An array of $26$ pointers to child nodes (one per letter $a$–$z$) and a boolean flag such as is_word marking whether the path from the root to this node spells a complete stored word.

9. What is the lookup time in a trie for a key of length $k$ stored among $n$ keys?

   $O(k)$ — you follow one pointer per character of the key. Crucially this is independent of $n$: lookup takes the same time whether the trie holds ten words or ten million, effectively constant time for bounded-length keys such as names.

10. What is the main disadvantage of a trie?

    Enormous memory usage: every node allocates an entire array of child pointers (e.g., $26$ per node for letters), most of which are NULL, so tries trade large amounts of space for very fast lookups.

11. How do you insert the word 'cat' into an (initially empty) lowercase-letter trie?

    Starting at the root, follow (creating if NULL) the child pointer for 'c', then from that node for 'a', then for 't'; at the final node set the is_word flag to true. Shared prefixes (like 'car' and 'cat') reuse the same initial path.

12. What is a hash function?

    A function that takes input data (e.g., a string key) and deterministically returns a nonnegative integer — the hash code — used as an index (bucket number) into a hash table's array.

13. Name three properties a good hash function for a hash table should have.

    (1) Deterministic: the same input always yields the same index. (2) Uniform: it spreads keys evenly across buckets to minimize collisions. (3) It outputs only valid indices (e.g., via taking the value $\bmod$ the array size) and is fast to compute.

14. What is a hash table, structurally?

    The combination of an array (the buckets) and a hash function that maps each key to an array index; conceptually, an array of $n$ buckets where element placement is decided by hashing — in CS50, typically an array of linked lists.

15. What is the ideal (average-case) lookup time of a hash table, and its worst case?

    Ideal/average: $O(1)$ — hash the key and go straight to its bucket. Worst case: $O(n)$, when all $n$ keys collide into a single bucket and you must scan a linked list of length $n$.

16. Give the classic simple example of a hash function for names, and its main weakness.

    Hash on the first letter: index $=$ first character $-$ 'A', giving $26$ buckets (like sorting cards into piles). Weakness: highly non-uniform — many names share first letters (and letters like Q or X are rare), producing many collisions and unbalanced buckets.

17. What is a collision in a hash table?

    The event where two different keys hash to the same array index (bucket), so they compete for the same location and the table needs a resolution strategy to store both.

18. Why are collisions unavoidable in general for a hash table?

    By the pigeonhole principle: the number of possible keys is (much) larger than the number of buckets $m$, so once more than $m$ distinct keys are possible, some two keys must map to the same bucket no matter how good the hash function is.

19. What is chaining (separate chaining) as a collision-resolution strategy?

    Each bucket of the hash table holds a pointer to a linked list; all keys that hash to that index are inserted into that bucket's list (typically prepended in $O(1)$). Lookup hashes to the bucket, then linearly searches its chain.

20. With chaining, if $n$ keys are distributed evenly over $k$ buckets, how long is an average lookup, and what is this asymptotically?

    About $\frac{n}{k}$ comparisons on average (the load factor). Since $k$ is a constant, this is still $O(n)$ asymptotically — but in practice a good hash function with enough buckets makes lookups roughly $k$ times faster, approaching constant time.

21. What is linear probing, and what problem can it suffer from?

    An open-addressing alternative to chaining: on a collision, step forward through the array (index $+1, +2, \dots$, wrapping around) until an empty slot is found. It suffers from clustering — runs of occupied slots grow and lengthen future probes — and the table can fill up entirely.

22. Rank these structures by lookup cost for $n$ stored items: unsorted linked list, sorted array (binary search), hash table (average), trie (key length $k$).

    Trie: $O(k)$ (constant in $n$) $\approx$ hash table average: $O(1)$; then sorted array: $O(\log n)$; slowest is the unsorted linked list: $O(n)$. (Hash table worst case degrades to $O(n)$; trie pays with heavy memory use.)

23. Which data structure in CS50 offers lookup time independent of the number of stored elements, and at what cost?

    The trie: lookup is $O(k)$, where $k$ is the key's length, regardless of how many keys are stored. The cost is very large memory consumption, since each node holds a full array of mostly-NULL child pointers.

24. Summarize the core trade-off theme of CS50's data structures lecture: what do you generally exchange when choosing a structure?

    Time versus space (and code complexity): arrays are memory-lean with fast random access but costly to grow; linked lists grow in $O(1)$ but search in $O(n)$; balanced BSTs give $O(\log n)$ dynamic operations; hash tables approach $O(1)$ average lookups; tries achieve $O(k)$ lookups by spending huge amounts of memory.

What this deck covers

Data Structures flashcards FAQ