Data structures worksheet with answers

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

1. ALeft subtree, then node, then right subtree
2. BLeft subtree, then right subtree, then node
3. CNode, then left subtree, then right subtree
4. DRight subtree, then node, then left subtree

Which data structure is most suitable for the "undo" feature in a text editor?

1. AStack
2. BHash set
3. CQueue
4. DGraph

Which data structure works on the principle "first in, first out"?

1. AHeap
2. BQueue
3. CBinary tree
4. DStack

A hash table of size 7 uses h(k) = k mod 7 and linear probing. After inserting 10, where is 17 stored?

1. AIndex 6
2. BIndex 4
3. CIndex 0
4. DIndex 3

In a hash table using open addressing, what is the maximum possible load factor?

1. AThere is no maximum
2. B0.5
3. C2
4. D1

What is the value of the postfix expression 3 4 + 2 * ?

1. A10
2. B14
3. C24
4. D11

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

1. AIt makes the table sorted
2. BDeleted keys must be kept forever for security, so slots can never be reused
3. CEmptying the slot could break the probe sequence for other keys
4. DTombstones speed up hashing

What is the main advantage of a skip list over a sorted linked list?

1. AIt uses no extra memory
2. BExpected O(log n) search by using several levels of forward pointers
3. CIt stores keys without order
4. DGuaranteed O(1) search because every node stores a pointer to every other node