**UNIVERSITY EXAMINATIONS: 2018/2019**

**EXAMINATION FOR BACHELOR OF SCIENCE IN INFORMATION **

**TECHNOLOGY/ BACHELOR OF BUSINESS INFORMATION TECHNOLOGY**

**FULL TIME/PART TIME/DISTANCE LEARNING**

**BBIT 106/BIT 3101A: DATA STRUCTURES AND ALGORITHMS **

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

**INSTRUCTIONS: Answer QUESTION ONE and any other TWO QUESTIONS**

**QUESTION ONE [30MARKS]**

a) List at least two differences between linear and nonlinear data structure

[4 Marks]

b) Discuss the following cases used in estimating the complexity of an algorithm.

i. Best case

ii. Worst case

[4 Marks]

c) Express the following functions in terms of Big-O notation

[2 Marks]

d) Explain three reasons why even a presumably good algorithm must be analyzed.

[3 Marks]

e) Suggest and explain a suitable algorithm in each of the following fields:

i. Mining in databases

ii. Determine the path with minimum distance from start node is S and final state is T

where S and T are nodes in a search space.

[4 Marks]

f) Given a one dimensional array below, explain how you can locate an integer 2, using binary

search algorithm.

1 2 3 5 9 11 15

[5 Marks]

g) Suppose you are given an infix expression and asked to convert it into postfix. Explain the

general procedure of achieving this.

[8 Marks]

**QUESTION TWO [20 MARKS]**

a) You are given a one dimensional array below:

6 5 7 8 4 5 6 9 10

i. Remove the elements from this array and store them in a binary search tree.

[3 Marks]

ii. Traverse the tree in (i) using post order traversal

[3 Marks]

iii. Discuss any three operations you can perform on binary search tree apart from

traversal.

[4 Marks]

b) Assuming A,B,D,F, and G represent vertices of a graph and adjacency matrix below:

i. Construct a directed graph using this adjacency matrix.

[6 Marks]

ii. Traverse the resultant graph using depth first search.

[4 Marks]

**QUESTION THREE [20 MARKS]**

a) Differentiate between a post condition and precondition in an algorithm.

[2 Marks]

b) Explain any two advantages and disadvantages of selection sort

[4 Marks]

c) Consider the following array of integers: 5, 1, 12, -5, 16, 2, 12, 14

Show the steps to sort the numbers in ascending order using a selection sort.

[4 Marks]

d) Differentiate between a stack and a queue data structure

[2 Marks]

e) Define the priority queue abstract data type and give two operations associated with priority

queue.

[4 Marks]

f) Consider the following queue, where queue is a circular queue having 6 memory cells,

Front=2, Rear=4

Queue: _, A, C, D, _, _

Show the queue as following operations take place:

i) F is added to the queue

ii) Two letters are deleted

iii) R is added to the queue

iv) S is added to the queue

[4 Marks]

**QUESTION FOUR [20 MARKS]**

a) Differentiate between linear probing and chaining as collision solving techniques in a hash

table.

[4 Marks]

b) Design an algorithm that uses arrays to prompt the user to enter twenty six integer values

then displays only those integers that are odd.

[6 Marks]

c) You are given the following linked list

i. Explain the procedure of deleting the node that stores 80 in this list.

[4 Marks]

ii. Explain two drawbacks of using linked lists

[2 Marks]

iii. State and explain how this list can be implemented.

[4 Marks]

**QUESTION FIVE [20 MARKS]**

a) Write a recursive algorithm in pseudo code to calculate the nth Fibonacci number.

[5 Marks]

b) Discuss how genetic algorithms work. Give one example of a genetic algorithm.

[5 Marks]

c) Heapify the following binary tree to make it a maximal heap.

[6 Marks]

d) Explain the General Properties of Spanning Tree

[4 Marks]