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)
