How many pointers are set to NULL in a binary tree with n nodes?
A binary tree with n nodes has 2n total child pointers. Since exactly n-1 pointers are used to connect non-root nodes, the remaining 2n - (n - 1) = n + 1 pointers are NULL.
In a min-max heap containing n elements, where is the minimum element always located?
A Min-Max heap alternates min levels and max levels. The root node resides at level 0 (a min level), so the minimum element is always at the root.
Which statement gives the worst-case search time of a standard randomized Skip List with n elements?
The standard randomized Skip List has expected O(log n) search time, but its worst case can be Θ(n). Therefore none of A-C is the correct worst-case bound.
What is the height of a balanced AVL tree with n nodes?
Because balance factors are strictly bounded in {-1, 0, +1}, an AVL tree height is guaranteed to be at most ~1.44 log2(n), which is O(log n).
Which statement gives the exact worst-case time complexity for searching for the minimum element in a valid Max Heap of n elements?
The minimum element of a Max Heap can occur at any leaf. In the worst case, the leaves must be examined, requiring Θ(n) time; therefore none of A-C is correct.