April 1999
AP207: ADVANCED PROGRAMMING TECHNIQUES

QUESTION 1 (Compulsory)

Total Marks: 20 Marks

 Click here to access other questions

GRADE A
Sample student's solutions are indicated in green.
Return to Question 1

 
(a) Briefly explain each of the following terms:
(i) Array. [2]
An array is a fixed size data structure. Accessing the elements in the array can be performed through indexing. Elements can be retrieve from any point of the array. Time for lookup is constant with respect to the size of the array. Access array through the use of array subscript.

 
(ii) List. [2]
A list is dynamically sized data structure. Indexing is performed from the front of the list. It uses pointers to link the nodes in the list. Elements in the list are access in a sequential manner.

 
(iii) Iteration [2]
Iteration is a construct of a programming language that allows an instruction or a group of instructions to be repeated until a termination condition is met. Example : a for do loop

 
(iv) Recursion [2]
Recursion is a procedure or function that calls itself within the body of the procedure or function. Some form of selection would be used to determine when to recursively call a procedure or function.

 
(b) (i) Define a RECORD, called EmployeeId, which contains the following fields:
  • name, consisting of up to 20 characters
  • employeenumber, an integer ranging from 1 to 9999
  • next, a pointer to the next record

You can assume the definition of a pointer to the EmployeeID type as follows:

  EmployeeIDPtr = EmployeeId;

 [3]
Type
   NumberRange = 1 .. 9999;
   EmployeeIDPtr = ^EmployeeId;
   EmployeeID = RECORD
          name = string[20];
          employeenumber = NumberRange;
          next = EmployeeIDPtr;
          end;

 
(ii) Given the following definition of a linked list of type EmployeeID as above, write a recursive procedure, called NumberOfNodes that will return the number of nodes in a linked list consisting of the record type above. The procedure should return zero if the list is empty. You can assume the existence of a Boolean function isEmpty, which will return TRUE if the list is empty, and FALSE otherwise.

TYPE
   List = EmployeeIdPtr;

 [4]
Procedure NumberOfNodes(var list = EmployeeIDPtr);
var
    sta = Boolean;
    begin
       if (list = NIL) then
           begin
                sta = IsEmpty(TRUE);
               NumberOfNodes = 0;
           end
        else
            begin
                sta = IsEmpty (FALSE);
               NumberOfNodes = 1 + NumberOfNodes(list^.next);
            end;
       end;
(c) Assume the following definitions of the types One, Two, Three, and Four:

TYPE One = ^OneItem;
     OneItem = RECORD
                  info : Integer;
                  next : One;
                  prev : One;
               END;

CONST Max = 20;
TYPE Two = RECORD
              front,rear : 0..Max;
              elements : ARRAY[1..Max] OF Integer;
           END;

TYPE Three = ^ThreeItem;
     ThreeItem = RECORD
                    info : Integer;
                    next : Three;
                 END;

TYPE FourPtr = ^FourItem;
     FourItem = RECORD
                   info : Integer;
                   next : FourPtr;
                END;
     Four     = RECORD
                   front,rear : FourPtr;
                              END;

 
Which of these types would be best best suited to represent the following?
(i) A stack of integers. [1]
Three

 
(ii) A static (i.e., fixed maximum size) queue of integers. [1]
Two

 
(iii) A double linked list of integers. [1]
One

 
(iv) A dynamic (i.e. arbitrary length) queue of integers. [1]
Four

 
(v) A binary tree containing integers at the leaves. [1]
One