August
1999 QUESTION 3 Total Marks: 20 Marks |
Click here to access other
questions
Click to access |
| (a) | (i) Describe what is meant by a recursive
procedure. (ii) Explain what is meant by the base case of a recursive function.
|
[2] [2] |
| (b) | In mathematics, N! (known as N
factorial ) can be computed using the formula N! = N * ( (N-1) ! ) The base case, 0!, is defined as being 1. Write a recursive Pascal function, called Factorial, which takes an integer N, and returns N!.
|
[4] |
| (c) | Give the expression AB
- C * D - E / F / ( G - H ), (i) Rewrite this expression in fully bracketed form. (ii) Convert the expression into post fix form.
|
[2] [2] |
| (d) | Binary tress can be used to model
arithmetic expressions. To model a simple arithmetic expression, a node in the tree
contains an integer, and an operation. An operation is a variable of the following type : TYPE OpType = (Int, Add, Subtract); The leaves of the tree contains just integers; each integer is represented by a node which contains an int in the operation field, and an int in the value field, and no left or right sub-trees. In contrast, the branches of the tree contain operations, which are one of the binary operations given above, and left and right sub-expression trees. Give a definition of such a binary tree.
|
[4] |
| (e) | Write a recursive
function that determines the height of a dynamic binary tree, such as the one described
above.
|
[4] |