AD-303 Data Structure - Jun 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
   aWhat is Abstract data type? Explain with the help of example.
   How to answer

   • Definition of ADT (data representation independent of implementation)
   • Key components: values and allowed set of operations
   • Example of an ADT (e.g., Stack ADT, List ADT, or Queue ADT)
   • Declaration/specification of operations with inputs and outputs
2. 7 Marks
   bDifferentiate array and linked list.
   How to answer

   • Tabular comparison between Array and Linked List
   • Key differences: static vs dynamic memory allocation, contiguous vs non-contiguous storage
   • Time complexity comparison for indexing, insertion, and deletion
   • Memory overhead (pointers in linked list vs direct storage in arrays)
3. 7 Marks
   aDraw an AVL tree on following inputs, assume that tree is initially empty: 485, 575, 655, 745, 830, 910, 100, 110, 520, 130, 340, 450, 365, 525, 204, 155, 130, 35
   How to answer

   • Step-by-step insertion of keys into the AVL tree
   • Calculation of balance factor $\{-1, 0, +1\}$ at each node after insertion
   • Identification and execution of rotations (LL, RR, LR, RL) when imbalance occurs
   • Final balanced AVL tree structure
4. 7 Marks
   bCompare and Contrast the Spanning tree and Minimum Spanning Tree
   How to answer

   • Definition of Spanning Tree (connected subgraph with $V$ vertices and $V-1$ edges without cycles)
   • Definition of Minimum Spanning Tree (spanning tree with minimum total edge weight)
   • Key comparisons: total weight consideration, algorithms (DFS/BFS for ST vs Kruskal/Prim for MST)
   • Example illustrating both on a simple weighted graph
5. 7 Marks
   aWhat do you mean by an algorithm? Write the criteria and characteristics of an algorithm.
   How to answer

   • Definition of an algorithm (unambiguous step-by-step procedure to solve a problem)
   • Key criteria/characteristics: Input, Output, Definiteness, Finiteness, and Effectiveness
   • Additional properties: Feasibility, Independent of programming languages
6. 7 Marks
   bDemonstrate the efficiency of an algorithm.
   How to answer

   • Concept of algorithm efficiency: Time and Space complexity
   • Analysis of running time: best case, average case, worst case
   • Asymptotic notations: $O$, $\Omega$, $\Theta$
   • Demonstration with an example (e.g., Linear Search vs Binary Search or sorting algorithms)
7. 7 Marks
   aWrite an algorithm to convert infix expression into postfix form using Stack. Also evaluate the given postfix form using stack $$2 \ 3 \ 9 \ * \ + \ 2 \ 3 \ \text{^} \ - \ 6 \ 2 \ / \ +$$
   How to answer

   • Step-by-step algorithm for Infix to Postfix conversion using stack and operator precedence
   • Step-by-step stack evaluation table for $2 \ 3 \ 9 \ * \ + \ 2 \ 3 \ \text{^} \ - \ 6 \ 2 \ / \ +$:
   • Token-by-token stack state tracing
   • $3 * 9 = 27$; $2 + 27 = 29$; $2^3 = 8$; $29 - 8 = 21$; $6 / 2 = 3$; $21 + 3 = 24$
   • Final calculated value: 24
8. 7 Marks
   bWrite a program in 'C' to implementation of QUEUE.
   How to answer

   • Declaration of Queue structure/array, front and rear variables
   • Implementation of enqueue() function with overflow check
   • Implementation of dequeue() function with underflow check
   • Implementation of display() function and main() function demonstrating usage
9. 7 Marks
   aWhat are the differences between i) Height and depth ii) Order and degree
   How to answer

   • Part i: Height is the number of edges on the longest path from node to a leaf; Depth is the number of edges from the root to that node
   • Part ii: Degree of a node is the number of children it has; Order usually refers to the maximum number of children a node can have in multiway search trees (like B-trees)
10. 7 Marks
    bShow that the maximum number of nodes in a binary tree of height $h$ is $2^{h+1}-1$.
    How to answer

    • State maximum nodes at level $i$ is $2^i$ (for $i = 0, 1, 2, \dots, h$)
    • Sum of nodes across all levels: $N = \sum_{i=0}^h 2^i = 2^0 + 2^1 + 2^2 + \dots + 2^h$
    • Use sum of geometric series formula: $S_n = \frac{a(r^n - 1)}{r - 1} = \frac{1(2^{h+1} - 1)}{2 - 1} = 2^{h+1}-1$
    • Alternative proof using mathematical induction on height $h$
11. 7 Marks
    aWhat are sparse matrices? Explain the representation of the Sparse matrix. Also, demonstrate the upper triangle and lower triangular sparse matrices. Suggest a space efficient representation for sparse matrices and determine the address determination formulas for it.
    How to answer

    • Definition of sparse matrix (majority elements are zero)
    • Representation forms: 3-tuple / Triplet representation (row, column, value) and linked lists
    • Definitions and matrix examples of Upper and Lower triangular matrices
    • 1D compact array storage for triangular matrices
    • Derivation of address determination formula: $\text{Loc}(A[i][j]) = \text{Base} + \left(\frac{i(i+1)}{2} + j\right) \times w$ (for lower triangular, 0-indexed)
12. 7 Marks
    bWrite a note on Compaction, overflow, and Underflow in Array term.
    How to answer

    • Definition of Overflow (attempting to insert an element into an already full array/data structure)
    • Definition of Underflow (attempting to delete an element from an empty array/data structure)
    • Definition and purpose of Compaction (shifting active elements together to eliminate fragmented unused space)
13. 7 Marks
    aWhat is HashMap in data structure? How does HashMap handle collisions? Explain with C or Java.
    How to answer

    • Definition of HashMap (key-value pair storage based on hashing)
    • Concept of hash collisions ($h(k_1) = h(k_2)$)
    • Collision resolution techniques: Separate Chaining and Open Addressing (Linear probing, Quadratic probing, Double hashing)
    • Code illustration or explanation using C or Java
14. 7 Marks
    bDemonstrate LRU Algorithm. Which data structure uses LRU algorithm.
    How to answer

    • Concept and working principle of Least Recently Used (LRU) algorithm
    • Demonstration with a reference string / sequence of memory accesses
    • Data structures used to implement LRU cache efficiently: Doubly Linked List combined with Hash Map ($O(1)$ operations)
15. 7 Marks
    aDraw the directed graph that corresponds to the following adjacency matrix. $$\begin{array}{c|cccc} & V_0 & V_1 & V_2 & V_3 \\ \hline V_0 & 0 & 1 & 1 & 0 \\ V_1 & 0 & 0 & 1 & 1 \\ V_2 & 0 & 0 & 0 & 1 \\ V_3 & 1 & 0 & 0 & 0 \\ \end{array}$$
    How to answer

    • Identify 4 vertices: $V_0, V_1, V_2, V_3$
    • Identify directed edges from 1s in matrix: $(V_0 \to V_1)$, $(V_0 \to V_2)$, $(V_1 \to V_2)$, $(V_1 \to V_3)$, $(V_2 \to V_3)$, $(V_3 \to V_0)$
    • Draw clear directed graph showing all 4 vertices and 6 directed arrows
16. 7 Marks
    bExplore all types of operations that can be performed on a linked list.
    How to answer

    • Traversal / Display operation
    • Insertion operations (at beginning, at end, at specified position/after a node)
    • Deletion operations (from beginning, from end, specific node/value)
    • Search and Update operations
    • Other advanced operations: Reversal, Concatenation/Merging, Sorting