312-174

Exam 3 Topics

Spring 2000

Exam date: Friday, 5 May 2000, 7:30-10:00 AM, Williams 310.

This exam will consist of multiple choice and short answer questions. Some questions will be theoretical in nature, eg "What is the difference between a requirement and a specification", some are mathematical, eg "give the big-oh time of the following function", and some are practical, eg "write a class that ...."

some questions will require you to write short pieces of code. The code does not have to be perfect (I won't compile your answer!), but must be conceptually correct. For example, forgetting to declare a loop variable is not important, but looping through the correct number of times is important.

Some questions will be multiple choice. Examples are questions that require you to choose a correct big-O time, correctly choose a missing statment in a program, etc.

The exam will cover chapters 8-10 of the Dale book and labs 9, 10, and 12 of the Roberge book and the lab 13 that we did in the last week of class. You are responsible for all of the material in the book chapters and in the labs unless I explicitly exempt material below.

You may bring in one hand-written 8.5 X 11 sheet of notes. You may not share notes; if you forget your page, you will have to take the exam without notes.

The topics covered on this exam are listed below.

Chapter 8:

1. Know how binary search trees are implemented using both iteration and recursion.

2. Know how to use BSTs in an application (as in the in-lab exercise).

3. Know how to use pointers. Be able to use pointers to implement data structures (such as BSTs). Know how arrays and pointers are related and be able to use pointer arithmetic to iterate through arrays.

4. Know how to analyze the running time of BSTs.

Chapter 9:

1. You are not responsible for binary expression trees.

2. Be able to create the code for heaps including reHeapUp and reHeapDown.

3. Be able to implement priority queues using heaps.

4. You are not responsible ofr graphs.

Chapter 10:

1. Know how to implement and anaylze the straight selection sort.

2. You are not responsible for the bubble sort or the insertion sort.

3. Know how to implement and analyze the merge sort.

4. Know how to implement and analyze the quicksort.

5. Know how to implement and analyze the heapsort.

6. Know how to implement hashing.
   • Be able to use/create simple hash functions.

   • Know how to use linear probing to resolve collisions.

   • Be able to resolve clustering using rehashing.

   • Know how to use buckets and chaining.

   • You are not responsible for pages 632-637.

   • You should know the running time of hashing and why it sometimes fails to meet the expected running time.

7. You are not responsible for the radix sort.

Return to Student Pages

Return to John Barr's Home Page

Last Modified: 27 April 2000

THIS PAGE MAINTAINED BY:
John Barr, Ithaca College