Skip to content

Data Structure

SWE · Final · Spring 26

Paper 1 of 2By Taohid Hassan ShahedSwitch

Paper 1 of 2

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 Software Engineering Final Examination, Spring 2026 Course Code: SE 131 Course Title: Data Structure Level: 1 Term: 3 Section: A, B, C, D, E, F, G, H, I, J, K Instructor: AB (A, B), DMA (C, D, E), MAK (F), HBM (G), SD (H, I), MAB (J, K), NML (L) Time: 2:00 Hrs 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. In a high-performance backend system, a company is tracking API request IDs generated by different microservices. Each request is assigned a unique 3-digit ID based on its processing sequence. To ensure efficient searching, logging, and debugging, the system organizes these request IDs using a Tree with this rule: "Request IDs with smaller values are placed to the left of a node, And equal/larger values are placed to the right." As requests arrive in real time, their IDs are inserted in the following order: 551, 279, 743, 618, 396, 421, 672, 758, 185, 365, 138, 659, 417, 157 a) Construct the appropriate tree by inserting the request IDs in the given order. [Marks-2] b) Based on the tree from question 'a', explore the depth of id 551, degree of id 743, level of id 365 and height of the tree. [Marks-2] c) Construct the preorder and postorder traversal sequences of the tree. [Marks-3] d) Build the C structure for representing the tree and write a function to perform the inorder traversal that prints the request IDs (main part of code only). [Marks-3] 2. In SkyCity Drone Network, several stations are connected through one-way drone routes. The Control Center (CC) sends drones to the Warehouse (WH) and the Charging Station (CS). From the Warehouse (WH), drones are dispatched to Delivery Hub A (A) and Delivery Hub B (B). The Charging Station (CS) sends drones to Delivery Hub B (B) and the Maintenance Unit (MU). Delivery Hub A (A) sends drones to Customer Zone 1 (C1). Delivery Hub B (B) sends drones to both Customer Zone 1 (C1) and Customer Zone 2 (C2). The Maintenance Unit (MU) sends drones back to the Warehouse (WH). All routes are one-way, so drones can travel only in the specified direction. i. Draw this situation as a directed graph, where each station is a vertex and each route is a directed edge. ii. Show the adjacency matrix iii. Show the reachable nodes from CC using BFS. [Marks-2+4] b) Consider the Graphs given below. Illustrate which of them are connected, loop-free graph? Illustrate with a one-line reason. [Marks-4] [Figure: Four graphs labeled (1), (2), (3), (4). Graph 1 is a triangle with an extra edge, Graph 2 is a triangle with an internal node, Graph 3 is a square with diagonals, Graph 4 is a triangle] 3. a) At a busy coffee shop, customers line up to place orders. The Linear queue is managed using an array, where each element represents a customer's order value. Customers join at the rear and are served from the front (FIFO order). Initially, the queue is empty (front = -1, rear = -1). (Enqueue=Insert into the queue, Dequeue=Delete from Queue). Perform the following sequence of operations: Enqueue 1, Enqueue 2, Dequeue, Enqueue 3, Dequeue, Dequeue, Enqueue 4, Enqueue 5, Dequeue, Enqueue 6, Enqueue 7, Dequeue, Dequeue, Dequeue, Enqueue 8. i. Show the sequence of elements in the queue after each operation. [Marks-2] b) An airport shuttle operates a priority queue for passengers using a linked list. Passengers arrive in the following order with priorities: P1(3), P2(1), P3(5), P4(2), P5(4), P6(6), P7(2), P8(5), P9(3), where a higher number indicates higher priority. During the journey, some passengers exit at intermediate terminals while new passengers continue to arrive, and the shuttle always serves passengers by priority while maintaining FIFO for equal priorities. i. Insert passengers P1 to P5 into the priority queue and show the priority queue by using a linked list with updated front and rear. ii. Two passengers exit at intermediate terminals before P6 to P9 arrive; perform those two dequeues and show the updated queue. iii. Insert P6 to P9 into the queue in arrival order and draw the final linked list with front and rear, maintaining priority and FIFO for equal priorities. iv. The shuttle completes its route; perform dequeue until empty. Show the exact sequence of passengers exiting one by one. [Marks-4] c) Construct the main part of the code that performs insertion and deletion operations in a queue. (No need to write the full program - only write the essential logic.) [Marks-4] 4. A Hospital Medication Tracking System keeps track of medicines currently being administered to patients in a ward using a doubly Circular linked list. Each medicine has a unique Medicine ID. Currently administered medicines: M101, M102, M103 Available memory cells for storing nodes: 7301, 7302, 7303, 7304, 7305, 7306. a) Construct a doubly linked list. [Marks-2] b) Insert new medicines into the list as follows: I. M104 at the beginning II. M105 at the 3rd position Sketch the updated doubly linked list from question number a. [Marks-2] c) Remove the 2nd and 4th medicines from the updated list in Question b: Sketch the updated doubly linked list after removing the medicines. [Marks-2] d) Customize the updated doubly linked list from question c into a circular linked list with sentinel value in a header node. [Marks-2] e) Customize the updated circular linked with sentinel value from question d into a singly circular linked list with flag. [Marks-2]