**UNIVERSITY EXAMINATIONS: 2016/2017**

**EXAMINATION FOR THE DEGREE OF BACHELOR OF SCIENCE IN**

**INFORMATION TECHNOLOGY**

**BIT3101A BBIT106 DATA STRUCTURES AND ALGORITHMS**

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

**SUPPLEMENTARY/ SPECIAL EXAMINATIONS**

**DATE: JULY, 2017 TIME: 2 HOURS**

**INSTRUCTIONS: Answer Question One & ANY OTHER TWO questions.**

**QUESTION ONE [30 MARKS]**

a) Explain THREE guidelines for designing algorithms using a pseudo code.

(3 Marks)

b) Compare and contrast an algorithm and a program.

(4 Marks)

c) Describe the procedure for performing a dry run.

(3 Marks)

d) Explain the difference between algorithm analysis and algorithm testing.

(4 Marks)

e) Explain TWO techniques for resolving collisions in a hash table.

(4 Marks)

f) Describe THREE applications of directed graphs.

(3 Marks)

g) You are given some letters of alphabet stored in a one dimensional array as shown below.

F D B C A F H E G J

Store the letters in the order shown in the array, and store them in binary search tree (BST).

(6 Marks)

h) You are given binary tree shown below. Construct a maximal heap using this information.

(3 Marks)

**QUESTION TWO [20 MARKS]**

a) Design an algorithm using pseudo code to calculate and display the L.C.M of two numbers

keyed in by the user through the keyboard.

(8 Marks)

b) Discuss the TWO parameters determining the complexity of an algorithm.

(6 Marks)

c) For each of the following complexity functions for algorithms, estimate the big O and state

the family of the algorithm.

(6 Marks)

**QUESTION THREE [20 MARKS]**

A graph data structure is a collection of nodes called vertices, and the connections between them,

called edges. Graphs can be represented using adjacency matrix and/or adjacency lists. Use the

adjacency matrix below to construct a graph. (8 Marks)

a) Discuss the TWO techniques for graph traversal.

(6 Marks)

b) Describe the procedure for search a value in a database table assuming the records are not

sorted.

(6 Marks)

**QUESTION FOUR [20 MARKS]**

a) Define the term linear data structures. Give three examples of linear data structures.

(4 Marks)

b) Compare and contrast a class and structure.

(4 Marks)

c) Describe the algorithm for converting an infix expression into prefix using a stack ADT.

(6 Marks)

d) Define the term “genetic algorithms”. Give two examples of genetic algorithms.

(6 Marks)

**QUESTION FIVE [20 MARKS]**

a) Explain the concept of “sort algorithm”.

(2 Marks)

b) Consider the following one-dimensional array, with nine (9)

elements.

Use the given sort algorithm, to arrange the elements in ascending order.

i. Merge sort

ii. Heap sort

iii. Bubble sort.

(12 Marks)

c) Describe how you will insert a new node after the last node of the singly linked list below.

(6 Marks)