Skip to content

Data Structures

CSE · Final · Spring 22

Section All

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 Department of Computer Science and Engineering Faculty of Science & Information Technology Final Examination, Spring-2022 Course Code: CSE134 (Day), Course Title: Data Structure Sections, Teachers: All Time: 2:00 Hrs. Marks: 40 Answer ALL Questions: 1. a) For the following binary tree, answer the following questions: [Figure: Binary tree with root 24, left child 12 with children 10 and 13 (where 13 has child 18), and right child 21 with children 20 and 40 (where 40 has child 50)] Now, for the above tree, write the order of nodes visited: (i) In-order Traversal, (ii) Pre-order Traversal and (iii) Post-order Traversal. 3 b) Construct a Max Heap from the Tree shown and insert nodes 14, and 19. 2.5 c) Construct a Min Heap from the Tree shown and delete nodes 40, and 10. 2.5 d) Write the differences between Max Heap and Min Heap. 2 2. a) Construct a Binary Search Tree (BST) and write properties of it. 3 b) Show the BST after adding new nodes with the data value 16, 26. 2.5 c) Show the BST after deleting the nodes having the data value 21, 24. 2.5 d) Write, why all the binary trees are not BST. 2 3. a) Consider the following graph and answer the following questions: [Figure: Directed graph with nodes A, B, C, D, E, F, G with directed edges] Now, Determine the sorted sequence of the nodes for the above graph. 3 b) Determine the strongly connected components of the above graph. 4 c) Conclude the differences between directed graph and undirected graph. 3 4. a) For the Graph processing, answer the following questions: | | A | B | C | K | E | F | G | Z | |---|---|---|---|---|---|---|---|---| | A | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | | B | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | | C | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | | K | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | | E | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | | F | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | | G | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 1 | | Z | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | Use the above adjacency matrix and draw the graph. 2 b) Apply BFS to find the path from A to Z. 5 c) Illustrate your idea about DAG. 3