Data Structure and Algorithm
ITM · Final · Fall 24
Section MA
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, Fall 2024
Course Code: ITM 217; Course Title: Data Structure and Algorithms
Sections & Teachers: MA
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. a) Define graph data structure with a real life example. Explain the properties of tree data structure. | [Marks-5] | CLO-3 Level-2
1. b) What is BST? Write down an algorithm to delete a node from a BST where both children are present. | [Marks-5] | CLO-3 Level-1
2. a) Explain different types of linked lists. Differentiate between array and linked list. | [Marks-5] | CLO-3 Level-4
3. a) [Figure: A directed graph with nodes A, B, C, D, E, F, S and directed edges between them]. Consider this graph. Represent the graph using both adjacency matrix and adjacency list. Which representation is better in terms of space for this graph? Justify your answer. | [Marks-8] (3+3+2) | CLO-4 Level-5
3. b) Calculate the discovery time d, finish time f and previous node prev for all the nodes in the given graph using appropriate graph traversal algorithm. Show step by step implementation. | [Marks-7] | CLO-4 Level-3
4. a) Array = [12, 7, 19, 4, 22, 15, 3, 10, 6, 18]
Consider the array and apply merge sort for ascending order. Illustrate the whole process step by step. | [Marks-5] | CLO-4 Level-3
4. b) B = [12, 10, 7, 5, 2, 1]
Apply insertion sort on the given array and demonstrate each step. | [Marks-5] | CLO-4 Level-3