UNIVERSITY EXAMINATIONS: 2015/2016
EXAMINATION FOR THE DIPLOMA IN INFORMATION
TECHNOLOGY
DIT 307 DATA STRUCTURES AND ALGORITHM
DATE: AUGUST 2016 TIME: 1½HOURS
INSTRUCTIONS: Answer Any THREE Questions.
QUESTION ONE
a) Describe the procedure of performing a dry run (4 Marks)
b) Explain two techniques for resolving collisions in a hash table (6 Marks)
c) Describe 3 applications of directed graphs (6 Marks)
d) You have been given some letters of the alphabet stored in one dimensional array as shown
below (4 Marks)
F D B C A F H E G J
Store the letters in the order shown in the array and store them in binary search tree
(BST)
QUESTION TWO
a) Discuss the two techniques for graph traversal (6 Marks)
b) Describe the procedure for searching a value in a database table assuming the records are
not sorted (6 Marks)
c) Explain the four guidelines for designing algorithms using a pseudo code
(4 Marks)
d) Compare and contrast an algorithm and a program (4 Marks)
QUESTION THREE
a) Define the term linear data structures. Give 3 examples of linear data structures
(6 Marks)
b) Compare and contrast a class and structure (4 Marks)
c) Describe the algorithm for converting an infix expression to postfix using a stack ADT
(6 Marks)
d) Define the term “greedy algorithm”. Give 2 examples of greedy algorithms
(4 Marks)
QUESTION FOUR
a) Describe the following searching techniques:-
(i) Binary (3 Marks)
(ii) Sequential (3 Marks)
b) Distinguish between static and dynamic data strictures giving an example in each case
(4 Marks)
c) With the aid of diagrams, describe the following data structures:-
(i) Array (4 Marks)
(ii) Queues 4 Marks)
d) Explain the term ‘data structure’ (2 Marks)
QUESTION FIVE
a) Write a pseudo code that would delete the first element of a singly linked list data
structure (4 Marks)
b) Use the tree data structure to answer the questions.
(i) Identify the type of tree giving a reason for your answer (3 Marks)
(ii) State the output for each of the following traversal methods if applied on the tree:-
1) Post order (3 Marks)
2) In order (3 Marks)
3) Pre order (3 Marks)
(C) Briefly explain the two properties that are used as a measure of the
performance of an algorithm (4 Marks)
