**UNIVERSITY EXAMINATIONS: 2018/2019**

**EXAMINATION FOR BACHELOR OF SCIENCE IN INFORMATION **

**TECHNOLOGY**

**BIT 3101A: DATA STRUCTURES AND ALGORITHMS**

**MODE: FULL TIME/PART TIME/DISTANCE LEARNING**

**ORDINARY EXAMINATIONS **

**DATE: NOVEMBER, 2018 TIME: 2 HOURS **

**INSTRUCTIONS: Answer question ONE and any other TWO**

**QUESTION ONE [30 MARKS]**

a) State and explain the data structures used in BFS and DFS algorithm of a graph ADT.

4 Marks

b) Describe the scenario under which binary search algorithm can be used.

2 Marks

c) Describe two advantages of selection sort

4 Marks

d) Define the graph data structure.

2 Marks

e) Using stack ADT, convert the following infix expressions to prefix:

i. (𝐴 + 𝐵) * (𝐶 + 𝐷) * (𝐸 + 𝐹)

ii. 𝐴 + ((𝐵 + 𝐶) * (𝐷 + 𝐸))

iii. 𝐴 * 𝐵 * 𝐶 * 𝐷 + 𝐸 + F

9 Marks

f) Briefly explain three methods of handling collisions in a hash table.

6 Marks

g) Briefly explain the average, best and worst case complexity.

3 Marks

**QUESTION TWO [20 MARKS]**

a) Discuss the steps involved in the development of an algorithm.

5 Marks

b) Given the array below, use bubble sort to arrange the elements in ascending order.

6 Marks

c) Estimate the complexity of following pseudo code:

1. Declare i ,j and n

2. Get value of n

3. For i=1 To i<=n

3.1. For j=1 To j<=i

3.1.1. Display “Hello”

3.1.2. Update j=i+1

3.2. END FOR

3.3. Update I=I+1

5. END FOR

3 Marks

d) Consider the binary tree below:

Write the order of the nodes visited in:

i. An in-order traversal.

ii. A pre-order traversal.

iii. A post-order traversal.

6 marks

**QUESTION THREE [20 MARKS]**

a) Given the directed graph below, use adjacency matrix to represent the graph.

7 Marks

b) Distinguish between a linear data structure and non-linear data structure. Give one example

for each.

4 Marks

c) When the entries 7, 4, 6, 1, 2, 3, 8, 5 are successively inserted into an initially empty binary

search tree, state and explain the height of the resulting tree.

3 Marks.

d) The following sequence of operations were performed on stack s:

Push(1),push(2), pop(),(push(1),push(2),pop(),pop(),pop(),push(2),pop() determine the

sequences of popped out values.

6 Marks

**QUESTION FOUR [20 MARKS]**

a) Write a recursive algorithm in pseudo code to calculate the nth Fibonacci number.

5 Marks

b) Write an algorithm for converting infix expression to postfix expression.

6 Marks

c) Heapify the following binary tree to make it a maximal heap.

6 Marks

d) Define the priority queue abstract data type and give two operations associated with priority

queue.

3 Marks

**QUESTION FIVE [20 MARKS]**

a) Design an algorithm using pseudo code to convert decimal number (a number in base 10) to

its binary equivalent.

6 Marks

b) Describe any two advantages of singly-linked list over contiguous list.

4 Marks

c) Design an algorithm for inserting a new node in middle of a singly linked list.

4 Marks

d) Take a queue containing numbers 10,15,5,25,30 in which 30 has been inserted first. After

performing the following operations, what would be the contents of the queue?

i. Delete two elements

ii. Insert 7 and then 20

iii. Delete an element

6 Marks