UNIVERSITY EXAMINATIONS: 2017/2018
EXAMINATION FOR THE DEGREE IN BACHELOR OF SCIENCE IN
BACHELOR OF BUSINESS INFORMATION TECHNOLOGY/
BIT 2102/BIT 3101A/BBIT 106: DATA STRUCTURES AND ALGORITHMS
MODE: FULL TIME/PART TIME/DISTANCE LEARNING
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
i. Algorithm and program
ii. Desk check and walk through
iii. Post condition and preconditions
b) Given the letters F, T, E, B, Y, G, P arrange them in descending order using bubble sort.
c) Discuss the following hash table collision handling techniques.
i. Linear probing
iii. Separate chaining.
d) Briefly describe three reasons for analyzing an algorithm.
e) Design algorithm to calculate and display the binomial coefficient once the user keys in
the exponent value.
QUESTION TWO [20 MARKS]
a) Discuss the following types of algorithms:
i. Branch and bound algorithms
ii. Greedy algorithms
iii. Genetic algorithms
b) Study the following algorithm and perform a dry run.
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
c) Design an algorithm using a pseudo code to create a singly linked list to store six
integers, then display them onscreen.
QUESTION THREE [20 MARKS]
a) Explain the difference between a circular queue and a circularly linked list.
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.
c) Draw the directed graph that corresponds to this adjacency matrix:
d) Describe two implementations of queue data structure.
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?
b) Define a recursive function and give any two examples that can be solved recursively.
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.
d) Explain the sufficient conditions for a binary tree to be a heap.
QUESTION FIVE [20 MARKS]
a) Write down an algorithm for constructing a binary search tree (BST).
b) Using the algorithm above, construct a binary tree to store the following list:
c) Traverse the tree constructed in b). above using:
i. In-order traversal
ii. Pre-order traversal
iii. Post order traversal
d) Describe any TWO operations performed on a hash table. [4 Marks]