August 1999
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) Briefly explain the following terms :

(i) Sorting

(ii) Searching

(iii) White box testing

(iv) Black box testing

 

  

[1]

[1]

[1]

[1]
(b) (i) Explain, informally, how a selection sort works, and state how many passes of an unsorted list of length N it will take to ensure the list is sorted.

(ii) Explain, informally how a binary search works, and state the maximum number of passes it will take over a list of length N to find an item.

 

 [3]

 

[3]
(c) Given the following definition of a binary tree, and the procedure FooBar

TYPE

TreeType: ^TreeNode;
TreeNode = RECORD

left : TreeType;
data : Integer;
right : TreeType;

END;

PROCEDURE (FooBar VAR root : TreeType; item : Integer)
Begin

IF root == Nil THEN
BEGIN

New(root);
Root^.data :=item;
Root^.left:=Nil;
Root^.right:=Nil;

END
ELSE

IF item < root^.data THEN

FooBar(root^.left, item)

ELSE

FooBar(root^.right, item);

END;

(i) Describe the effect of the procedure FooBar on the root of a tree like the one above.

(ii) Assuming an initially empty tree, illustrate, with the aid of a diagram, the tree resulting from the following code fragment :

Foobar(6);
Foobar(2);
Foobar(6);
Foobar(4);
Foobar(9);
Foobar(1);
Foobar(5);

 

  

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

[2]

 

[4]
(d) Write a recursive function, Power, which takes two integer arguments, x and y, and returns xy. You can assume that both parameters will be greater than zero.

 

 [4]