UNIVERSITY EXAMINATIONS: 2017/2018
EXAMINATION FOR DEGREE OF BACHELOR SCIENCE/BUSINESS
BBIT 106/BIT 3101A: DATA STRUCTURES AND ALGORITHMS
MODE: FULL TIME/PART TIME/DISTANCE LEARNING
DATE: JULY.2018 DURATION: 2 HOURS
INSTRUCTIONS: Answer Question ONE and any other TWO questions
QUESTION ONE [30 MARKS]
a) Describe the steps for designing an algorithm.
b) Differentiate between a walk through and a desk check as used in testing the algorithm.
c) Describe the algorithms for each of the following operations performed in a linked list data structure:
i. Delete a node from the middle
ii. Insert a node at the beginning
d) Discuss how heuristic algorithms work and give two examples.
e) Design an algorithm to store patient number, name and consultation fee in a structure called
PATIENT. The design should allow users to key in all the values (patient number, name and
consultation fee) for ten (10) patients and then display the total fee chargeable to all the patients.
f) Describe linear probing as one of the techniques for solving collisions in a hash table.
QUESTION TWO [20 MARKS]
a) Design an algorithm using a pseudo code that uses a selection structure to prompt the user to enter a
grade then display the remarks using the criteria below.
B Very good
b) Describe any three rules used to estimate the big O value for a complexity f(n) were n is the size of
c) Briefly describe why algorithm analysis is necessary.
QUESTION THREE [20 MARKS]
a) Briefly explain how array elements can be accessed.
b) Explain the difference between static and dynamic arrays.
c) Design an algorithm to swap two variables using a flowchart.
d) Design an algorithm using a pseudo code to calculate and display average score for forty scores keyed
in by the user.
QUESTION FOUR [20 MARKS]
a) Define a queue ADT and hence explain any three applications of a queue.
b) Define a stack ADT and hence outline any three operations performed on a stack.
c) Discuss the sufficient conditions for a heap abstract data type
d) Construct a binary search tree to store the names of wildlife animals below
Lion, Giraffe, Elephant, Kangaroo, snake, monkey and Zebra.
QUESTION FIVE [20 MARKS]
a) Design an algorithm using pseudo code to sort elements by insert sort technique.
b) Design an algorithm using pseudo code to search elements in an array of size n by linear search.
c) Describe the algorithm for depth first search traversal in a graph.
d) Briefly explain the two techniques of representing graph ADT.