| 3. |
(a) Rewrite the
following infix expressions in a fully bracketed form, and then convert them into
their post-fix forms. |
|
|
Expression
trees and post-fix forms: |
|
|
|
(i) (A + B) x C - D |
[2] |
|
|
Expression:
(A + B) x C - D |
|
|
|
Fully
bracketed: (((A + B) x C) - D) |
[1] |
|
|
Post-fix
notation: A, B, +, C, x, D, - |
[1] |
|
|
(ii) A x B / (C + D ^ E) / F ^
G |
[3] |
|
|
Expression:
A x B / (C + D ^ E) / F ^ G |
|
|
|
Fully
bracketed: (((A x B) / (C + (D ^ E))) / (F ^ G)) |
[1] |
|
|
Post-fix
notation: A, B, x, C, D, E, ^, +, /, F, G, ^, / |
[2] |
|
|
(iii) A ^ B - C x D + E / F /
(G + H) |
[4] |
|
|
Expression:
A ^ B - C x D + E / F / (G + H) |
|
|
|
Fully
bracketed: (((A ^ B) - (C x D)) + ((E / F) / (G + H))) |
[2] |
|
|
Post-fix
notation: A, B, ^, C, D, x, -, E, F, /, G, H, +, /, + |
[2] |
|
Do not deduct
a mark from the fully bracketed notation if the students omit the outermost brackets. If
the students give incorrect answers for the fully bracketed notation, but their + postfix
notation is a correct translation of their fully bracketed answer, then award marks for
the postfix notation. |
|
|
|
|
|
(b) Given the
following type definition for a binary tree: |
|
|
|
|
|
|
|
where a leaf node contains Nil
entries for both the Left and Right sub-trees. |
|
|
Binary
trees: |
|
|
|
(i) Write a recursive
procedure that traverses the tree using a post-order traversal, printing the
data item Data during the traversal. |
[5] |
|
|
A sample
definition of the post-order recursive printing procedure is shown below: |
|
|
|
 |
|
|
|
and the
following marking scheme should be used: |
|
|
|
|
one mark for the procedure
declaration |
|
|
|
|
one mark for identifying
the base case of the recursion as a Nil tree; |
|
|
|
|
one mark if the first
statement executed when passed a non-empty tree is a recursive call that passes the left
sub-tree as its argument. |
|
|
|
|
one mark if the second
statement executed when passed a non-empty tree is recursive call that passes the right
sub-tree as its argument. |
|
|
|
|
one mark if the third
statement executed when passed a non-empty tree is some kind of output statement that
prints the data stored in a branch. |
|
|
|
|
do not deduct marks for
trivial syntactic errors when marking the above points. |
|
|
|
[5
marks] |
|
|
|
(ii) Write a recursive
function that determines the height of a binary tree. |
[6] |
|
|
A sample
definition of the recursive height function is shown below: |
|
|
|
 |
|
|
|
and the
following marking scheme should be used: |
|
|
|
|
one mark for a function
definition that identifies that the argument to the function is a Tree, and the result is
an Integer. |
|
|
|
|
one mark for identifying
that the height of an empty tree is zero. |
|
|
|
|
one mark for calculating
the height of the left sub-tree |
|
|
|
|
one mark for calculating
the height of the right sub-tree |
|
|
|
|
one mark for identifying
that the height of the tree is related to the height of the largest sub-tree. |
|
|
|
|
one mark for identifying
that the height is actually the height of the largest sub-tree plus one. |
|
|
|
do not deduct
marks for trivial syntactic errors when marking the above points. |
|
|
|
[6
marks] |
|