Skip to content

Data Structure

SWE · Final · Spring 25

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 2025 Course Code: SE131; Course Title: Data Structure Sections: A,B,C,D,E,F,G,H,I,J,K & Teachers: RI, AB, DMA, MSP, SAM, MRD, TM, KF 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. a) A software tool is parsing arithmetic expressions using a binary expression tree. The tree stores the operands and operators in nodes and uses different traversals to evaluate or represent the expression in different notations. If the traversal of the tree is: Inorder Traversal: 15, 20, 25, 30, 35, 40, 45 Postorder Traversal: 15, 25, 20, 35, 45, 40, 30 Based on the given traversals, Construct the preorder traversal of the binary tree. [Marks-2] [CLO-4 Level-3] b) You are developing an AI-powered scheduling system for a university. Each class is assigned a unique numeric priority code (lower number = higher priority) and is stored in a Binary Search Tree (BST) for efficient access. A new term is starting, and the BST is initially empty. The following classes need to be scheduled in the given order: 401 (Math), 201 (Physics), 601 (Chemistry), 101 (English), 301 (Biology), 501 (Islamiyah), 701 (ICT). Later, the Math class (code 401, which was the first class inserted and thus the root) is merged with another department and must be deleted. i. Draw the BST after all insertions, showing class codes clearly. ii. Draw the BST after deleting class 401, and explain which class replaces it in the root and why briefly? [Marks-4] [CLO-4 Level-3] c) You are implementing a simplified BST-based contact manager. Each contact is stored using an integer key (e.g. phone number). Simulate the short C functions to: i. Insert a new node into a BST ii. Delete a node from the BST. [Marks-4] [CLO-4 Level-3] 2. Leuna wants to travel to Sundarbans. She starts from her Home to the Train Station (600 TK), then Train Station to Jessore (1800 TK), Jessore to Khulna (2000 TK), Khulna to Mongla Port (2300 TK), and finally Mongla Port to the Sundarbans (3000 TK). Alternatively, she can go directly from the Train Station to Mongla Port (5000 TK) or from Home to Khulna (4500 TK). On her return, she travels from Sundarbans to Mongla Port (2800 TK), then Mongla Port to Home (5500 TK). Alternatively, she can go from Sundarbans to Jessore (6500 TK), then Jessore to Home (2000 TK), or directly from Sundarbans to Home via helicopter for 48000 TK. [Marks-4] [CLO-4 Level-3] a) Draw the Weighted Directed graph. [Marks-3] b) Show the Adjacency Matrix representation of the graph which you have just drawn in the previous question. [Marks-2] c) Show the Adjacency List representation of the graph which you have just drawn in the first question. [Marks-3] d) Illustrate the DFS Traversal 'Train Station' to 'Sundarban'. [Marks-2] 3. Assume a Circular Queue of Size 6 (Index 0 to 5). Initially, the Queue is empty with Front = -1 and Rear = -1. [Marks-3] [CLO-3 Level-3] a) i. Sketch the Circular Queue after Enqueuing the elements M, S, P, A, L. Show the Front and Rear pointer values. ii. Illustrate the Queue after performing a Delete operation for two elements. Update the Front and Rear accordingly. iii. Insert C, T, R, U into the Queue. Show the final state of the Queue. Is Insertion still possible? iv. Show what happens when we try to delete an element from a Circular Queue of Front = -1. [Marks-6] b) Demonstrate the working of Linear Queue vs Circular Queue with an example. [Marks-3] c) Demonstrate Double Ended Queue (Deque) with example and mention the restrictions associated with it. [Marks-3] 4. You are developing a resource tracking system for an emergency relief coordination platform in Gaza, Palestine. The system needs to efficiently manage a dynamic list of Relief Center Names currently connected to the central network for distributing aid. The Relief Center Names are: Gaza, Rafah, Salfit, Nablus The memory cells available for storing logistics data are: 0x1782, 0x1783, 0x1784, 0x1785, 0x1786, 0x1787 a) Construct a Double-way Linked list using the available memory cells and store data elements in the list following the above instructions and sketch the available linked lists. [Marks-2] [CLO-2 Level-3] b) After constructing the linked list, as done in question 'a', insert "Jenin" as the 1st element, "Tulkarm" as the 4th element, and "Hebron" as the last element of the list, and sketch the resulting linked list. [Marks-2] c) Now, Construct a circular linked list with the given data and memory with a flag value and sketch the linked list. [Marks-2] [CLO-2 Level-3] d) After constructing the linked list, as done in question 'c' Convert the resulting list into a circular linked list with a sentinel value, insert "Bethlehem" as the 3rd element of the list and sketch the linked list. [Marks-2]