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

, 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]

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]

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

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]