Data Structures fa © © oonroom in35Sec G)+ Which data structure is commonly used to...
Fujitsu technical mcq question, verified with a worked answer. Free to practise - no sign-up.
Data Structures fa © © oonroom in35Sec G)+ Which data structure is commonly used to implement a hash table with open addressing, where collisions are resolved by searching for the next available slot in the array? - A) Linked List - B) Binary Search Tree - C) Linear Probing - D) Quadratic Probing
Show answer & explanation
Linear probing is a specific open addressing strategy where, upon a collision, the algorithm searches the array sequentially (index by index) for the next empty slot.
Step-by-step Derivation:
Step 1: Analyze the requirement 'open addressing'. Open addressing means all elements are stored within the hash table array itself, eliminating the need for external structures like Linked Lists (which are used in Separate Chaining).
Step 2: Analyze the requirement 'searching for the next available slot'. This implies a sequential search pattern.
Step 3: Evaluate Option C (Linear Probing): The probe sequence is defined as h(k, i) = (h'(k) + i) mod m. This means it checks index 0, then 1, then 2, etc., which matches the description of searching for the 'next available slot'.
Step 4: Evaluate Option D (Quadratic Probing): The probe sequence is h(k, i) = (h'(k) + c1i + c2i^2) mod m. This skips slots quadratically rather than searching for the immediate 'next' available slot.
Step 5: Conclusion: Linear Probing is the correct mechanism for sequential slot searching in open addressing.