Data Structure Using C & C++ Important Questions BCA 3rd Semester CCSU

1. What do you understand by Data Structure? Explain Operations.
A data structure is a way of organizing and storing data so that it can be accessed and modified efficiently. Examples include arrays, linked lists, stacks, queues, trees, graphs, and hash tables.
Operations performed on data structures include:

• Traversal: Accessing each element of the data structure.
• Insertion: Adding an element to the data structure.
• Deletion: Removing an element from the data structure.
• Searching: Finding an element within the data structure.
• Sorting: Arranging the elements in a specific order.
• Merging: Combining two data structures into one.

---

2. Define Stacks and Queues with an example.

• Stack: A stack is a linear data structure that follows the Last In, First Out (LIFO) principle. Example: A stack of plates, where the last plate added is the first one to be removed.

  • Operations: Push (add element), Pop (remove element), Peek (view top element).
  • Example:

    Stack: [10, 20, 30]
    Push(40): [10, 20, 30, 40]
    Pop(): [10, 20, 30]
    

• Queue: A queue is a linear data structure that follows the First In, First Out (FIFO) principle. Example: A line at a ticket counter, where the first person in line is served first.

  • Operations: Enqueue (add element), Dequeue (remove element), Front (view first element).
  • Example:

    Queue: [10, 20, 30]
    Enqueue(40): [10, 20, 30, 40]
    Dequeue(): [20, 30, 40]
    

---

3. Explain the term Hashing.
Hashing is a technique used to map data to a fixed-size value, called a hash code or hash value, using a hash function. It is commonly used in hash tables to store and retrieve data efficiently.
Example: Storing student IDs with their names, where the student ID is hashed to determine its storage location.
Hashing ensures fast lookup, insertion, and deletion operations.

---

4. Explain Priority Queue in brief.
A priority queue is a type of queue where each element is associated with a priority. The element with the highest (or lowest, depending on the implementation) priority is dequeued first, regardless of the order in which it was enqueued.
Example: In a hospital emergency room, patients with critical conditions are treated first, regardless of their arrival time.

---

5. Explain B-tree.
A B-tree is a self-balancing search tree used for storing large amounts of data in a sorted order for efficient searching, insertion, and deletion.

• It is commonly used in databases and file systems.
• Properties:
  • All leaf nodes are at the same level.
  • A B-tree node can have multiple keys and children.
  • It ensures a balanced structure, leading to O(log n) time complexity for operations.

---

6. Where can we use Stack? Give applications of stack.
Stack Applications:

• Function Call Management: Storing function calls and recursion information.
• Expression Evaluation: Evaluating postfix or infix expressions.
• Undo/Redo Operations: In text editors and IDEs.
• Browser History: Backtracking the browsing history.
• Parsing: In compilers for syntax checking.
• DFS (Depth-First Search): In graph algorithms.

---

7. What is a linked list?
A linked list is a linear data structure where elements (called nodes) are connected using pointers. Each node contains two parts:

1. Data: The value stored in the node.
2. Next: A pointer/reference to the next node in the sequence.
   Types: Singly Linked List, Doubly Linked List, Circular Linked List.
   Example:

Node 1 -> Node 2 -> Node 3 -> NULL

---

8. Write the limitations of arrays.

• Fixed Size: Array size is fixed and cannot be changed dynamically.
• Contiguous Memory Requirement: Requires a continuous block of memory.
• Insertion/Deletion Overhead: Adding or removing elements can be time-consuming as elements may need to be shifted.
• Wastage of Memory: If not fully utilized, it can lead to memory wastage.
• Inefficient Search: Searching for an element (unless sorted) requires O(n) time in a linear array.

---

9. Explain how two-dimensional array is stored in memory.
A two-dimensional array is stored in memory in either:

• Row-Major Order: Row by row. Elements of the first row are stored, followed by elements of the second row, and so on.
• Column-Major Order: Column by column. Elements of the first column are stored, followed by elements of the second column, and so on.
  Example (Row-Major for a 2x3 array):

Array: [[1, 2, 3], [4, 5, 6]]
Memory: 1, 2, 3, 4, 5, 6

---

10. What do you mean by Sparse arrays?
A sparse array is an array where most of the elements are zeros or do not hold meaningful data.
To save memory, only non-zero elements and their positions are stored.
Example:
Array:

0  0  3  
0  0  0  
5  0  0  

Sparse representation: [(0, 2, 3), (2, 0, 5)]

---

Here are the detailed answers for your questions. Each answer is detailed and formatted to provide comprehensive understanding.

---

11. Explain D-Queue & Priority Queue with a suitable example.

D-Queue (Deque)

• A deque (double-ended queue) is a linear data structure that allows insertion and deletion at both ends (front and rear).
• It can be used as both a stack and a queue.
• There are two types:
  1. Input-restricted deque: Insertion at only one end.
  2. Output-restricted deque: Deletion at only one end.

Example:

Deque: []
InsertRear(10): [10]
InsertRear(20): [10, 20]
InsertFront(5): [5, 10, 20]
DeleteFront(): [10, 20]
DeleteRear(): [10]

Priority Queue

• A priority queue is a special type of queue where elements are dequeued based on priority instead of the order of insertion.
• Elements with higher priority are dequeued first.
• Implementations: Binary heap, Fibonacci heap, or balanced binary search tree.

Example (Using max-priority queue):

Queue: [(priority 1, task A), (priority 3, task B), (priority 2, task C)]
After dequeue: [(priority 1, task A), (priority 2, task C)]

---

12. Explain Heap and Sort with suitable example.

Heap

• A heap is a complete binary tree where each parent node satisfies the heap property:
  • Max-Heap: Parent node is greater than or equal to its children.
  • Min-Heap: Parent node is less than or equal to its children.

Example (Max-Heap):

          10
        /    \
       5      8
      / \    / 
     2   4  7  

Heap Sort

• Heap sort uses a heap to sort elements in ascending or descending order.
• Steps:
  1. Build a heap from the given data.
  2. Extract the root (largest or smallest element) repeatedly and adjust the heap.

Example:
Input: [4, 10, 3, 5, 1]

• Build max-heap: [10, 5, 3, 4, 1]
• Sorted: [1, 3, 4, 5, 10]

---

13. Write a program of multidimensional array (m*n).

#include <stdio.h>
int main() {
    int m, n;
    printf("Enter number of rows and columns: ");
    scanf("%d %d", &m, &n);
    
    int arr[m][n];
    printf("Enter elements of the array:\n");
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &arr[i][j]);
        }
    }
    
    printf("The 2D array is:\n");
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            printf("%d ", arr[i][j]);
        }
        printf("\n");
    }
    return 0;
}

---

14. Write a recursive function to count the number of leaves in a binary tree.

struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

int countLeaves(struct Node* root) {
    if (root == NULL)
        return 0;
    if (root->left == NULL && root->right == NULL)
        return 1;
    return countLeaves(root->left) + countLeaves(root->right);
}

---

15. Write short notes on:

(a) Collision Resolution Techniques:

• In hashing, collisions occur when two keys hash to the same index.
• Techniques:
  • Chaining: Use a linked list at each index to store multiple elements.
  • Open Addressing: Use probing (linear, quadratic, or double hashing) to find the next empty slot.

(b) B-Tree:

• A self-balancing tree for efficient search, insertion, and deletion.
• Used in databases and file systems.

(c) Heap Sort:

• A sorting algorithm that uses a binary heap.
• Time complexity: O(n log n).

(d) Applications of Binary Search Tree:

• Searching, dynamic sets, and sorting.
• Used in database indexing and priority scheduling.

(e) Hashing Techniques:

• Direct Addressing: Simple hash function like key % size.
• Chaining and Probing for collision resolution.

---

16. (a) How to delete an element from a linked queue? Write Procedure.

struct Node {
    int data;
    struct Node* next;
};

struct Node* front = NULL;
struct Node* rear = NULL;

void deleteFromQueue() {
    if (front == NULL) {
        printf("Queue is empty.\n");
        return;
    }
    struct Node* temp = front;
    front = front->next;
    free(temp);
}

---

(b) Find the time complexity of Bubble Sort Algorithm.

• Best Case: O(n) (when the array is already sorted).
• Worst Case: O(n²) (when the array is sorted in reverse order).

---

17. Implement Singly Linked List using Dynamic Memory Allocation.

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node* next;
};

struct Node* head = NULL;

void insertAtEnd(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = NULL;

    if (head == NULL) {
        head = newNode;
        return;
    }

    struct Node* temp = head;
    while (temp->next != NULL) {
        temp = temp->next;
    }
    temp->next = newNode;
}

void displayList() {
    struct Node* temp = head;
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

---

18. Algorithm and C syntax to insert an element at the Kth position into a linear array.

Algorithm:

1. Shift all elements from index k onward to the right by one position.
2. Insert the new element at index k.

C Code:

void insertAtK(int arr[], int* n, int k, int element) {
    for (int i = *n; i > k; i--) {
        arr[i] = arr[i - 1];
    }
    arr[k] = element;
    (*n)++;
}

---

19. Construct a Binary Tree from Traversals.

Inorder: D, B, E, A, F, C
Preorder: A, B, D, E, C, F

Steps:

• Root is A (first element in preorder).
• Left subtree: Inorder (D, B, E) and Preorder (B, D, E).
• Right subtree: Inorder (F, C) and Preorder (C, F).

Tree:

          A
       /     \
      B       C
    /   \        \
   D     E        F

---

20. What is Threaded Binary Tree? Explain with a suitable example.

• A threaded binary tree is a binary tree in which NULL pointers are replaced with pointers to the inorder predecessor or successor.
• This allows efficient traversal without using a stack or recursion.

Example:

          10
        /    \
       5      15
    Inorder threads point to 10 and 15.

---

NOTE : 

• This is an expected question answer which you have appeared in most of the exams. You will be able to study chapterwise most important topics as per your knowledge and will not be afraid of giving the paper. This is a great tool to improve your preparation.
• The answers which are given in short cut or less words, here you can write and read them according to your understanding.