DATA STRUCTURES & ALGORITHMS
EXAM QUESTIONS AND ANSWERS
Search structures - Correct Answers -Data structures oriented to searches
• Array-based structures (array and std::vectors)
• Linked lists (any variant)
• Binary search trees, AVL trees, and skip lists.
hash table - Correct Answers -is a data structure that stores a collection of unique
search keys and associated values (or pointers) directly in the cells of the array
Handling *Collisions* The problem - Correct Answers -Definition: There is a collision
involving the keys k1 and k2 when both k1 and k2 are determined to belong at the same
index
Two approaches to handle collisions: - Correct Answers -Allow more than one key to
reside in the same place
Separate chaining
Store keys in an alternative location Open Addressing
Handling Collisions: Separate Chaining - Correct Answers -It allows more than one key
to be stored at the same index in the array
Approach
• Each cell in the array will be a singly-linked list
• It has no size limit
Handling Collisions: Separate Chaining: Common Operations: The lookup algorithm -
Correct Answers -The lookup algorithm
• Get key's hash => use % to get index
• Search the linked list at that index
Handling Collisions: Separate Chaining: Common Operations: The insertion algorithm -
Correct Answers -Lookup
Add a new node in the linked list (front or tail)
, Handling Collisions Separate Chaining: Analysis: - Correct Answers -Hash functions
runs in Θ(1) time
Bottle neck => Linked list
Approaches
• Efficiency of hashing/indexing
• Capacity of the hash table (re-hashing).
Hash Function Design
Goals: We look for two qualities: - Correct Answers -Fast to compute.
It needs to be called in every common operation.
It should not depend on the number of keys in the table (n).
It spreads the keys evenly in the hash table.
It maintains an even number of elements in each linked list
Handling Collisions: Open Addressing - Correct Answers -It allows keys to be stored
somewhere other than where the hash function says they belong
Handling Collisions: Open Addressing: Approach - Correct Answers -Find an alternative
index to store the key
Handling Collisions: Open Addressing: Advantages over Separate Chaining: - Correct
Answers -It does not use dynamic memory allocation.
It actually uses less memory, as we don't need linked lists.
Handling Collisions Open Addressing: Linear probing - Correct Answers -Insertion
algorithm:
Hash the key => get the index i with %
If index i is empty => Insert the key into i
Otherwise, probe backward to i-1, i-2, and so on.
If we reach index 0 => wrap around, stating from the index s.
Handling Collisions Open Addressing: Analysis of Linear probing - Correct Answers -
Primary clustering: Clusters grow and performance degrades
quickly
We consider length of the array's clusters
• Sequences of contiguous cells in use.
Larger clusters => higher changes to hit one during insertion
EXAM QUESTIONS AND ANSWERS
Search structures - Correct Answers -Data structures oriented to searches
• Array-based structures (array and std::vectors)
• Linked lists (any variant)
• Binary search trees, AVL trees, and skip lists.
hash table - Correct Answers -is a data structure that stores a collection of unique
search keys and associated values (or pointers) directly in the cells of the array
Handling *Collisions* The problem - Correct Answers -Definition: There is a collision
involving the keys k1 and k2 when both k1 and k2 are determined to belong at the same
index
Two approaches to handle collisions: - Correct Answers -Allow more than one key to
reside in the same place
Separate chaining
Store keys in an alternative location Open Addressing
Handling Collisions: Separate Chaining - Correct Answers -It allows more than one key
to be stored at the same index in the array
Approach
• Each cell in the array will be a singly-linked list
• It has no size limit
Handling Collisions: Separate Chaining: Common Operations: The lookup algorithm -
Correct Answers -The lookup algorithm
• Get key's hash => use % to get index
• Search the linked list at that index
Handling Collisions: Separate Chaining: Common Operations: The insertion algorithm -
Correct Answers -Lookup
Add a new node in the linked list (front or tail)
, Handling Collisions Separate Chaining: Analysis: - Correct Answers -Hash functions
runs in Θ(1) time
Bottle neck => Linked list
Approaches
• Efficiency of hashing/indexing
• Capacity of the hash table (re-hashing).
Hash Function Design
Goals: We look for two qualities: - Correct Answers -Fast to compute.
It needs to be called in every common operation.
It should not depend on the number of keys in the table (n).
It spreads the keys evenly in the hash table.
It maintains an even number of elements in each linked list
Handling Collisions: Open Addressing - Correct Answers -It allows keys to be stored
somewhere other than where the hash function says they belong
Handling Collisions: Open Addressing: Approach - Correct Answers -Find an alternative
index to store the key
Handling Collisions: Open Addressing: Advantages over Separate Chaining: - Correct
Answers -It does not use dynamic memory allocation.
It actually uses less memory, as we don't need linked lists.
Handling Collisions Open Addressing: Linear probing - Correct Answers -Insertion
algorithm:
Hash the key => get the index i with %
If index i is empty => Insert the key into i
Otherwise, probe backward to i-1, i-2, and so on.
If we reach index 0 => wrap around, stating from the index s.
Handling Collisions Open Addressing: Analysis of Linear probing - Correct Answers -
Primary clustering: Clusters grow and performance degrades
quickly
We consider length of the array's clusters
• Sequences of contiguous cells in use.
Larger clusters => higher changes to hit one during insertion
