**UNIVERSITY EXAMINATIONS: 2016/2017**

**EXAMINATION FOR THE DEGREE IN BACHELOR OF **

**SCIENCE IN INFORMATION TECHNOLOGY/**

**BACHELOR OF BUSINESS INFORMATION TECHNOLOGY/**

**BIT2102 BIT 3101A BBIT 106 DATA STRUCTURES AND **

**ALGORITHMS**

**MODE: FULL TIME/PART TIME/DISTANCE LEARNING**

**ORDINARY EXAMINATIONS **

**DATE: AUGUST, 2017 DURATION: 2 HOURS**

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

**QUESTION ONE [30 MARKS]**

a) Differentiate between the following concepts as used in algorithm analysis.

i. Space complexity and time complexity

ii. Big O notation and theta notation

[4 Marks]

b) If you push the letters D, C, B and A in order onto a stack of characters and then pop

them, in what order will they be deleted from the stack?

[4 Marks]

c) Define a recursive function and give any two examples that can be solved recursively.

[4 Marks]

d) The numbers 20, 70, 68, 59,30,15,90,70,60,85 are to be stored for some processing in

that order. Write down the order in which the numbers will be printed if they are:

i. stored in a queue

ii. stored in a stack and

iii. stored in a binary search tree and traversed in order.

[9 Marks]

e) Explain the sufficient conditions for a binary tree to be a heap.

[2 Marks]

f) Design an algorithm for calculating Fibonacci series and estimate its big O.

[7 Marks]

**QUESTION TWO [20 MARKS]**

a) Write down the algorithm for merge sort and state its big O.

[6 Marks]

b) Performing operations such as delete and insert in a doubly linked list is not easy.

Explain.

[4 Marks]

c) Explain how the divide and conquer technique works. Give two examples.

[4 Marks]

d) Represent the following expression tree: (((A+B)*C+D)*E)-((A+B)*C-D) and write

the prefix and postfix expressions.

[6 Marks]

**QUESTION THREE [20 MARKS]**

a) Distinguish between preorder and postorder traversal of a binary tree

[4 Marks]

b) Consider the following of a table fields, construct a binary tree to represent them.

[4 Marks]

c) Describe two applications of binary search trees.

[2 Marks]

d) ) Explain why a queue is a two-point structure where a stack is one point structure

[3 Marks]

e) What is an algorithm?

[2 Marks]

f) Describe the following properties that an algorithm must have: precision, uniqueness,

finiteness, input and output.

[5 Marks]

**QUESTION FOUR [20 MARKS]**

a) Explain what is an in-order traversal for a binary tree?

[2 Marks]

b) Write an algorithm to execute an in-order traversal.

[3 Marks]

c) Estimate the order of magnitude for the expression

[4 Marks]

d) Describe two ways of representing a graph ADT.

[4 Marks]

e) Construct a directed graph with the vertices A,B,C,D and E using the information

below.

[5 Marks]

f) Briefly describe the depth first search algorithm as used in graph traversal.

[2 Marks]

**QUESTION FIVE [20 MARKS]**

a) If two or more values in a hash function, map to the same key, a collision is said to

occur. Collisions are not allowed in a hash table. Briefly describe the following

techniques for resolving collisions.

i. re-hashing

ii. chaining

iii. linear probing.

[6 Marks]

b) Differentiate between dynamic programming and backtracking algorithms. Give one

example for each.

[4 Marks]

c) Describe the guidelines for developing an algorithm using a pseudo code.

[5 Marks]

d) Describe the procedure for insert sort.

[3 Marks]

e) Re-arrange the following numbers in descending order using insert sort.

2,4,8,6,10,16,12,14,20,18.

[2 Marks]