Data structures worksheet with answers

A graph consists of:

1. AOnly a root and leaves
2. BKeys and hashes only
3. CRows and columns
4. DVertices (nodes) connected by edges

In a hash table, what is a collision?

1. AA key cannot be hashed at all
2. BTwo different keys map to the same index
3. CTwo equal keys are stored twice
4. DThe table runs out of memory

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. CLeft subtree, then node, then right subtree
4. DNode, then left subtree, then right subtree

An adjacency matrix for a graph with V vertices uses how much memory?

1. AO(log V)
2. BO(V + E)
3. CO(E)
4. DO(V²)

A queue is implemented with two stacks: push onto an "in" stack, and pop from an "out" stack, refilling it from "in" when empty. What is the amortised cost per operation?

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

Which data structure is used by depth-first search (iterative version)?

1. AA stack
2. BA queue
3. CA heap
4. DA hash table only

A segment tree is typically used to:

1. AImplement a stack
2. BAnswer range queries (such as range sums) and updates in O(log n)
3. CSort strings alphabetically by storing each prefix in a separate tree node
4. DStore a graph's edges

An object is stored as a key in a hash map, and then a field used by its hash function is changed. What is the likely result?

1. AThe map throws an error at the moment the field changes
2. BLooking up the object may fail because it sits in the bucket for its old hash
3. CThe map automatically moves the key to its new bucket
4. DNothing changes, because a key's hash is computed only once when the program starts