December 1999
AP207 : ADVANCED PROGRAMMING TECHNIQUES

QUESTION 1 (Compulsory)

Total Marks: 30 Marks

• Question 2
• Question 3
• Question 4
• Question 5
• Cover Page

Click to access
SUGGESTED SOLUTIONS
for Question 1

Briefly explain the main characteristics of the following terms:

(i)Binary trees [1 mark ]

(ii)N-ary trees [1 mark ]

(iii)FIFO queues [1 mark ]

(iv)LIFO queues [1 mark ]

[4]

In terms of lookup and update times, briefly identify the differences between arrays and dynamic linked lists .

[2]

(i)Explain, informally, how a bubble sort works.[3 marks ]

(ii)Explain, informally, how hashing works.[3 marks ]

(iii)Briefly identify the most common problem with hashing.[1 mark ]

[7]

(i)Write an iterative function, called Remainder , the signature of which is given below, which takes in two integer parameters by value and returns the remainder of x /y .You may not use any library functions.[3 marks ]

FUNCTION Remainder(x: INTEGER, y: INTEGER): INTEGER;

(ii)Write an iterative function, called IsPrime , the signature of which is given below, which takes an integer parameter by value and returns TRUE if the parameter is prime and FALSE otherwise. Note that an integer N (for N2)is prime if the result of dividing it by each of 2 through to (N/2)-1 produces a non zero remainder. [4 marks ]

FUNCTION IsPrime(x: INTEGER): BOOLEAN;

[7]

Assume the following definition of a double linked list,together with the signature of the procedure Remove ,which removes from the list x the item pointed to by y :

(i)Write a recursive function, called Search , the signature of which is given below. This function takes in two parameters by value, the first of which is a double linked list, and the second being an integer, and returns either a pointer to the first occurrence of the integer in the list or a NULL pointer if the integer is not in the list.[5 marks ]

FUNCTION Search(x: List,y: INTEGER): NodePtr;

(ii)Write a recursive procedure, called SearchAndRemove , the signature of which is given below, which takes in a reference parameter which is a list, and a value parameter which is an integer. Upon termination of the procedure, the list should have all occurrences of the integer removed.You should assume the existence of the Search function defined above, as well as the procedure Remove , the signature of which is given above. [5 marks ]

PROCEDURE SearchAndRemove(VAR x :LIST,y: INTEGER);

[10]