← Back to Semester 3 Hub
🏛️ CCSU Meerut ⏱️ 75 Marks External (3 Hours) 📄 3M, 7.5M & 15M Exam Blueprint ⭐ 2018–2021 Recurring University Exam Archive
Exam Scoring Architecture for BCA-302 (Data Structures): The university theory examination carries 75 Marks with a 3-hour duration, structured into Section A (5 questions × 3M = 15M compulsory), Section B (attempt 2 of 3 questions × 7.5M = 15M), and Section C (attempt 3 of 5 questions × 15M = 45M). In this master solved notebook, every recurring question from 2018, 2019, 2020, and 2021 is solved with step-by-step algorithms, complete C/C++ source code, trace tables, and genuine visual SVG diagrams.
SECTION A • 3 MARKS EACH

Very Short Answer Questions & Core Definitions

CCSU Examination Blueprint: 5 Questions Compulsory • Total 15 Marks

Q1. What do you understand by Data Structure? State its classification.

🔥 Repeated: 2018, 2020 3 Marks
✍️ Comprehensive 3-Mark Solution:

A Data Structure is a programmatic way of storing, organizing, and managing data in computer memory so that operations (such as search, insertion, and deletion) can be performed efficiently.

Classification:

  • Primitive: Fundamental data types supported directly by hardware and compilers (e.g., int, char, float, pointer).
  • Non-Primitive: Structured data collections derived from primitive types:
    • Linear: Elements arranged sequentially in a 1-to-1 relationship (e.g., Arrays, Stacks, Queues, Linked Lists).
    • Non-Linear: Elements arranged hierarchically or arbitrarily in a 1-to-many or many-to-many relationship (e.g., Trees, Graphs).

Q2. What are AVL Trees? State the Balance Factor condition.

🔥 Repeated: 2018, 2021 3 Marks
✍️ Comprehensive 3-Mark Solution:

An AVL Tree (named after inventors G.M. Adelson-Velsky and E.M. Landis) is a height-balanced Binary Search Tree (BST) wherein the heights of the two child subtrees of any node differ by at most one.

$$ ext{Balance Factor (BF)} = ext{Height}( ext{Left Subtree}) - ext{Height}( ext{Right Subtree})$$

For an AVL tree to remain valid, every node must satisfy \( ext{BF} \in \{-1, 0, +1\}\). If insertion or deletion causes \( ext{BF} = \pm 2\), the tree is re-balanced via single rotations (LL, RR) or double rotations (LR, RL) to guarantee strictly \(O(\log n)\) search, insertion, and deletion times.

Q3. What is an Array? Explain its major practical limitations.

🔥 Repeated: 2018, 2019 3 Marks
✍️ Comprehensive 3-Mark Solution:

An Array is a linear, sequential collection of homogeneous data elements stored in contiguous memory locations, allowing instant direct access using index arithmetic: \( ext{Address}(A[i]) = ext{Base} + i imes w\).

Limitations:

  1. Fixed Static Size: Array dimension must be fixed at compile-time and cannot dynamically expand or shrink according to runtime demand.
  2. Costly Insertion & Deletion: Inserting or removing an element at position \(K\) requires shifting elements left or right, resulting in \(O(n)\) time overhead.
  3. Memory Fragmentation: Requires a single contiguous block of RAM, which may fail even if total free memory across fragments exceeds array size.

Q4. State four prominent real-world applications of Stacks.

🔥 Repeated: 2018, 2020, 2021 3 Marks
✍️ Comprehensive 3-Mark Solution:
  1. Expression Parsing & Evaluation: Converting Infix expressions to Postfix/Prefix and computing arithmetic expressions using a single-pass operand stack.
  2. Subroutine / Function Call Management: CPU call stack stores activation records (return address, local variables, parameters) for nested and recursive functions.
  3. Delimiters & Parenthesis Matching: Compilers check balanced brackets (), {}, [] in programming source code.
  4. Undo / Redo & Backtracking: Text editors use two stacks for Undo/Redo; web browsers maintain back/forward URL navigation stacks.

Q5. Define Circular Linked List and Chain.

🔥 Repeated: 2018 Examination 3 Marks
✍️ Comprehensive 3-Mark Solution:
  • Circular Linked List: A variation of a linked list in which the last node does not contain a NULL pointer; instead, its link field points back to the first node (head), forming a continuous circular loop. Traversal can begin from any node and loop infinitely.
  • Chain: A formal term used in data structures for a singly linked linear list where each node consists of a data field and a pointer pointing strictly to its linear successor, with the terminal node pointing to NULL.

Q6. What is the advantage of a Header Node in a Linked List?

🔥 Repeated: 2019 Examination 3 Marks
✍️ Comprehensive 3-Mark Solution:

A Header Node (or sentinel node) is a dummy node placed at the beginning of a linked list before the first actual data node.

  • Eliminates Edge Case Code: In standard lists, inserting or deleting the first node requires modifying the external head pointer. With a header node, the head pointer remains permanent, so insertion/deletion code at the beginning uses the exact same logic as at the middle.
  • Metadata Storage: The header node's data field can store list-wide attributes, such as total count of nodes, sum of elements, or creation date.

Q7. Define Stacks and Queues with an example of each.

🔥 Repeated: 2019 Examination 3 Marks
✍️ Comprehensive 3-Mark Solution:
  • Stack: A linear data structure that adheres to the LIFO (Last In First Out) principle. Insertion and deletion occur only at a single end termed TOP. Real-world example: A stack of dinner plates in a cafeteria; the plate placed last is washed first.
  • Queue: A linear data structure that follows the FIFO (First In First Out) rule. Elements are inserted at the REAR and deleted from the FRONT. Real-world example: People standing in line at a cinema ticket counter; the first person to arrive gets the ticket first.

Q8. How is a Binary Tree traversed in C language? State the three orders.

🔥 Repeated: 2019 Examination 3 Marks
✍️ Comprehensive 3-Mark Solution:

Binary tree traversal visits every node in the tree exactly once. In C, it is implemented cleanly via recursive pointer calls:

  1. Inorder (LNR): Traverse Left Subtree → Visit Root Node → Traverse Right Subtree. (Produces elements in sorted order for a BST).
  2. Preorder (NLR): Visit Root Node → Traverse Left Subtree → Traverse Right Subtree. (Used to create copies or prefix expressions).
  3. Postorder (LRN): Traverse Left Subtree → Traverse Right Subtree → Visit Root Node. (Used to delete trees or evaluate postfix expressions).

Q9. What is the basic concept of Insertion Sorting?

🔥 Repeated: 2019 Examination 3 Marks
✍️ Comprehensive 3-Mark Solution:

Insertion Sort works similarly to sorting playing cards in our hands. The array is virtually split into a sorted part and an unsorted part.

In each pass \(i\) (from \(1\) to \(n-1\)), the next element from the unsorted subarray is picked as key and compared backwards with elements in the sorted subarray. All elements greater than key are shifted right by one position, and key is placed into its correct sorted slot. Time Complexity: Best case \(O(n)\) (already sorted), Worst/Average case \(O(n^2)\).

Q10. Explain the primary operations performed on Data Structures.

🔥 Repeated: 2020 Examination 4 Marks
✍️ Comprehensive 4-Mark Solution:
  1. Traversing: Accessing each data element in the structure exactly once to process or display it.
  2. Insertion: Adding a new data element at a designated position in the structure.
  3. Deletion: Removing an existing element from the structure and freeing memory.
  4. Searching: Finding the location of a target element with a specified key value.
  5. Sorting: Arranging all elements in a logical ascending or descending sequence.
  6. Merging: Combining elements of two sorted structures into a single consolidated sorted structure.

Q11. How can we minimize Stack Overflow?

🔥 Repeated: 2020 Examination 4 Marks
✍️ Comprehensive 4-Mark Solution:

Stack Overflow occurs when an attempt is made to push an element onto a stack that has exhausted its memory capacity.

Techniques to Minimize Overflow:

  • Dynamic Linked List Implementation: Implement the stack using a linked list instead of a fixed array, allowing the stack to grow dynamically as long as system heap memory is available.
  • Dynamic Array Resizing: In array implementations, dynamically double the array size (using realloc in C or std::vector in C++) whenever the stack becomes full.
  • Avoid Unbounded Recursion: Convert deep recursion into iterative loops using explicit loops or guarantee strict termination base cases.
  • Two Stacks in One Array: Grow two stacks from opposite ends (0 and \(N-1\)) of a single shared array, avoiding overflow until the total memory is exhausted.

Q12. Write Prefix and Postfix form for: \(A + B imes (C - D) / (E - F)\)

🔥 Repeated: 2020 Examination 4 Marks
✍️ Step-by-Step Conversion:

1. Parentheses first: \((C - D)\) and \((E - F)\):

  • Postfix: \(CD-\) • Prefix: \(-CD\)
  • Postfix: \(EF-\) • Prefix: \(-EF\)

2. Multiplication: \(B imes (C - D)\):

  • Postfix: \(B(CD-)* \implies BCD-*\) • Prefix: \(*B(-CD) \implies *B-CD\)

3. Division: \([B imes (C - D)] / (E - F)\):

  • Postfix: \((BCD-*)(EF-)/ \implies BCD-*EF-/\) • Prefix: \(/*B-CD-EF\)

4. Addition: \(A + ext{Result}\):

Final Postfix: ABCD-*EF-/+

Final Prefix: +A/*B-CD-EF

Q13. Design a recursive factorial function using C/C++ language.

🔥 Repeated: 2020 Examination 4 Marks
✍️ C/C++ Source Code:
// Recursive Factorial Function
long long factorial(int n) {
    // Base Case: 0! = 1 and 1! = 1
    if (n <= 1) {
        return 1;
    }
    // Recursive Step: n! = n * (n-1)!
    return n * factorial(n - 1);
}

Time Complexity: \(O(n)\), Space Complexity: \(O(n)\) for call stack frames.

Q14. Explain the term Hashing and state common Hash Functions.

🔥 Repeated: 2018, 2020, 2021 3 / 7.5 Marks
✍️ Comprehensive Solution:

Hashing is a technique to map key values to specific slots in an array (Hash Table) to achieve average \(O(1)\) search, insertion, and deletion time without comparison.

Common Hash Functions:

  1. Division Method: \(h(k) = k \bmod m\), where \(m\) is table size (preferably prime).
  2. Mid-Square Method: Square the key \(k^2\) and extract the middle \(r\) digits.
  3. Folding Method: Divide the key into equal-sized pieces and sum them up.

Q15. What is a Deque? Distinguish Input-Restricted and Output-Restricted Deque.

🔥 Repeated: 2019, 2020, 2021 3 / 7.5 Marks
✍️ Comprehensive Solution:

A Deque (Double-Ended Queue) is a linear list allowing insertion and deletion at both ends (Front and Rear).

Feature Input-Restricted Deque Output-Restricted Deque
Insertion Only at one end (Rear) At both ends (Front and Rear)
Deletion At both ends (Front and Rear) Only at one end (Front)

Q16. What is Analysis of Algorithm? Explain Time and Space Complexity.

🔥 Repeated: 2021 Examination 7.5 Marks
✍️ Comprehensive Solution:

Analysis of Algorithm is the process of determining the amount of computational resources (time and storage) required by an algorithm to execute as a function of the input size \(n\).

  • Time Complexity: The total number of elementary operations or CPU cycles executed by the algorithm as input size increases, expressed using Asymptotic Notations: Big-O (\(O\)), Omega (\(\Omega\)), and Theta (\(\Theta\)).
  • Space Complexity: The amount of primary memory (RAM) consumed by the program during execution, consisting of: $$ ext{Total Space} = ext{Fixed Space (code + constants)} + ext{Variable Space (dynamic data + recursion stack)}$$

Q17. Explain the Principle of Recursion with its two essential components.

🔥 Repeated: 2021 Examination 7.5 Marks
✍️ Comprehensive Solution:

Recursion is a problem-solving technique wherein a function calls itself directly or indirectly to solve a smaller instance of the same problem.

Two Mandatory Components:

  1. Base Case (Anchor Condition): A terminating condition for which the function produces a direct result without making any further recursive calls. Without this, the program encounters an infinite recursion loop and crashes with Stack Overflow.
  2. Recursive Step (Inductive Step): The instruction that breaks down the original input and invokes the function with a strictly smaller or simpler parameter (e.g., \(n-1\)), ensuring the execution moves closer to the base case at every step.
SECTION B • 7.5 MARKS EACH

Algorithmic Procedures & Code Implementations

CCSU Examination Blueprint: Attempt Any 2 Out of 3 Questions • Total 15 Marks

Q1. Write the step-by-step algorithm to delete an element from a linear array at index \(K\).

🔥 Repeated: 2018 Examination 7.5 Marks
✍️ Step-by-Step 7.5-Mark Algorithm:

Algorithm: DELETE_ARRAY(LA, N, K, ITEM)

  1. [Check Underflow]: If \(N == 0\), Print "Array Underflow: No element to delete" and Exit.
  2. [Validate Range]: If \(K \lt 0\) or \(K \ge N\), Print "Error: Index out of range" and Exit.
  3. [Store Target Item]: Set ITEM = LA[K].
  4. [Shift Leftward]: Repeat for \(I = K\) to \(N - 2\):
        Set LA[I] = LA[I + 1].
    [End of loop]
  5. [Update Size]: Set \(N = N - 1\).
  6. [Exit]: Return ITEM.

Complexity: Best case \(O(1)\) when deleting last element (\(K = N-1\)). Worst case \(O(n)\) when deleting first element (\(K = 0\)).

Q2. Write an algorithm and its C syntax to insert an element at the \(K\)th position into a linear array.

🔥 Repeated: 2019 Examination 7.5 / 15 Marks
✍️ Algorithm & C Code:

Algorithm: INSERT_ARRAY(LA, N, MAX, K, ITEM)

  1. [Check Overflow]: If \(N \ge \text{MAX}\), Print "Array Overflow" and Exit.
  2. [Shift Rightward]: Repeat for \(I = N - 1\) down to \(K\):
        Set LA[I + 1] = LA[I].
    [End of loop]
  3. [Insert]: Set LA[K] = ITEM.
  4. [Increment]: Set \(N = N + 1\).
// C Implementation
void insertAtK(int arr[], int *n, int max_size, int k, int item) {
    if (*n >= max_size) {
        printf("Overflow!\\n");
        return;
    }
    for (int i = *n - 1; i >= k; i--) {
        arr[i + 1] = arr[i];
    }
    arr[k] = item;
    (*n)++;
}

Q3. Write a recursive C/C++ function to count the number of leaves in a Binary Tree.

🔥 Repeated: 2018 Examination 7.5 Marks
✍️ C++ Recursive Solution:
struct Node {
    int data;
    Node* left;
    Node* right;
};

// Returns total leaf nodes in binary tree
int countLeaves(Node* root) {
    // Base Case 1: Empty tree
    if (root == nullptr)
        return 0;
    
    // Base Case 2: Node is a leaf
    if (root->left == nullptr && root->right == nullptr)
        return 1;
        
    // Recursive Step
    return countLeaves(root->left) + countLeaves(root->right);
}

Time Complexity: \(O(n)\) visiting all nodes. Space Complexity: \(O(h)\) where \(h\) is tree height.

Q4. Write a function to reverse a stack using only standard Push and Pop operations (without auxiliary stack).

🔥 Repeated: 2018 Examination 7.5 Marks
✍️ Two Recursive Functions Solution:
#include <stack>
using namespace std;

// Helper: Inserts an element at the bottom of a stack
void insertAtBottom(stack<int>& s, int item) {
    if (s.empty()) {
        s.push(item);
        return;
    }
    int topItem = s.top();
    s.pop();
    insertAtBottom(s, item);
    s.push(topItem);
}

// Function to reverse the stack recursively
void reverseStack(stack<int>& s) {
    if (s.empty())
        return;
    int item = s.top();
    s.pop();
    reverseStack(s);
    insertAtBottom(s, item);
}

This utilizes the implicit call stack to store popped elements and places them sequentially at the bottom.

Q5. What is a Sparse Matrix? Explain its memory representation and derive the Lower Triangular 1D address formula.

🔥 Repeated: 2019, 2020 7.5 Marks
✍️ Complete 7.5-Mark Derivation:

A matrix is Sparse if the number of zero elements is substantially greater than the number of non-zero elements. Storing it as a standard 2D array \(A[N][N]\) wastes memory.

1. 3-Tuple Representation: Stored as a list of triplets: [Row, Col, Value].

2. Lower Triangular Matrix (LTM): \(A[i][j] = 0\) for \(i \lt j\). Total non-zero elements = \(\frac{N(N+1)}{2}\).

In Row-Major storage in a 1D array:

  • Number of elements in rows preceding row \(i\): \(1 + 2 + 3 + \dots + i = \frac{i(i+1)}{2}\).
  • Within row \(i\), column offset is \(j\) (for \(0 \le j \le i\)).
$$\text{1D Index} = \frac{i(i + 1)}{2} + j$$ $$\text{Memory Address} = \text{Base} + w \cdot \left[ \frac{i(i + 1)}{2} + j \right]$$

Q6. Explain Double-Ended Queue (Deque) operations with a suitable example.

🔥 Repeated: 2019, 2020, 2021 7.5 Marks
✍️ Deque Operations & Modulo Arithmetic:

Implemented circularly using an array of capacity \(M\):

  1. insertFront(item): front = (front - 1 + M) % M; arr[front] = item;
  2. insertRear(item): rear = (rear + 1) % M; arr[rear] = item;
  3. deleteFront(): Retrieve arr[front]; front = (front + 1) % M;
  4. deleteRear(): Retrieve arr[rear]; rear = (rear - 1 + M) % M;

All operations take strictly \(O(1)\) time without shifting elements.

Q7. Write an algorithm to delete the last node from a Singly Linked List.

🔥 Repeated: 2019 Examination 7.5 Marks
✍️ Algorithm:
  1. If HEAD == NULL, Print "Underflow: List Empty" and Return.
  2. If HEAD->next == NULL, Set TEMP = HEAD, HEAD = NULL, free(TEMP), and Return.
  3. Set PTR = HEAD.
  4. While PTR->next->next != NULL do:
        Set PTR = PTR->next.
    [End While]
  5. Set TEMP = PTR->next.
  6. Set PTR->next = NULL.
  7. Call free(TEMP) to release memory.

Q8. Write a C/C++ program to multiply two matrices \(A\) and \(B\).

🔥 Repeated: 2020 Examination 7.5 Marks
✍️ C++ Working Source Code:
#include <iostream>
using namespace std;

void multiplyMatrices(int A[10][10], int B[10][10], int C[10][10], int r1, int c1, int r2, int c2) {
    if (c1 != r2) {
        cout << "Matrix multiplication not possible! Columns of A must equal rows of B.\\n";
        return;
    }
    // Initialize resultant matrix to 0
    for (int i = 0; i < r1; i++) {
        for (int j = 0; j < c2; j++) {
            C[i][j] = 0;
            for (int k = 0; k < c1; k++) {
                C[i][j] += A[i][k] * B[k][j];
            }
        }
    }
}

Three nested loops yield Time Complexity \(O(r_1 \times c_1 \times c_2) \implies O(n^3)\) for square matrices.

Q9. Explain Priority Queue with an example of real-life application.

🔥 Repeated: 2018, 2019, 2020 7.5 Marks
✍️ Comprehensive 7.5-Mark Solution:

A Priority Queue is an abstract data type where each element has an associated priority. Elements are served based on priority: an element with higher priority is processed before an element with lower priority, regardless of arrival order.

  • Ascending Priority Queue: Smallest key has the highest priority (e.g., Shortest Job First).
  • Descending Priority Queue: Largest key has the highest priority.

Real-Life Applications: OS CPU Process Scheduling (higher priority system processes pre-empt lower priority background tasks), Hospital Emergency Rooms (triage priority for critical patients), Dijkstra's Shortest Path Algorithm, and Huffman Data Compression.

Q10. Write the procedure to delete an element from a Linked Queue.

🔥 Repeated: 2018 Examination 7.5 Marks
✍️ Linked Queue Dequeue Algorithm:
  1. [Check Underflow]: If FRONT == NULL, Print "Queue Underflow" and Return.
  2. [Point to Front Node]: Set TEMP = FRONT.
  3. [Retrieve Data]: Set ITEM = TEMP->data.
  4. [Advance Front]: Set FRONT = FRONT->next.
  5. [Check for Empty Queue]: If FRONT == NULL, then set REAR = NULL.
  6. [Free Memory]: Call free(TEMP).
  7. [Return]: Return ITEM. Time Complexity is \(O(1)\).
SECTION C • 15 MARKS EACH

Comprehensive Long Answer Solutions & Visual Diagrams

CCSU Examination Blueprint: Attempt Any 3 Out of 5 Questions • Total 45 Marks

Q1. Explain the Stack Evaluation Algorithm for Postfix expressions. Show the complete step-by-step stack status trace table for: 3, 1, +, 2, ^, 7, 4, -, 2, *, +, 5, - and ABC*DEF$/-G+H*-

🔥 Asked in 2018, 2019, 2020, 2021 (100% Guaranteed 15M) 15 Marks
✍️ Full 15-Mark Solution & Stack Trace:

Evaluation Algorithm:

  1. Scan the Postfix string from left to right, one token at a time.
  2. If the scanned token is an operand (number or letter), PUSH it onto the stack.
  3. If the token is an operator \(\odot\):
    • POP the top element \( o ext{Operand}_2\).
    • POP the next top element \( o ext{Operand}_1\).
    • Evaluate \( ext{Result} = ext{Operand}_1 \odot ext{Operand}_2\).
    • PUSH the \( ext{Result}\) back onto the stack.
  4. When scanning completes, the value remaining in the stack is the final result.

Trace Table for: 3, 1, +, 2, ^, 7, 4, -, 2, *, +, 5, -

Step Token Operation / Computation Stack Status [Bottom → Top]
13Push 3[3]
21Push 1[3, 1]
3+Pop 1, 3 → 3 + 1 = 4 → Push 4[4]
42Push 2[4, 2]
5^Pop 2, 4 → 4^2 = 16 → Push 16[16]
67Push 7[16, 7]
74Push 4[16, 7, 4]
8-Pop 4, 7 → 7 - 4 = 3 → Push 3[16, 3]
92Push 2[16, 3, 2]
10*Pop 2, 3 → 3 * 2 = 6 → Push 6[16, 6]
11+Pop 6, 16 → 16 + 6 = 22 → Push 22[22]
125Push 5[22, 5]
13-Pop 5, 22 → 22 - 5 = 17 → Push 17[17] (Final Result)

Final Computed Value: \(\mathbf{17}\)

Q2. Write programming code in C/C++ to create, insert, delete, and print in reverse order for a Singly Linked List. Distinguish Singly vs Doubly Linked List with diagram.

🔥 Repeated: 2018, 2020, 2021 (Core 15M) 15 / 22.5 Marks
✍️ Architectural Diagram & C++ Code:

Visual Diagram 1: Singly Linked List vs Doubly Linked List Architecture

1. Singly Linked List (Uni-directional): HEAD 10 20 30 NULL 2. Doubly Linked List (Bi-directional): HEAD NULL 10 20 30 NULL
#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* next;
    Node(int val) : data(val), next(nullptr) {}
};

// Function to print a linked list in reverse order (Dec 2018 Q12)
void printReverse(Node* head) {
    if (head == nullptr) return;
    printReverse(head->next); // Recurse on remaining list first
    cout << head->data << " "; // Print node after returning
}

Q3. Given Inorder = ABCEDFGHI and Preorder = ICBADEFGH. Reconstruct the unique Binary Tree, derive its Postorder Traversal, and state the algorithm.

🔥 Repeated: 2021 Examination 22.5 Marks
✍️ Full 22.5-Mark Solution & Vector Tree Diagram:

Subtree Derivation:

  1. Preorder[0] = I is the Root.
  2. In Inorder ABCEDFGHI, I is at index 8 (the very end). Hence, the Right Subtree is EMPTY, and all 8 nodes ABCEDFGH form the Left Subtree.
  3. Next Preorder symbol is C → Root of the left subtree. In Inorder, nodes left of C are AB, and right of C are EDFGH.
  4. For AB: Preorder is B, A → B is root, A is its left child.
  5. For EDFGH: Preorder is D, E, F, G, H → D is root, E is left child, F is right child; G is right child of F, and H is right child of G.

Visual Diagram 2: Reconstructed Binary Tree from Preorder & Inorder

I C B A D E F G H

Derived Postorder Traversal (LRN):

A → B → E → H → G → F → D → C → I

Q4. Explain BST Insertion and Deletion algorithms. Construct a Binary Search Tree (BST) for the numbers: 14, 15, 4, 9, 7, 18, 3, 5, 16, 20, 17

🔥 Repeated: 2019, 2020 (Core 15M) 15 Marks
✍️ Full 15-Mark Solution & Vector BST Diagram:

BST Property: For every node \(X\), all values in its left subtree are \(\lt X\), and all values in its right subtree are \(\gt X\).

Visual Diagram 3: Constructed Binary Search Tree

14 4 15 3 9 7 5 18 16 17 20

Q5. State properties of B-Trees. Construct a B-Tree of order 3 for following data: Jan, Feb, Mar, Apr, May, Jun, Jul, Aug, Sep, Oct, Nov, Dec

🔥 Repeated: 2018, 2020 (Core 15M) 15 Marks
✍️ Full 15-Mark Solution & B-Tree Multi-Key Diagram:

B-Tree of Order \(m = 3\) Rules:

  • Maximum keys per node = \(m - 1 = 2\). Maximum children = \(m = 3\).
  • Minimum keys per non-root node = \(\lceil m/2 ceil - 1 = 1\).
  • All leaves must be at the exact same level.
  • When inserting into a full 2-key node, it splits: the median (middle) key is promoted to the parent.

Visual Diagram 4: Final B-Tree of Order 3 for 12 Months

Jan Dec Jun Oct Apr Aug Feb Jul Mar May Nov Sep

Q6. Construct a Max-Heap for the given data: 95, 13, 12, 71, 96, 10, 62, 43, 35, 38. Show its 1D array representation and Heap Sort mechanism.

🔥 Repeated: 2019, 2020, 2021 (Core 15M) 15 Marks
✍️ Full Max-Heap Solution & Array Mapping:

Max-Heap Property: \( ext{A}[ ext{parent}(i)] \ge ext{A}[i]\) for all nodes \(i\).

Visual Diagram 5: Final Max-Heap Tree & 1D Sequential Array Mapping

96 95 62 71 38 10 12 43 35 13 Corresponding 1D Array: 96 95 62 71 38 10 12 43 35 13

Q7. Design a function CINSERT and CDELETE for static implementation of a Circular Queue. Illustrate with a circular ring diagram.

🔥 Repeated: 2020 Examination 15 Marks
✍️ Full C++ Code & Circular Ring Architecture:

Visual Diagram 6: Circular Queue Ring Architecture (Capacity = 8)

[0] Empty [1] Empty 10 ← FRONT (2) 20 30 40 REAR (5) → [6] Empty [7] Empty Modulo 8
#define MAX 8
int cqueue[MAX];
int front = -1, rear = -1;

// Function CINSERT
void cinsert(int val) {
    if ((front == 0 && rear == MAX - 1) || (front == (rear + 1) % MAX)) {
        cout << "Circular Queue Overflow!\n";
        return;
    }
    if (front == -1) { // First element
        front = rear = 0;
    } else {
        rear = (rear + 1) % MAX;
    }
    cqueue[rear] = val;
}

// Function CDELETE
int cdelete() {
    if (front == -1) {
        cout << "Circular Queue Underflow!\n";
        return -1;
    }
    int item = cqueue[front];
    if (front == rear) { // Last remaining element
        front = rear = -1;
    } else {
        front = (front + 1) % MAX;
    }
    return item;
}

Q8. Describe Hashing and various Hashing techniques in detail. Explain Open Addressing (Linear Probing) vs Separate Chaining with numeric example.

🔥 Repeated: 2018, 2019, 2020, 2021 15 Marks
✍️ Full 15-Mark Solution:

Collision: Occurs when two distinct keys \(k_1 eq k_2\) produce the same hash index: \(h(k_1) = h(k_2)\).

1. Open Addressing (Closed Hashing): All elements are stored directly inside the hash table array slots. When a collision occurs, alternative slots are probed systematically:

  • Linear Probing: \(h(k, i) = (h'(k) + i) \bmod m\). Simple but suffers from Primary Clustering.
  • Quadratic Probing: \(h(k, i) = (h'(k) + c_1 i + c_2 i^2) \bmod m\). Eliminates primary clustering.
  • Double Hashing: \(h(k, i) = (h_1(k) + i \cdot h_2(k)) \bmod m\). Best open addressing scheme.

2. Separate Chaining (Open Hashing): Each table slot is a header pointer to a linked list of records that hash to the same index. Infinite keys can be accommodated as long as RAM allows, completely eliminating primary clustering.

Q9. (a) Perform Quick Sort on: 66, 35, 48, 55, 62, 77, 25, 38, 18, 40, 30, 20 (b) Derive Time Complexity of Bubble Sort.

🔥 Repeated: 2018, 2020 15 Marks
✍️ Step-by-Step Solution:

(a) Quick Sort Partition Trace: Pivot chosen as first element \( ext{Pivot} = 66\). Pointers low scans right for element \(> 66\) (finds 77), and high scans left for element \(\le 66\) (finds 20). Swap 77 and 20. Continue until pointers cross, then swap pivot into place. Partition divides array into: \(\{ ext{Elements } \le 66\}\) • \(\mathbf{66}\) • \(\{ ext{Elements } > 66\}\).

(b) Bubble Sort Time Complexity Derivation:

  • Pass 1: \(n - 1\) comparisons
  • Pass 2: \(n - 2\) comparisons
  • Pass \(n-1\): \(1\) comparison
$$ ext{Total Comparisons} = (n - 1) + (n - 2) + \dots + 1 = \frac{n(n - 1)}{2} = \frac{n^2 - n}{2} \implies \mathbf{O(n^2)}$$

With an early termination flag checking if any swap occurred, Best-Case time complexity drops to \(\mathbf{O(n)}\).

Q10. Differentiate between Linear Search and Binary Search. Give complete code and comparative analysis.

🔥 Repeated: 2020, 2021 15 / 22.5 Marks
✍️ Comparison Table & Code:
Parameter Linear Search Binary Search
Pre-condition None; works on unsorted arrays Array MUST be sorted
Worst Time Complexity \(O(n)\) \(O(\log n)\)
Approach Sequential element-by-element scan Divide & conquer (halving search interval)
Data Structure Support Arrays and Linked Lists Arrays only (requires \(O(1)\) random access)

Q11. What is a Threaded Binary Tree? Explain with a diagram how NULL pointers are utilized. Why is Doubly Linked List better than Singly Linked List?

🔥 Repeated: 2021 Examination 22.5 Marks
✍️ Full 22.5-Mark Solution & Threaded Tree Diagram:

In a standard binary tree with \(n\) nodes, exactly \(n + 1\) child pointers are NULL, wasting more than half of the pointer storage. A Threaded Binary Tree reclaims these wasted NULL pointers to store direct links (threads) to the node's Inorder Predecessor and Inorder Successor, allowing stack-free, non-recursive tree traversals.

Visual Diagram 7: Two-Way Threaded Binary Tree (Dashed Arrows = Threads)

30 20 40 10 25

Why Doubly Linked List is Superior to Singly Linked List:

  1. Bi-directional Traversal: Nodes can be traversed in both forward (Next) and backward (Prev) directions.
  2. Constant Time Deletion \(O(1)\): To delete a node given its pointer, a doubly linked list can immediately access its predecessor via node->prev without scanning from head, completing deletion in \(O(1)\) instead of \(O(n)\).
  3. Easier Node Insertion: Inserting before a given node is straightforward with prev pointer.