ITPEC FE Subject B October 2024 Question 8
ITPEC FE Subject B October 2024 — Question 8 of 20
Priority queue behavior with FIFO tiebreaking.
A PrioQueue extracts the element with the smallest priority number first (smaller = higher priority). When multiple elements share the same priority, it uses FIFO order (first enqueued, first extracted).
Tracing the operations:
| # | Operation | Queue after (element:priority) |
|---|---|---|
| 1 | enqueue("E", 3) | E:3 |
| 2 | enqueue("F", 2) | E:3, F:2 |
| 3 | enqueue("G", 1) | E:3, F:2, G:1 |
| 4 | enqueue("H", 1) | E:3, F:2, G:1, H:1 |
| 5 | dequeue() → G | E:3, F:2, H:1 |
| 6 | dequeue() → H | E:3, F:2 |
| 7 | enqueue("I", 1) | E:3, F:2, I:1 |
| 8 | enqueue("J", 1) | E:3, F:2, I:1, J:1 |
| 9 | dequeue() → I | E:3, F:2, J:1 |
| 10 | enqueue("K", 2) | E:3, F:2, J:1, K:2 |
| 11 | enqueue("L", 3) | E:3, F:2, J:1, K:2, L:3 |
| 12 | enqueue("M", 1) | E:3, F:2, J:1, K:2, L:3, M:1 |
Final dequeue order (smallest priority first, FIFO within same priority):
- Priority 1: J, M
- Priority 2: F, K
- Priority 3: E, L
Output: "J", "M", "F", "K", "E", "L"
Why not others:
- (a) "M", "I", "K", "F", "L", "E" — wrong order within priority groups and includes "I" which was already dequeued earlier
- (b) "M", "L", "K", "I", "F", "E" — treats higher number as higher priority and includes already-dequeued "I"
- (d) "E", "L", "F", "K", "I", "M" — reverses the priority (extracts largest number first) and includes already-dequeued "I"
Key rule: in this priority queue, smaller number = higher priority, and ties are broken by FIFO (first added = first out).
AI-generated — may contain errors
The original exam layout is preserved in the image so diagrams, formulas, tables, and code remain accurate.
This question comes from an official ITPEC past paper. ITPEC Practice is an independent study tool and is not affiliated with ITPEC. See the official FE past-paper collection or Report an issue.