Sample problems for tutorial #9

1. If we have a skip list with n elements, what is the expected number of levels of that skip list?
2. Are the levels of the nodes in a skip list uniformly distributed between 1 and its height H? That is, is the probability that a node will have height h equal to 1/H? If not, what is that probability (approximately)?
3. A user calls Search(S, 35) on the skip list S from the following figure. Which pointers will be followed during the search? You can draw the skip list and highlight these pointers, or you can simply list them (e.g. “Pointer at level 1 from 22 to 27”).