AD-303 Data Structure - Dec 2022 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
   aExplain Red Black Trees , also discuss the properties of Red Black Tree .
   How to answer

   • Definition of Red-Black Tree as a self-balancing binary search tree
   • Key properties: Node color (red/black), root is black, all leaves (NIL) are black
   • Red node constraint (no two consecutive red nodes)
   • Black-height property (equal black nodes on all paths to leaves)
   • Time complexity of search, insertion, deletion: O(log n)
2. 7 Marks
   bSort using quick sort algorithm - $36, 25, 32, 5, 8, 65, 38, 47, 95$.
   How to answer

   • Select pivot (e.g., first, last, or middle element)
   • Show partitioning step with pointers i and j
   • Recursively apply quick sort on left and right sub-arrays
   • Final sorted sequence: 5, 8, 25, 32, 36, 38, 47, 65, 95
3. 7 Marks
   aWhat is Hashing ? Explain different Hash function in detail .
   How to answer

   • Definition of hashing and hash table
   • Purpose of hash functions (mapping large keys to smaller address space)
   • Types of hash functions: Division method ($h(k) = k \bmod m$), Mid-Square method, Folding method, Multiplication method
   • Characteristics of a good hash function
4. 7 Marks
   bExplain AVL Tree . Insert the following elements in AVL Search Tree . $$48 \quad 25 \quad 10 \quad 5 \quad 7 \quad 3 \quad 28 \quad 20 \quad 8 \quad 16$$
   How to answer

   • Define AVL tree and balance factor (-1, 0, +1)
   • Mention four rotation types (LL, RR, LR, RL)
   • Step-by-step insertion of each element: 48, 25, 10 (imbalance, rotate), 5, 7, 3, 28, 20, 8, 16
   • Show tree state and balance factors after each required rotation
   • Final balanced AVL tree structure
5. 7 Marks
   aExplain analysis of Heap Operation with example .
   How to answer

   • Definition of binary heap (complete binary tree, heap property)
   • Primary operations: Insert, Delete/Extract-Max, Heapify, Build-Heap
   • Step-by-step example of insertion and deletion/heapify
   • Time complexity analysis: Insert $O(\log n)$, Delete $O(\log n)$, Heapify $O(\log n)$, Build-Heap $O(n)$
6. 7 Marks
   bSort the following list using quick sort . $$44, 33, 11, 55, 77, 90, 40, 60, 99, 22, 88, 66$$
   How to answer

   • Choose pivot element
   • Demonstrate partitioning into elements smaller and larger than pivot
   • Show sub-array recursive steps
   • Final sorted sequence: 11, 22, 33, 40, 44, 55, 60, 66, 77, 88, 90, 99
7. 7 Marks
   aWrite the algorithm of insertion sort and find its Time complexity .
   How to answer

   • Step-by-step algorithm/pseudocode for insertion sort
   • Explanation of sorted and unsorted partitions
   • Best-case time complexity analysis: $O(n)$ (already sorted)
   • Worst-case and average-case time complexity: $O(n^2)$ (reverse sorted)
8. 7 Marks
   bDifference Between Internal sorting and External sorting .
   How to answer

   • Tabular comparison between internal and external sorting
   • Memory storage: RAM vs secondary storage (disk)
   • Volume of data: fits in primary memory vs exceeds primary memory
   • Speed: Fast I/O vs slower secondary memory access
   • Examples: Quick sort/Merge sort vs Multiway merge sort
9. 7 Marks
   aGive the solution for following Recursion – $T(n) = 2T[n/2] + n \log n$ .
   How to answer

   • Identify parameters: $a = 2$, $b = 2$, $f(n) = n \log n$
   • Calculate $n^{\log_b a} = n^{\log_2 2} = n$
   • Compare $f(n)$ with $n^{\log_b a}$: $f(n) = n \log n = \Theta(n^{\log_b a} \log^k n)$ with $k = 1$
   • Apply extended Master Theorem Case 2: $T(n) = \Theta(n \log^{k+1} n) = \Theta(n \log^2 n)$
10. 7 Marks
    bDifference between Breadth First Search and Depth First Search
    How to answer

    • Tabular comparison between BFS and DFS
    • Data structures: Queue for BFS vs Stack/recursion for DFS
    • Traversal order: Level-by-level vs branch-by-branch depth-wise
    • Memory/Space requirements
    • Applications: Shortest path in unweighted graphs (BFS) vs Topological sorting/cycle detection (DFS)
11. 7 Marks
    aWrite an algorithm for insertion and deletion in priority Queues .
    How to answer

    • Define Priority Queue and underlying data structure (array/linked list/heap)
    • Algorithm for Insert (with priority checking / heap insertion)
    • Algorithm for Delete (highest/lowest priority removal / extract-max with heapify)
    • Time complexity discussion of both operations
12. 7 Marks
    bExplain Dijkstra's algorithm for finding shortest path with an exampl
    How to answer

    • Principle of Dijkstra's algorithm (greedy approach, non-negative weights)
    • Initialization of distances, visited set, and predecessor array
    • Step-by-step node selection and edge relaxation ($d[v] > d[u] + w(u,v)$)
    • Complete worked example with a graph and a distance table
13. 7 Marks
    awrite short note on Internal trees . Explain with example .
    How to answer

    • Definition of internal nodes vs external nodes (leaves) in trees
    • Concept of internal tree structure and internal path length
    • Illustrative example diagram showing internal nodes and external nodes
    • Significance and properties in search trees
14. 7 Marks
    bHow can you covert an infix expression to postfix operation using stac Give one Example .
    How to answer

    • Algorithm for infix-to-postfix conversion using a stack
    • Handling operands, operators, precedence, associativity, and parentheses
    • Worked example (e.g. $(A + B) * C - D / E$)
    • Tabular trace showing input symbol, stack contents, and postfix expression string
15. 7 Marks
    aWrite an algorithm Which counts the number of connected component a graph .
    How to answer

    • Concept of connected components in an undirected graph
    • Initialize visited array to false and component counter to 0
    • Iterate over all vertices: if unvisited, increment counter and invoke BFS/DFS
    • Pseudocode and analysis of time complexity $O(V + E)$
16. 7 Marks
    bConstruct a Tree for the given Inorder And Postorder traversals . Inorder : DGBAHEICF Postorder: GDBHIEFCA
    How to answer

    • Identify root node as the last element of postorder: 'A'
    • Partition inorder traversal around 'A': Left subtree = 'DGB', Right subtree = 'HEICF'
    • Corresponding postorder splits: Left subtree = 'GDB', Right subtree = 'HIEFC'
    • Recursively determine left and right children for each subtree
    • Draw the final constructed binary tree