**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