University of Management and Technology, Lahore Campus
Terminal Examination – FALL 2020
Credit
Course Title: Data Structure and Algorithm Lab Course Code: CC2042L 1
Hrs:
Course Programme
Muhammad Waheed Waqar BSCS
Instructor/s: Name:
Semester: 3rd Batch: SP19 Section: Date: 10th Feb, 2021
V4
Time Allowed: 3 Hr. Maximum Marks: 100
Student’s Name: Reg. No.
Important Instructions / Guidelines:
● All questions are compulsory. Manage time properly and try to attempt easy problems first.
● Questions understanding is the part of exam.
● Cheating will result in negative marking.
Best of Luck!!!
Question No. Obtained Marks Maximum Marks
1 20
2 40
3 40
100
Page | 1
Question #1
Implement a recursive C++ function which takes an array of integers (arr) and the starting
(start) and ending (end) indices of a portion (part) of this array, and returns the index of the
second largest element present in that portion of array arr. The prototype of your function
should be:
int findSecondLargest (int* arr, int start, int end)
For example, the function call findSecondLargest(arr,3,8) should determine and return the
index of the second largest element present in the array arr between the indices 3 and 8 (both
inclusive).
Question #2
Implement a class for Circular Doubly Linked List (with a dummy header node) which
stores integers in unsorted order. Your class definitions should look like as shown below:
class CDLinkedList;
class DNode {
friend class CDLinkedList;
private:
int data;
DNode* next;
DNode* prev;
};
class CDLinkedList {
private:
DNode head; // Dummy header node
public:
CDLinkedList(); // Default constructor
bool insert (int val); // Inserts val into the linked list. Time complexity: O(1)
bool removeLastValue (int v);
//Note: Remove the last val from the linked list. Time complexity: O(1)
void findMiddleValue(); // find middle value of the linklist and delete it.
void display(); // Displays the contents of linked list on screen …
};
Question #3
In this lab you are going to start implementing a class for creating and storing Binary Search
Trees (BST). Each node of this BST will store the roll number, name and CGPA of a
student. The class definitions will look like:
class StudentBST;
class StudentNode {
friend class StudentBST;
private:
Page | 2
int rollNo; // Student’s roll number (must be unique)
string name; // Student’s name
double cgpa; // Student’s CGPA
StudentNode* left; // Pointer to the left subtree of a node
StudentNode* right; // Pointer to the right subtree of a node
};
class StudentBST {
private:
StudentNode* root; // Pointer to the root node of the tree
public:
StudentBST(); // Default constructor
};
bool insert (int, string, double)
This function will insert a new student’s record in the BST. The 3 arguments of this function
are the roll number, name, and CGPA of this new student, respectively. This function will
check whether a student with the same roll number already exists in the tree. If it does not
exist, then this function will make a new node for this new student, insert it into the tree at its
appropriate location, and return true. If a student with the same roll number already exists,
then this function should return false.
bool search (int)
This function will search the BST for a student with the given roll number. If such a student
is found, then this function should display the details (roll number, name, and CGPA) of this
student and return true. If such a student is not found then this function should display an
appropriate message and return false.
void displayInRange (double cgpaStart, double cgpaEnd)
This function will search the BST for those students whose CGPA is between cgpaStart and
cgpaEnd (both inclusive). The records of all such student should be displayed in ascending
order of their Roll Numbers.
Hint: You may need to implement one or more helper functions.
Page | 3
