**COM 1201 Algorithms and Data Structures 2**

**Notes for Quiz #2 --
To be given Tuesday, May 30th**

#### Spring 2000 -- Professor Futrelle

College of Computer Science, Northeastern U., Boston, MA

#### (Version of 5/28/00)

The quiz will last for half an hour. Closed book, no calculators allowed.
I plan to return the graded quiz to you on Thursday June 1st.

There will be two questions on the quiz, the first on **binary search trees** and
the second on **hashing**.

**Notes on the Binary Search Trees question:**
Basically, you'll be asked to draw diagrams that show a binary
search tree after the insertion of each element in a sequence of
elements. This will basically look like Figures 12.5 and 12.6
of the text. I will include the code for InsertR() from Program 12.8 for
your reference.

**Notes on the Hashing question:**
The question will ask you about hashing with separate chaining -- what
you are doing in Machine Problem #3. You will be given a sequence of items
to be inserted and a simple hash function to use. You will be asked
to draw the final hash table after these items have been inserted.
The hash function will use the remainder operator "%" (Lippman and Lajoie,
pgs. 143-144).

**Extra-credit question:** This brief question will be based on a different
hashing strategy, Linear Probing, Sec. 14.3 of your text. It will use the
same data sequence as in the previous hashing question.