Data Structures Assignment: A Comprehensive Guide

In the third-semester course on Computer Science & Technology at Siliguri Govt. Polytechnic, students dive into the fundamental concepts of data structures. This guide addresses each question from the assignment to provide clear, concise answers and program solutions, helping to solidify students’ understanding of these core concepts.

1. What is a data structure?

• Answer: A data structure is a specialized format for organizing, managing, and storing data so that it can be accessed and modified efficiently. Common types include arrays, linked lists, stacks, queues, and trees. Each type of data structure is suited to specific types of operations, making it crucial to choose the appropriate structure for a given application.

2. What is a linked list?

• Answer: A linked list is a linear data structure where elements, called nodes, are stored in sequence but not in contiguous memory locations. Each node contains the data and a pointer to the next node, allowing dynamic memory allocation and efficient insertion and deletion of elements. Types of linked lists include singly linked lists, doubly linked lists, and circular linked lists.

3. Write a program in C to sort the following array using selection sort technique:

Array: 23, 56, 21, 77, 36, 18, 66, 44

   #include <stdio.h>

   void selectionSort(int arr[], int n) {
       for (int i = 0; i < n - 1; i++) {
           int minIndex = i;
           for (int j = i + 1; j < n; j++) {
               if (arr[j] < arr[minIndex]) {
                   minIndex = j;
               }
           }
           // Swap the found minimum element with the first element
           int temp = arr[minIndex];
           arr[minIndex] = arr[i];
           arr[i] = temp;
       }
   }

   int main() {
       int arr[] = {23, 56, 21, 77, 36, 18, 66, 44};
       int n = sizeof(arr) / sizeof(arr[0]);

       selectionSort(arr, n);

       printf("Sorted array: ");
       for (int i = 0; i < n; i++) {
           printf("%d ", arr[i]);
       }
       return 0;
   }

4. Write a program in C to search for 15 in the following array using linear search technique:

Array: 20, 45, 35, 25, 15, 75

   #include <stdio.h>

   int linearSearch(int arr[], int n, int x) {
       for (int i = 0; i < n; i++) {
           if (arr[i] == x) {
               return i; // Return the index where `x` is found
           }
       }
       return -1; // Return -1 if `x` is not found
   }

   int main() {
       int arr[] = {20, 45, 35, 25, 15, 75};
       int n = sizeof(arr) / sizeof(arr[0]);
       int x = 15;

       int result = linearSearch(arr, n, x);
       if (result != -1) {
           printf("Element %d found at index %d.\n", x, result);
       } else {
           printf("Element %d not found.\n", x);
       }
       return 0;
   }

5. Write a program in C to create a singly linked list of 5 elements, then insert two new elements: one in the front and one in the middle of the list.

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

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

   struct Node* createNode(int data) {
       struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
       newNode->data = data;
       newNode->next = NULL;
       return newNode;
   }

   void insertFront(struct Node** head, int data) {
       struct Node* newNode = createNode(data);
       newNode->next = *head;
       *head = newNode;
   }

   void insertMiddle(struct Node* head, int data, int position) {
       struct Node* temp = head;
       for (int i = 1; i < position - 1 && temp != NULL; i++) {
           temp = temp->next;
       }
       if (temp != NULL) {
           struct Node* newNode = createNode(data);
           newNode->next = temp->next;
           temp->next = newNode;
       }
   }

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

   int main() {
       struct Node* head = NULL;
       // Creating the initial list
       insertFront(&head, 50);
       insertFront(&head, 40);
       insertFront(&head, 30);
       insertFront(&head, 20);
       insertFront(&head, 10);

       printf("Original List: ");
       printList(head);

       // Insert at front
       insertFront(&head, 5);

       // Insert in the middle (position 4 for this example)
       insertMiddle(head, 25, 4);

       printf("Modified List: ");
       printList(head);
       return 0;
   }

6. Which is the best case for applying binary search algorithms?

• Answer: The best case for applying a binary search algorithm is when the dataset is sorted in ascending or descending order. Binary search only works efficiently on sorted data, as it repeatedly divides the search interval in half, allowing rapid location of the target value.

7. In what areas are data structures applied?

• Answer: Data structures are widely used in various areas of computer science, including:

  • Operating Systems: Process scheduling, memory management

  • Database Management: Indexing, caching

  • Networking: Routers use data structures for efficient routing

  • AI and Machine Learning: Efficient data handling

  • Graphics and Gaming: Real-time rendering, spatial partitioning

8. Is a linked list a linear or non-linear data structure? Explain.

• Answer: A linked list is considered a linear data structure because its elements are arranged in a sequential order, where each node points to the next node in the sequence. Although memory locations may be scattered, the logical structure remains linear, enabling sequential traversal.

9. What is the difference between an array and a linked list? Explain with examples.

• Answer:

  • Array: Elements are stored in contiguous memory locations, allowing random access using indices. Example: int arr[5] = {10, 20, 30, 40, 50};

  • Linked List: Elements are stored in nodes with each node containing data and a reference to the next node, providing dynamic memory usage and easy insertion/deletion. Example: A linked list storing values 10 -> 20 -> 30 -> NULL.

10. (a) What is sorting? Give Examples. (b) Mention different types of sorting.

• Answer:

  • (a) Sorting is the process of arranging data in a specified order, typically ascending or descending. Example: Sorting the array [3, 1, 4, 2] in ascending order results in [1, 2, 3, 4].

  • (b) Types of sorting include:

    • Bubble Sort

    • Selection Sort

    • Insertion Sort

    • Merge Sort

    • Quick Sort

    • Heap Sort