Data structures worksheet with answers

Which operation is slow in an array but fast at the head of a linked list?

1. AAccessing the 5th element
2. BReading the last element by index
3. CInserting at the beginning
4. DFinding the length of a fixed array

Which data structure is used to perform a level-order traversal of a tree?

1. AStack
2. BPriority queue
3. CHash table
4. DQueue

In a tree, what is a leaf?

1. AA node with no children
2. BA node with exactly one child
3. CA node with no parent
4. DThe node with the largest value

In a binary min-heap stored in an array (index starting at 0), the children of the node at index i are at:

1. Ai/2 and i/2 + 1
2. Bi + 1 and i + 2
3. C2i and 2i + 1
4. D2i + 1 and 2i + 2

In a circular queue stored in an array of capacity n, how is the next position after index i computed?

1. A(i − 1) mod n
2. B(i + 1) mod n
3. Ci + 1
4. D2i + 1

What balance condition does an AVL tree maintain at every node?

1. AEvery node is coloured red or black
2. BBoth subtrees of every node contain exactly the same number of nodes
3. CAll leaves are at exactly the same depth
4. DThe heights of the left and right subtrees differ by at most 1

Under simple uniform hashing, what is the expected time of a search in a hash table with chaining, n keys and m buckets?

1. AO(m)
2. BO(1 + α), where α = n / m
3. CO(n)
4. DO(log n)

What is the main advantage of a skip list over a sorted linked list?

1. AGuaranteed O(1) search because every node stores a pointer to every other node
2. BIt uses no extra memory
3. CExpected O(log n) search by using several levels of forward pointers
4. DIt stores keys without order