Skip to content

Data Structures

CSE · Final · Spring 24

Batch ALL

This browser can’t show the PDF here

Open it, and your phone’s PDF viewer takes it, or download it.

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