|
(a)Identify and explain one difference
and one similarity between a dynamic linked list and a dynamic double
linked list.[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 ]
(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 ]
(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 ]
|