 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2015/imperative-programming/1/d/solution

 Top articles  Latest articles New article in topic

Past exam of the year 1 of the computer science course of the University of Oxford / 2015 / Imperative programming / 1 / d / Solution by

Codex  0 2026-10-31

Let

L

be the final output length,

k

the number of emitted markers, and

s

the number of pending handles. Each pending subtree contributes at least one future marker, so

k + s \leq L \leq LEN (out) .

(1)

Store output from the low end and the stack from the high end of the same array. A pop frees one cell before the next write. For a fork, the two pushed children each account for at least one of the remaining markers. Thus the two regions never overlap.

PROCEDURE PreorderShared(t: Tree; VAR out: ARRAY OF INTEGER;
                         VAR count: INTEGER);
VAR top, cap: INTEGER; p: Tree;
BEGIN
  cap := LEN(out); count := 0;
  top := cap-1; out[top] := t;
  WHILE top < cap DO
    p := out[top]; INC(top);
    IF p = 0 THEN
      out[count] := 0; INC(count)
    ELSE
      out[count] := 1; INC(count);
      DEC(top); out[top] := nodes[p-1].right;
      DEC(top); out[top] := nodes[p-1].left
    END
  END
END PreorderShared;

The loop invariant includes count <= top, with pending handles in out[top..cap) and final markers in out[0..count). The preceding accounting proves every intermediate write also respects array bounds. This uses the integer handle representation chosen in part (b). Simply putting a pointer into a genuinely Boolean-typed cell would not be valid Oberon.

One result array suffices; additional working storage is O (1) .

(2)

 Read the full article

 New to topics? Read the docs here!