Data Structure
SWE · Final · Summer 25
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]