Data structures worksheet with answers

In a graph, what is a cycle?

1. AAn edge with a weight of zero
2. BA path that visits every vertex
3. CA path that starts and ends at the same vertex
4. DA vertex with no edges

In a singly linked list, each node contains:

1. AOnly data
2. BData and an index
3. CData and a reference to the next node
4. DData and references to all other nodes

What is a deque (double-ended queue)?

1. AA structure that allows insertion and removal at both ends
2. BA queue that only allows removal at the back
3. CA queue sorted by priority
4. DTwo separate queues sharing one array

A node in a binary search tree has a right subtree. Where is its in-order successor?

1. AThe rightmost node of its left subtree
2. BThe leftmost node of its right subtree
3. CIts right child, always
4. DIts parent, always

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²)

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. BVisit every leaf and compare them
3. CLook at the root only
4. DFollow right children from the root until there is no right child

Why can elements not simply be deleted from a standard Bloom filter by clearing their bits?

1. AThose bits may also belong to other elements, which would cause false negatives
2. BDeleting would increase the false positive rate to 100%
3. CBloom filters store the full elements, and these cannot be located again once hashed
4. DBits in a Bloom filter cannot be changed after creation

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

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