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
