**UNIVERSITY EXAMINATIONS: 2014/2015**

**ORDINARY EXAMINATION FOR THE BACHELOR OF BUSINESS**

**INFORMATION TECHNOLOGY**

**BBIT 106 DATA STRUCTURES AND ALGORITHIMS – DISTANCE**

**LEARNING**

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

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

**QUESTION ONE [30 MARKS]**

a) Describe the steps for designing an algorithm. [5 Marks]

b) Differentiate between a walk through and a desk check as used in testing the algorithm. [4 Marks]

c) Describe any three operations performed in a binary tree data structure. [6 Marks]

d) Design an algorithm that inserts a node at the beginning of a linked list. [5 Marks]

e) Design an algorithm that uses two nested FOR loops to print the pattern below:

*

* *

* * *

* * * *

* * * * *

* * * * * *

* * * * * * *

* * * * * * * *

[6 Marks]

[a].Describe linear probing as one of the techniques for solving collisions in a hash table.

[4 Marks]

**QUESTION TWO [20 MARKS]**

(a) Design an algorithm using a pseudo code that uses the SWITCH keyword to prompt

the user to enter a grade then display the remarks using the criteria below.

Grade Remark

1 Agree

2 Strongly agree

3 Disagree

4 Strongly disagree

5 Neither agree nor disagree

[8 Marks]

(b) Calculate the big O for the in each of the following functions:

[6 marks]

(c) Briefly describe why algorithm analysis is necessary. [6 Marks]

**QUESTION THREE [20 MARKS]**

a) Briefly explain how array elements can be accessed. [6 Marks]

b) Explain the difference between static and dynamic arrays. [6 Marks]

c) Design an algorithm using a pseudo code to calculate and display average score for

forty scores keyed in by the user. [8 Marks]

**QUESTION FOUR [20 MARKS]**

a) Define a queue ADT and hence explain any three operations of a queue. [6 marks]

b) Define a stack ADT and hence outline any applications of a stack ADT. [8 Marks]

c) A binary tree is a tree in which each parent node can have a maximum of two child

nodes. Each node has two pointers- left pointer and right pointer. Given a binary tree

below, you are required to display its elements using in-order and preorder traversals.

[6 Marks]

**QUESTION FIVE [20 MARKS]**

a) Design an algorithm using pseudo code to sort elements by insert sort technique.

[8 Marks]

b) Design an algorithm using pseudo code to search elements in an array of size n by linear search. [8 Marks]

c) Briefly explain the two techniques of traversing a graph ADT. [4 Marks]