Exam 3 Review

The exam will consist of short-answer questions, multiple choice questions, understanding written code, and writing your own code. The emphasis is on reading and writing code, and it is cumulative. The following materials are considered fair game:

• All the labs, including lab 9.
• Exam 1 and the Exam 1 Review
• Exam 2 and the Exam 2 Review
• Questions similar to those similar below

If you're pushed for time, my personal recommendation is to spend the majority of your time studying the code you wrote for your labs. You may also benefit from writing additional code.

Binary Search Trees

1. What is the time complexity of removing a node from a binary search tree? Why?

2. What is the time complexity of removing a node from a balanced binary search tree? Why?

3. For an arbitrary binary search tree, how many levels deep could a tree containing N nodes be?

4. For a balanced binary search tree, how many levels deep could a tree containing N nodes be?

Heaps

1. In what ways are heaps different from binary search trees?

2. In what ways are heaps similar to binary search trees?

3. Assuming a heap is complete, how many levels deep is a heap containing N nodes guaranteed to be? Why?

4. Name and describe an abstract data type which can be efficiently implemented using heaps.

5. Be able to illustrate how bubbleUp works, given a heap and an element which is to be enqueued. You should be able to draw out the different intermediate forms of the data structure as it is processed (i.e., the results of the various swaps performed).

6. Be able to illustrate how bubbleDown works, given a non-empty heap. You should be able to draw out the different intermediate forms of the data structure as it is processed (i.e., the results of the various swaps performed).

Hash Tables

Given that your labs have not required you to implement anything regarding hash tables, there will be no questions requiring you to implement anything regarding them. However, you should still understand the basic ideas behind how they work, and be able to draw diagrams consistent with the hash table implementation discussed in Tuesday's lecture.

1. What is the worst-case time complexity of looking up an element in a hash table?

2. What is the best-case time complexity of looking up an element in a hash table?

3. Name two reasons why hash tables are used.

4. List two situations in which hash tables are likely to degrade from the best-case O(1) complexity into the worst-case O(N) complexity.

5. Given a hash function and a series of key/value pairs, draw out a hash table which results from adding all the elements in sequence.