UNIVERSITY EXAMINATION 2024/2025
PY
SCHOOL OF COMPUTING AND INFORMATICS
DEPARTMENT OF INFORMATION TECHNOLOGY/ENTERPRISE COMPUTING
BEDA/BECS/BCCS/BBIT/BIT
O
SCHOOL BASED
UNIT CODE: BIT2203 UNIT TITLE: DATA STRUCTURES &
C
ALGORITHMS
DATE: SAT 7TH DEC, 2024 4.00PM MAIN EXAM TIME: 2 HOURS
Y
INSTRUCTIONS: ANSWER QUESTION ONE AND ANY OTHER TWO
AR
QUESTION ONE
a) Define the following terms; (4 Marks)
i) Directed graph
ii) Abstract data type (ADT)
iii) Pendant
BR
iv) Heap
b) Discuss any TWO advantages of linked list over linear list. (4 Marks)
c) Write a C++ statement that checks whether a circular queue if full or empty
LI
(8 Marks)
d) Outline any FIVE data structures that are used in programming. (5 Marks)
e) Cite any three areas where trees can be applied in information systems.
(3 Marks)
f) Define data encapsulation and identify any its merits. (3 Marks)
g) Define space complexity. Why is it important in analysis of algorithms?
(3 Marks)
Paper Two Page 1
QUESTION TWO
a) Define a string ADT (2 Marks)
b) Write a C++ program that achieves the following in an array list ADT
Implementation. (5 Marks)
i) Add a new item at position i
ii) Deletes item at position i
PY
c) i) Discuss the operations performed on a heap. (4 Marks)
ii) Represent the array below in a binary tree. Perform a heap sort on it
(5 Marks)
O
(0) 70
(1) 60
(2) 12
(3) 40
(4) 30
(5) 8
C
Y
(6) 10
AR
d) Write a C++ code section for merge sort algorithm (4 Marks)
QUESTION THREE
a) i) Define a stack ADT (2 Marks)
ii) Compare sequential search with binary search (2 Marks)
BR
b) Show how the following items; 40 50 30 can be implemented on a
Stack ADT that uses an array (2 Marks)
c) Trace the behavior of the following operation on the ADT in (b) above:
LI
PUSH (70) PUSH (80) PUSH (90) POP () PUSH (77) POP ()
(3 Marks)
d) Give all orders of traversal for following binary tree (6 Marks)
Paper Two Page 2
5 9
PY
2
6
O
e) Write a pseudo code for a binary search tree. Assume the array is already sorted.
(5 Marks)
C
QUESTION FOUR
a) Given the equation in infix (A+B)*C, A+B*C and A-B+C formulate the equivalent
pre fix and post fix notation (6 Marks)
Y
b) Write a C++ code to implement the POP and PUSH functions of stack ADT.
(6 Marks)
AR
c) Define a binary search tree and outline four of its properties. (4 Marks)
d) Write an algorithm for performing a sequential search. (4 Marks)
BR
QUESTION FIVE
a) Given the graph below find the shortest path using Dijkstras algorithm.
(7 Marks)
LI
Paper Two Page 3
b)
Explain
any four
PY
O
desirable traits of a good algorithm
C (4 Marks)
c) Given the tree below perform a down-heap followed by up-heap of value 10
Y
(6 Marks)
AR
6 5
BR
9
8
LI
e) Define the following term in relation to trees using examples
i) Siblings (3 Marks)
ii) Depth
iii) Leaf
Paper Two Page 4
