Data structures worksheet with answers

In which order does a preorder traversal of a binary tree visit nodes?

1. ALevel by level from the top
2. BLeft subtree, then node, then right subtree
3. CLeft subtree, then right subtree, then node
4. DNode, then left subtree, then right subtree

What is the max-heap property?

1. AEvery parent's key is greater than or equal to its children's keys
2. BThe keys are sorted from left to right
3. CAll leaves contain the maximum key
4. DEvery left child's key is greater than or equal to its right sibling's key

A hash table stores data as:

1. AKey–value pairs located by a hash function
2. BA tree with ordered keys
3. CA sorted list only
4. DA fixed-length string

A binary tree has root 1 with left child 2 and right child 3; node 2 has children 4 (left) and 5 (right). What is the preorder traversal?

1. A1 2 3 4 5
2. B4 5 2 3 1
3. C4 2 5 1 3
4. D1 2 4 5 3

A trie (prefix tree) is especially efficient for:

1. APrefix searches such as autocomplete
2. BFinding shortest paths
3. CStoring matrices
4. DSorting numbers

An in-order traversal of a binary search tree visits the keys in:

1. AAscending sorted order
2. BLevel order
3. CInsertion order
4. DDescending order always

The time complexity of decrease-key in a binary heap (given the element's position) is:

1. AO(1)
2. BO(log n)
3. CO(n)
4. DO(n log n)

Which structure lets you compute the maximum of every window of size k in an array in O(n) total?

1. AA sorted array updated by shifting
2. BA singly linked list of the window's elements
3. CA min-heap rebuilt for every window
4. DA deque holding indices in decreasing order of value