Skip to content

Data Structure

SWE · Final · Summer 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 Department of Software Engineering Faculty of Science & Information Technology Final Examination, Summer 2025 Course Code: SE131; Course Title: Data Structure Level: 2, Term: 1, Sections & Teachers: A(A), DMA(B,C,D), RJM(E,F), MHS(G), MBH(H,I), MRD(J,K,O), SAN(L), AAS(M,N), AF(P) 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. At the end of the year, the University Archives began sorting through digital records labeled by letters for easy access. The archivist, Ms. Z., followed a strict rule: "Labels that come earlier in the alphabet go to the left, and those that come later go to the right." The order of received record labels is: M, G, T, D, J, P, W, B, F, H, K, N, R, U, X I. Construct the BST by inserting the book IDs in the given order. II. Draw the BST after deleting node T. III. Insert L and V into the BST. Sketch the updated tree. IV. Construct the preorder and postorder traversal sequences. V. Map the type of binary trees formed in part IV (binary tree, full binary tree, complete binary tree, etc.), with a short justification. | [Marks-10] | CLO-4 Level-3 2. In Metro Health Complex, the Emergency Ward (EW) connects directly to the Radiology Unit (RU). Adjacent to the Radiology Unit is the Pharmacy (PH), which also has paths leading to the Cardiology Department (CD) and RU. The Hospital Garden (HG) lies near the Cardiology Department and is accessible directly from both CD and PH, and it's a peaceful area where patients and visitors often rest. The Emergency Ward (EW) also has another path leading directly to the Operation Theater (OT), which in turn is connected to the Cafeteria (CA). Additionally, the Emergency Ward (EW) has a direct path to the Cafeteria (CA) as well. All these facilities are connected by two-way pathways, allowing easy movement throughout the hospital. a) Draw the unweighted, undirected graph of Metro Health Complex based on the above description. | [Marks-4] | CLO-4 Level-3 b) Show the Adjacency List representation of the graph. | [Marks-3] c) Using the BFS search algorithm that finds the shortest path, starting from EW, illustrate the traversal order and trace the path to reach CA from EW. | [Marks-3] 3. a) During course registration, each student is placed in a Priority Queue. The priority is calculated using: priority(x) = N - indexOf(x) Where, N = total number of students in the list. The list of students is: [S1, S2, S3, S4, S5] Assume the Priority Queue can hold a maximum of 6 students. Sketch the queue. i. Insert all students into the Priority Queue based on their calculated priorities. Sketch the queue. ii. Perform delete operations for the first two students. Show the updated queue. iii. Insert two new students S6 and S7 with priorities 3 and 4. Draw the final state of the queue. Is insertion still possible? iv. Show the sequence of deletions if all students are removed one by one. | [Marks-4] | CLO-3 Level-3 b) Illustrate a Circular Queue and a Double-Ended Queue with relevant examples. | [Marks-3] c) Construct the main part of the code for Queue operations (Insertion, Deletion) with handling of Overflow and Underflow situations. (no need to write the full code). | [Marks-3] 4. The DIU Research Office is maintaining collaborations in a linked list system. Each collaboration has a unique ID. Currently stored collaborations are: C201 C202 C203 C204 The available memory cells are: 7001, 7002, 7003, 7004, 7005, 7006 a) Construct a doubly linked list with the collaborations. Sketch with next and prev pointers. | [Marks-2] | CLO-3 Level-3 b) Insert new collaborations into the list as follows: I. C205 at the beginning II. C206 at the 3rd position III. C207 at the end Sketch the updated doubly linked list from question number a | [Marks-2] c) Convert the updated doubly linked list into a circular linked list with sentinel value. | [Marks-2] d) Transform the circular linked list, that was drawn in question number d, into a circular linked list with flag. Insert C208 at the 2nd position. Sketch the updated circular list. | [Marks-2] e) Construct a sudo code/main part of the code to construct and traverse the linked list exactly once, starting from head. (no need to write the full code) | [Marks-2]