Data structures worksheet with answers

The depth of a node in a tree is:

1. AThe number of nodes in its subtree
2. BThe number of children of that node
3. CThe number of edges from that node to the deepest leaf
4. DThe number of edges from the root to that node

Where is the smallest element of a binary min-heap found?

1. AIn the leftmost leaf
2. BAt the root
3. CIn the last array position
4. DIn any leaf, which must be searched

How are the elements of an array stored in memory?

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

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

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

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 + 1 and i + 2
2. Bi/2 and i/2 + 1
3. C2i + 1 and 2i + 2
4. D2i and 2i + 1

An in-order traversal of a binary search tree visits the keys in:

1. AAscending sorted order
2. BDescending order always
3. CLevel order
4. DInsertion order

Which structure lets you compute the maximum of every window of size k in an array in O(n) total?

1. AA deque holding indices in decreasing order of value
2. BA singly linked list of the window's elements
3. CA sorted array updated by shifting
4. DA min-heap rebuilt for every window

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