ITPEC FE Subject B October 2024 Question 8

Topic: Stack

From the answer group below, select the correct answer to be inserted into blank in the description.

This program performs operations on a priority queue.
A priority queue is a queue where the handled elements have a priority assigned to them, and the elements are extracted with the order of the highest priority first. The class PrioQueue represents a priority queue. The Figure shows an explanation of the class PrioQueue. Here, the priority is the integer value 1, 2, or 3, and the smaller the value the higher the priority.
When the procedure prioSched is called, the order of the output is blank.

ConstructorDescription
PrioQueue()Creates an empty priority queue.
MethodType of return valueDescription
enqueue(string: s,integer: prio)NoneAdds string s as an element to a priority queue with the priority prio.
dequeue()stringExtracts the element with the highest priority in a priority queue and returns it. If multiple elements with the highest priority exist, it extracts the element that was added first and returns it.
size()integerReturns the number of elements that are stored in a priority queue.

Figure Explanation of the class PrioQueue

[Program]
○ prioSched()
PrioQueue: prioQueue ← PrioQueue()
prioQueue.enqueue("E", 3)
prioQueue.enqueue("F", 2)
prioQueue.enqueue("G", 1)
prioQueue.enqueue("H", 1)
prioQueue.dequeue() /* The return value is ignored */
prioQueue.dequeue() /* The return value is ignored */
prioQueue.enqueue("I", 1)
prioQueue.enqueue("J", 1)
prioQueue.dequeue() /* The return value is ignored */
prioQueue.enqueue("K", 2)
prioQueue.enqueue("L", 3)
prioQueue.enqueue("M", 1)
while (prioQueue.size() is not equal to 0)
output prioQueue.dequeue()
endwhile

Answer group

Explanation

"J", "M", "F", "K", "E", "L" — the smaller number comes out first, and within one priority the element that was added earlier.

OperationsQueue afterwards (element:priority)
enqueue E, F, G, HE:3, F:2, G:1, H:1
two dequeues remove G, then HE:3, F:2
enqueue I, JE:3, F:2, I:1, J:1
dequeue removes I (added before J)E:3, F:2, J:1
enqueue K, L, ME:3, F:2, J:1, K:2, L:3, M:1

The while loop then empties the queue: priority 1 gives J, M (J was added first), priority 2 gives F, K, and priority 3 gives E, L.

Answer (c)

Why not others:

  • •(a) — breaks ties newest first, like a stack inside each priority: the third dequeue then removes J instead of I, and the end order is M, I, then K, F, then L, E
  • •(b) — ignores priorities and works as a plain stack: H, G and J are removed, and the rest come out newest first
  • •(d) — serves the largest number first (priority 3 before 1), and still contains I, which the third dequeue removed

Key rule: Trace the dequeues in the middle of the program too, not only the final loop; a priority queue orders by priority first and by arrival only among equal priorities.

Stack · AI-written, may contain errors

Practice this exam

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.