UNIVERSITY EXAMINATIONS: 2020/2021
EXAMINATION FOR THE DIPLOMA IN INFORMATION TECHNOLOGY
DIT 307/DBIT 305: DATA STRUCTURES AND ALGORITHMS
FULLTIME/ PART TIME
DATE: DECEMBER, 2021 TIME: 2 HOURS
INSTRUCTIONS: QUESTION ONE IS COMPULSORY, CHOOSE TWO OTHER
QUESTIONS
QUESTION ONE (20 Marks) Compulsory
1. Differentiate the following: (4 Marks)
i. Time complexity and space complexity
ii. Algorithm and Pseudocode
2. Explain the following data structures and for each describe any two areas of application (
using an illustration) (4 Marks)
i. Stack
ii. Queue
3. Using an example, illustrate the difference between Pop( ) and Push( )operations of the
stack (4 Marks)
4. Give the output of the following binary tree traversal (3 Marks)
i. Pre order
ii. Post Order
iii. In order
5. Write a pseudo-code for binary search algorithm (5 Marks)
G
C J
A E H K
QUESTION TW0 (15 Marks)
1. Differentiate the following terms as used in tree data structure (4 Marks)
i. Root
ii. Leaf
iii. Parent
iv. Child
2. Convert the following infix expressions into prefix and postfix expressions (6 Marks)
Infix notation Postfix notation Prefix notation
A – (B – (C-D))
A-B-C-D
(A+B)*(C/(D-E))
3. State any two properties of a binary search tree (2 Marks)
4. Explain three strategies that divide and conquer algorithms uses to solve problems. (3 Marks)
QUESTION THREE (15 Marks)
1. Discuss the following types of graphs. (3 Marks)
i. Mixed graph
ii. Undirected graph
iii. Directed graph
2. Describe four real world application of algorithms (4 Marks)
3. Write a pseudo code for each of the following operations of the linked list: (6 Marks)
i. Inserting a node
ii. Traversing a linked list
4. State any two factors that influence the running time of an algorithm (2 Marks)
QUESTION FOUR (15 Marks)
1. Discuss the advantages and disadvantages of the linked list and array-based
implementations of queues (4 Marks)
2. Given the following array elements [ 34,17,38,8,67,90,78]. Use any search technique to
find element 67 in the array. (4 Marks)
3. Write a program that makes use of a stack to read in a single line of text and write out
the characters in the line in reverse order. (4 Marks)
4. Explain the following terms as used in algorithm analysis (3 Marks)
i. Best case
ii. Worst case
iii. Average case
