**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]