Skip to content

Data Structure and Algorithm

ITM · Final · Summer 25

Section A

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 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