**UNIVERSITY EXAMINATIONS: 2017/2018**

**EXAMINATION FOR THE DEGREE IN BACHELOR OF SCIENCE IN**

**INFORMATION TECHNOLOGY/**

**BACHELOR OF BUSINESS INFORMATION TECHNOLOGY/**

**BIT 2102/BIT 3101A/BBIT 106: DATA STRUCTURES AND ALGORITHMS**

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

**ORDINARY EXAMINATIONS **

**DATE: NOVEMBER, 2017 DURATION: 2 HOURS**

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

**QUESTION ONE [30 MARKS]**

a) Briefly explain the differences between the following terms as used in data structures and

algorithms:

i. Algorithm and program

ii. Desk check and walk through

iii. Post condition and preconditions

[6 Marks]

b) Given the letters F, T, E, B, Y, G, P arrange them in descending order using bubble sort.

[6 Marks]

c) Discuss the following hash table collision handling techniques.

i. Linear probing

ii. Re-hashing

iii. Separate chaining.

[6 Marks]

d) Briefly describe three reasons for analyzing an algorithm.

[3 Marks]

e) Design algorithm to calculate and display the binomial coefficient once the user keys in

the exponent value.

[9 Marks]

**QUESTION TWO [20 MARKS]**

a) Discuss the following types of algorithms:

i. Branch and bound algorithms

ii. Greedy algorithms

iii. Genetic algorithms

[9 Marks]

b) Study the following algorithm and perform a dry run.

1.START

2.Declare variable x, y

3.FOR x=1 TO x<4

3.1. Calculate y=2x+1

3.2. Display y

3.3. Increase x by 1

4.END FOR

5.STOP

[6 Marks]

c) Design an algorithm using a pseudo code to create a singly linked list to store six

integers, then display them onscreen.

[5 Marks]

**QUESTION THREE [20 MARKS]**

a) Explain the difference between a circular queue and a circularly linked list.

[4 Marks]

b) A stack is an ordered collection of data elements in which access is possible only at one

end called top of the stack. Describe any three application of stacks in computing.

[6 Marks]

c) Draw the directed graph that corresponds to this adjacency matrix:

[6 Marks]

d) Describe two implementations of queue data structure.

[4 Marks]

**QUESTION FOUR [20 MARKS]**

a) If you push the letters F, A, C and E in order onto a stack of characters and then pop them, in

what order will they be deleted from the stack?

[5 Marks]

b) Define a recursive function and give any two examples that can be solved recursively.

[4 Marks]

c) The numbers 20, 70, 68, 59,30,15,90,70,60,85 are to be stored for some processing in that

order. Write down the order in which the numbers will be printed if they are:

i. stored in a queue

ii. stored in a stack and

iii. stored in a binary search tree and traversed in order.

[9 Marks]

d) Explain the sufficient conditions for a binary tree to be a heap.

[2 Marks]

**QUESTION FIVE [20 MARKS]**

a) Write down an algorithm for constructing a binary search tree (BST).

[4 Marks]

b) Using the algorithm above, construct a binary tree to store the following list:

12, 15,20,17,22,8,10,6,14

[6 Marks]

c) Traverse the tree constructed in b). above using:

i. In-order traversal

ii. Pre-order traversal

iii. Post order traversal

[6 Marks]

d) Describe any TWO operations performed on a hash table. [4 Marks]