This website is an archive of the Spring 2019 semester of CS 225.

**→ Click here to view the current semester.**

Back to Exams
# Exam 3

### Topics Covered

Theory Exam 3 contains only multiple choice or short answer problems. You will have 50 minutes to complete this exam.

*Note: Topics covered on previous exams may be referenced (eg: you need to be able to compare anything vs. the running time of a sorted array/list, etc).*

New topics from lecture for the exam:

- AVL
- Difference between a “Tree”, “BST”, and an “AVL”
- Operation
`find`

, including running times in terms of`h`

and`n`

- Operation
`insert`

, including running times in terms of`h`

and`n`

- Operation
`delete`

, including running times in terms of`h`

and`n`

- Strategy for a 2-child delete
- AVL Tree Rotations
- Minimum/maximum nodes in an AVL tree

- BTree
- Difference between a key and a node in a BTree
- The order of a BTree
- Structural properties of a BTree
- The min/max keys/children in each node in a BTree
- The min/max total number of keys in a BTree
- Advantages of a BTree
- Running time of a BTree

- Hash Table
- Hash functions
- Properties of a good hash function
- SUHA
- Hash Table Array
- Load Factor
- Hash Table Collisions
- Open Hashing vs. Closed Hashing
- Separate Chaining
- Linear Probing
- Double Hashing
- Re-Hashing
- Runtime of a hash table, in terms of
`n`

- Load factor’s impact on running times
- Properties of a good hash table

- Heaps
- Construction of a Heap
- Heap runtime
- HeapifyUp
- HeapifyDown
- Priority queue ADT

Assignments referenced:

- MP4, MP5
- lab_huffman, lab_avl, lab_btree, lab_heaps

**Points:**70

**Registration:** Thursday, March 21

**Start:** Thursday, April 04

**End:** Sunday, April 07