Data structures worksheet with answers

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. CTwo separate queues sharing one array
4. DA queue sorted by priority

In a singly linked list, each node contains:

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

A hash table stores data as:

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

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

1. A4 2 5 1 3
2. B4 5 2 3 1
3. C5 4 3 2 1
4. D1 2 4 5 3

How long does a search for a word of length L take in a trie with a fixed alphabet?

1. AO(L × n)
2. BO(L), independent of how many words are stored
3. CO(log n), where n is the number of words
4. DO(n), where n is the number of words

In a binary heap stored in an array starting at index 0, where is the parent of the node at index i?

1. AAt index i − 1
2. BAt index ⌊i / 2⌋ + 1
3. CAt index 2i + 1
4. DAt index ⌊(i − 1) / 2⌋

What does a splay tree do after each access?

1. ARotates the accessed node up to the root
2. BRebuilds the whole tree in balanced form
3. CMoves the accessed node to a leaf
4. DRecolours the nodes on the search path

For each element of an array you want the next greater element to its right, in O(n) total time. Which structure helps?

1. AA queue that holds every pair of elements
2. BA binary search tree rebuilt for each element
3. CA stack that keeps elements waiting for their answer
4. DA hash table of all elements