April 1999
AP207: ADVANCED PROGRAMMING TECHNIQUES

QUESTION 1 (Compulsory)

Total Marks: 20 Marks

 Click here to access other questions

Click to access
SAMPLE STUDENT'S SOLUTIONS
for Question 1

 
(a) Briefly explain each of the following terms:
(i) Array. [2]
(ii) List. [2]
(iii) Iteration [2]
(iv) Recursion

 

 [2]
(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]
(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]
(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]
(ii) A static (i.e., fixed maximum size) queue of integers. [1]
(iii) A double linked list of integers. [1]
(iv) A dynamic (i.e. arbitrary length) queue of integers. [1]
(v) A binary tree containing integers at the leaves. [1]