UNIVERSITY EXAMINATIONS: 2013/2014
ORDINARY EXAMINATION FOR THE BACHELOR OF SCIENCE
IN INFORMATION TECHNOLOGY
BIT 3101A BBIT 106 DATA STRUCTURES AND ALGORITHMS
DATE: APRIL, 2014 TIME: 2 HOURS
INSTRUCTIONS: Answer Question ONE and any other TWO
QUESTION ONE
(a) Describe the binary search algorithm. [3 Marks]
(b) Describe the heap sort algorithm [4 Marks]
(c) Explain the difference between static and dynamic arrays. [4 Marks]
(d) Describe how you will declare a structure and name it item whose members are int
cost, float weight and has three objects salt, sugar and soap. [5 Marks]
(e) Describe the three class member access specifiers: private, public and protected.
[6 Marks]
(f) Explain the procedure of inserting a new node at the beginning of linked list.
[4 Marks]
(g) Outline any two applications of a queue. [4 Marks]
QUESTION TWO
(a) Outline any four operations that can be performed on a tree data structure. [4 Marks]
(b) Describe how greedy algorithms work. [4 Marks]
(c) Outline three ways of used to initialize an array structure. [3 Marks]
(d) Differentiate between circular queue and deque. [6 Marks]
(e) Describe any three applications of a stack data structure [3 Marks]
QUESTION THREE
(a) Describe the following sort algorithms:
i. Insert sort [4 Marks]
ii. Bubble sort [4 Marks]
(b) Write a program in C++ to calculate and display the first 20 numbers in Fibonacci
series. Given that f(n)=f(n-1)+f(n-2), where f(n) is the nth term. [8 Marks]
(c) Describe differences between structure and class data structures. [4 Marks]
QUESTION FOUR
(a) Discuss time complexity as used in algorithm analysis. [6 Marks]
(b) Outline any four basic operations considered when estimating the running time of a
program. [8 Marks]
(c) Outline four rules for calculating running time of a programs [6 Marks]
QUESTION FIVE
(a) Using your knowledge of stack ADT and program control structures such as for loop,
write a program in C++ that prompts the user to enter five floating point values then
store them in a stack. The program should be able to display the value at the top of
the stack and also the size of the stack. [8 Marks]
(b) Write small code snippet to declare a binary tree ADT (abstract data type).
[4 Marks]
(c) Discuss the two properties of a heap abstract data type. [6 Marks]
(d) Discuss two applications of graph abstract data type (ADT). [2 Marks]
