**UNIVERSITY EXAMINATIONS: 2014/2015**

**ORDINARY EXAMINATION FOR THE BACHELOR OF SCIENCE **

**IN INFORMATION TECHNOLOGY/BACHELOR OF **

**INFORMATION TECHNOLOGY**

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

**DATE: APRIL, 2015 TIME: 2 HOURS**

**INSTRUCTIONS: Answer Question ONE and any other TWO**

**QUESTION ONE [30 MARKS]**

a) Explain why programmers may need to spent more time analyzing their program designs than

the actual code. [3 Marks]

b) Differentiate between depth first search (DFS) and breadth first search (BFS). [6 Marks]

c) The following expressions represents complexity of an algorithm, state and explain the big O

in each case:

[4 Marks]

d) Discuss the steps for developing an algorithm. [5 Marks]

e) Design an algorithm using a flowchart that gets integer value from the keyboard then displays

remarks depending on a criteria as shown below:

integer Remark

0 Back to school

1 Easter holiday!

[6 Marks]

f) Design an algorithm that uses arrays to prompt the user to enter all the twenty six letters of

alphabet then display the vowels only. [6 Marks]

**QUESTION TWO [20 MARKS]**

An array can be defined as a collection of attributes of the same type and stored in

contiguous memory locations. In this regard,

a) Differentiate between the following terms used in classifying arrays

i) Static and dynamic arrays

ii) One dimensional and three dimensional arrays [4 Marks]

b) Discuss any two advantages and two disadvantages of arrays [4 Marks]

c) Explain the memory size allocated to the following array declarations if the machine allocates

the memory sizes to data types as follows:8 bytes for double, 4 bytes for integers, 16 bytes for

string.

i) Int myage[3][4][2]

ii) String team[2][2][7]

iii) Double studentweight[5][9] [6 Marks]

d) Study the pseudo code below:

Start

Declare variables profit, cost, loss, sellprice

Get value of cost and sellprice

IF cost>sell_price

Loss=cost-sellprice

ELSE IF sell_price>cost

Profit=sellprice-cost

ELSE

Display “no profit nor loss”

END IF

Stop

Required: Use test values sellprice=4000 and cost=5000 to perform a dry run for this pseudo

code. [6 Marks]

**QUESTION THREE [20 MARKS]**

a) A linked list is a data structure that consists of nodes , where each node stores at least two

values- the data and address to the next node. In this regard,:

i) Describe any two applications of a linked list. [2 Marks]

iii) Explain three operations that can be performed on a singly linked list [6 Marks]

iv) Construct a doubly linked list that stores five characters K,E,N,Y, A where each

character appear in its own node. [4 Marks]

b) A stack can be defined as a linear data structure that allows elements to be stored and

removed from the same end called the top. From this background:

i) Explain any four applications of stacks. [4 Marks]

ii) Explain the contents of the stack after the following operations have completed.

Push(2)

Push(20)

Push(200)

Push(2000)

Pop()

Push(20000)

Push(0) [4 Marks]

**QUESTION FOUR [20 MARKS]**

Hash table is an array implementation of dictionary data structures that allow values to be

stored in a unique location depending on the hash value generated using hash function.

From the context:

i) Discuss the application of hash tables in databases. [4 Marks]

ii) Discuss any three techniques that help to resolve collisions in hash tables [6 Marks]

iii) Construct a hash table to store the integers 2,56,7,8,9,2,22 and 56. [6 Marks]

iv) The values in a hash table may not be sorted after, all. Support this argument with a

reason. [4 Marks]

**QUESTION FIVE [20 MARKS]**

a) When a search algorithm receives an argument to search it will go through the data structure

looking for the match. If the match is found, the index or position of that value is returned.

i) Explain the circumstances under which you will use binary search instead of

linear search. [3 Marks]

ii) Discuss how the linear search works if the values are stored in an array

[6 Marks]

b) Explain the algorithm for selection sort. Support your explanation with an example.

[6 Marks]

c) Explain how a graph can be represented using an adjacency matrix. [3 Marks]

d) Construct maximum heap data structure that stores the integers 3,7,9,3,5,6 and 7.

[2 Marks]