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]
