IT-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
   aDefine Data Structures. With the aid of a neat diagram describe the classification of data structures.
   How to answer

   • Define data structure as a specialized format for organizing, processing, retrieving, and storing data.
   • Draw hierarchical taxonomy tree: Primitive (int, float, char, pointer) vs Non-Primitive.
   • Subdivide Non-Primitive into Linear (Arrays, Linked Lists, Stacks, Queues) and Non-Linear (Trees, Graphs).
   • Briefly describe characteristics of linear vs non-linear structures.
2. 7 Marks
   bWhat is asymptotic analysis? Explain Big-oh notation. Analyse and write the running time complexity of the following function. ```c A() { int i, j, k, n; for(i=1; i<=n; i++) for(j=1; j2<=n; j++) for(k=1; 2k<=n; k++) printf("*"); } ```
   How to answer

   • Define asymptotic analysis as evaluating performance of an algorithm as input size n grows towards infinity.
   • Provide formal mathematical definition of Big-O: $f(n) \le c \cdot g(n)$ for $n \ge n_0$.
   • Analyze loop 1: runs $n$ times.
   • Analyze loop 2: condition `j2<=n` (interpreted either as $j^2 \le n \implies \sqrt{n}$ or $j \times 2 \le n \implies n/2$).
   • Analyze loop 3: condition `2k<=n` runs $n/2$ times.
   • Multiply loop bounds to give overall Big-O bound.
3. 7 Marks
   aGiven an array with both positive and negative numbers, find the two elements such that their sum is closest to zero. For the below array, algorithm should give $-80$ and $85$. Example: $1, 60, -10, 70, -80, 85$ Also discuss the complexity of the process and suggest and alternate way to optimize the complexity.
   How to answer

   • State naive/brute force approach: compare every pair $(i, j)$ in $O(n^2)$ time.
   • Propose optimized approach: sort the array in $O(n \log n)$ time.
   • Use two pointers (left at start, right at end); update minimum absolute sum and move left or right based on whether sum is negative or positive.
   • Demonstrate on example: sorted array is `[-80, -10, 1, 60, 70, 85]`, showing pair $(-80, 85)$ gives sum $5$.
   • Complexity analysis: $O(n \log n)$ time and $O(1)$ extra space.
4. 7 Marks
   bConsider a two-dimensional array $A$ of order $[20 * 5]$. The base address of the array is $840$, words per memory cell is $8$. Find the address of $A[15, 3]$ using row major and column major addressing.
   How to answer

   • State given values: $BA = 840$, $w = 8$, $m = 20$, $n = 5$, target $(i, j) = (15, 3)$ (assuming 0-indexed or 1-indexed, clearly stated).
   • Formula for Row Major: $Address = BA + w \times (i \times n + j)$ (for 0-based indexing: $840 + 8 \times (15 \times 5 + 3) = 840 + 8 \times 78 = 1464$; if 1-based: $840 + 8 \times (14 \times 5 + 2) = 1416$).
   • Formula for Column Major: $Address = BA + w \times (j \times m + i)$ (for 0-based indexing: $840 + 8 \times (3 \times 20 + 15) = 840 + 8 \times 75 = 1440$; if 1-based: $840 + 8 \times (2 \times 20 + 14) = 1272$).
   • Provide explicit calculation steps and final numerical values.
5. 7 Marks
   aWhat is a link list? Discuss the advantages of using link list; also write about the various operations which can be performed on link list with their time complexities.
   How to answer

   • Define linked list as a linear collection of data elements (nodes) where each points to the next.
   • List advantages: dynamic size, ease of insertion/deletion without shifting.
   • Tabulate operations and time complexities: Insertion at head $O(1)$, Insertion at tail $O(n)$ or $O(1)$ with tail pointer, Deletion at head $O(1)$, Search $O(n)$, Traversal $O(n)$.
6. 7 Marks
   bSuppose there are two singly linked lists both of which intersect at some point and become a single linked list as shown below: The head pointers of both the lists are known. Give an algorithm for finding the merging point and write the running time complexity.

   

   How to answer

   • State the algorithm: 1) Count lengths $L_1$ and $L_2$ of both linked lists.
   • 2) Find the absolute difference $d = |L_1 - L_2|$.
   • 3) Advance the pointer of the longer list by $d$ steps.
   • 4) Move both pointers simultaneously one node at a time until they point to the same node.
   • 5) The meeting node is the intersection/merging point.
   • State time complexity: $O(L_1 + L_2)$ time, and $O(1)$ auxiliary space.
7. 7 Marks
   aDefine Stack. What are the different operations, which can be performed on stack. Explain why Stack is a recursive data structure?
   How to answer

   • Define stack as a linear data structure following LIFO (Last In First Out).
   • List basic operations: Push, Pop, Peek/Top, IsEmpty, IsFull.
   • Explain why stack is recursive: a stack can either be empty, or consist of a top element followed by a stack; alternatively, function call stack implements recursion.
8. 7 Marks
   bWrite an algorithm for evaluating a postfix expression and apply the same for the given postfix expression: $2 \ 8 \ 4 - 5 * + 7 \ 7 / +$, showing the content of stack at each step.
   How to answer

   • State algorithm: scan left to right; if operand, push to stack; if operator, pop top two operands, evaluate, and push result back.
   • Step-by-step trace of expression `2 8 4 - 5 * + 7 7 / +` in a table with columns: Symbol, Action, Stack content.
   • `8 4 -` $\implies 4$; stack: `[2, 4]`.
   • `4 5 *` $\implies 20$; stack: `[2, 20]`.
   • `2 20 +` $\implies 22$; stack: `[22]`.
   • `7 7 /` $\implies 1$; stack: `[22, 1]`.
   • `22 1 +` $\implies 23$; stack: `[23]`.
   • Final evaluated result is 23.
9. 7 Marks
   aExplain the importance of queue. Describe why it is a bad idea to implement a linked list version a queue which uses the head of the list as the rear of the queue.
   How to answer

   • Explain importance of queue: scheduling processes, asynchronous data transfer (buffers, IO queues), breadth-first search.
   • Analyze using head as rear (enqueue at head): inserting at head takes $O(1)$.
   • However, dequeue must happen at the front, which corresponds to the tail of the singly linked list.
   • Deleting the tail node in a singly linked list requires finding the node preceding the tail, which takes $O(n)$ time.
   • Conclude that dequeue becomes $O(n)$ instead of $O(1)$, which is inefficient.
10. 7 Marks
    bWhat is the advantage of circular queue over ordinary queue? Write a C program to simulate the working of circular queue of integers using array. Provide the following operations: i) Insert ii) Delete iii) Display
    How to answer

    • Advantage: avoids memory wastage in linear queues where space vacated by deleted items cannot be reused without shifting.
    • Modulo arithmetic $(rear + 1) \% MAX$ allows wrap-around.
    • Provide C code defining array, `front`, `rear` initialized to -1.
    • Implement `insert(val)` checking for full condition: `(rear + 1) % MAX == front`.
    • Implement `delete()` checking for empty condition: `front == -1`.
    • Implement `display()` to print elements from `front` to `rear` circularly.
11. 7 Marks
    aShow the steps of quick sort on the following set of elements. $26, 56, 47, 36, 13, 95, 85, 32$ Assume the last element as the pivot element.
    How to answer

    • Initial array: `[26, 56, 47, 36, 13, 95, 85, 32]`, pivot = 32.
    • Partitioning pass: compare elements with 32; elements $\le 32$ are 26, 13. Swapping places 32 at its correct sorted position (index 2): `[26, 13, 32, 36, 56, 95, 85, 47]`.
    • Show recursive call on left sub-array `[26, 13]` with pivot 13 $\implies [13, 26]$.
    • Show recursive call on right sub-array `[36, 56, 95, 85, 47]` with pivot 47.
    • Continue recursive partitioning for remaining sub-arrays until the array is completely sorted: `[13, 26, 32, 36, 47, 56, 85, 95]`.
12. 7 Marks
    bDesign a data representation which sequentially map '$n$' data objects into an array $a[1, n]$, $n_1$ of these data objects are stacks and the remaining are queues. Write algorithms to add and delete elements from these objects.
    How to answer

    • Divide array $a[1, n]$ into multiple segments: allocate fixed/proportional slices or use top/base pointer arrays for the $n_1$ stacks and front/rear pointers for the remaining $k - n_1$ queues.
    • Define boundary array $B[i]$ and top/rear pointers $T[i]$ for each structure.
    • Write algorithm for Push (stack): check overflow against boundary $B[i+1]$, increment $T[i]$, insert.
    • Write algorithm for Pop (stack): check underflow against base $B[i]$, retrieve and decrement $T[i]$.
    • Write algorithm for Enqueue and Dequeue using front and rear pointers for queue segments.
    • Mention memory shift / reallocation strategy when an individual segment overflows.
13. 7 Marks
    aWhat is collision? What are the methods to resolves collision? Using the hash function 'key mod 7', insert the following sequence of keys in the hash table- $32, 50, 700, 140, 76, 85, 46, 92, 70, 73$ and $101$ Use separate chaining technique for collision resolution.
    How to answer

    • Define collision: when two distinct keys map to the same hash index.
    • List collision resolution methods: Separate Chaining (Open Hashing) and Open Addressing (Linear Probing, Quadratic Probing, Double Hashing).
    • Calculate $k \pmod 7$ for each key:
    • $32 \% 7 = 4$; $50 \% 7 = 1$; $700 \% 7 = 0$; $140 \% 7 = 0$; $76 \% 7 = 6$; $85 \% 7 = 1$; $46 \% 7 = 4$; $92 \% 7 = 1$; $70 \% 7 = 0$; $73 \% 7 = 3$; $101 \% 7 = 3$.
    • Show separate chaining linked list at each index (0 to 6):
    • Index 0: $700 \to 140 \to 70$
    • Index 1: $50 \to 85 \to 92$
    • Index 2: empty
    • Index 3: $73 \to 101$
    • Index 4: $32 \to 46$
    • Index 5: empty
    • Index 6: $76$
14. 7 Marks
    bWhat are L-L, L-R and R-R rotation? Write procedure for adding and deleting a node from the balanced tree and leave the resulting tree balanced.
    How to answer

    • Explain LL rotation: single right rotation applied when insertion is into the left subtree of the left child.
    • Explain RR rotation: single left rotation applied when insertion is into the right subtree of the right child.
    • Explain LR rotation: double rotation (left rotation on left child followed by right rotation on parent).
    • Provide steps for insertion: standard BST insertion, update balance factors, perform appropriate rotation on lowest unbalanced ancestor.
    • Provide steps for deletion: standard BST deletion, backtrack upwards updating balance factors and perform rotations (LL, RR, LR, RL) as needed.
15. 7 Marks
    aWhat is the sequence of nodes visited for the following tree for a preorder, postorder, and breadth first traversal?

    

    How to answer

    • Identify tree hierarchy: Root is `j`; children of `j` are `f`, `c`, `e`. Under `f`: `d`, under `d`: `g`. `c` has no children. Under `e`: `a`, `h`, `i`; under `i`: `b`.
    • Preorder (Root, Left, Right): `j, f, d, g, c, e, a, h, i, b`.
    • Postorder (Left, Right, Root): `g, d, f, c, a, h, b, i, e, j`.
    • Breadth-first / Level-order: Level 0: `j`; Level 1: `f, c, e`; Level 2: `d, a, h, i`; Level 3: `g, b` $\implies$ `j, f, c, e, d, a, h, i, g, b`.
16. 7 Marks
    bWhat is Graph traversal? Discuss the difference between traversing a graph and a tree. Consider the following graph, Among the following sequences, which are the depth-first traversals of the above graph? Justify your answer by showing the adjacency list and stack contents for the traversals. i) a b e g h f ii) a b f e h g iii) a b f h g e iv) a f g h b e

    

    How to answer

    • Define graph traversal as visiting all vertices systematically.
    • Compare tree vs graph traversal: graphs can contain cycles, requiring a `visited` array to prevent infinite loops, whereas trees are acyclic and start at a unique root.
    • Construct adjacency list from the diagram: vertices are {a, b, e, f, g, h} with undirected edges (a-b, a-e, a-f, e-b, e-g, b-h, b-f, f-h, f-g, h-g).
    • Trace DFS for each of the 4 candidate sequences using the stack.
    • Verify valid paths and determine which sequence(s) represent valid DFS orders with justification.