UNIVERSITY EXAMINATIONS: 2017/2018
EXAMINATION FOR THE DEGREE IN BBIT/BAC/Bsc IT/Bsc ICT
BIT3101A DATA STRUCTURES AND ALGORITHMS
MODE: FULL TIME/PART TIME/DISTANCE LEARNING
ORDINARY EXAMINATIONS
DATE: APRIL, 2018 DURATION: 2 HOURS
INSTRUCTIONS: Answer question ONE and any other TWO
QUESTION ONE [30 MARKS]
a) Describe THREE reasons for analyzing an algorithm.
3 Marks
b) Using depth first search traversal, traverse the directed graph in fig 1 below:
Fig 1: Directed graph
5 Marks
c) Describe the procedure for testing an algorithm.
4 Marks
d) Briefly explain how divide and conquer algorithms work.
4 Marks
e) Discuss greedy algorithms. Give two examples.
6 Marks
f) A mathematics teacher at Mbooni girls high school wants to use a computer program to assist
his students learn how to expand a binomial expression that has been raised to some large
power. Using your knowledge of dynamic programming algorithms, provide the design using
a pseudo code for this program such that the user will key in the large power, then the system
calculates the binomial coefficient.
8 Marks
QUESTION TWO [20 MARKS]
a) State and explain the TWO sufficient conditions for a binary tree to be a heap.
4 Marks
b) The array represented in fig 2 below is to be sorted using bubble sort technique. Showing
your working rearrange the elements in ascending order.
Fig 2: one dimensional array.
6 Marks
c) Discuss the various ways of classifying algorithms. Give examples.
8 Marks
d) Differentiate between deque and dequeue as used in queue ADT.
2 Marks
QUESTION THREE [20 MARKS]
a) Assuming you are given the complexity function f(n) of an algorithm, explain, using an
example any THREE rules that can be used when estimating the big O complexity of that
algorithm.
6 Marks
b) The elements stored in a hash table are not always sorted. Explain.
3 Marks
c) Discuss any FOUR techniques for resolving a collision in a hash table ADT.
8 Marks
d) State and explain any THREE applications of stack ADT.
3 Marks
QUESTION FOUR [20 MARKS]
a) Given the infix expression: (((A+B) *C+D) *E)-((F+G) *H-I) and using stack ADT convert
this expression to its prefix form.
6 Marks
b) Describe the procedure for inserting a new node to store integer value 7 between 4 and 6 in
the linked list represented in fig 3 below.
Fig 3: singly linked list
5 Marks
c) Consider the business process case below:
In a certain chain store in town, a customer picks items he/she wants to buy and puts them in
a shopping basket provided at the entrance. The customer then proceeds to the teller/cashier.
The teller scans each item in the basket using a bar code reader to ascertain the price and
quantity. The program then computes the total cost of the items. The customer pays for the
items using a debit card, credit card, cash or by mobile money. The program then prints the
receipt. The transaction is then closed. Design an algorithm for this business process using a
flowchart.
9 Marks
QUESTION FIVE [20 MARKS]
a) Define a graph ADT.
2 Marks
b) Given that V = {A, B, F, T, R, S, W} is set of seven town of population 1000, 1500, 1200,
1500, 1600, 1800 and 20000, respectively. E ={(x,y) | if x more populated than y} where V
and E are set of vertices and edges respectively, construct a directed graph.
6 Marks
c) Represent the graph constructed in b) using adjacency matrix.
4 Marks
3 4 6 8 9
null
d) The tree data structure represented by fig 5 below is a binary search tree, give two reasons to
support this claim.
fig 5: Tree ADT
2 Marks
e) Traverse the tree ADT in fig 5 using in-order traversal.
4 Marks
f) Explain your observation of the output after the traversal in e).
2 Marks
