IPA FE Subject B sample Question 8

Topic: Stack

A question IPA Japan published in 基本情報技術者試験 科目B サンプル問題 問8, translated into English. ITPEC is based on the same exams.

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("A", 1)
prioQueue.enqueue("B", 2)
prioQueue.enqueue("C", 2)
prioQueue.enqueue("D", 3)
prioQueue.dequeue() /* The return value is ignored */
prioQueue.dequeue() /* The return value is ignored */
prioQueue.enqueue("D", 3)
prioQueue.enqueue("B", 2)
prioQueue.dequeue() /* The return value is ignored */
prioQueue.dequeue() /* The return value is ignored */
prioQueue.enqueue("C", 2)
prioQueue.enqueue("A", 1)
while (prioQueue.size() is not equal to 0)
output prioQueue.dequeue()
endwhile

Answer group

Explanation

"A", "C", "D", "D" — the smallest priority number comes out first, and within one priority the element that was added earliest.

OperationsQueue afterwards (element:priority)
enqueue A, B, C, DA:1, B:2, C:2, D:3
two dequeues remove A, then B (added before C)C:2, D:3
enqueue D, BC:2, D:3, D:3, B:2
two dequeues remove C (added before B), then BD:3, D:3
enqueue C, AD:3, D:3, C:2, A:1

The while loop then empties the queue: A (priority 1), C (priority 2), then the two Ds (priority 3).

Answer (d)

Why not others:

  • •(a) — the order of the first four enqueues, as if the dequeues in the middle removed nothing; at the end the queue holds two Ds and no B
  • •(b) — has no C, yet a C is enqueued just before the loop; and no B is left, since the second pair of dequeues removes both priority-2 elements, C and B
  • •(c) — keeps the first C past the second pair of dequeues, as if that pair removed B and a D; but C has priority 2, which comes before the Ds' 3

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 the past questions IPA Japan publishes, translated into English by ITPEC Practice. ITPEC Practice is an independent study tool and is not affiliated with IPA or ITPEC. See the original paper (PDF) or Report an issue.