ITPEC IP April 2021 Question 7

Topic: Algorithm and ProgrammingAlso asked in October 2022

A stack is a first-in last-out data structure. By using the stack, a device changes the order of data received from the right side and sends it to the left side, as shown in the figure below. There are three types of operations available on the device, as described below.

(1)Data received from the right side is sent to the left side without any alteration.(2)Data received from the right side is pushed into the top of the stack.(3)Data popped out of the top of the stack is sent to the left side.

When the device receives X, Y, and Z in this order from the right side, which of the following is the order in which the device cannot send them to the left side even if the operations (1) to (3) are combined?

(1)(3)(2)StackX, Y, Z

Explanation

Z, X, Y — to send Z first, X and Y must both wait on the stack, and then Y is on top.

Z arrives last, so sending it first means X and Y were both pushed (operation (2)) in that order. The stack holds Y on top of X, and a stack releases only its top, so the next two outputs can only be Y then X. The order Z, X, Y is impossible.

Answer (c)

Why not others:

  • •(a) X, Z, Y — pass X (1), push Y (2), pass Z (1), pop Y (3)
  • •(b) Y, Z, X — push X (2), pass Y (1), pass Z (1), pop X (3)
  • •(d) Z, Y, X — push X and Y (2), pass Z (1), pop Y then X (3)

Key rule: Items pushed onto a stack come out in reverse order; an output order is impossible when it needs an item that lies below another one still on the stack.

Algorithm and Programming · 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 IP past-paper collection or Report an issue.