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.