December 1998
AP207: ADVANCED PROGRAMMING TECHNIQUES

QUESTION 1 (Compulsory)

Total Marks: 20 Marks

 Click here to access other questions

Click to access
SUGGESTED SOLUTIONS
for Question 1

 
(a) Give two distinguishing characteristics (e.g., size, lookup and update policy/efficiency) for each of the following data-structures:
(i) linked-list [2]
(ii) array [2]
(iii) FIFO queue [2]
(iv) LIFO queue

 

 [2]
(b) Given the following tree:

pic1.gif (6659 bytes)

 
(i) Write a Pascal type definition, called TreeType that models the tree data-structure shown above. [3]
(ii) What will be printed when the tree shown above is passed to the procedure anonymous below? [2]
PROCEDURE anonymous(VAR root:TreeType);
VAR ptr,copy : TreeTypes;
    BEGIN
    ptr := root;
    WHILE (ptr <> Nil) DO
       BEGIN
       copy := ptr;
       IF (ptr^.Left <> Nil) THEN
           BEGIN
           ptr := ptr^.Left;
           copy^.Left := Nil;
           END
       ELSE
           BEGIN
           IF (ptr^.Right <> Nil) THEN
              BEGIN
              ptr := ptr^.Right;
              copy^.Right := Nil;
              END
           ELSE
              BEGIN
              WRITELN(ptr^.Data);
              ptr := ptr^.Up;
              END
           END
      END
END;

 
(iii) Does the procedure anonymous print out the integers held in the tree in a prefix, infix, or postfix style? [1]
(iv) What effect does the procedure have on the tree root? [1]
(v) Write a reursive procedure that performs a preorder traversal of the tree, printing out the integers held within the tree during the traversal. [5]