UNIVERSITY EXAMINATIONS: 2014/2015
ORDINARY EXAMINATION FOR THE BACHELOR OF BUSINESS
INFORMATION TECHNOLOGY
BBIT 106 DATA STRUCTURES AND ALGORITHIMS – DISTANCE
LEARNING
DATE: DECEMBER, 2014 TIME: 2 HOURS
INSTRUCTIONS: Answer Question ONE and any other TWO
QUESTION ONE [30 MARKS]
a) Describe the steps for designing an algorithm. [5 Marks]
b) Differentiate between a walk through and a desk check as used in testing the algorithm. [4 Marks]
c) Describe any three operations performed in a binary tree data structure. [6 Marks]
d) Design an algorithm that inserts a node at the beginning of a linked list. [5 Marks]
e) Design an algorithm that uses two nested FOR loops to print the pattern below:
*
* *
* * *
* * * *
* * * * *
* * * * * *
* * * * * * *
* * * * * * * *
[6 Marks]
[a].Describe linear probing as one of the techniques for solving collisions in a hash table.
[4 Marks]
QUESTION TWO [20 MARKS]
(a) Design an algorithm using a pseudo code that uses the SWITCH keyword to prompt
the user to enter a grade then display the remarks using the criteria below.
Grade Remark
1 Agree
2 Strongly agree
3 Disagree
4 Strongly disagree
5 Neither agree nor disagree
[8 Marks]
(b) Calculate the big O for the in each of the following functions:
[6 marks]
(c) Briefly describe why algorithm analysis is necessary. [6 Marks]
QUESTION THREE [20 MARKS]
a) Briefly explain how array elements can be accessed. [6 Marks]
b) Explain the difference between static and dynamic arrays. [6 Marks]
c) Design an algorithm using a pseudo code to calculate and display average score for
forty scores keyed in by the user. [8 Marks]
QUESTION FOUR [20 MARKS]
a) Define a queue ADT and hence explain any three operations of a queue. [6 marks]
b) Define a stack ADT and hence outline any applications of a stack ADT. [8 Marks]
c) A binary tree is a tree in which each parent node can have a maximum of two child
nodes. Each node has two pointers- left pointer and right pointer. Given a binary tree
below, you are required to display its elements using in-order and preorder traversals.
[6 Marks]
QUESTION FIVE [20 MARKS]
a) Design an algorithm using pseudo code to sort elements by insert sort technique.
[8 Marks]
b) Design an algorithm using pseudo code to search elements in an array of size n by linear search. [8 Marks]
c) Briefly explain the two techniques of traversing a graph ADT. [4 Marks]
