Data Structure
SWE · Final · Fall 25
Paper 3 of 3Batch 44Switch
Batch 44
Paper 3 of 3
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, Fall 2025
Course Code: SE131; Course Title: Data Structure
Level: 2 Term: 1 Section: A, B, C, D, E, F, G, H, I, J, K
Instructor: AB (A, B), MAK (C, D), FA (E), DMA (F, G, H), FE (I, J, K)
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. [Marks-10] [CLO-4, Level-3]
In a drone delivery coordination center, each delivery zone is marked by a unique capital letter. As drones report their assigned zones, the system stores these zone codes using the following rule for fast lookup:
“Zone codes that come earlier in the alphabet are placed to the left,
and those that come later are placed to the right”
The sequence in which the zone codes arrive is:
N, F, S, Q, W, C, J, H, L, B, E, T, Z, O, R
Using this sequence:
I. Construct the Binary Search Tree (BST) by inserting the zone codes in the given order.
II. Draw the BST after deleting node S.
III. Insert U and A into the updated BST. Sketch the resulting tree.
IV. Assume the BST uses the following C structure:
struct Zone {
char key;
struct Zone *left;
struct Zone *right;
};
Build a C function that prints the preorder traversal of the BST.
V. Based on the final BST from part III, identify what type(s) of binary tree it represents (Binary tree, full binary tree, complete binary tree, perfect binary tree, etc.) with a brief justification.
2. [Marks-2+4] [CLO-4, Level-3]
In GreenCity Metro Park, several key locations are connected by walking paths. The Main Entrance (ME) opens into the Visitor Center (VC). From the Visitor Center, there are paths to the Playground (PG) and the Lake View Point (LV). The Playground (PG) is also directly connected to the Food Court (FC), which in turn has paths to both the Lake View Point (LV) and the Rose Garden (RG).
The Lake View Point (LV) has a small wooden bridge leading to the Bird Watching Tower (BT). The Rose Garden (RG) is connected to the Botanical Dome (BD), and there is also a direct path between the Food Court (FC) and the Botanical Dome (BD).
All paths in the park are two-way, so visitors can walk in either direction along any path.
i. Draw this situation as an undirected graph, where each location is a vertex and each path is an edge.
ii. Show the adjacency list and the reachable nodes from FC using DFS.
Consider the Graphs given below. Which of them are connected, loop-free graph? Identify with a one-line reason. [Marks-4]
[Figure: Four graphs labeled (1), (2), (3), (4)]
3. [CLO-3, Level-3]
At an international airport, a 7-seater automated shuttle transports passengers between terminals. Passengers enter the shuttle in the order they arrive, and the system stores them in a Circular Queue.
The arrival order of passengers is: [P1, P2, P3, P4, P5]
Initially, the shuttle queue is empty with: front = -1, rear = -1
a) [Marks-4]
i. Insert all passengers (P1–P5) into the 7-seater Circular Queue. Draw the array representation of the queue after all insertions and indicate the updated values of front and rear.
ii. Two passengers get off at their terminals. Perform two dequeue operations and show the updated queue, and the new values of front and rear.
iii. Insert P6 and P7 into the queue. Show the final state, and update the values of front and rear. Also state whether additional passengers can still be inserted and illustrate your answer.
iv. Finally, the shuttle completes its route and all remaining passengers exit. Draw the exact sequence of deletions (the order in which passengers leave one by one).
b) A small parking lane allows cars to enter and exit from both ends and is implemented using a double-ended queue (deque), with size 3, input restricted at right side. In this parking lane, cars C1 and C2 first enter from the front. After that, another car, C3, enters from the rear. Later, one car leaves the parking lane from the rear side. Finally, another car, C4, arrives and enters from the rear again. Based on these operations, draw the state of the deque after all actions have been completed. [Marks-3]
c) Construct the main part of the code that performs Searching in a Queue, where the program checks whether a given element exists in the queue or not. (No need to write the full program — only the essential logic for searching.) [Marks-3]
4. [CLO-3, Level-3]
The DIU Library Automation System stores information about newly purchased books using a doubly linked list. Each book record has a unique Book Code. The currently stored book codes are:
B111
B112
B113
The available memory cells for storing the nodes are:
8001, 8002, 8003, 8004
a) Construct a Circular linked list with flag. [Marks-2]
b) Insert new collaborations into the list as follows: [Marks-2]
I. B115 at the beginning
II. B16 at the 3rd position
Sketch the updated Circular linked list with flag from question number a.
c) Customize the updated circular linked list from question b into a Doubly linked list. [Marks-2]
d) Customize the updated circular linked list from question b into a Circular linked list with sentinel value. [Marks-2]
e) Construct a main part of the code to construct a node if it contains three data potion "Student Name", "Student ID" and "Mobile Number". (no need to write the full code) [Marks-2]