IT-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
   aWhat is Data structure? Write a brief note on classification of data structure.
   How to answer

   • Define data structure as a specialized format for organizing, processing, retrieving, and storing data
   • Classification hierarchy: Primitive (int, char, float) vs. Non-Primitive
   • Classification into Linear (Array, Linked List, Stack, Queue) and Non-Linear (Tree, Graph)
   • Static vs. Dynamic classification with brief descriptions
2. 7 Marks
   bWhat do you mean by algorithmic complexity? Explain Time complexity and space complexity in brief.
   How to answer

   • Define algorithmic complexity as a measure of resources (time/space) required relative to input size
   • Explain Time complexity: execution time as a function of input size $n$
   • Explain Space complexity: memory/storage needed as a function of $n$ (auxiliary vs input space)
   • Mention asymptotic notations briefly (Big-O, Omega, Theta)
3. 7 Marks
   aHow do you implement binary search recursively?
   How to answer

   • Explain the precondition (sorted array) and recursive divide-and-conquer logic
   • Base cases: element found ($arr[mid] == key$) or search interval empty ($low > high$)
   • Recursive cases: search left half ($mid - 1$) or right half ($mid + 1$)
   • Provide algorithm / pseudocode or C/C++ function
4. 7 Marks
   bHow does the size of the input array affect the time complexity of linear search and binary search?
   How to answer

   • State time complexity of linear search: worst-case $O(n)$ proportional directly to array size $n$
   • State time complexity of binary search: worst-case $O(\log_2 n)$ growing logarithmically
   • Compare rate of growth as $n$ increases substantially
   • Draw comparative growth curve / table for values of $n$
5. 7 Marks
   aEvaluate the post fix expression using stack $$8\ 3\ 4\ +\ -\ 3\ 8\ 2\ /\ +\ *\ 2\ \$\ 3\ +$$
   How to answer

   • Set up tabular steps with columns: Symbol Scanned, Operation / Action, Stack Contents
   • Scan from left to right: push operands, apply operator to top two elements
   • Detailed evaluations: $3+4=7$, $8-7=1$, $8/2=4$, $3+4=7$, $1*7=7$, $7\$2 = 7^2 = 49$, $49+3=52$
   • Final value in stack is 52
6. 7 Marks
   bExplain and implement a singly linked list with an example?
   How to answer

   • Define singly linked list (nodes consisting of data and a next pointer)
   • Illustrate node structure and a simple linked list with a diagram
   • Provide code for node definition (struct Node) and primary functions like insertion and display
   • Walk through a concrete example inserting a few values
7. 7 Marks
   aSuppose you have a queue with the following elements: $[10, 20, 30, 40, 50]$. What will be the result of dequeuing two elements from this queue, then enqueueing three new elements with the values of $60$, $70$ and $80$, and finally dequeuing one more element?
   How to answer

   • State initial queue: $[10, 20, 30, 40, 50]$ (Front: 10, Rear: 50)
   • Step 1: Dequeue two elements $\rightarrow$ removes 10, then 20; queue becomes $[30, 40, 50]$
   • Step 2: Enqueue 60, 70, 80 $\rightarrow$ queue becomes $[30, 40, 50, 60, 70, 80]$
   • Step 3: Dequeue one more element $\rightarrow$ removes 30; final queue state is $[40, 50, 60, 70, 80]$
   • List all dequeued elements (10, 20, 30) and final queue contents
8. 7 Marks
   bHow can you implement a queue using two stacks, and what are the advantages and disadvantages of this approach?
   How to answer

   • Describe two-stack implementation: Stack1 (for enqueue) and Stack2 (for dequeue)
   • Explain Enqueue operation (push to Stack1) and Dequeue operation (if Stack2 empty, transfer all from Stack1 to Stack2, then pop from Stack2)
   • Advantages: Easy implementation on systems with only stack primitives; amortized $O(1)$ time complexity
   • Disadvantages: Worst-case dequeue takes $O(n)$ time; double memory overhead compared to single array
9. 7 Marks
   aExplain Insertion sort in details. Write an algorithm for it. Discuss the complexity of insertion sort.
   How to answer

   • Explain insertion sort working principle (dividing array into sorted and unsorted subarrays, inserting key into correct position)
   • Write pseudocode/algorithm for insertion sort
   • Discuss Time Complexity: Best case $O(n)$ (already sorted), Worst case $O(n^2)$, Average case $O(n^2)$
   • State Space Complexity: $O(1)$ auxiliary space (in-place, stable)
10. 7 Marks
    bWhat is max heap? Write an algorithm to perform heap sort. Give example.
    How to answer

    • Define Max Heap: a complete binary tree where parent node is greater than or equal to its children ($A[PARENT(i)] \ge A[i]$)
    • Provide algorithm for Heap Sort: Build-Max-Heap, repeatedly swap root with last element and reduce heap size, call Max-Heapify
    • Illustrate with an example array walkthrough showing heap creation and step-by-step extraction
    • Mention complexity: $O(n \log n)$ time and $O(1)$ space
11. 7 Marks
    aSuppose you have an array with the following elements: $[22, 7, 2, 9, 8, 15, 13, 3, 11]$. What will be the result of sorting this array using the quicksort algorithm with the first element as the pivot?
    How to answer

    • Identify initial pivot = 22
    • Partition array: all other elements ($7, 2, 9, 8, 15, 13, 3, 11$) are smaller than 22, so 22 moves to the end (index 8)
    • Recursive call on left sub-array $[7, 2, 9, 8, 15, 13, 3, 11]$ with 7 as pivot
    • Show sub-partitions and recursive steps clearly until all base cases are reached
    • State final sorted array: $[2, 3, 7, 8, 9, 11, 13, 15, 22]$
12. 7 Marks
    bDefine the properties of circular queue. How will you check whether the circular queue is i) Full ii) Empty
    How to answer

    • Define circular queue as a linear data structure that connects the last position back to the first using modulo arithmetic to overcome linear queue memory wastage
    • Condition for Empty: `front == -1` (or `front == rear` depending on convention)
    • Condition for Full: `(rear + 1) % MAX == front`
    • Briefly illustrate with a circular diagram showing front and rear pointers
13. 7 Marks
    aInsert the set of elements $\{30, 40, 24, 58, 48, 26, 11, 13\}$ to construct a binary search tree starting from a null tree taking one element at a time from left to right. Draw a tree for each steps?
    How to answer

    • Step 1: Insert 30 as root
    • Step 2: Insert 40 (right child of 30)
    • Step 3: Insert 24 (left child of 30)
    • Step 4: Insert 58 (right child of 40)
    • Step 5: Insert 48 (left child of 58)
    • Step 6: Insert 26 (right child of 24)
    • Step 7: Insert 11 (left child of 24)
    • Step 8: Insert 13 (right child of 11)
    • Draw the resulting BST at each of the 8 steps
14. 7 Marks
    bConstruct a binary tree whose preorder and post order traversal as follows i) Preorder- F, B, A, D, C, E, G, I, H, K, J ii) Postorder- A, C, E, D, B, H, K, I, J, G, F
    How to answer

    • Identify root is 'F' (first in preorder, last in postorder)
    • Left subtree root is 'B' (next in preorder), locate 'B' in postorder to determine left subtree elements: {A, C, E, D, B}
    • Right subtree elements: {H, K, I, J, G} with root 'G'
    • Recursively construct left subtree from preorder [B, A, D, C, E] and postorder [A, C, E, D, B]
    • Recursively construct right subtree from preorder [G, I, H, K, J] and postorder [H, K, I, J, G]
    • Draw the final constructed binary tree
15. 14 Marks
    Write short note on any two: i) Application of queue ii) BFS and DFS iii) Doubly circular linked list
    How to answer

    • For (i): CPU scheduling, disk scheduling, print spooling, IO buffers, breadth first search
    • For (ii): BFS uses queue, explores level by level; DFS uses stack/recursion, explores as deep as possible; compare time/space complexities
    • For (iii): Structure with prev and next pointers, head's prev points to tail and tail's next points to head, operations and advantages over linear doubly linked list