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: APRIL, 2019 TIME: 2 HOURS
INSTRUCTIONS: Award Marks for question ONE and any other TWO
QUESTION ONE [30 MARKS]
a) What are the steps to inserting a new item at the head of a linked list?
3 Marks
b) Discuss any four properties of a good algorithm.
4 Marks
c) Differentiate between walk through and desk check as used in dry run.
2 Marks
d) Differentiate between deque and dequeue as used in queue abstract data types(ADT).
2 Mark.
e) Differentiate between linear and non-linear data structures. Give one example for each type.
4 Marks
f) Explain the differences between array and linked list data structures.
4 Marks
g) Breadth first search(BFS) and depth first search (DFS) are two important techniques in graph
traversal. Describe a data structure used for each of these techniques.
4 Marks
h) State and explain the worst-case complexity of binary search.
4 Marks
i) Design an algorithm using pseudo code to read some integer n, then reverse the digits
3 Marks
QUESTION TWO [20 MARKS]
a) Describe the scenario under which binary search algorithm can be used.
2 Marks
a) Describe two advantages of selection sort
4 Marks
b) Using stack ADT, convert the following infix expression to prefix:
𝐴 + ((𝐵 + 𝐶) * (𝐷 + 𝐸))
4 Marks
c) Briefly explain three methods of handling collisions in a hash table.
6 Marks
d) Briefly explain the best and worst case complexity.
4 Marks
QUESTION THREE [20 MARKS]
a) Explain how you can reference all the elements in a one-dimension array.
2 Marks
b) Briefly explain how a linear search algorithm works.
2 Marks.
c) Design a pseudo code for searching using binary search tree.
6 Marks.
d) Explain the process for selection sort.
4 Marks.
e) Briefly explain the important factors considered while choosing a hash function.
4 Marks
f) What are different application of stack?
2 Marks
QUESTION FOUR [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) Take a queue containing numbers 10,15,5,25,30 in which 30 has been inserted first and 10 is the
last to be inserted. After performing the following operations, what would be the contents of the
queue?
i. Delete two elements
ii. Insert 7 and then 20
4 Marks
c) Write a recursive algorithm in pseudo code to calculate and display Fibonacci series once they user
keys in the number of terms n.
7 Marks
d) Describe the procedure of a post order traversal in a binary tree.
3 Marks
QUESTION FIVE [20 MARKS]
a) For each of the following statements state whether the assertion is true(T) or false(F).
i. A heap data structures is a binary tree.
ii. Binary search is used for searching in a sorted array.
iii. All nodes in a singly linked list point to some other node.
iv. In a queue, elements are both inserted and deleted from one end.
v. In depth first search(DFS), all the nodes adjacent to the current node are visited.
vi. Traversal in a graph is visiting each node at least once.
6 Marks
b) In the following questions, consider the list of numbers: 62, 31, 70, 91, 25, 11, 9, 61,23, 73, 96.
i. Construct a binary search tree.
4 Marks
ii. Traverse the tree using pre-order traversal
4 Marks
iii. Store the elements displayed from the traversal in ii in a hash table.
6 Marks
