UNIVERSITY EXAMINATIONS: 2017/2018
EXAMINATION FOR THE DIPLOMA IN INFORMATION
TECHNOLOGY
DIT307 DATA STRUCTURES & ALGORITHMS
FULLTIME/PARTTIME
DATE: APRIL, 2018 TIME: 1 ½ HOURS
INSTRUCTIONS: Answer Question ONE AND any other TWO questions.
QUESTION ONE [20 MARKS]
(a) Susan a programmer would like to test an application for a client. Describe two types of test
data that she could use in the test [4 Marks]
(b) Write a pseudo code for a program that would prompt the user to enter four scores scored by
a student in an exam and program should then store the entered scores in an array named Marks;
calculate the sum and average scores and display the calculated average. [8 Marks]
(c) Figure 1 show a tree data structure. Use it to answer the questions that follow:-
Figure 1
Required:-
(i) Identify the type of tree giving a reason for your answer [2 Marks]
(ii) Give three applications of tree data structures [3 Marks]
(iii)Explain three data operations supported by a tree data structure [3 Marks]
(d) i) With the aid of a diagram, describe the quee data structure. [4 Marks]
ii) List & explain four operations supported by a queue data structure. [4 Marks]
(e) Define the following terms; [2 Marks]
i) Translator program
ii) Comments
QUESTION TWO [20 MARKS]
(a) With the aid of a flowchart in each case, distinguish between a selection and repetition
controls as used in programming [4 Marks]
(b) explain the following terms:- [5 Marks]
(i) Algorithm
(ii) Dry running
(iii)Data structure
(iv)Test data
(v) Structured walkthrough
(c) Outline two benefits of storing data in a data structure [2 Marks]
(d) Write a C++ code skeleton to illustrate each of the following operations on a queue:-
[4 Marks]
(i) Insertion
(ii) Deletion
(e) Figure 1 show a typical data structure. Use it to answer the questions that follow:
Required: Write a C++/ C program statement to: [4 Marks]
(i) Declare the data structure
(ii) Initialize the data structure
(iii)State one limitation of this data structure [1 Mark]
QUESTION THREE [20 MARKS]
(a) Describe the following searching techniques:- [4 Marks]
(i) Binary
(ii) Sequential
(b) Distinguish between static and dynamic data structures giving an example in each case.
[4 Marks]
(c) The Kenyan Electoral system involves voting by users pressing a number representing
candidate of their choice. The numbers used range from 1to 5.the recent presidential polls
had five candidates whose identification numbers and philosophical messages were as
follows:
Required:
(i) Design an algorithm using flowchart for a C/C++ program that prompts the voter to
enter a number representing her/ his preferred candidate. The program then outputs
an appropriate message depending on the choice made. [9 Marks]
(ii) Outline three advantages of flowcharts [3 Marks]
QUESTION FOUR [20 MARKS]
(a) Outline the steps of designing an algorithm [5 Marks]
(b) With the aid of illustrations describe the following data structures: [6 Marks]
(i) Linked list
(ii) Graphs
(c) KCA University libray keeps the following details about the library books:-Book Author,
Year of publication, BookID, Publisher.
Required:
(i) Explain the most appropriate data structure that can be used to store the library books
details [3 Marks]
(ii) Using C/C++ programming language, declare the data structure identified in 4((i)
[6 Marks]
QUESTION FIVE [20 MARKS]
(a) Convert the following infix expressions into postfix using stack ADT: [4 Marks]
(i) A*B+C/D-E
(ii) A*(B+C/D)
(b) Explain five features of a good algorithm [5 Marks]
(c) Write a C/C++ program segment that adds the following elements into a stack named
numbers and reads and returns the top most data element in the stack:
12, 67, 78, 90 [7 Marks]
(d) Explain the purpose of the following operations as used in stacks:- [4 Marks]
(i) Pop()
(ii) Top()
(iii)Empty()
(iv)Size()
