Data Structures
CSE · Final · Fall 23
Batch 61
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, Fall-2023
Course Code: CSE123, Course Title: Data Structures
Level: 1, Term: 2, Batch: 61
Time: 2 Hours
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. Consider the following figure of a BST:
[Figure: A binary search tree with root 19, left child 16 having left child 14 and right child 18, and right child 25 having left child 23 and right child 30, with further nodes like 13 and 15 attached below]
Answer the following questions:
(A) Show the traversal of the tree using inorder, preorder and postorder traversal technique. [4]
(B) Suppose a new node having data 12 is to be inserted and node 18 is to be deleted, show the operation of insertion and deletion and elaborate briefly. [3]
(C) Show the implementation scheme using link list nodes for the above BST. [2]
(D) Why BST is popular in computing. [2]
2. (A) Given set of data in an array is {13, 15, 17, 19, 24, 9, 11, 4, 8, 5}. Insert the above data in an empty AVL tree and show each step of AVL formation including rotations. [8]
(B) Why AVL plays a significant role in data search using BST. [2]
3. For the data set shown in an array {23, 15, 19, 6, 33, 45, 4, 55, 8, 22, 39, 2}, answer the following questions:
(A) Form a minHeap and maxHeap and show each necessary intermediate tree. Identify total number of percolations needed for minHeap and maxHeap. [4]
(B) Suppose the node 15 is to be deleted in minHeap you have formed above, write the process of deletion for node 15. [3]
(C) How heap data structure is different from BST. [2]
(D) Why percolation is needed in Heap. [2]
4. Consider the following graph:
[Figure: A directed graph with vertices A, B, C, D, E with weighted edges between them]
Answer the following questions:
(A) Represent the graph using Adjacency matrix and Adjacency list. [4]
(B) Why Graph data structure has significance in real-life. [2]
(C) How indegree and outdegree signifies using graph computing. [2]