This quiz will be all short answer and multiple choice.
Topics Covered
Note: Topics covered on previous quizes 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 quiz:
- 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
Assignments referenced:
- mp_traversal
- lab_huffman, lab_avl, lab_btree, lab_hash