Data structures worksheet with answers

What defines a binary tree?

1. AEvery node stores a binary number
2. BThe tree has exactly two levels
3. CEvery node has at most two children
4. DEvery node has exactly two children

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

1. AReading the first element
2. BInserting at the head
3. CAccessing the element at index i
4. DRemoving the head element

A hash table stores data as:

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

What is the cost of inserting an element in the middle of an array of n elements?

1. AO(1), because the index is known
2. BO(n²), because each element moves n times
3. CO(log n), because of binary search
4. DO(n), because later elements must shift

What is the time complexity of searching for a key in a balanced binary search tree?

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

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 postorder traversal?

1. A1 2 4 5 3
2. B5 4 3 2 1
3. C4 5 2 3 1
4. D4 2 5 1 3

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

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

In a hash table using open addressing, why is deletion often done with a "tombstone" marker?

1. ATombstones speed up hashing
2. BIt makes the table sorted
3. CDeleted keys must be kept forever for security, so slots can never be reused
4. DEmptying the slot could break the probe sequence for other keys