UNIVERSITY EXAMINATIONS: 2011/2012
THIRD YEAR EXAMINATION FOR THE BACHELOR OF
SCIENCE IN INFORMATION TECHNOLOGY
BIT 3101 DATA STRUCTURES AND ALGORITHMS
DATE: AUGUST, 2013 TIME: 2 HOURS
INSTRUCTIONS: Answer Question ONE and any other TWO
QUESTION ONE [30 MARKS]
a) Compare and contrast flowchart and pseudo code as algorithm development tools.
[4 Marks]
a) Using your knowledge of algorithm analysis arrange the following functions
ascending order of their efficiency form the lowest to highest.
logn, n2, nlogn, n!, 7n, n7 [4 Marks]
b) Explain the following cases of algorithm complexity.
i). The worst-case complexity.
ii). The best-case complexity.
iii). The average-case complexity. [3 Marks]
c) Write the c++ function that implements the definition, including the post conditions
and preconditions for: [4 Marks]
d) Design an algorithm to calculate binomial coefficients. [3 Marks]
e) Discuss three techniques for resolving collisions in hash tables. [3 Marks]
f) Describe the following methods used in traversing a graph
i). Depth First Search [3 Marks]
ii). Breadth First Search [3 Marks]
1
g) Write an algorithm to create a singly linked list to store the elements 2,4,2,6,7 and 11
in that order. [3 Marks]
QUESTION TWO [20 MARKS]
a) Design algorithms for the following search methods.
i). Linear search [4 Marks]
ii). Binary search [4 Marks]
b) State the worst case and the best case in each of the algorithms in a). [4Marks]
c) Write the algorithm for each of the following sort methods
i). Bubble sort [4 Marks]
ii). Insertion sort [4 Marks]
QUESTION THREE [20 MARKS]
a) Describe any two advantages and two disadvantages of array data structure.
[4 Marks]
b) You are required to develop an algorithm to compute average speed of 40 cars. The
average speed can be calculated as speed= (distance/time). Use a flowchart to
develop the algorithm. [4 Marks]
c) Implement the algorithm in b) above using c++. [4 Marks]
d) Give two advantages and two disadvantages of union data structure. [4 Marks]
e) Write a program in c++ to implement the following. Create union employee whose
members are age and salary. Create objects for employee union Jane and Henry.
[4 Marks]
QUESTION FOUR [20 MARKS]
a) Explain two advantages and two disadvantages of structures. [4 Marks]
b) Write a c++ program that uses structure as follows; create structure item whose
members are quantity, size and price. Create objects for the structure item soap and
salt. [5 Marks]
c) Define the following terms.
i). Class [1 Mark]
ii). Object [1 Mark]
iii). Access specifier [1 Mark]
iv). Member function [1 Mark]
d) Explain the following access specifiers of a class.
i). Public [1 Mark]
ii). Private [1 Mark]
iii). Protected [1 Mark]
e) Discuss the differences between:
i. Class and union structures [2 Mark]
ii. Destructor and constructor [2 Mark]
2
QUESTION FIVE [20 MARKS]
a) Outline any four operations that can be performed on a dictionary data structure.
[4 Marks]
b) Given the tree below, answer the questions that follow.
3
9 8 6
11
5 2
11 10 7 4 11 16
19 19 20
i. State the depth of node containing 7. [1 Mark]
ii. State the height of the tree. [1 Mark]
iii. State the length of the path 8, 2,7,19. [1 Mark]
c) Write a program in c++ to store six characters in a stack data structure. [5 Marks]
d) Outline any four operations that can be performed on a queue data structure.
[4 Marks]
e) Draw a new heap that is created by inserting 10 into the following heap:
[4 Marks]
12
8 9
7 6
5
4
