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