Data structures worksheet with answers

What is the main difference between a static array and a dynamic array?

1. AA dynamic array can grow by moving to a larger block of memory
2. BA static array allows slower index access
3. CA dynamic array stores its elements in linked nodes so it can grow one at a time
4. DA static array can only store numbers

What does each node in a doubly linked list contain?

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

Which data structure works on the principle "first in, first out"?

1. AStack
2. BHeap
3. CQueue
4. DBinary 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

You have a reference to a node in the middle of a list. In which list can you remove it in O(1)?

1. AA dynamic array
2. BA doubly linked list
3. CA sorted array
4. DA singly linked list

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

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

The union-find (disjoint set) structure with union by rank and path compression has an amortised cost per operation of:

1. AO(log n) exactly
2. BO(α(n)), the inverse Ackermann function, which is practically constant
3. CO(n)
4. DO(n²)

Which statement about heapsort is correct?

1. AIt runs in O(n) time on any input
2. BIt is stable and needs O(n) extra memory
3. CIt needs a binary search tree as extra storage, so it uses O(n) extra memory
4. DIt sorts in place in O(n log n) worst-case time but is not stable