Data structures worksheet with answers

What is the name of the stack operation that adds an element to the top?

1. APop
2. BPush
3. CEnqueue
4. DPeek

In an adjacency list representation of a graph, what is stored for each vertex?

1. AThe shortest path to every other vertex
2. BA list of its neighbouring vertices
3. CA row of V Boolean values
4. DThe total number of edges in the graph

What is the name of the queue operation that removes the element at the front?

1. APush
2. BDequeue
3. CEnqueue
4. DInsert

An application needs fast lookups and also needs to list keys in sorted order and answer range queries. Which structure fits best?

1. AA stack
2. BAn unsorted linked list
3. CA hash table
4. DA balanced binary search tree

How do you find the minimum key in a binary search tree?

1. AFollow right children from the root until there is no right child
2. BLook at the root only
3. CVisit every leaf and compare them
4. DFollow left children from the root until there is no left child

How many nodes does a perfect binary tree of height h have, with height counted in edges?

1. A2^h+1 − 1
2. B2^h
3. Ch²
4. D2h + 1

How can you detect whether a singly linked list contains a cycle using O(1) extra memory?

1. AMove one pointer by one step and another by two steps and check whether they meet
2. BSort the list and look for duplicates
3. CCount the nodes until the count exceeds the list length field
4. DStore every visited node in a hash set

A Bloom filter can answer "is this element in the set?" with:

1. APossible false negatives but no false positives
2. BAnswers only for numbers
3. CPossible false positives but no false negatives
4. DExact answers always