August 1999
AP207 : ADVANCED PROGRAMMING TECHNIQUES

QUESTION 2

Total Marks: 20 Marks

• Question 1
• Question 3
• Question 4
• Question 5
• Cover Page

SUGGESTED SOLUTIONS
Solutions and allocated marks are indicated in green.
Return to Question 2

(ii) Describe what is meant by the term abstraction.

(iii) Identify and explain the difference between a static and dynamic data structure.

[2]

[2]

• FIFO is a First In, First Out data structure, for example a queue;
• LIFO is a Last In, First Out data structure, for example a stack.

(ii) Abstraction means

• separating the physical properties of a data type
• from its logical properties (how it is used).

(iii)

• A static data structure has a size which is fixed,
• while a dynamic structure can shrink or grow.

• The title of the book (a string 100 characters long);
• The catalogue number of the book (an integer);
• The status of the book, wither on loan or in the library (an integer);
• The due date of return of the book (the Date type given below).

TYPE Date = RECORD

Day : Integer of [1..31];
Month : Integer of [1..12];
Year : Integer of [0..99];

END;

(i) Define a data structure Book, which contains all of the information above.

(ii) The library holds 1000 books in total. Define a suitable static data structure, called StaticLibraryCatalogue which will hold the details of all 1000 books.

(iii) Suppose that more books need to be added to the library. Suggest a suitable dynamic data structure, called DynamicLibraryCatalogue which could be used to hold the data as the number of books held in the library changes, and explain why your suggested data structure is suitable.

(iv) Implement a function
Function IsDateValid(MyDate : Date): BOOLEAN
which uses a case statement, and checks that the value of day is valid for the month. The function should return TRUE if the data is valid, and FALSE otherwise. (For example, if the day were given as 30 and the month as 2, the function would return false; but if the day were given 30 and the month 6, the function would return true.)

(v) A problem exits with the year field in date. Explain what this problem is, and give a new definition of the Date structure which solves it.

[4]

[1]

[2]

[5]

[2]

END;

(ii) A sample definition of StaticLibraryCatalogue follows:

StaticLibraryCatalogue= ARRAY[0..1000] OF Book;

(iii)

• A suitable data structure would be a dynamic linked list,
• Because it can grow with the size of the library, and items can be added and removed from it arbitrarily.

(iv) A sample of definition of IsDateValid follows:

FUNCTION IsDateValid(MyDate : Date)
BEGIN
      CASE MyDate.Month OF
           2              : IF MyDate.Day > 28 THEN IsDateValid:= FALSE;
          4,6,9,11     : IF MyDate.Day > 30 THEN IsDateValid:= FALSE;
         OTHERWISE : IsDateValid:= TRUE;
     END; { case }
END;

(v)

• The problem is that the year field is only represented by 2 digits - the "Year 2000 problem".
• It can be corrected by using 4 digits to represented the Year field, or by not bounding it to 99, for example:
  TYPE Date = RECORD
                              Day      : Integer of [1..31];
                              Month : Integer of [1..12];
                              Year     : Integer of [0..];
                        END;