August 2000
AP207 : ADVANCED PROGRAMMING TECHNIQUES

QUESTION 2

Total Marks: 15 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

You are to implement a data structure which can be used to store details of Informatics students. Each student is to be represented by a record, and the system requires to store details of each students name, number and whether or not the student has passed or failed.

(a) Define a simple enumerated data type, called ResultsCategory, which can take on either of the values Pass or Fail. [1 mark]
(a) Type ResultsCategory= (Pass, Fail); [1 mark]

(b) Define a suitable data structure for a student, called Student, which contains the student’s name - a string of up to 50 characters in length, the student’s identification number, which is an integer, and the student’s result, which is of type ResultsCategory given above. [4 marks]
(b) A sample definition follows:
Type
Student= Record
  Name : String[50];
  ID : Integer;
  Result : ResultsCategory;
End;
And the following marking scheme should be used:
• A correctly structured Record; (1 mark)
• The Name; (1 mark)
• The ID; (1 mark)
• The Result; (1 mark)
[4 marks]

(c) It has been decided that the complete set of all student details should be held in a double linked list. Give a definition of a double linked list, called StudentList, where nodes in the list consist of a Student structure and pointers to the next and previous nodes in the list.
You may assume that both ends of the list are represented by null pointers. [5 marks]
Type ListElemPtr= ˆListElem
ListElem= Record
  Datum: Student;
  previous, next: ListElemPtr;
End;
StudentList= Record
  Length: Integer;
  Front, Back: ListElemPtr;
End;
And the following marking scheme should be used:
• Declaring a pointer type to point to an element in the list; (1 mark)
• Declaring a data structure to represent an element in the list; (1 mark)
• Which contains the students details and the previous and next pointers; (1 mark)
• Declaring a data structure to represent the list; (1 mark)
• Which contains pointers to the front and back of the list; (1 mark)
[5 marks]

(d) Define a procedure, called Separate, the signature of which is given below, which takes a StudentList, and references to two other StudentLists. On termination, the procedure should have copied all of the students in the original list with passes into one list, and fails into the other. You may wish to use the standard list manipulation function Add, which takes a list element E and adds it to the list L. You are not required to implement Add.
PROCEDURE Add(Var L : StudentList; Student E);
PROCEDURE Separate(RegisterList : StudentList;
VAR PassList, FailList: StudentList); [5 marks]
(d) A sample definition of Separate follows:
Procedure Separate(RegisterList: StudentList; Var PassList, FailList: StudentList);
Var CurrentElement: ListElem;
Begin
  CurrentElement:= RegisterListˆ.Front;
  while(CurrentElement!= NULL) do begin
    if CurrentElement.Datum.Result= Pass then
    Add(PassList, CurrentElement.Datum);
    else
    Add(FailList, CurrentElement.Datum);
    CurrentElement:= CurrentElementˆ.Next;
  end;
End;
And the following marking scheme should be used:
• Declaring a local temporary to manipulate the current element; (1 mark)
• Bounds checking to ensure the source list is non empty; (1 mark)
• Checking the value of Pass or Fail in the current element; (1 mark)
• And adding it to the correct list as appropriate; (1 mark)
• Iterating along the source list until the end is reached; (1 mark)
[5 marks]