Data Structures
CSE · Final · Spring 24
Batch ALL
Read the questions as text
Read off the PDF by AI, so it may have mistakes. The PDF is the original.
Daffodil International University
Faculty of Science & Information Technology
Department of Computer Science and Engineering
Final Examination, Spring 2024
Course Code: CSE123, Course Title: Data Structures
Level: 1 Term: 2 Batch: ALL
Time: 2.0 Hours
Marks: 40
Answer ALL Questions
[The figures in the right margin indicate the full marks and corresponding course outcomes. All portions of each question must be answered sequentially.]
1. SCENARIO:
You are required to implement a binary search tree (BST) to manage a dynamically changing dataset of student records for a university database. Each record consists of a unique student ID and the student's grade point average (GPA). The university requires quick access to records for adding new students, updating existing records, and generating sorted lists of student IDs.
A. Propose a design of the node for BST based on the above scenario. Justify your design of the node briefly. | 2 | CO2
B. Implement a INSERT method that adds a new node to the BST. The student should be inserted based on their ID number in such a way that for any node, all IDs in the left subtree are less than the node's ID, and all IDs in the right subtree are greater. | 5 | CO3
C. Suppose you are inserting {107, 3.2}, {103, 3.6}, {109, 3.3}, {105, 3.3}, {115, 3.7} and {10, 3.7} as node in the BST, show the final BST and write the in-order traversal of the BST based on ID. | 3 | CO1
D. Suppose you are to insert another node {102, 3.8} in the above BST, write how the insertion process insert the node {102, 3.8} in the BST. | 2 | CO2
E. Suppose you need to form an AVL of the BST shown on (D), for the AVL formation considering the nodes, show each step including rotations. | 6 | CO2
2. SCENARIO:
You are data analyst working on improving public transportation in a city. The city's transportation network can be modeled using a graph where bus stops are represented as nodes and bus routes connecting these stops are edges. Each edge has a weight representing the time taken to travel between two stops.
A. Show a graph to model this transportation network based on your assumption of bus stops. Consider a maximum of 6 to 7 bus stops and bus routes are weighted with a value between 2 to 7 which is assumed by you too. Edge having higher value generally looks longer than other edges. | 4 | CO1
B. Represent your proposed Graph model using adjacency matrix and adjacency list. | 3 | CO2
3. a) Convert the following infix expression to postfix and then evaluate the value of the expression using Stack:
(I) 2*2-4+8/2-2
(II) 2^2-6/2+2
| 3 | CO1
| 3 | CO1
4. Consider an array having data {9, 3, 10, 15, 4, 18, 6, 11, 7, 1}. As an expert of data structure, answer the following questions using the array:
A. Form a MinHeap and MaxHeap from the array and identify the total number of percolations needed. | 5 | CO2
B. How Heap is different from BST, briefly elaborate with example. | 2 | CO1
C. Why Heap is important in computing | 2 | CO1