l\1Io t111t I(e11,ra

'

UNIVERSITY EXAMINATION 2019/2020

SCHOOL OF COMPUTING AND INFORMATICS

DEPARTMENT OF INFORMATION TECHNOLOGY

BACHELOR OF SOENCE IN INFORMATION TECHNOLOGY/ BACHELOR OF BISINESS

INFORMATION TECHNOLOGY

REGULAR

UNIT CODE: BIT2203 UNIT TITLE: DATA STRUCTURES AND ALGORITHMS

DATE: DECEMBER, 2019 MAIN EXAM TIME: 2 HOURS

INSTRUCTIONS:
ANSWER QUESTION ONE AND ANY OTHER TWO QUESTIONS

Question 1 (30marks)
a) Define the term algorithm (2 Marks)

V f;,-.'l-+P"i 1
b) Outline four characteristics of a good algorithm. v "' ~ ~r i.... ~ 4 Marks) P~.I'\ ?~1'
v ~~ ·t... t tl""'i 1
c~ ·~
c) Explain the function of the following ADT primitives. Write the re levant syntax. ~ d~-:J
i) Enqueue ( ) (2 Marks)
ii) Push0 (2 Marks)
iii) IndexOf () (2 ~v1arks)

d) One of the applications of stacks in computing is to evaluc1te postfix cxpre::;.;ion. 1

From the given expression 5+4*6-3

y- i) Convert the expression into postfix expression . (2 Marks)

Paper One Pagel

 ii) Using stack ADT, show how the expression will be evaluated. (4 Marks)

e) A queue is implemented using ADT list to presents its items. Discuss the efficiency
of the queue insertion and deletion operations when the ADT list Implementation
IS:

i) Array based.
ii) Pointer based. (6 Marks)

f) Outline four possible application of ADT Quey_ejn_cor:npu.ting. (4 Marks)

------
9) In context of arrays, explain the term index. Show an example. (2 Marks)

Question 2 (20marlcs)
a) Using examples differentiate between a binary tree and general tree. (4 Marks)
I
b) Write a two dimensional array to explain the concept of row major order.
- I
(6 Marks)

c) Explain two types of complexities of study In data structures. (4 Marks)

d) Give the algebraic expression: (a-b/c)+d*e

i. Convert it into postfix expression. (3 Marks)

ii. Generate a binary tree from the expression. (3 Marks)

Question 3 (20marks)
a) Give three reasons why you woul d choose~ list over array. (3 Marks)

b) Name and explain th ree inpu t cases and the effect on running time of an
algorithm. (3 Marks)

Paper One Page2

• I

vr
c) D 'b
escn e th e concept and motivation of circular QUEUE. Use illustration.
(S Marks)

11
d) '. terms of computational complexity, using big o, Explain the cost of:
.') lnserting element at the end of array list. (3 Marks)
II) Inserting element at end linked list (3 Marks)

e) Write down the algorithms for inserting a new element into stack. (3 Marks)

~ -Question 4 (20marks)

a) Define the term "Algorithm analysis'. Explain two important quantitative metrics
of interest in algorithm analysis. (4 Marks)

b) Sort the array given below using INSERTION sort algorithm. (6 Marks)

130 120 16 115 8 3 4

1 1 1 I

c) Explain three characteristics of ADT Linked list. (6 Marks)

d) Using illustrative diagram, show how a new element is added in-between other
elements in linked list (4 Marks)

Question 5 (20marks)
a) Explain two data types used to Implement ADTs. (4 Marks)
,v 8 ~
v ~~
b) Perform Pre-Order, In-order and Post-Ordertraversal on the following tree.
(6 Marks)

Paper One
 l
-p ( f ~~J
,._ {''1 f

~~' ~~ ~~~

c) Discuss five benefits of studying data structures and algorithms by software

developers. (10 Marks)

Paper One Page4