**UNIVERSITY EXAMINATIONS: 2010/2011 **

**SECOND YEAR STAGE EXAMINATION FOR THE DEGREE OF BACHELOR **

**OF SCIENCE IN INFORMATION TECHNOLOGY **

**BIT 2102: DATA STRUCTURES AND ALGORITHMS **

**DATE: AUGUST 2011 TIME: 2 HOURS **

**INSTRUCTIONS: Answer question ONE and any other TWO questions**

**Question One [30 Marks]**

(a)Describe the following terms:

(i) Abstract Data Types (ADT)

(ii) Data structures

(iii)Data abstraction and

(iv)Structured data types [4 Marks]

(b)Using examples, explain the meaning of the following terms:

i) Full-binary tree and

ii)complete binary tree [4 Marks]

(c) (i) Explain why a queue is a two point structure where a stack is one point structure. [2 Marks]

(ii) State an example of the ADT Queue in everyday life and ADT Queue applications in computer

science. [2 Marks]

(iii)Distinguish between a queue and a priority queue giving an example of each. [4 Marks]

(d) (i) Beginning with an empty binary search tree (BST) what binary search tree is formed when you

insert the following values in the order given: 60,70,20,10,40,30,50 [4 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? Demonstrate with an example. [4 Marks]

(e) (i) Explain how a binary search algorithm works. What properties must the input have?[4 Marks]

(ii) What is the worst-case time for binary search algorithms? [2 Marks]

**Question Two [20 Marks]**

a) (i) Increasing the size of a dynamically allocated array can waste storage and time. Explain

[4 Marks]

(ii) Show how to increase the size of a dynamically allocated array. [4 Marks]

b) Suppose that you have a stack S and an auxiliary stack T. Show how you can do the following by

using only ADT stack operations:

(i) Displaying the contents of S in reverse order, that is, displaying the top last[3 Marks]

(ii) Count the number of items in S leaving S unchanged. [3 Marks]

c) Suppose that pointers require two bytes of storage and values require four. How much total storage

is required for a binary tree of N items? Derive answers for pointer, three-array and single array

storage. [6 Marks]

**Question Three [20 Marks]**

a) The tribonacci sequence is defined by the equations

(i) Find t4 and t5. [2 Marks]

(ii) Write a recursive algorithm to compute [3 Marks]

b) Evaluate the following postfix expressions: AB+C-DE+*. Show the status of the stack after each

step assume the following values for the identifiers: A = 7, B = 3, C = -12,

D = 5, E =2.

[4 Marks]

c) Write down the functional specification, preconditions and post conditions for the following Queue

operations:

t1 = t2 = t3 =1, tn = tn−1 + tn−2 + tn−3 n ≥ 4

tn , n ≥1

(i) QueueIsEmpty

(ii) QueueDelete and

(iii) GetQueue Front [6 Marks]

d) (i) Explain how does bubble sort works. [2 Marks]

(ii) Estimate how many times faster an average successful search will be in a sorted array

of 100,000 elements if it is done by binary search versus sequential search [3 Marks]

**Question Four [20 Marks]**

a) Describe briefly the following terms: –

(i) Recursions algorithm

(ii) Order of magnitude analysis

(iii) Algorithm design

(iv)Complexity of algorithm [8 Marks]

b) Explain how a circular linked list eliminates special cases for insertion and deletion.

[2 Marks]

c) The functions below represent the running time of programs, as the input n increases: f

(n) = nlogn, f (n) = 4n, f (n) =n!, f (n) = 6n2

i) Arrange them in order of increasing growth rate. [2 Marks]

ii) Sketch in the same axis (n version time) to illustrate the growth

of the function as in increases. [4 Marks]

d) Convert the following infix expression to postfix form. Show the status of the stack

after each step of the algorithm: A/B/C-(D+E)*F. [4 Marks]

**Question Five [20 Marks]**

(a)(i) Write down the pseudocode for mergesort on an array A of N items [4 Marks]

(ii) Demonstrate that mergesort satisfies the criteria for recursion. [4 Marks]

(b)Give an intuitive interpretation of how f and g are related if f(n)=O(g(n)). [2 Marks]

(c)Explain the meaning of the following terms: (i) recurrence relations and (ii) initial conditions.

[2 Marks]

(d)(i) Represent the following expression ((A−C)*D)/(A+ (B + D)) as a binary tree for and write the

prefix and postfix form of the expression. [5 Marks]

(ii) How many different trees are there with three nodes? Draw each. [3 Marks]