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