Data Structures and Algorithms Analysis Exam - CP 213
THE UNIVERSITY OF DODOMA
COLLEGE OF INFORMATICS AND VIRTUAL EDUCATION
SCHOOL OF INFORMATICS
UNDERGRADUATE UNIVERSITY EXAMINATIONS
SECOND SEMESTER 2017/2018
CS 122: DATA STRUCTURES AND ALGORITHMS
Date: 04th July, 2018
Time Allocated: 3 Hours
Instructions:
- This question paper consists of six questions.
- Attempt THREE (3) questions, question ONE (1) is compulsory.
- All University of Dodoma examination regulations apply.
Question One (Compulsory)
Consider any business of your choice (banking, pharmacy, retail shop, etc.). Choose one of its undertaking and:
(a) Define a data structure pertinent to such undertaking. [5 Marks]
(b) Create nodes/objects from the definition in (a). [5 Marks]
(c) Using loop approach generate and feed data in at least ten nodes of the structure. [5 Marks]
(d) Using dynamic approach generate and link the nodes that you have formed in (c). [5 Marks]
(e) Create a stack of at least ten of the nodes that you have created in (c). [5 Marks]
(f) Create a Binary tree of at least four branches of the nodes you have created in (c). [5 Marks]
(g) Discuss computing functionalities where linked list concept is applied. [10 Marks]
(h) Using structure definition example, show how trees are different from queues. [5 Marks]
(i) Using structure definition example show how stacks are similar to queues. [5 Marks]
(j) Given set ( B = (5, 8, 46, -98, 46, 67, -5, 36, -89, 0, 345, 45.88, 4.87) )
i. Using bubble sort algorithm sort these values in ascending order. [5 Marks]
ii. Using quick-sort algorithm sort these values in descending order. [5 Marks]
Question Two
a. Using arrays approach show the implementation of queues using C++. [5 Marks]
b. Using dynamic approach show the implementation of queues using C++. [5 Marks]
c. Discuss computing functionalities where queue concept is applied. [10 Marks]
Question Three
a. With examples show the implementation of stacks using C++. [10 Marks]
b. Discuss some examples of computing where stack concept is applied. [10 Marks]
Question Four
a. Show how Binary trees are generated: sequentially and by looping. [5 Marks Each]
b. Using examples demonstrate the various algorithms for traversing binary-trees. [10 Marks]
Question Five
Given set A = {23, 56, -7, 6, 0, 75, 2.7, -3.6, 8, -4.77, 43, 678}
And set B = {5, 8, 46, -98, 46}
a. Using Merge sort approach, sort the numbers in set A and B jointly. [10 Marks]
b. Using RAM diagrams, show the values of parameters that are passed between the partition() function and sort() function. [10 Marks]
Question Six
a. Using quick sort approach, sort the numbers in set A and B given in question 5 jointly. [10 Marks]
b. Show the values of parameters that are passed between the partition() function and sort() function. [10 Marks]
END OF EXAMINATION