1. Insert the following characters with their respective priorities (shown as ordered pairs) into an empty treap:
(K, 17), (F, 22), (P, 29), (M, 10), (N, 15), (L, 26), (G, 13), (X, 20), (A, 44), (P, 19), (Q, 30).
Show the result after each insertion.
2. Given a Skiplist with probability p and maximum node size M that contains N nodes, show the expected distribution of node sizes (how many nodes of each size).
3. How would choosing a large value (close to 1) of p or a small value (close to 0) affect the performance of a skiplist? Justify your answer.
4. Insert the values 89, 19, 50, 59, 76 and 26 into an empty hash table of size 11 that uses f( k ) = k mod 11 for its hash function and linear probing using f( i ) = i for collision resolution.
5. Is a hash table a good choice to implement a priority queue? Justify your answer.