Data structures worksheet with answers

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

1. AInserting at the beginning
2. BFinding the length of a fixed array
3. CReading the last element by index
4. DAccessing the 5th element

How are the elements of an array stored in memory?

1. AIn one contiguous block, one after another
2. BIn random locations chosen by a hash
3. CIn a tree of memory pages
4. DScattered, linked by pointers

In a binary search tree, values in the left subtree of a node are:

1. AEqual to the node's value
2. BSmaller than the node's value
3. CLarger than the node's value
4. DIn random order

How long does it take to check whether the edge (u, v) exists using an adjacency matrix?

1. AO(log V)
2. BO(E)
3. CO(1)
4. DO(V)

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 ⌊(i − 1) / 2⌋
4. DAt index 2i + 1

A trie (prefix tree) is especially efficient for:

1. APrefix searches such as autocomplete
2. BStoring matrices
3. CSorting numbers
4. DFinding shortest paths

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 hash table of all elements
4. DA stack that keeps elements waiting for their answer

A Fenwick tree (binary indexed tree) over an array of n numbers supports which operations in O(log n)?

1. AFinding the median in O(1)
2. BSorting the array and binary search
3. CPrefix-sum queries and single-element updates
4. DInserting elements at any position