Data structures worksheet with answers

What does each node in a doubly linked list contain?

1. AData and a pointer to the next node only
2. BData and two pointers, one to the next node and one to the node after that
3. CData, a pointer to the next node and a pointer to the previous node
4. DTwo copies of the data and one pointer

What defines a binary tree?

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

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

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

1. A1 2 4 5 3
2. B4 2 5 1 3
3. C4 5 2 3 1
4. D1 2 3 4 5

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

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

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

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

Which data structure supports an LRU (least recently used) cache with O(1) get and put?

1. AA single sorted array
2. BA binary search tree only
3. CA stack only
4. DA hash map combined with a doubly linked list

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

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