CMSC Exam 3 ACTUAL UPDATED QUESTIONS AND CORRECT ANSWERS
A Set An abstract data type that represents a collection of unique elements, does not
allow duplicates
Set Operations Insertion, Deletion, Search, Iteration, Union, Intersection, Difference
A Map An abstract data type that represents a collection of key-value pairs. Each key is
unique and maps to a single value
, Map operations Insertions, Retrieval, Deletion, Search, Size, Iteration
HashTable Uses a hash function to compute an index in an array where a key-value pair or an
element is stored, O(1) operations
Binary Search Tree Data structure where each node has at most two children, a left and right child,
O(logn) operations
HashSet Implementation of set that is best for look ups and insertions when order doesn't
matter
TreeSet Implementation of set that is best when sorted order is needed
LinkedHashSet Implementation of set best for when order matters, and we want fast lookups
HashMap Implementation of map that has O(1) lookup and order doesn't matter
TreeMap Implementation of map best for when sorted keys are required
LinkedHashMap Implementation of map that maintains insertion order and has O(1) lookups
Hashing A technique for storing keys or key-value pairs in an array for efficient retrieval
Hash Function Maps each unique key to a distinct index
Collision When two or more keys map to the same index in a hash table
Clustering When keys are not distributed across the hash table uniformly
Open Addressing Method for handling collisions where, if a collision occurs, look for an unused slot
in the table using various strategies.
Linear Probing Find an unused slot in the table by just checking the next available index
Quadratic Probing Find an unused slot in the table by checking i, i+4, i+9, i+16, etc...
Double Hashing Using a second hash function to determine the step size to find an unused slot
Separate Chaining Method for handling collisions by having all elements that hash to the same index
be stored inside a bucket
A Set An abstract data type that represents a collection of unique elements, does not
allow duplicates
Set Operations Insertion, Deletion, Search, Iteration, Union, Intersection, Difference
A Map An abstract data type that represents a collection of key-value pairs. Each key is
unique and maps to a single value
, Map operations Insertions, Retrieval, Deletion, Search, Size, Iteration
HashTable Uses a hash function to compute an index in an array where a key-value pair or an
element is stored, O(1) operations
Binary Search Tree Data structure where each node has at most two children, a left and right child,
O(logn) operations
HashSet Implementation of set that is best for look ups and insertions when order doesn't
matter
TreeSet Implementation of set that is best when sorted order is needed
LinkedHashSet Implementation of set best for when order matters, and we want fast lookups
HashMap Implementation of map that has O(1) lookup and order doesn't matter
TreeMap Implementation of map best for when sorted keys are required
LinkedHashMap Implementation of map that maintains insertion order and has O(1) lookups
Hashing A technique for storing keys or key-value pairs in an array for efficient retrieval
Hash Function Maps each unique key to a distinct index
Collision When two or more keys map to the same index in a hash table
Clustering When keys are not distributed across the hash table uniformly
Open Addressing Method for handling collisions where, if a collision occurs, look for an unused slot
in the table using various strategies.
Linear Probing Find an unused slot in the table by just checking the next available index
Quadratic Probing Find an unused slot in the table by checking i, i+4, i+9, i+16, etc...
Double Hashing Using a second hash function to determine the step size to find an unused slot
Separate Chaining Method for handling collisions by having all elements that hash to the same index
be stored inside a bucket
