Data Structures
CSE · Final · Spring 22
Section All
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