AL-303 Data Structure - Dec 2024 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 the insertion operation in linked list. How nodes are inserted after a specified node?
   How to answer

   • Concept of linked list insertion cases (beginning, end, after a specific node)
   • Step-by-step algorithm/logic to insert after a given node
   • Pointer reassignment details: new_node->next = prev_node->next; prev_node->next = new_node
   • Diagrammatic representation before and after insertion
2. 7 Marks
   bWhat are the draw backs of single linked list? Write and explain the algorithm for search and modify operations in doubly linked list with example.
   How to answer

   • Drawbacks of single linked list (unidirectional traversal, deletion requires predecessor pointer, extra overhead for backwards search)
   • Algorithm for searching a value in a doubly linked list
   • Algorithm for modifying/updating the value of a target node
   • Trace with a small concrete example (e.g., list of 3-4 nodes)
3. 7 Marks
   aWhat are the limitations of queue? Explain the algorithms for various operations of circular queue.
   How to answer

   • Limitation of linear queue (false overflow due to unused space at the front after dequeues)
   • Concept of circular queue using modulo arithmetic
   • Algorithm for Enqueue (insert) including overflow condition: `(rear + 1) % MAX == front`
   • Algorithm for Dequeue (delete) including underflow condition: `front == -1`
   • Display/traversal operation
4. 7 Marks
   bExplain the array implementation of stack ADT in detail.
   How to answer

   • Definition of Stack ADT and LIFO principle
   • Variables: array `stack[MAX]`, `top` pointer initialized to -1
   • Push algorithm/logic with overflow check (`top == MAX - 1`)
   • Pop algorithm/logic with underflow check (`top == -1`)
   • Peek/isEmpty/isFull helper operations
   • Diagram of stack array showing top index
5. 7 Marks
   aExplain an algorithm to check whether the parentheses in an expression are balanced using a stack.
   How to answer

   • Principle: push opening brackets `(`, `{`, `[` onto stack; pop on closing brackets `)`, `}`, `]` and verify matching type
   • Error cases: underflow when closing bracket encountered, mismatch in popped vs current, or non-empty stack at the end
   • Step-by-step pseudo-code or algorithm
   • Walkthrough example with a valid and invalid expression
6. 7 Marks
   bHow to insert and delete an element into a binary search tree and write down the code for the insertion.
   How to answer

   • BST property definition (left < root < right)
   • Explanation of insertion logic (compare key and recurse left or right until null)
   • Explanation of deletion cases: leaf node, node with one child, node with two children (replace with inorder successor/predecessor)
   • Code/pseudocode for BST insertion function
7. 14 Marks
   Construct an expression tree for the expression $(a + b * c) + ((d * e + f) * g)$. Give the outputs when you apply in order preorder and post order traversals.
   How to answer

   • Operator precedence analysis to form sub-trees: $(b * c)$ then $+ a$; $(d * e)$ then $+ f$ then $* g$; finally combine with main root $+$
   • Complete expression tree diagram
   • Inorder traversal output: $a + b * c + d * e + f * g$
   • Preorder traversal output: $+ + a * b c * + * d e f g$
   • Postorder traversal output: $a b c * + d e * f + g * +$
8. 7 Marks
   aCompare Prim's algorithm with Kruskal's algorithm for finding minimum spanning trees.
   How to answer

   • Definition and goal of Minimum Spanning Tree (MST)
   • Tabular comparison based on: approach (vertex vs edge), intermediate trees vs forest, suitability for dense vs sparse graphs
   • Data structures required (min-heap/priority queue vs disjoint-set/union-find)
   • Time complexities comparison ($O(E \log V)$ vs $O(E \log E)$)
9. 7 Marks
   bExplain Breadth First Search algorithm with example.
   How to answer

   • Concept of BFS (level-by-level traversal using a FIFO queue)
   • Algorithm steps using a visited array and queue
   • Sample graph example with vertices and edges
   • Step-by-step execution showing queue states and output order
   • Time and space complexity ($O(V + E)$)
10. 7 Marks
    aCreate a binary search tree for the following numbers start from an empty binary search tree. 45, 26, 10, 60, 70, 30, 40 Delete keys 10, 60 and 45 one after the other and show the trees at each step.
    How to answer

    • Construct initial BST with nodes: root 45; left subtree (26 -> left 10, right 30 -> right 40); right subtree (60 -> right 70)
    • Step 1: Delete key 10 (leaf node removal)
    • Step 2: Delete key 60 (node with one child 70, 70 replaces 60)
    • Step 3: Delete key 45 (root with two children, replaced by inorder successor/predecessor e.g., 70 or 40)
    • Draw tree diagrams clearly for each of the 4 stages
11. 7 Marks
    bProvide examples of real-world applications where hashing is used and explain any two example in details.
    How to answer

    • List real-world applications (password verification/storage, compilers/symbol tables, caching/database indexing, cryptography/blockchain)
    • Detailed explanation of Example 1 (e.g., Password verification using salted hash)
    • Detailed explanation of Example 2 (e.g., Symbol table in compilers for fast identifier lookup)
12. 7 Marks
    aExplain how to sort the elements by using selection sort and derive time complexity for the same.
    How to answer

    • Working principle of selection sort (finding minimum element in unsorted partition and swapping to front)
    • Step-by-step algorithm/pseudocode
    • Derivation: counting total comparisons $(n-1) + (n-2) + \dots + 1 = n(n-1)/2$
    • Conclusion: best, average, and worst-case time complexity is $O(n^2)$
13. 7 Marks
    bIllustrate with examples the operations of insertion and deletion in an AVL tree.
    How to answer

    • Definition of AVL tree and balance factor criteria ($-1, 0, +1$)
    • Insertion: explanation of 4 rotation cases (LL, RR, LR, RL) with an example diagram
    • Deletion: explanation of rebalancing after deletion (R0, R1, R-1 rotations) with an example diagram
14. 14 Marks
    Write a short notes (any three)

    1. i)Merge Sort
    2. ii)Graph
    3. iii)B+ Tree
    4. iv)Dqueue
    How to answer

    • i) Merge Sort: Divide-and-conquer strategy, recursive partitioning, merge process, $O(n \log n)$ time complexity
    • ii) Graph: Definition $G=(V, E)$, directed vs undirected, representations (adjacency matrix vs list)
    • iii) B+ Tree: Self-balancing multi-way search tree, all keys stored in leaves, linked leaf nodes for range queries, index nodes for navigation
    • iv) Dqueue (Deque): Double-ended queue allowing insertion/deletion at both ends, input-restricted vs output-restricted types