COMP 251 Study Guide - Midterm Guide: Avl Tree, Hash Table, Open Addressing
19 Nov 2018
School
Department
Course
Professor
Document Summary
Hashing: suppose that you use a hash table and a hash function implementing the division method. The following keys are inserted: 5, 28, 19, 15, 20, 33, 12, 17, 10 and m = 9 (for simplicity, here we do not distinguish a key from its hashcode, so we assume h(key)=key). In which slots do collisions occur: now suppose you use open addressing with linear probing and the same keys as above are inserted. More collisions occur than in the previous question. If an insertion causes the tree to become unbalanced, then perform the necessary rotations to maintain the balance. Heaps: suppose you have a heap which supports the usual add() and removemin() operations, but also supports a changepriority (name, new priority) operation. 1: suppose you used an ordered array to implement a priority queue. Disjoint sets: consider the set of all trees of height h that can be constructed by a sequence of union-by- height operations.
