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 2016/2017
CS 122: DATA STRUCTURES AND ALGORITHMS
Date: 06th July, 2017
Time Allocated: 3 Hours
Instructions:
- This question paper consists of six questions.
- Attempt ANY FIVE (5) questions.
- All University of Dodoma examination regulations apply.
Question One
a. Given the following array, how will it appear after the first five(5) iterations of the insertion sort algorithm? [10 Marks]
{6, 9, 1, 4, 15, 12, 5, 6}
b. Study the tree shown in Figure 1 and answer the questions that follow.
i. Find the height of the tree. [1 Mark]
ii. Write down the pre-order, in-order and post-order traversal of the tree above. [9 Marks]
Question Two
a. Based on the following declarations, tell whether each statement below is syntactically legal (Yes) or illegal (No) and explain your answer. [10 Marks]
int *p, *q, *r;
int a, b, c;(i) p = new int;
(ii) *q = new int;
(iii) a = new int;
(iv) p = r;
(v) q = b;
(vi) r = NULL;
(vii) c = *p;
(viii) *q = NULL;
(ix) *p = a;
(x) *p = a;
b. Employ the infix-to-prefix algorithm to convert ((a+b)*c)/(d-c)+f into prefix. [7 Marks]
c. Evaluate the postfix string ab+c*de-f-/ given that a=10, b=2, c=4, d=5, e=2, f=1. [3 Marks]
Question Three
a. Define and implement a structure/object which contains at least three fundamental data types. [5 Marks]
b. Write a code to input-process and output data using your structure. [5 Marks]
c. Given an array A of numeric type, size 20. Write an algorithm based on iteration to bubble sort the array A. [5 Marks]
d. Rewrite the resultant code in C++ using recursion. [5 Marks]
Question Four
a. Using recursion concept, write an algorithm function that implements a DFS on a BST. [14 Marks]
b. Write down the BFS and DFS of the graph in Figure 1. [6 Marks]
FIgure 1 : Graph
Question Five
a. Illustrate the following queue operations:
enqueue(1), enqueue(2), enqueue(5), dequeue(), dequeue(), enqueue(4), dequeue(), dequeue(). [8 Marks]
b. Using the following structure specification, write a program with two functions that perform enqueue and dequeue operations on a linked list based queue. [12 Marks]
struct Part {
string part_name;
double price;
int count;
Part* next;
};Question Six
Using your programming knowledge write a code to implement a stack of at least 12 nodes. Perform pop() and push() functions in your stack. [20 Marks]
Question Seven
Figure 2 : Linked List
Use the linked list in Figure 2 to answer the following questions:
a. Give the value of the following expression [3 Marks]
(i) ptr1->info
(ii) ptr2->next->info
(iii) listData->next->next->info
b. Are the following statement True or False? [4 Marks]
(i) listData->next == ptr1
(ii) ptr1->next->info = 60
(iii) ptr2->next == NULL
(iv) listData->info == 25
c. Write one statement to do each of the following [4 Marks]
(i) Make listData point to the node containing 45
(ii) Make ptr2 point to the last node in the list
(iii) Make listData point to an empty list
(iv) Set the info member of the node containing 45 to 60
d. Decide whether the syntax of each of the following statements is valid or invalid. If it is valid mark it as V and if it is invalid mark it as I and explain what is wrong [4 Marks]
(i) listData->next = ptr1->next
(ii) listData->next = *(ptr2->next)
(iii) *listData = ptr2
(iv) ptr2 = ptr1->next->info
e. Write a piece of code for Traversing the Linked List [5 Marks]
END OF EXAMINATION