|
(a) Briefly explain the following terms:
(i) Sorting [1 mark]
(ii) Searching [1 mark]
(iii) Binary trees [1 mark]
(iv) N-ary trees [1 mark]
(b) (i) Explain, informally, how an
insertion sort works. [3 marks]
(ii) Explain, informally, how a selection sort works. [3 marks]
(c) (i) Implement the iterative procedure
Shift, the signature of which is given below, which will take a reference
to an array A, the length of the array L and an index I. Upon termination,
each element in the array from position I should be shifted along
to the I+1th position. You may ignore any elements which fall off
the end of the array.
PROCEDURE Shift(Var A: IntArray; L: INTEGER; I :INTEGER); [4 marks]
(ii) Implement the procedure Insert, the signature of which is given
below, which takes an array of integers A, sorted into increasing
order, and a value V, and inserts V into the correct position in the
array. You may wish to use the procedure Shift, given above.
PROCEDURE
Insert(Var A: IntArray; L: INTEGER; V: INTEGER); [4 marks]
(d) Assume the following definition of
a dynamic queue together with the signature of the function Empty,
which returns the boolean value True if the queue is empty and False
otherwise.
TYPE
NodePtr = ˆNode;
Node = RECORD
Datum : INTEGER;
Next : NodePtr;
END;
Queue = RECORD
Front, Rear : NodePtr;
END;
FUNCTION Empty(Q : Queue) : BOOLEAN;
(i) Implement the procedure Add, the signature of which is given below,
which takes in a reference to a Queue, Q, and an integer X, which
is the data value to be added to the queue. Upon termination of the
procedure, the queue should have the new data value added to the end
of the queue.
PROCEDURE Add(Var Q: Queue; X: INTEGER); [4 marks]
(ii) Implement the function Remove, the signature of which is given
below, which takes in a reference to a Queue Q, and will remove and
return the item at the head of the queue.
FUNCTION Remove(Var Q : Queue) : INTEGER; [4 marks]
(iii) Implement the recursive function Find, the signature of which
is given below, which takes in a reference to a Queue Q, and an Integer
X, and will search the queue for the first occurrence of X, returning
its position if found, or the length of the queue otherwise.
FUNCTION Find(Q : Queue; X : INTEGER) : INTEGER; [4 marks]
|