Data structures worksheet with answers

The depth of a node in a tree is:

1. AThe number of children of that node
2. BThe number of edges from that node to the deepest leaf
3. CThe number of edges from the root to that node
4. DThe number of nodes in its subtree

Which operation is O(1) for an array but O(n) for a singly linked list?

1. AAccessing the element at index i
2. BInserting at the head
3. CReading the first element
4. DRemoving the head element

What is the load factor of a hash table?

1. AThe time needed to load the table from disk
2. BThe number of collisions so far
3. CThe number of stored elements divided by the number of buckets
4. DThe number of buckets divided by the average length of the keys stored

What happens when a hash table rehashes after its load factor exceeds a threshold?

1. AThe existing keys are sorted in place
2. BThe oldest keys are deleted to make room
3. CA larger table is allocated and every key is inserted again
4. DOnly the colliding keys are moved to a new overflow list at the end of the table

Why is traversing an array often much faster in practice than traversing a linked list of the same length?

1. AArray elements are contiguous, so they make good use of the CPU cache
2. BLinked lists always store elements on disk
3. CArray traversal is O(1) in total, while linked list traversal is O(n)
4. DArrays use fewer instructions to compare values

Which collision resolution method stores colliding keys in a list at the same bucket?

1. ASeparate chaining
2. BLinear probing
3. CQuadratic probing
4. DDouble hashing

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

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

What guarantee do the red-black tree rules give about the height of a tree with n keys?

1. AThe height is at most 2 log₂(n + 1)
2. BThe height is at most n / 2
3. CThe height is exactly log₂ n
4. DThe height is at most log₂ n + 1