|
(a) Describe informally what is meant
by a stack abstract data type. [2 marks]
(a) A stack adt
• Is a first in, last out structure; (1 mark)
• Where newest elements are removed from the top, and new elements
are added to the top; (1 mark)
[2 marks]
(b) Given the following definition of
a stack abstract data type, and the functions and procedures which
operate on it:
TYPE
StackType= ˆStackElement;
StackElement= RECORD
next : StackType;
data : INTEGER;
END;
FUNCTION IsEmpty(stack : StackType) : BOOLEAN;
FUNCTION Pop(VAR stack : StackType) : StackElement;
PROCEDURE Push(VAR stack : StackType; a : StackElement);
(i) Explain, with reference to the above examples, the difference
between a function and a procedure. [1 mark]
(ii) Explain why the parameter stack is declared as a VAR parameter
in the procedure Push. [1 mark]
(iii) Explain why the parameter stack is not declared as a VAR parameter
in the function IsEmpty. [1 mark]
(b) (i) A function returns a result, e.g.,
IsEmpty, a procedure does not, e.g.,
Push. [1 mark]
(ii) Because we want changes to the stack made by this procedure to
be reflected in the rest of the program; [1 mark]
(iii) Because we do not want any changes made in this function to
be reflected elsewhere. [1 mark]
(c) (i) Implement the function Inspect,
the signature of which is given below, which takes a stack s and an
element e, and returns the position of the first occurrence of e in
the stack, and the depth of the stack should e not occur in the stack.
The function should not attempt to remove e from the stack.
FUNCTION Inspect(s: StackType; e: INTEGER) : INTEGER; [5 marks]
(ii) Implement the procedure SplitStack, which takes three stacks
a, b, and c as
reference parameters. The procedure should iterate through the stack
a, such that on each odd iteration it removes the item from a and
adds it to b, and on each even iteration it removes the item from
a and adds it to c, until a is empty. On
termination of the procedure, a should be returned empty. [5 marks]
(c) (i) A sample definition of Inspect follows:
Function Inspect(s: StackType; e: Integer) : Integer;
Var tmp: StackElement;
Begin
if IsEmpty(s) then
Inspect:=
0;
else
begin
tmp:=
Pop(s);
if
tmp.data= e then
Inspect:=
1;
else
Inspect:=
1+Inspect(s, e);
end;
End;
And the following marking scheme should be used:
• Declaring a local temporary to inspect the current element;
(1 mark)
• Popping the top element off the stack; (1 mark)
• Returning 1 if it is what we are looking for; (1 mark)
• Recursing with the amended stack if not; (1 mark)
• Guarding the operation with the empty stack test; (1 mark)
[5 marks]
(ii) A sample definition of SplitStack follows:
Procedure SplitStack(Var a, b, c: StackType);
Begin
while
not IsEmpty(s) do begin
Push(a,
Pop(s));
if
not IsEmpty(s) then
Push(b,
Pop(s));
end
End;
And the following marking scheme should be used:
• Declaring an appropriate procedure signature with Var parameters;
(1 mark)
• Declaring a loop to iterate over the stack whilst it is non
empty; (1 mark)
• Pushing the elements popped on odd cycles onto a; (1 mark)
• Pushing the elements popped on even cycles onto b; (1 mark)
• Ensuring that the stack is always non empty when a pop is attempted;
(1 mark)
[5 marks]
|