|
Do not award half
marks. Do not deduct marks for trivial syntactic errors. Alternative
correct answers should be given credit, unless otherwise indicated
in the marking scheme.
(a)Identify and explain one difference
and one similarity between a dynamic linked list and a dynamic double
linked list.[3 marks ]
(a) • Differences:
– A linked list can be traversed in one direction (1 mark),but
a doublelinked
list can be traversed in both;(1 mark)
– A double linked list has double the pointer overheads of a
single linked list.
(2 marks)
• Similarities:
– Both are collection of homogeneous data;(1 mark)
– Both have nodes which contain both the data,and an indexing
method.
(1 mark)
[3 marks ]
(b)Assume the following definition of
a stack data type,and the routines Push and Pop which operate on it:
TYPE
StackType= ˆStackElement;
StackElement= RECORD
next: StackType;
data: INTEGER
END;
PROCEDURE Push(VAR stack: StackType; datum: INTEGER);
FUNCTION Pop(VAR stack: StackType): INTEGER;
(i)Implement the function IsEmpty the
signature of which i given below,such that it returns a value of 1
if the stack is empty,and 0 otherwise.
FUNCTION IsEmpty(stack: StackType): INTEGER;
[2 marks ]
(i)A sample definition
of IsEmpty follows:
FUNCTION IsEmpty(stack: StackType) : INTEGER;
BEGIN
IF stack= nil THEN
IsEmpty:= 1
ELSE
IsEmpty:= 0;
END;
And the following marking scheme should be used:
• A correctly structured IF statement to test the stack pointer;(1
mark)
• Returning 1 if it is nil and returning 0 if it is not.(1 mark)
[2 marks ]
(ii)Implement the recursive function
Reverse the signature of which is given below, such that it returns
a stack which contains all the elements of the original stack, but
with their order reversed.
FUNCTION Reverse(stack: StackType): StackType;
[5 marks ]
(ii)A sample definition of Reverse follows:
FUNCTION Reverse(stack: StackType) : StackType;
VAR datum: INTEGER;
BEGIN
IF(IsEmpty(stack)) THEN
Reverse:= stack
ELSE
BEGIN
datum:= Pop(stack);
stack:= Reverse(stack);
Push(stack, datum);
END;
END;
And the following marking scheme should be used:
• A correctly structured IF statement;(1 mark)
• Testing for the empty stack condition;(1 mark)
• Popping the datum from the top of the stack;(1 mark)
• Then recursing with the new stack;(1 mark)
• Then pushing the datum back onto the forming stack.(1 mark)
[5 marks ]
(iii)Implement the function Concatenate
the signature of which i given below,
such that it returns a stack which consists of all the elements of
the stacks left
and right concatenated (i.e.,joined together).The left stack should
be at the
bottom of the new stack,and the right on the top,and the order of
the original
stack should be preserved.For example,the result of concatenating
the two
stack {1, 2, 3} and {4, 5, 6} would be the stack {1, 2, 3, 4, 5, 6}.
FUNCTION Concatenate(left, right: StackType): StackType;}
[5 marks ]
(iii)A
sample definition of Concatenate follows:
FUNCTION Concatenate(left, right : StackType) : StackType;
VAR NewStack, TempLeft, TempRight : StackType;
BEGIN
TempLeft:= Reverse(left);
TempRight:= Reverse(right);
WHILE(!IsEmpty(TempLeft)) DO
Push(NewStack, Pop(TempLeft));
WHILE(!IsEmpty(TempRight)) DO
Push(NewStack, Pop(TempRight));
Concatenate:= NewStack;
END;
And the following marking scheme should be used:
• Creating a local reversed copy of the Left stack;(1 mark)
• Creating a local reversed copy of the Right stack;(1 mark)
• Push and Pop the elements of the reversed TempLeft stack onto
the
new stack;(1 mark)
• Push and Pop the elements of the reversed TempRight stack onto
the
new stack;(1 mark)
• Returning the new stack.(1 mark)
[5 marks ]
|