UNIVERSITY EXAMINATIONS: 2018/2019
EXAMINATION FOR BACHELOR OF SCIENCE IN INFORMATION
BIT 3101A: DATA STRUCTURES AND ALGORITHMS
MODE: FULL TIME/PART TIME/DISTANCE LEARNING
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.
b) Describe the scenario under which binary search algorithm can be used.
c) Describe two advantages of selection sort
d) Define the graph data structure.
e) Using stack ADT, convert the following infix expressions to prefix:
i. (𝐴 + 𝐵) * (𝐶 + 𝐷) * (𝐸 + 𝐹)
ii. 𝐴 + ((𝐵 + 𝐶) * (𝐷 + 𝐸))
iii. 𝐴 * 𝐵 * 𝐶 * 𝐷 + 𝐸 + F
f) Briefly explain three methods of handling collisions in a hash table.
g) Briefly explain the average, best and worst case complexity.
QUESTION TWO [20 MARKS]
a) Discuss the steps involved in the development of an algorithm.
b) Given the array below, use bubble sort to arrange the elements in ascending order.
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
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.
QUESTION THREE [20 MARKS]
a) Given the directed graph below, use adjacency matrix to represent the graph.
b) Distinguish between a linear data structure and non-linear data structure. Give one example
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.
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.
QUESTION FOUR [20 MARKS]
a) Write a recursive algorithm in pseudo code to calculate the nth Fibonacci number.
b) Write an algorithm for converting infix expression to postfix expression.
c) Heapify the following binary tree to make it a maximal heap.
d) Define the priority queue abstract data type and give two operations associated with priority
QUESTION FIVE [20 MARKS]
a) Design an algorithm using pseudo code to convert decimal number (a number in base 10) to
its binary equivalent.
b) Describe any two advantages of singly-linked list over contiguous list.
c) Design an algorithm for inserting a new node in middle of a singly linked list.
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