DSA (CP 213) UE 2018-2019

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 2018/2019

CS 122: DATA STRUCTURES AND ALGORITHM ANALYSIS

Date: 4th July, 2019
Time Allocated: 3 Hours

Instructions:

This question paper consists of two sections.
Answer all questions in section A and any TWO (2) questions in section B.
All University of Dodoma examination regulations apply.

SECTION A (60 Marks)

Question One

a) Using examples, define data structure. (2 Marks) b) Using examples, define algorithms. (2 Marks) c) With examples, show the difference between data structure and fundamental data types. (6 Marks) d) With examples, show how a binary tree of 9 nodes can be implemented. (10 Marks)

Question Two

a) With examples, show the difference between loops and recursions. (10 Marks) b) Using RAM diagrams show the output of the following code segment: (10 Marks)

int main() {
    int x, y, z;
    int *p, *p2;
    s = 0;
    p = &x;
    y = 7;
    y = *p;
    cout << y * 7;
    p2 = p;
    cout << s;
    z = *p2;
    cout << z;
    cout << *p2;
    cout << p, (*z, (*z + 1));
    return 0;
}

Question Three

i. State the difference between linked lists and queues. (4 Marks) ii. Given A = {3, a, 7, 6, 7, b, pp}
a) Implement a queue for set A. (8 Marks) b) Implement a stack for set A. (8 Marks)

SECTION B (40 Marks)

Attempt any TWO (2) questions from this section.

Question Four

Consider the following code (Quick-Sort):

int partition(int x[], int lb, int ub) {
    int temp, a, down, up;
    a = x[lb];
    up = ub;
    down = lb;
    while (down < up) {
        while (x[down] <= a && down < ub) {
            down++;
        }
        while (x[up] >= a) {
            up--;
        }
        if (down < up) {
            temp = x[down];
            x[down] = x[up];
            x[up] = temp;
        }
    }
    x[lb] = x[up];
    x[up] = a;
    return up;
}
 
void quick(int x[], int lb, int ub) {
    int j;
    if (lb >= ub) {
        return;
    } else {
        j = partition(x, lb, ub);
        quick(x, lb, j - 1);
        quick(x, j + 1, ub);
    }
}
 
int main(int argc, char *argv[]) {
    clrscr();
    int ar[100];
    int n, i, down, up;
    cout << "Enter the size of the array: " << endl;
    cin >> n;
    cout << "Enter the elements of the array:" << endl;
    for (i = 0; i < n; i++) {
        cin >> ar[i];
    }
    down = 0;
    up = n - 1;
    quick(ar, down, up);
    cout << "The sorted array is:" << endl;
    for (i = 0; i < n; i++) {
        cout << ar[i];
    }
    getch();
    return 0;
}

a) Show the lines where recursion occurs in the code. (6 Marks) b) Given array {-11, 3, 0, 46, 24, 6, -3, 8, 11, 24, -4, 0, 12}. Show the pivot value for sorting this array. (7 Marks) c) Show how you obtain the values of x, j, lb, ub, down, and up. (7 Marks)

Question Five

a) Provide an example of insertion sort for an array of size 7. (8 Marks) b) Show how parameters are passed in this algorithm. (8 Marks) c) What are the disadvantages of insertion sort? (4 Marks)

Question Six

a) With examples, show how in-order, pre-order and post-order traversal differ from one another. (10 Marks) b) With examples, demonstrate the breadth-first search and depth-first search algorithms. (10 Marks)

Question Seven

Given an array {-1, 1, 3, 0, 46, 24, 6, -3, 8, 11, 24, -4, 0, 12}

a) Write bubble-sort algorithm for this array. (8 Marks) b) Using two cycles of the outer loop, show how the values exchange in the inner loop. [12 Marks)

END OF EXAMINATION

MGODI💎

Explorer