Data structures worksheet with answers

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

1. ARight subtree, then node, then left subtree
2. BLeft subtree, then right subtree, then node
3. CNode, then left subtree, then right subtree
4. DLeft subtree, then node, then right subtree

What is the load factor of a hash table?

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

A hash table stores data as:

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

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

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

Which data structure is used to check whether the brackets in "{[()]}" are balanced?

1. AA stack
2. BA queue
3. CA hash table
4. DA binary search tree

In a binary min-heap stored in an array (index starting at 0), the children of the node at index i are at:

1. A2i and 2i + 1
2. B2i + 1 and 2i + 2
3. Ci/2 and i/2 + 1
4. Di + 1 and i + 2

In the BST with root 50, left subtree 30 (children 20, 40) and right subtree 70 (children 60, 80), the root is deleted using the in-order successor. Which key becomes the new root?

1. A70
2. B40
3. C60
4. D80

Which problem of linear probing does double hashing mainly reduce?

1. APrimary clustering, where long runs of occupied slots form
2. BThe need for a hash function
3. CThe need to store keys in the table
4. DThe O(n) cost of reading a key's value