Match the items in Column 1 with the items in Column 2 in the following table:
Tap to open full sizeA two-column table. Column 1: (p) First In First Out; (q) Lookup Operation; (r) Last In First Out. Column 2: (i) Stacks; (ii) Queues; (iii) Hash Tables.
(p) − (ii), (q) − (iii), (r) − (i)
(p) − (ii), (q) − (i), (r) − (iii)
(p) − (i), (q) − (ii), (r) − (iii)
(p) − (i), (q) − (iii), (r) − (ii)
ANSWER
Option A: (p)-(ii), (q)-(iii), (r)-(i), that is FIFO with Queues, Lookup with Hash Tables, and LIFO with Stacks.
Official answer: ASource: Official answer key, GATE 2024 DA (IISc Bengaluru)
First In First Out (FIFO) means the earliest inserted item leaves first. That is the queue discipline, so (p) matches (ii) Queues.
Last In First Out (LIFO) means the most recently inserted item leaves first. That is the stack discipline, so (r) matches (i) Stacks.
Lookup (search by key) is the defining operation of a hash table, which gives expected constant-time lookup. So (q) matches (iii) Hash Tables.
The matching is (p)-(ii), (q)-(iii), (r)-(i), which is option A.
Checking the other options against this matching: B pairs lookup with stacks and LIFO with hash tables, so (q) and (r) are wrong. C pairs FIFO with stacks, lookup with queues and LIFO with hash tables, so all three pairs are wrong. D gets lookup right but swaps FIFO and LIFO, pairing FIFO with stacks and LIFO with queues.
KEY IDEA
Match each item to the structure that defines it: FIFO is the queue discipline, LIFO is the stack discipline, and key-based lookup is what a hash table is built for.
WATCH OUT FOR
Swapping FIFO and LIFO, so that stacks are paired with first-in-first-out (option D). Remember that a queue serves the oldest item and a stack serves the newest.
From the GATE 2024 DA paper. Every question of this paper · Download the full paper · All 13 Linear structures questions, with notes