BCA PAPER CODE BCAC302 SEM -3 [2025]

 

MAULANA ABUL KALAM AZAD UNIVERSITY OF TECHNOLOGY, WEST BENGAL

Paper Code: BCAC302
Data Structure through C
UPID: 3000071

Time Allotted: 3 Hours
Full Marks: 70

The figures in the margin indicate full marks.
Candidates are required to give their answers in their own words as far as practicable.

---

Group-A (Very Short Answer Type Questions)

Answer any ten of the following: (1 × 10 = 10)

1. Prerequisite for Binary Search: The array must be sorted.

2. Hashing: A technique to map data to fixed-size tables using a hash function.

3. malloc() Function: Allocates memory dynamically (e.g., int *ptr = (int*)malloc(5 * sizeof(int));).

4. peek() in Stack: Returns the top element without removing it.

5. Circular Singly Linked List: The last node points back to the first node.

6. Recursive Function: A function that calls itself (e.g., factorial calculation).

7. Height of Binary Tree: Longest path from root to a leaf node.

8. Insertion Sort on Sorted Array: Runs in O(n) time (best case).

9. Collision Resolution Technique: Chaining (using linked lists) or Open Addressing (linear probing).

10. Stack Application in Parsing: Used for syntax checking (e.g., parenthesis matching).

11. Stack via Linked List: Implement push() and pop() using node insertions/deletions at the head.

12. Time Complexity for Insertion at Linked List Head: O(1).

---

Group-B (Short Answer Type Questions)

Answer any three of the following: (5 × 3 = 15)

2. Binary Tree vs. Complete Binary Tree

• Binary Tree: Each node has ≤ 2 children.

• Complete Binary Tree: All levels are fully filled except possibly the last, which is left-filled.

3. Quick Sort Algorithm

1. Choose a pivot (e.g., last element).

2. Partition the array into elements < pivot and > pivot.

3. Recursively sort the sub-arrays.

   c

   Copy

   Download

   void quickSort(int arr[], int low, int high) {
       if (low < high) {
           int pi = partition(arr, low, high);
           quickSort(arr, low, pi - 1);
           quickSort(arr, pi + 1, high);
       }
   }

4. Mean Square Method in Hashing

• Technique: Squares the key, extracts middle digits as the hash.

• Advantages: Uniform distribution.

• Disadvantages: Computationally heavy.

5. Self-Referential Pointer & Student Structure

c

Copy

Download

struct Student {
    int rollNo;
    char name[50];
    struct Student *next; // Self-referential pointer
};

6. Sparse Matrix

• Definition: A matrix with mostly zero elements.

• Applications: Image processing, graph algorithms.

---

Group-C (Long Answer Type Questions)

Answer any three of the following: (15 × 3 = 45)

7. Stack Operations & Multidimensional Array

(a) Stack Insertion (push()):

c

Copy

Download

void push(int stack[], int *top, int item, int size) {
    if (*top == size - 1) printf("Stack Overflow!");
    else stack[++(*top)] = item;
}

(b) Multidimensional Array Storage:

c

Copy

Download

int matrix[3][3] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};

(c) Sparse Matrix Representation:

c

Copy

Download

struct SparseMatrix {
    int row, col, value;
};

8. Hashing Collisions & Rehashing

(a) Collision Types:

• Primary: Two keys hash to the same slot.

• Secondary: Clustering due to probing.
  (b) Rehashing Advantages:

• Reduces clustering.

• Hash Function Choice: Should be uniform (e.g., division method).

9. Recursion & Binary Search

(a) Tail Recursion Example (Factorial):

c

Copy

Download

int factorial(int n, int acc) {
    if (n == 0) return acc;
    return factorial(n - 1, n * acc);
}

(b) Recursive Binary Search:

c

Copy

Download

int binarySearch(int arr[], int l, int r, int x) {
    if (r >= l) {
        int mid = l + (r - l) / 2;
        if (arr[mid] == x) return mid;
        if (arr[mid] > x) return binarySearch(arr, l, mid - 1, x);
        return binarySearch(arr, mid + 1, r, x);
    }
    return -1;
}

(c) Tower of Hanoi Algorithm:

c

Copy

Download

void towerOfHanoi(int n, char from, char to, char aux) {
    if (n == 1) printf("Move disk 1 from %c to %c\n", from, to);
    else {
        towerOfHanoi(n - 1, from, aux, to);
        printf("Move disk %d from %c to %c\n", n, from, to);
        towerOfHanoi(n - 1, aux, to, from);
    }
}

10. Threaded Binary Tree

(a) Definition: Uses NULL pointers to point to in-order predecessors/successors.
(b) Advantages:

• Faster in-order traversal.

• Disadvantages: Complex implementation.
  (c) Example Construction:

• Data: P, R, G, T, H, K, A, Z, J, V, W, M.

11. AVL Tree

(a) Height-Balanced Tree:

• Balance Factor: height(left subtree) - height(right subtree) (must be -1, 0, or 1).
  (b) AVL Tree Construction:

• Insertions: 10, 20 (LL rotation), 30 (RR rotation), etc.

• Rotation Types: LL, RR, LR, RL.

*************************End of Paper*********************************************

Solutions

********************************************************************************

Group-A (Very Short Answer Type Questions)

Solutions (Any 10):

1. Binary Search Prerequisite

   • Array must be sorted (ascending/descending order).

2. Hashing Definition

   • Technique to map data to fixed-size tables using a hash function (e.g., key % table_size).

3. malloc() Function

   • Allocates memory dynamically:

     c

     Copy

     Download

     int *arr = (int*)malloc(5 * sizeof(int)); // Allocates array of 5 integers

4. peek() in Stack

   • Returns the top element without removal:

     c

     Copy

     Download

     int peek(int stack[], int top) { return stack[top]; }

5. Circular Singly Linked List

   • Last node's next points to the head node (forms a loop).

6. Recursive Function

   • A function that calls itself (e.g., factorial):

     c

     Copy

     Download

     int factorial(int n) { return (n <= 1) ? 1 : n * factorial(n-1); }

7. Height of Binary Tree

   • Longest path from root to leaf (e.g., height = 3 for a tree with 3 levels).

8. Insertion Sort on Sorted Array

   • Best-case time complexity: O(n) (only compares elements without swaps).

9. Collision Resolution Technique

   • Chaining: Store collided elements in a linked list at the same hash index.

   • Open Addressing: Find next available slot via probing (linear/quadratic).

10. Stack Application in Parsing

    • Used for parenthesis matching (e.g., checking ({[]}) validity).

11. Stack via Linked List

    • Push: Insert at head.

    • Pop: Delete from head.

    • Time complexity: O(1) for both operations.

12. Time Complexity for Insertion at Linked List Head

    • O(1) (directly update head pointer).

---

Group-B (Short Answer Type Questions)

Solutions (Any 3):

1. Binary Tree vs. Complete Binary Tree

Feature	Binary Tree	Complete Binary Tree
Structure	Each node has ≤ 2 children	All levels filled except last (left-filled)
Example	Any tree with 0-2 children	Heap data structure

2. Quick Sort Algorithm

c

Copy

Download

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = (low - 1);
    for (int j = low; j <= high - 1; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

• Time Complexity: O(n log n) average, O(n²) worst-case.

3. Mean Square Method in Hashing

• Steps:

  1. Square the key (e.g., key = 25 → 625).

  2. Extract middle digits (e.g., 62 or 25).

• Advantage: Uniform distribution.

• Disadvantage: Computationally expensive.

4. Self-Referential Pointer & Student Structure

c

Copy

Download

struct Student {
    int rollNo;
    char name[50];
    struct Student *next; // Points to another Student
};

5. Sparse Matrix

• Definition: Matrix where most elements are zero.

• Applications:

  • Image compression (e.g., JPEG).

  • Graph adjacency matrices.

---

Group-C (Long Answer Type Questions)

Solutions (Any 3):

1. Stack Operations & Multidimensional Array

(a) Stack Insertion (push):

c

Copy

Download

void push(int stack[], int *top, int item, int size) {
    if (*top == size - 1) printf("Stack Overflow!");
    else stack[++(*top)] = item;
}

(b) 2D Array Storage:

c

Copy

Download

int matrix[2][3] = {{1, 2, 3}, {4, 5, 6}};

(c) Sparse Matrix Representation:

c

Copy

Download

struct SparseMatrix {
    int row, col, value;
} reps[100]; // Stores non-zero elements

2. Hashing Collisions & Rehashing

(a) Collision Types:

• Primary: Two keys hash to the same slot.

• Secondary: Clustering due to probing (e.g., linear probing).

(b) Rehashing:

• Advantages: Reduces clustering, improves load factor.

• Hash Function Choice: Should minimize collisions (e.g., prime number modulus).

3. Recursion & Binary Search

(a) Tail Recursion (Factorial):

c

Copy

Download

int factorial(int n, int acc) {
    if (n == 0) return acc;
    return factorial(n - 1, n * acc);
}

(b) Recursive Binary Search:

c

Copy

Download

int binarySearch(int arr[], int l, int r, int x) {
    if (r >= l) {
        int mid = l + (r - l) / 2;
        if (arr[mid] == x) return mid;
        if (arr[mid] > x) return binarySearch(arr, l, mid - 1, x);
        return binarySearch(arr, mid + 1, r, x);
    }
    return -1;
}

(c) Tower of Hanoi:

c

Copy

Download

void towerOfHanoi(int n, char from, char to, char aux) {
    if (n == 1) printf("Move disk 1 from %c to %c\n", from, to);
    else {
        towerOfHanoi(n - 1, from, aux, to);
        printf("Move disk %d from %c to %c\n", n, from, to);
        towerOfHanoi(n - 1, aux, to, from);
    }
}

4. AVL Tree Construction

(a) Balance Factor:

• balance = height(left) - height(right) (must be -1, 0, or 1).

(b) AVL Tree Example:

• Insertions: 10, 20 (no rotation), 30 (RR rotation), 8 (no rotation), 7 (LL rotation), etc.

• Rotation Types:

• LL: Right rotation.

• RR: Left rotation.

• LR: Left-right rotation.

• RL: Right-left rotation.

Thanks

SK Institute