Data structures worksheet with answers

How many edges does a tree with n nodes have?

1. An − 1
2. Bn
3. C2n
4. Dn + 1

Which structure is typically used to implement a priority queue?

1. AA stack
2. BA string
3. CA singly linked list without order
4. DA heap

What does a map (dictionary) store?

1. AOnly values in insertion order
2. BValues sorted by size
3. CPairs of equal keys
4. DKey-value pairs with unique keys

How do you find the minimum key in a binary search tree?

1. AFollow left children from the root until there is no left child
2. BLook at the root only
3. CFollow right children from the root until there is no right child
4. DVisit every leaf and compare them

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(n), because later elements must shift
4. DO(log n), because of binary search

Why can a binary heap be stored in an array without any pointers?

1. AArrays automatically keep the keys in sorted order, so no pointers are needed
2. BHeaps never contain more than 100 elements
3. CIt is a complete binary tree, so positions follow simple index formulas
4. DAll keys in a heap are equal

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

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

For a hash table to work correctly, which rule must hash and equality follow?

1. AEqual hash values imply equal keys
2. BEqual keys must have equal hash values
3. CHash values must be prime numbers
4. DDifferent keys must have different hash values