&
AP207
April 1997
&
|
Question 1 (Compulsory) |
(a) Briefly explain the following terms:
(i) Portability [2 marks]
(ii) Iteration [2 marks]
(iii) Pointer [2 marks]
(iv) Stack [2 marks]
(v) Abstract Data Type [2 marks]
v Answerv
i. the ability to port a program to a different platform.
a program is said to be portable if it can be transferred to a different machine which may have a different hardware configuration or operating system with minimal modification and no adverse effect on performance.
ii. A construct of programming used in most programming languages which allows an instruction or a group of instruction to be repeated until a certain condition is met. To implement an iterative process, the use of implicit commands like FOR..DO, WHILE..DO, or REPEAT..UNTIL etc.
iii. A variable which holds the memory address of another variable.
Used to establish links in dynamic lists and allows the direct manipulation of storage locations.
iv. Homognous data type which is dynamic. Size can change during run-time. It follows the LIFO concept where the last item added to the stack will be the first item that is removed.
v. Data type where the behaviour or the characteristic of the ADT is more important then the method of iplementation. It includes the data-structure and a set of operations for manipualting that data structure. Example of Astract Data Types are stack, queue, lined list, binary trees.
(b) Write a Pascal type declaration for trees such as the one shown:
Assume that 'Data' is a character, and 'PP' is a pointer to the parent of eachnode in the tree. [5 marks]
v Answerv
TYPE
Tree = ^NodeType;
NodeType = RECORD
Left, Right, Parent : Tree;
Data : Char;
END;
VAR
Top : Tree;
|
& Note |
The order of the entries Left, Right, Parent and Data is irrelevant. Similarly alternative names may be given for Tree, Left, Right, and Parent (i.e. Tree,l,r,pp_. The answer may also include the type Tree after each of the entries Left, Right, or Parent. |
(c) Write a recursive procedure 'ReversePrint' which takes a List as its argument, and displays the contents of the list starting from the last node.
Assume the following declaration for the list:
Type List=^Node;
Node=Record
Element:Integer;
Next :List;
End;
(Note: The routine does not have to return any values) [5 marks]
v Answerv
PROCEDURE ReversePrint (Current : List);
begin
If Current <> Nil Then
begin
ReversePrint(Current.Next);
WriteLn(Current.Element);
end;
end;
If the WriteLn is used before the recursive call, then only a maximum of 3 marks can be obtainted for the question.
|
Question 2 |
(a) Write a function Multiple that accepts an integer argument and determines if x is a multiple of 7, 11 or 13, and returns 7, 11 or 13 respectively. If x is not a multiple of any of these numbers, a value of 0(zero) should be returned. [5 marks]
v Answerv
Function Multiple(N : Integer) : Integer;
begin
if (N mod 7=0) Then
Multiple := 7;
else
If (N Mod 11=0) Then
Multiple := 11
else
if (N mod 13 = 0) Then
Multiple := 13
else
Multiple := 0;
end;
(b) Explain the difference between call-by-value and call-by-reference parameter passing. [2 marks]
v Answerv
Call-by-value makes a copy of the argument passed as parameter to the routine. Any changes to the parameter within the body of the routine will not be reflected in the variable that was passed to the routine. This means if the formal parameter is changed, the actual parameter value will still remain unchanged.
Any changes to a parameter that was passed using a call-by-reference parameter passing scheme will be reflected in the original variable.
(c) Write a procedure minpair that takes two integer valued parameters x and y as its arguments. The effect of the procedure should be to change the value of x so that it holds the smaller of the two values, and y the larger. [5 marks]
v Answerv
Procedure minpair(Var x : Integer; Var y : Integer)
Var
Temp : Integer;
begin
if (x > y) then
begin
temp := x;
x := y;
y := temp;
end;
end;
|
& the conditional expression may also be (x>=y) |
(d) Illustrate, step by step, how Quicksort will rearrage the following listinto descending order. Note: Use the first element of the sequence produced in the divide step of quicksort as the pivot.
26 24 3 17 25 6 7 60 [8 marks]
v Answerv
{26 24 3 17 25 6 7 60}
[60] (26) {3 17 25 6 7 24}
{24 17 25 6 7} (3)
[25] (24) {17 6 7}
(17) {6 7}
(7) [6]
|
& Note: ( ) represents pivots and [ ] for ‘solo’ values |
|
Question 3 |
(a) Identify and explain the differences between the implementation of a sequence (ie. a list abstract data type) using a singly-linked-list and a static array. [10 marks]
v Answerv
A linked list is dynamic.
It can grow abd shrink during program execution wheras an array remains the same size throuhout.
For short sequences, a linked list is more economical with its use of memory as only the active elements in thelist need storing. In contrast, an array based representation has to overcompensate it’s memory use.
For large sequences, the pointer used in the linked list can be a large memory overhead.
Indexing into a linked list requires a linear traversal of the list, whereas the lookup can be performed in constant time for an array.
A singly linked list has to be traversed rfom front to back, wheras an array based scheme can be traversed in any order.
A linked list requires little rearrangement during inserion and deletion of data, whereas an array requires a potentially large amount of data movement and copying.
Changes in storage size requirements can be catered for by dynamic lists without the need to amend the program, wheras for static list, the program may have to be changed.
(b) Complete the following definition of a procedure that deletes the first occurence of the element Item from a doubly linked-list. [10 marks]
Procedure Delete (Var Start:NodePtr; Item:Integer);
Var Prev, Curr : NodePtr;
Begin
Curr := Start;
While ((Curr^.Data <> Item) and (Curr<>Nil)) DO
Curr := Curr^.Next;
{ missing lines}
End;
Note: (i) Assume the following global declaration:
Type NodePt=^Node;
v Answerv
Procedure Delete (Var Start:NodePtr; Item:Integer);
Var Prev, Curr : NodePtr;
Begin
Curr := Start;
While ((Curr^.Data <> Item) and (Curr<>Nil)) DO
Curr := Curr^.Next;
If Curr^.Data = Item Then
begin
Start := Start^.Next;
Start^.Prev := Nil;
end
else
begin
Prev := Curr^.Next;
Prev^.Next := Curr^.Next;
If (Curr^.Next <> NIL) Then
Curr^.Next^.Prev := Prev;
end;
Dispose(Curr);
End;
|
Question 4 |
(a) Convert the following infix expression into their Prefix and Postfix forms. (You are not required to show any working)
(i) (A+B) * (C-D) [2 marks]
(ii) A-B/(C+D^E) [3 marks]
(iii)A^B*C-D*E/F/(G+H) [4 marks]
ANSWER
(i) Preorder: * + A B - C D
Postorder: A B + C D - *
(ii) Preorder: - A / B + C ^ D E
Postorder: A B C D E ^ + / -
(iii) Preorder: - * ^ A B C // * D E F + G H
Postorder: A B ^ C * D E * F / G H + / -
(b) Identify two constraints of using a binary tree. [2 marks]
v Answerv
(b)
Any two of the following (total 2 marks):All operations must start from the root.
Every node has at most 2 children.
Every node (except the root node) only has 1 parent.
(c) Write a recursive function countLeaves that determines the number of leaf nodes in the tree shown below. (Note: a leaf is a node that has NIL in both its left and right sub-tree.) [9 marks]
Type TreePtr=^Branch;
Branch = RECORD
left :TreePtr;
data : Integer;
right:TreePtr;
End;
v Answerv
Function countLeaves (xs: TreePtr) : Integer;
Begin
if (xs=Nil) THEN
CountLeaves := 0
else
if (xs^.left = NIL and xs^.right=NIL) THEN
countLeaves:=1
else
countLeaves(xs^.right)
end;
|
Question 5 |
(a)(i) Given the following program specification, tabulate all possible ranges of total against commission:
The program reads in a list of sales figures and calculates the total. If the total is greater than $1000 but does not exceed $3000, a 5% commission is given; If the total is greater $3000, a 20% commission is given. The total should never exceed $10000 and should be a non negative figure. [5 marks]
v Answerv
total<0.0 total too small
0.0<=total<=1000 no commission
1000 <total<=3000 5% commission
3000< total<=10000 10% commission
total> 10000 total too large
(ii) Write a function commssion that takes an argument total as ita parameter, and changes the value of total to include the appropriate commission as specified informally above. Your function should return FALSE i an erroneous value was passed to the function; otherwise TRUE should be returned. [8 mark]
v Answerv
ii)
Function commission (var total:real) : Boolean;
begin
if ((total <0.0) or total>10000.0) then
commission := false
else
begin
if (total > 1000) and (total <=3000) then
total := total * 1.05
else
if (total <=1000.0) Then
total := total *1.1
commission := True;
end;
end;
(b) Identify and explain the errors that can occur in using the following Pascal statements:
(i) x:=sqrt(y);
Assumption: x and y are integers, x and y are equal to -10. [2 marks]
(ii) x:= x + y div x;
Assumption: x and y are real numbers [2 marks]
(iii) If sex <> 'F' or sex <>'M' then
WriteLn ('Illegal Sex');
Assumption:sex stores a single character; The message is displayed upon a wrong entry for sex. [ 3 marks]
v Answerv
i) -runtime error
-function Sqrt() does not accept negative integer numbers
ii) -syntax error
-DIV is the division operator for integer operands only, not real operands.
iii) -Logic error
-The error message will be displayed even when either ‘F’ or ‘M’ is entered.