Data Structure and Algorithm
ITM · Final · Summer 25
Section A
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 Information Technology & Management
Final Examination, Summer 2025
Course Code: ITM 217; Course Title: Data Structure and Algorithm
Sections & Teachers: FM (A)
Marks: 40
Time: 2:00 Hrs
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) Define the terms Degree, Height, Depth, and Leaf Node in a tree with an appropriate example. | [Marks-3] | CLO-2 Level-1
1. b) Explain why a Complete Binary Tree with height h has at least 2^h nodes and at most 2^(h+1) - 1 nodes, using an example. | [Marks-5] | CLO-2 Level-2
2. Given student roll numbers: 45, 30, 60, 25, 35, 50, 70, 65
2. a) Construct a Binary Search Tree (BST) using the given values and draw the tree. Then, determine the Preorder, Inorder, and Postorder traversals. | [Marks-4] | CLO-3 Level-3
2. b) Analyze the BST to explain how searching for roll number 65 will proceed step by step, and evaluate the efficiency of this search. | [Marks-2] | CLO-3 Level-4
3. You are given the following campus map (distances in minutes to walk):
Admin-Library (4)
Admin-Cafeteria (2)
Library-Cafeteria (1)
Library-Auditorium (7)
Cafeteria-Auditorium (3)
Cafeteria-ITM-(8)
Auditorium-ITM (2)
3. a) Define shortest path algorithm. State one key difference between Dijkstra's Algorithm and Prim's Algorithm. | [Marks-2] | CLO-2 Level-1
3. b) Construct the given weighted graph in the form of both adjacency matrix and adjacency list | [Marks-4] | CLO-3 Level-3
3. c) Draw the graph with proper edge weights. Using Prim's Algorithm starting from the Admin node, demonstrate step-by-step selection of edges to construct the Minimum Spanning Tree (MST). | [Marks-5] | CLO-4 Level-4
4. A company wants to arrange its data in ascending order for efficient searching and retrieval. The dataset is given as:
[5, 3, 8, 4, 2, 7, 1, 10]
To optimize performance, different sorting algorithms are being considered.
4. a) Explain the concept of Dynamic Programming (DP) with one real-life example. | [Marks-2] | CLO-1 Level-2
4. b) Using the given dataset, apply Quick Sort with the first element as the pivot, and illustrate the recursive partitioning steps. | [Marks-4] | CLO-3 Level-3
4. c) Determine the total number of comparisons made during the Quick Sort process. Then, evaluate its time complexity in best, worst, and average cases. | [Marks-3] | CLO-1 Level-5
4. d) Differentiate between Bubble Sort and Merge Sort in terms of efficiency. | [Marks-3] | CLO-1 Level-2
5. a) Explain why BFS is suitable for finding the shortest path in an unweighted graph, while Dijkstra's algorithm is more appropriate for a weighted graph. Illustrate with examples. | [Marks-3] | CLO-4 Level-4