April 2000
AP207 : ADVANCED PROGRAMMING TECHNIQUES

QUESTION 5

Total Marks: 15 Marks

• Question 1
• Question 2
• Question 3
• Question 4
• Cover Page

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

Do not award half marks. Do not deduct marks for trivial syntactic errors. Alternative correct answers should be given credit, unless otherwise indicated in the marking scheme.

When an aeroplane approaches a certain airport,a record is entered in a queue which contain the right registration number,which is a string of up to ten characters,an arrival number,which si an integer indicating the order in which aeroplanes arrived in the airport, and a landing priority,which can be one of urgent,normal or low.

(a)Briefly explain what i meant by a queue data structure.[2 marks ]
• A queue is an ordered data structure;(1 mark)
• Where item first in are first out,and items last in are last out.(1 mark)
[2 marks ]

Give a suitable type declaration for the LandingPriority type described above,such that variables of this type can have any one of the values urgent normal or low [1 mark ]
(b)TYPE LandingPriority = {urgent, normal, low}; [1 mark ]

(c)Give a definition of a data tructure called FlightArrival which holds all of the
right details mentioned above.[4 marks ]
A sample definition of FlightArrival follows:
TYPE
  FlightArrival= RECORD
    Registration : STRING[10];
    ArrivalNumber : INTEGER;
    Priority : LandingPriority;
  END;
And the following marking scheme should be used:
• A Correctly tructured TYPE RECORD statement;(1 mark)
• Registration : STRING[10]; (1 mark)
• ArrivalNumber : INTEGER; (1 mark)
• Priority : LandingPriority; (1 mark)
[4 marks ]

(d)Give a definition of a data tructure which can be used to implement a dynamic queue of FlightArrival structures.[3 marks ]
A sample definition of the queue follows:
TYPE NodePtr = ˆNode;
  Node= RECORD
    Next : NodePtr;
    Data : FlightArrival;
  END;
  Queue= RECORD
    Front, Rear : NodePtr;
  END;
And the following marking scheme should be used:
• Declaring a Node for the queue elements;(1 mark)
• Which contains FlightArrival and a pointer to the next node;(1 mark)
• Declaring Queue which has pointers to the Front and Rear elements.(1 mark)
[3 marks ]

(e)Write a function,called PeekNextLanding the signature of which is given below, which takes a queue q and returns a copy of the first FlightArrival in q which has a urgent landing priority,or the first element in the queue should there not be an element with this priority.You may assume standard queue manipulation routines, and the function should not remove the element from the queue.

FUNCTION PeekNextLanding(q : Queue) : FlightArrival;
[5 marks ]
A sample definition of PeekNextLanding follows:
FUNCTION PeekNextLanding(q : Queue) : FlightArrival;
VAR CurrentLanding: FlightArrival;
BEGIN
   CurrentLanding:= Head(q);
   WHILE NOT EmptyQueue(q) DO BEGIN
      CurrentLanding:= Head(q);
      IF CurrentLanding.Priority= urgent THEN
          PeekNextLanding := CurrentLanding;
    END;
    PeekNextLanding:= CurrentLanding;
END;
And the following marking scheme should be used:
• Taking a copy of the first element,to ensure it can be returned by default if
required;(1 mark)
• Iterating along the queue whilst it is non empty;(1 mark)
• Taking the item at the head of the queue on each iteration;(1 mark)
• And returning the element should it be found to have
CurrentLanding.Priority= urgent (1 mark)
• Returning the copy of the first element,if the list si empty and no other suitable
element has been found.(1 mark)
[5 marks ]