|
(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]
(a) (i) Arranging lists of data items into
some defined order. [1 mark]
(ii) Looking through a list of data items to find a given item. [1
mark]
(iii) A data structure where a node has as a single parent node, a
data value and two child nodes. [1 mark]
(iv) Like a binary tree, but with N child nodes. [1 mark]
(b) (i) Explain, informally, how an
insertion sort works. [3 marks]
(ii) Explain, informally, how a selection sort works. [3 marks]
(b) (i) An insertion sort:
• Scans through the source list for the next unsorted data item;
(1 mark)
• Inserts that data item into a sorted copy of the list; (1 mark)
• Until every item in the source list is in the copy of the list
(i.e., until every
element is sorted). (1 mark)
[3 marks]
(ii) A selection sort:
• Searches the list for the next unsorted element; (1 mark)
• And moves it to the first unsorted position; (1 mark)
• By swapping the two elements around; (1 mark)
[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]
(c) (i) A sample definition of Shift follows:
Procedure Shift(Var A: IntArray; L: INTEGER; I: INTEGER);
Begin
for i:= L-1 to I step -1 do begin
a[i+1]:= a[i];
end
End
And the following marking scheme should be used:
• Declaring a loop bound by the length of the array; (1 mark)
• Starting at L-1 and finishing at I; (1 mark)
• A suitable increment (decrement); (1 mark)
• Assigning the relevant elements on each iteration; (1 mark)
[4 marks]
(ii) A sample definition of Insert follows:
Procedure Insert(Var A: IntArray; L: INTEGER; V: INTEGER);
Var i: INTEGER
Begin
i:= 0;
while(V< A[i+1] && V> A[i] && i<
L) do begin
i:= i+1;
end
Shift(A, L, i+1);
A[i]:= V;
End;
And the following marking scheme should be used:
• Declaring a loop to look for the correct position in the array;
(1 mark)
• Shifting the subsequent elements when the position is found;
(1 mark)
• Placing the new element in the correct position; (1 mark)
• Guarding against writing off the array; (1 mark)
[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]
(d) (i) A sample definition of Add follows:
Procedure Add(Var Q: Queue; X: Integer);
Var NewNode: Node;
Begin
Q.Rearˆ.Next:= ˆNode;
Node.Datum:= X;
Node.Next:= NULL;
Q.Rear:= ˆNode;
End;
And the following marking scheme should be used:
• Declaring a new node and assigning the new value to it; (1
mark)
• Updating the pointers at the end of the list; (1 mark)
• Setting the new Next pointer to NULL to indicate the end of
the list; (1 mark)
• Setting the Next pointer in the node currently at the end to
point to the new
item; (1 mark)
[4 marks]
(ii) A sample definition of Remove follows:
Function Remove(Var Q: Queue): Integer;
Var tmp: Integer;
Var n: NodePtr;
Begin
if not Empty(Q) then begin
n:= Q.Front;
tmp:= Q.Frontˆ.Datum;
Q.Front:= Q.Frontˆ.Next;
Dispose(n);
Remove:= tmp;
end
else begin
Remove:= 0;
end
End;
And the following marking scheme should be used:
• Declaring a local temporary which is used to return the value;
(1 mark)
• Moving the front of queue pointer along; (1 mark)
• Disposing of the old node; (1 mark)
• Bounds checking to ensure the queue is non empty; (1 mark)
[4 marks]
(iii) A sample definition of Find follows:
Function Find(Q: Queue; X: Integer) : Integer;
Begin
if Q.Front= NULL then
Find:= 0;
if Q.Frontˆ.Datum= X then
Find:= 0;
else
Find:= 1+ Find(Q.Frontˆ.Next, X);
End;
And the following marking scheme should be used:
• Bounds checking to ensure the queue is non empty; (1 mark)
• Returning 0 when the element is found; (1 mark)
• Recursing when it is not; (1 mark)
• Incrementing the value to be returned by one on each recursion;
(1 mark)
[4 marks]
|