No Title

CSE 5311 Fall 1999

Quiz #3

1.

(6 points.) Demonstrate two consecutive tree rotations that will reduce the height of the binary tree below from 5 to 3.

$\begin{figure} \bigskip \centerline{\psfig{figure=f1.ps}} \bigskip \end{figure}$

$\begin{figure} \bigskip \centerline{\psfig{figure=f2.ps}} \bigskip \end{figure}$

2.

(8 points.) Draw the 11-slot hash table (m = 11) that results from using the primary hash function h(i) = (2i+5) mod 11 to hash keys 12, 44, 13, 88, 23, 94, 11, 39, 20, 16, and 5. Handle collisions by double hashing, using h'(i) = 7 - (i mod 7) as a secondary hash function.

   key   h(i)   h'(i) i | slot  key
   ---------------------+----------
   12     7       2   0 |   0    11
   44     5       5   0 |   1    23
   13     9       1   0 |   2    20
   88     5       3   1 |   3    16
   23     7       5   1 |   4    39
   94     6       4   0 |   5    44
   11     5       3   2 |   6    94
   39     6       3   3 |   7    12
   20     1       1   1 |   8    88
   16     4       5   2 |   9    13
    5     4       2   3 |  10     5

3.

(6 points.) Binary heaps and hash tables are two well-known data structures for maintaining dynamic sets of elements. Describe an application scenario where you should use heaps instead of hash tables, and another scenario where you should use hash tables instead of heaps. If the elements are ordered and we want to find the mininum or maximum key, use a heap. If we need to search for any element (not just min or max), use a hash table.