Data Structures
CSE · Final · Summer 26
Paper 1 of 6Batch 70 · Shaker AbdullahSwitch
Batch 70
Paper 1 of 6
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 Computer Science & Engineering
Final Examination, Summer 2026
Course Code: CSE123, Course Title: Data Structure
Level: 1 Term: 3 Batch: 70
Time: 02: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 | Students at DIU have long wanted a transport service inside the campus to save time when moving between places. To meet this need, the university is now starting a cart service. Students can use this service with points, but each student will get only 100 points per month. This rule helps students plan carefully when to use the carts, while also reminding them that walking is important for health and exercise. The number of points needed depends on the distance between two locations, as shown on the campus map.
[Figure: A campus map showing nodes: annex, Shadhinota shommelon, Small Field, Food Court, AB-4, Central Field, Mosque, GG, Admission Office, with weighted edges between them] | CO3
a) | Classify the types of the given graph. | 2
b) | Construct the Adjacency Matrix of the given campus graph. | 3
c) | Rubayet has just been admitted to DIU and wants to explore the campus. He plans to use all of his 100 cart service points today. He will start from the Admission Office and move along a path shown in the campus map. He will keep going forward as long as there are connected places. If he reaches a point where no further path exists, he will go back, spending the same number of points for both forward and backward travel. His journey will stop as soon as his total points exceeds 100.
Write down the order of places (nodes) Rubayet visits during his exploration step by step.
N.B: in the traversal order, each place should appear only once | 5
2 | Upoma loves math and wants to make a dictionary of numbers where each number will have a short story or history. Her friend Sudip told her that in a normal dictionary, words are arranged by their symbols (the one that comes first will stay ahead) so readers can find them quickly. Upoma liked this idea and now wants to use a tree data structure to build something similar to a dictionary.
To test her idea, she will start with the ten numbers:
1, 32, 23, 11, 99, 17, 85, 92, 20, 100 | CO2
a) | Write a C program to construct the tree as mentioned in the scenario and print the information in a sorted list. | 6
b) | Write a function to delete the number 11 and 100 form the tree. | 4
3 | Shifat runs a software company. He wants to design a hierarchical tree structure of his employees based on their salaries.
The rules for the tree are:
1. The tree must be an almost complete binary tree.
This means all levels are completely filled except possibly the last.
In the last level, nodes must be filled from left to right without gaps.
2. In any part of the hierarchy, the boss's salary must be higher than the salaries of his immediate subordinates (at most two).
The salaries of 10 employees are:
78K, 76K, 65K, 18K, 50K, 46K, 90K, 98K, 120K, 56K | CO3
a) | Construct the tree as mentioned in the scenario (show all the steps visually). | 4
b) | Find the Inorder, Preorder and Postorder of the contracted tree Q3 (a). | 3
c) | Show the updated tree after deleting 3 nodes from the tree while keeping the properties mentioned in the question intact (Show all the steps visually). | 3
4 | Dr. Azmir is a renowned doctor and it is hard to get his visiting token. He takes the token in an ascending order and stores that into a binary search tree, so that he can search it whenever needed. The tokens are given below:
51, 52, 53, 55, 56, 57, 58, 60, 61 | CO3
a) | Construct the tree the way Dr. Azmir stored the information in the first place as mentioned (show visually steps one by one). | 4
b) | What kind of problem Dr. Azmir will face considering the pattern of data he is storing.
Can he get the benefits of the BST while searching, considering the data he is storing today? | 2
c) | Analyze the problem Dr. Azmir will face considering the data. Also construct the updated tree step by step after solving the problem. | 4