**UNIVERSITY EXAMINATIONS: 2012/2013**

**SECOND YEAR EXAMINATION FOR THE BACHELOR OF **

**SCIENCE IN INFORMATION TECHNOLOGY**

**DATA STRUCTURES AND ALGORITHMS**

**DATE: DECEMBER, 2012 TIME: 2 HOURS**

**INSTRUCTIONS: Answer Question ONE and any other TWO**

**QUESTION ONE**

a) Briefly define the following terms: [5 Marks]

i. Abstract data type (ADT)

ii. Data abstraction

iii. Data encapsulation

iv. Spanning tree

v. Order of magnitude

b) List and describe any five properties that an algorithm must possess. [5 Marks]

c) State and explain any six orders of magnitude commonly used in asymptotic time

complexity analysis. [6 Marks]

d) Distinguish between the following terms:

i. Analysis of algorithm and complexity of algorithm

ii. Depth-First-Search and Breadth-First-Search traversal algorithm

iii. Binary tree and binary search tree.

[6 Marks]

e) When sorting an array using mergesort

i. Do the recursive calls to mergesort depend on the values in the array, the number

of items in the array, or both? Explain. [3 Marks]

ii. In what step of mergesort are the items in the array actually swapped (that is

sorted)? Explain [3 Marks]

f) For large arrays and in the worst case is selection sort faster than insertion sort?

Explain [2 Marks]

**QUESTION TWO**

a) The following function computes the product of the first N≥1 real numbers in an

array.Demonstrate that this function is recursive by listing the criteria of a recursive

solution and state how this function satisfies the properties of a recursion function.

Double Product (const double A [], int N)

// Preconditions: 1<=N<=Max Size of A

// Post conditions: Return the product of the first N items in A; A is unchanged

{

If (N= =1)

return A [0];

else

return A [N-1]*Product (A, N-1);

} // end Product.

[8 Marks]

b) Write down the C++ specification for the array-based implementation of the ADTlist illustrating your answer with a diagram [6 Marks]

c) i. Explain how the use of the new operator can be used to allocate an array

dynamically. [2 Marks]

ii. Increasing the size of a dynamically allocated array can waste storage and time.

Explain [2 Marks]

iii. Show how you can increase the size of a dynamically allocated array [2 Marks]

**QUESTION THREE**

a) Define the structure node and write the C++ definition of the term. [3 Marks]

b) What is the value of the member next in the last node in the list [1 Mark]

c) What is a head pointer? Show how the pointer is created. [2 Marks]

d) i. Using the current pointer cur, write down the specification on how to display the

data in a linked list to which head points. [3 Marks]

ii. Using a diagram explain how to delete a specified node from a linked list. Write

the assignment statement to accomplish the task [5 Marks]

iii. For the case of (ii) above does the method work for any node N, regardless of

where in the linked list it appears? [2 Marks]

e) i. Beginning with an empty binary search tree, what binary search tree is formed

when you insert the following values in the order given: W,T,N,J,A,B,E

[2 Marks]

ii. If you delete an item from a binary search tree and then insert it back into the

tree, will you ever change the shape of the tree? [2 Marks]

**QUESTION FOUR**

a) i. What is an ADT stack and why is it referred as LIFO? [2 Marks]

ii. Distinguish between an infix form of expression and postfix form of the

expression [2 Marks]

iii. Explain how a tree can be used to represent an expression [2 Marks]

b) i. Represent the expression as a binary tree and write the prefix and postfix form of

the expression: (((A+B)*C+D)*E)-((A+B)*C-D). [6 Marks]

ii. Find the value of the postfix expression: ADBCD*-+* using the following

identifiers A=1, B=2, C=3 and D=4. [4 Marks]

c) For the following situations, which of these ADTs( 1 through 4) would be most

appropriate (1) a queue (2) a stack, (3) a list, (4) none of these [4 Marks]

i. Integers that needs to be sorted

ii. The items on a cash register tape

iii. A program that uses backtracking

iv. Airplanes that stack above a busy airport waiting to land

**QUESTION FIVE**

a) Consider a sequential search of N data items.

i. If the data items are sorted into ascending order, how can you determine that

your desired item is not in the data collection without always making N

comparisons? [3 Marks]

ii. What is the order of the sequential search algorithm when the desired item is not

in the data collection? Do this for both sorted and unsorted data, and consider the

best, average and worst cases. [4 Marks]

b) How does binary search works? What properties must the input have? [3 Marks]

c) i. Define

f (n) O g(n)

. What is this notation called? [1 Mark]

ii. Give an intuitive interpretation on how f and g are related if

f (n) O g(n)

[2 Marks]

d) i. State a necessary and sufficient condition for a graph to have a spanning tree

[2 Marks]

ii. What is a minimal spanning tree? [2 Marks]

iii. Explain how Prims’ algorithm finds a minimal spanning tree. [3 Marks]