DSA (CP 213) UE 2021-2022

Data Structures and Algorithms Analysis Exam - CP 213

UNIVERSITY OF DODOMA
OFFICE OF THE DEPUTY VICE CHANCELLOR
ACADEMIC, RESEARCH AND CONSULTANCY
COLLEGE OF INFORMATICS AND VIRTUAL EDUCATION
Department of Computer Science and Engineering

End of Semester One (1) University Examination for the 2021/2022 Academic Year

Course Name: Data Structures and Algorithms Analysis
Paper Code Number: CP213
Date of Examination: 23 February, 2022
Time: 15:30–18:30
Duration: 3 Hours
Venue(s): CIVE-AUDITORIUM
Sitting Programme(s): CS2, SE2, CNISE2, CES2, TE2, C5DFE2, and MATH2

SECTION A (15 MARKS)

Attempt ALL questions in this section.

Question One

QUESTION ONE MISSING : Please submit if available

a. Mention the name of the structure. (1 Mark)
b. Outline members of the structure. (1 Mark)
c. Re-write the program using the pointer operator. (3 Marks)

Question Two

Study the following program, then by using a single well-drawn diagram for each, show the effect of the execution of each indicated code segment.

#include<iostream>
using namespace std;
struct MyID
{
    string name;
    string natId;
    char gender;
    int age;
    MyID* next;
};
int main()
{
    MyID *head = NULL, *tail = NULL, *Person1, *Person2;
 
    // Code segment A
    Person1 = new MyID();
    Person1->name = "Kitwe Kitwana";
    Person1->natId = "T21-03-0000";
    Person1->gender = 'F';
    Person1->age = 17;
    Person1->next = NULL;
    // End of segment A
 
    // Code segment B
    head = Person1;
    // End of segment B
 
    // Code segment C
    Person2 = new MyID();
    Person2->name = "Kitwana Kitwe";
    Person2->natId = "T21-03-1111";
    Person2->gender = 'M';
    Person2->age = 47;
    Person2->next = NULL;
    // End of segment C
 
    // Code segment D
    Person2->next = Person1;
    head = Person2;
    // End of segment D
 
    tail = head;
    cout << "The IDs \n";
    while(tail)
    {
        cout << "ID: " << tail->natId << endl;
        tail = tail->next;
    }
}

(Code segments A, B, C, D as above)

Code segment A (1 Mark)
Code segment B (1 Mark)
Code segment C (1 Mark)
Code segment D (2 Marks)

Question Three

With the aid of a well sketch, show the execution flow of the following recursive function. (5 Marks)

#include<iostream>
using namespace std;
int facto(int);
int main()
{
    int num = 4;
    int factonum = facto(num);
    cout << "The factorial of " << num << " is: " << factonum;
}
int facto(int nam)
{
    if(nam == 0)
        return 1;
    else
        return nam * facto(nam - 1);
}

SECTION B (45 MARKS)

Attempt THREE (3) out of FOUR (4) questions in this section.

Question Four

Figure 1 is a linked list created from the structure HouseNo.

Figure 1: Linked List

a. Write a piece of code to define the structure. (1 Mark)
b. Write a piece of code to implement the linked list in Figure 1. (4 Marks)
c. Assume the linked list in Figure 1 is a queue:
i. Write a piece of code to add a node with data 20. (2.5 Marks)
ii. Write a piece of code to delete one node. (2.5 Marks)
d. Assume the linked list in Figure 1 is a stack:
i. Write a piece of code to add one node with data 30. (2.5 Marks)
ii. Write a piece of code to delete one node. (2.5 Marks)

Question Five

Consider the following array:
int arr[] = {63, 32, 11, 79, 68, 98, 17};

a. Write a C++ program to store the unsorted array. (3 Marks)
b. Write the bubble sort C++ program to rearrange the elements of the array in descending order. (5 Marks)
c. Using the program written in 5(b), what is the resultant array after the third pass? (Show how you have derived the answer). (5 Marks)
d. State the best and the worst cases of the algorithm in 5(b). (2 Marks)

Question Six

Consider the following array:
int arr[] = {63, 32, 11, 79, 68, 98, 17, 57, 45};

a. Write a C++ program to store the unsorted array. (3 Marks)
b. Write a merge sort C++ program to rearrange the array elements in ascending order.
Use the following function signatures:
void merge(int Arr[], int left, int mid, int right)
void Merge_sort(int Arr[], int a, int b)
(5 Marks)
c. Using the program written in 6(b), what will be the values of a and b at the first call, first recursive call, and second recursive call of the function Merge_sort? (Show all calculations). (5 Marks)
d. State the best and worst cases of the algorithm in 6(b). (2 Marks)

Question Seven

Answer the following questions:

a. Consider Figure 2, then use stack or queue data structure concepts to show the result of:
Figure 2: Tree Data Structure

i. Breadth-First Search Algorithm (Start at vertex 0). (3 Marks)
ii. Depth-First Search Algorithm (Start at vertex 8). (3 Marks)

b. Evaluate the following expressions:
i. Postfix expression: 8 2 + 3 * 16 / - (2 Marks)
ii. Prefix expression: 70 14 4 5 15 3 / * - - / 6 + (2 Marks)
iii. Show the conversion of the following infix expression to postfix:
A + B * (C + D) - E / F * G + H (5 Marks)

END OF EXAMINATION PAPER

MGODI💎

Explorer