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]
