UNIVERSITY EXAMINATIONS: 2015/2016
EXAMINATION FOR THE DIPLOMA IN INFORMATION
TECHNOLOGY
DIT 307 DATA STRUCTURES ALGORITHMS
DATE: AUGUST 2016 TIME: 1½HOURS
INSTRUCTIONS: Answer Any THREE Questions.
QUESTION ONE
a) Briefly explain the following algorithm design paradigms (8 Marks)
i. Divide and conquer
ii. Branch and bound
iii. Greedy method
iv. backtracking
b) Outline four advantages of using structured English in program design (4 Marks)
c) A client has requested that you test an application for him. Describe two types of data
that you could use in the test (4 Marks)
d) With the aid of a flow chart in each case, distinguish between a selection and a repetition
controls as used in programming (4 Marks)
QUESTION TWO
a) Write a pseudo code that would delete the first element of a singly linked list data
structure (4 Marks)
b) Figure 1 below shows a tree data structure. Use it to answer the questions that follow:
Figure 1
(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)
QUESTION THREE
a) Explain three operations that can be performed on a stack data structure (6 Marks)
b) Study the following pseudocode and then answer the question that follows:-
1. Start
2. Declare variable position
3. Enter the pupil position in class
4. If position=1
5. Display “Award 3 exercise books”
6. Else If position=2
7. Display “Award 2 exercise books”
8. Else If position=3
9. Display “Award a pencil and a rubber”
10. Else
10
6
4 8
18
15 21
3
11. Award nothing
12. End IF
13. Stop
Required: write a C++ or C program that would implement the above pseudocode. Use
if…else control structure (8 Marks)
(c) Outline the steps of designing an algorithm (6 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) Linked list (4 Marks)
(ii) Queues (4 Marks)
d) Explain the term ‘data structure’ (2 Marks)
QUESTION FIVE
(a) Figure 2 below shows a typical data structure. Use it to answer the questions that follow:-
4 6 2 0
5 3 8 7
9 0 11 13
Figure 2
Required: Write a C or C++ program statement to:-
(1)
(i) Declare the data structure (3 Marks)
(ii) Initialize the data structure (4 Marks)
(2) State two limitations of this data structure (2 Marks)
b) Briefly explain five properties of an algorithm (5 Marks)
c) Give two applications of graphs ADT (Abstract Data Type) (2 Marks)
d) Outline the differences between structures and unions (4 Marks)
