GATE CS 2021 Set 1 Q.14 (CS Q.4): Runtime Environments and Parameter Passing

Consider the following statements.

$S_1$ : The sequence of procedure calls corresponds to a preorder traversal of the activation tree.

$S_2$ : The sequence of procedure returns corresponds to a postorder traversal of the activation tree.

Which one of the following options is correct?

$S_1$ is true and $S_2$ is false

$S_1$ is false and $S_2$ is true

$S_1$ is true and $S_2$ is true

$S_1$ is false and $S_2$ is false

Official answer and solution

Official answer: C
From: Official GATE 2021 answer key

Solution

Connect procedure call entry and exit events to tree traversal orders on an activation tree.

In a compiler's runtime environment, an activation tree models procedural execution where each node represents an execution of a procedure. A procedure calls its children, and control enters a node before entering any of its children.

Therefore, the sequence of procedure calls visits the parent before its children, which corresponds precisely to a preorder traversal of the activation tree. Hence $S_1$ is true.

A procedure cannot return until all procedures called by it (its children) have returned. Thus, control exits a node only after all its children have finished, which corresponds precisely to a postorder traversal of the activation tree. Hence $S_2$ is true.

Since both $S_1$ and $S_2$ are true, option C is correct.

Final answer

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2021 Computer Science and Information Technology (CS, Set-1)
Question: 14 of 65, printed as CS Q.4
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source