AD-303 Data Structure - Dec 2023 Question Paper

Under each question, How to answer lists the points an answer should cover, outlined by CampusPrep from the syllabus. Check the details against your textbook.

1. 7 Marks
   aConstruct a Binary tree for the given traversals: Postorder Traversal: K, D, I, E, A, G, B, F, C, J, H Inorder Traversal: D, K, I, B, A, E, G, H, J, F, C Also, find the Preorder traversal of the Binary tree so formed.
   How to answer

   • Identify root from last element of postorder traversal (H)
   • Split inorder traversal into left subtree (D, K, I, B, A, E, G) and right subtree (J, F, C)
   • Recursively construct left and right subtrees
   • Draw the resulting binary tree
   • Perform preorder traversal (Root, Left, Right) and state the final sequence
2. 7 Marks
   bHow a tree can be stored in the memory? Explain with an example. Explain the advantages and disadvantages of the array representation of a tree.
   How to answer

   • Explain array (sequential) representation using indexing ($2i+1$, $2i+2$)
   • Explain linked (pointer-based) representation
   • Provide diagrammatic examples for both representations
   • List advantages of array representation (direct index access, no pointer overhead)
   • List disadvantages (memory wastage for skewed trees, fixed size)
3. 7 Marks
   aConstruct an expression tree for the following algebraic expression: $(3a - b)^2 (4c + 2d)^3$
   How to answer

   • Parse the algebraic expression into postfix form or operator hierarchy
   • Identify the root operator as multiplication ($*$)
   • Construct left subtree for exponentiation: $( (3 * a) - b ) \text{ ^ } 2$
   • Construct right subtree for exponentiation: $( (4 * c) + (2 * d) ) \text{ ^ } 3$
   • Draw the complete binary expression tree
4. 7 Marks
   bExplain the Binary Search Tree with an example. Make a Binary Search Tree for the following sequence of numbers, show all steps: 45, 32, 90, 34, 68, 72, 15, 24, 30, 66, 11, 50, 10. Also, delete 45, 90 and 11 (successively). Also, write an algorithm to insert an element into a Binary Search Tree.
   How to answer

   • Define Binary Search Tree (BST) property with an example
   • Show step-by-step insertion of each given number into the BST
   • Draw the final constructed BST
   • Perform successive deletions: delete 45 (replace by inorder successor/predecessor), delete 90, delete 11, showing trees after each deletion
   • Write pseudocode/algorithm for inserting a new node into a BST
5. 7 Marks
   aDefine AVL Trees. Explain its rotation operations with example. Construct AVL Tree by inserting the following data: 14, 17, 11, 7, 53, 4, 13, 12, 8, 60, 19, 16, 20
   How to answer

   • Define AVL tree and the balance factor formula ($BF = \text{height}(L) - \text{height}(R) \in \{-1, 0, 1\}$)
   • Explain and illustrate LL, RR, LR, and RL rotations with diagrams
   • Insert elements one by one, compute balance factors at each step, and perform necessary rotations
   • Show final balanced AVL tree
6. 7 Marks
   bDefine Huffman tree and describe an algorithm to create a Huffman tree. Construct a Huffman Tree for data structures with its optimal code.
   How to answer

   • Define Huffman tree and optimal prefix coding
   • State the greedy algorithm steps using a priority queue/min-heap
   • Count frequency of each character in the string 'data structures'
   • Step-by-step build the Huffman tree from character frequencies
   • Assign binary codes ('0' to left, '1' to right) and list the optimal codes for each unique character
7. 7 Marks
   aExplain in detail about the graph traversal techniques with suitable example.
   How to answer

   • Explain Breadth First Search (BFS) using Queue with algorithm/steps
   • Explain Depth First Search (DFS) using Stack/recursion with algorithm/steps
   • Provide an example graph and show traversal order for both BFS and DFS
   • Compare time and space complexities ($O(V + E)$)
8. 7 Marks
   bConsider the following undirected graph. i) Find the adjacency list representation of the graph. ii) Find a minimum cost spanning tree by Kruskal's algorithm.

   

   How to answer

   • Construct adjacency list for vertices A, B, C, D, E, F, G with neighbor nodes and weights
   • Sort all edges in ascending order of weights
   • Apply Kruskal's algorithm to add edges without creating cycles
   • Draw the resulting Minimum Spanning Tree (MST)
   • Calculate the total minimum cost
9. 7 Marks
   aWrite the algorithm to create a heap and sort the following elements using heap sort 12, 8, 10, 6, 4, 10, 6, 11, 9, 8, 14, 1, 2
   How to answer

   • Write algorithm for build-max-heap / heapify and heap sort
   • Construct initial binary tree from given array
   • Heapify bottom-up to obtain a valid Max-Heap
   • Perform successive extractions of max root, swapping with end element and re-heapifying
   • Show intermediate arrays/trees and present the final sorted sequence
10. 7 Marks
    bHow do you implement a circular queue in C using array? Write routines to implement operations for it. Differentiate between Linear Queue and Circular Queue.
    How to answer

    • Explain circular queue concept and indexing using $(rear + 1) \% MAX$
    • Write C routines for enqueue, dequeue, and display
    • Tabulate differences between Linear Queue and Circular Queue (memory efficiency, overflow handling)
11. 14 Marks
    Define doubly linked list. Describe an algorithm to insert an element at the beginning of the doubly linked list. Describe an algorithm to delete an element from the end of doubly linked list. Also explain the advantages and disadvantages of doubly linked list.
    How to answer

    • Define doubly linked list with node structure (data, prev, next)
    • Provide algorithm and diagram for inserting a node at the beginning
    • Provide algorithm and diagram for deleting a node from the end
    • List advantages (two-way traversal, easier deletion given pointer)
    • List disadvantages (extra memory for pointer, overhead in pointer manipulation)
12. 5 Marks
    aGiven a 2D array $A[-100:100, -5:50]$. Find the address of element $A[99, 49]$ considering the base address 10 and each elements requires 4 bytes for storage. Follow row-major order.
    How to answer

    • Calculate number of columns: $N = 50 - (-5) + 1 = 56$
    • State formula for row-major order: $\text{Address} = BA + W \times [(i - L_r) \times N + (j - L_c)]$
    • Substitute values: $BA = 10$, $W = 4$, $i - L_r = 99 - (-100) = 199$, $j - L_c = 49 - (-5) = 54$
    • Compute: $\text{Offset} = 199 \times 56 + 54 = 11144 + 54 = 11198$
    • Final Address = $10 + 4 \times 11198 = 10 + 44792 = 44802$
13. 5 Marks
    bWhat do you understand by stable and in-place sorting?
    How to answer

    • Define stable sorting (preserves relative order of duplicate keys)
    • Give examples of stable algorithms (Merge Sort, Insertion Sort) and unstable (Quick Sort, Heap Sort)
    • Define in-place sorting (requires $O(1)$ or minimal auxiliary memory)
    • Give examples of in-place algorithms (Bubble Sort, Selection Sort, Heap Sort)
14. 4 Marks
    cDefine Extended binary tree with example.
    How to answer

    • Define extended binary tree (2-tree) where every node has either 0 or 2 children
    • Explain replacement of null pointers with special external leaf nodes
    • Draw an illustrative example showing internal (circles) and external (squares) nodes
    • State property: $E = I + 2n$ or external nodes = internal nodes + 1
15. 7 Marks
    aDefine hash function. Discuss various methods used for resolving hash collisions.
    How to answer

    • Define hash function and its desired properties (uniformity, minimal collisions)
    • Explain Open Addressing methods: Linear Probing, Quadratic Probing, Double Hashing
    • Explain Closed Addressing / Separate Chaining using linked lists
    • Briefly compare the collision resolution techniques
16. 7 Marks
    bSuppose multidimensional arrays A and B are declared as $A(-2:2, 2:22)$ and $B(1:8, -5:5, -10:5)$ stored in row major order i) Find the length of each dimension of A and B. ii) The number of elements in A and B. iii) Assuming Base address $(B) = 500$, $W = 2$ Find the effective indices $E_1$, $E_2$, $E_3$ and address of the element $B[3, 3, 3]$.
    How to answer

    • i) Dimension lengths: For A: $L_1 = 2 - (-2) + 1 = 5$, $L_2 = 22 - 2 + 1 = 21$. For B: $L_1 = 8 - 1 + 1 = 8$, $L_2 = 5 - (-5) + 1 = 11$, $L_3 = 5 - (-10) + 1 = 16$
    • ii) Elements: Total in A = $5 \times 21 = 105$. Total in B = $8 \times 11 \times 16 = 1408$
    • iii) Effective indices for $B[3, 3, 3]$: $E_1 = 3 - 1 = 2$, $E_2 = 3 - (-5) = 8$, $E_3 = 3 - (-10) = 13$
    • Calculate address: $\text{Address} = 500 + 2 \times [2 \times (11 \times 16) + 8 \times 16 + 13] = 500 + 2 \times [352 + 128 + 13] = 500 + 2 \times 493 = 500 + 986 = 1486$