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]
