UNIVERSITY EXAMINATIONS: 2018/2019
EXAMINATION FOR THE DIPLOMA IN INFORMATION TECHNOLOGY
DIT307 DATA STRUCTURES AND ALGORITHMS
DATE: AUGUST 2019 TIME: 2 HOURS
INSTRUCTIONS: Answer Question One & ANY OTHER TWO questions.
QUESTION ONE
a) Using relevant examples, explain the application of Queue data structures. [5 Marks]
b) Write a well commented code for a program to create an array of size five to store Marks for the
five units done by the DIT students in the year 2019. [8 Marks]
Required:
The program should as the user to enter the file units, compute the total Marks for the five units,
compute the average and display the results to the user in the following format:
Student total Marks is:
Student average mark is:
c) Explain five main characteristics of a good Algorithms. [5 Marks]
d) Explain the main operations that can be performed in all the following data structures.
e) Arrays, liked list, queue and stack. [6 Marks]
f) With relevant examples define the following terms. [6 Marks]
i. operators operands
ii. Postfix Expression
iii. Prefix Expression
g) Differentiate between Depth First Search (DFS) and Breadth First Search( BFS). [4 Marks]
QUESTION TWO
a) Explain the two approaches that can be used to measure the performance analysis of an
algorithm. [4 Marks]
b) Using a relevant example, explain the difference between Stack and Queue data structures.
[6 Marks]
c) Convert the following expression into post-fix expression [2 Marks]
Q = Z + F * A
d) Differentiate between enQueue and deQueue as used in Queue abstract data structure.
[2 Marks]
e) Write a well commented C/C++ program to perform enqueue operation in a queue.
[6 Marks]
QUESTION THREE
a) Based on the organizing approaches of data structure, explain the main category/type of data
structures. [4 Marks]
b) Write a well commented C/C++ to insert an element before the first element in a liked list.
[7 Marks]
c) Given the following binary tree,
d) List the output if the following traversal were carried out on the binary tree above: [6 Marks]
i. In – Order Traversal
ii.Pre – Order Traversal
iii.Post – Order Traversal
f) Define the term variable. [1 Mark]
QUESTION FOUR
a) Explain the difference between arrays and structures. [4 Marks]
b) Define the following terms as used in tree data structures: [5 Marks]
i. root
ii. parent
iii. degree
iv. edge
v. leaf
c) Given the following list of elements, explain how you will search for element 2 using binary
search algorithm. SHOW ALL THE STEPS YOU FOLLOWED. [6 Marks]
d) Draw a flowchart to determine the smallest number and display the result to the user.
[5 Marks]
QUESTION FIVE
a) Using a well labeled diagram, explain any three types of non-linear data structures.
[9 Marks]
b) Explain the following search algorithms:
binary search algorithm [2 Marks]
sequential search algorithm [2 Marks]
c) Using a relevant example, Explain the term greedy algorithm [3 Marks]
d) Explain the difference between dry running and Structured walk-through [2 Marks]
e) Explain two advantages of using flowchart to represent your algorithms [2 Marks]
