Core Data Structures and Sorting Algorithms with C Examples

Posted on Mar 2, 2026 in Computers

(a) List the various operations performed on Data Structures

Traversal → Accessing each data element once. Insertion → Adding an element at a specific position. Deletion → Removing an element from a structure. Searching → Finding the location of an element. Sorting → Arranging elements in ascending or descending order. Merging → Combining two structures into one. Updating → Modifying existing data.

(f) Sort using Insertion Sort

Given: 22, 36, 6, 79, 26, 45, 75

Stepwise Sorting:

[22] 36 6 79 26 45 75
22 [36] 6 79 26 45 75
6 22 36 79 26 45 75
6 22 36 [79] 26 45 75
6 22 26 36 79 45 75
6 22 26 36 45 79 75
6 22 26 36 45 75 79  final 6, 22, 26, 36, 45, 75, 79

C Program: Delete an Element from Array (version 1)

#include <stdio.h>
int main() {
    int arr[100], n, pos, i;
    printf("Enter size: ");
    scanf("%d", &n);
    printf("Enter elements: ");
    for(i = 0; i < n; i++)
        scanf("%d", &arr[i]);

    printf("Enter position to delete: ");
    scanf("%d", &pos);

    printf("Deleted element: %d\n", arr[pos]);
    for(i = pos; i < n-1; i++)
        arr[i] = arr[i+1];

    n--;
    printf("New array: ");
    for(i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\nDeleted index: %d\n", pos);
    return 0;
}

C Program to Delete an Element from Array (duplicate)

#include <stdio.h>
int main() {
    int arr[100], n, pos, i;
    printf("Enter size: ");
    scanf("%d", &n);
    printf("Enter elements: ");
    for(i = 0; i < n; i++)
        scanf("%d", &arr[i]);

    printf("Enter position to delete: ");
    scanf("%d", &pos);

    printf("Deleted element: %d\n", arr[pos]);
    for(i = pos; i < n-1; i++)
        arr[i] = arr[i+1];

    n--;
    printf("New array: ");
    for(i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\nDeleted index: %d\n", pos);
    return 0;
}

(c) Applications of Stack — Push & Pop

Applications:

  • Expression evaluation (postfix, prefix).
  • Undo/Redo in editors.
  • Backtracking algorithms.
  • Function call management (call stack).
  • Browser history navigation.

Push Operation: Insert element at top.

stack[++top] = item;

Pop Operation: Remove element from top.

item = stack[top--];

Adjacency Matrix and Directed Edges

Matrix (rows/cols ordered v₀ v₁ v₂ v₃ v₄):

Adjacency matrix A:

v₀v₁v₂v₃v₄
A[0]01010
A[1]00000
A[2]01011
A[3]11000
A[4]00000

Edges (directed):
v₀→v₁, v₀→v₃
v₁ → (none)
v₂→v₁, v₂→v₃, v₂→v₄
v₃→v₀, v₃→v₁
v₄ → (none)

(a) Out-degree (row sum) & In-degree (column sum)

VertexOut-degIn-deg
v₀21
v₁03
v₂30
v₃22
v₄01

(b) Path / Reachability Matrix

Reachability matrix R (Warshall; 1 if there is a path of length ≥ 1):

v₀v₁v₂v₃v₄
R[0]11010
R[1]00000
R[2]11011
R[3]11010
R[4]00000

(Notice v₀→v₀ and v₃→v₃ via the cycle v₀ ↔ v₃.)

(c) Strongly connected?

No. v₁ (and v₄) cannot reach any other vertex.

(d) Cyclic?

Yes. There is a 2-cycle v₀→v₃→v₀ (and thus self-reachability for v₀ and v₃).

Q3 (Option-1): AVL tree idea and balancing

  • AVL: Height-balanced BST with |bf| ≤ 1 at every node, where bf = height(left) − height(right).

  • Rebalancing after insert/delete:

    • LL: Rotate right.

    • RR: Rotate left.

    • LR: Left rotate child, then right rotate node.

    • RL: Right rotate child, then left rotate node.

  • Complexities: Search / Insert / Delete O(log n); height ≤ 1.44 log2(n+2) − 0.328.

q4: Initialize & print a 2-D array at run time

#include <stdio.h>
int main(){
    int r, c, i, j; scanf("%d%d", &r, &c);
    int a[r][c];
    for(i = 0; i < r; i++) for(j = 0; j < c; j++) scanf("%d", &a[i][j]);
    for(i = 0; i < r; i++){
        for(j = 0; j < c; j++) printf("%d ", a[i][j]);
        printf("\n");
    }
    return 0;
}

.5 Bubble sort (or) create three nodes

Bubble sort program

#include <stdio.h>
int main(){
    int n, i, j, temp, a[100]; scanf("%d", &n);
    for(i = 0; i < n; i++) scanf("%d", &a[i]);
    for(i = 0; i < n-1; i++)
        for(j = 0; j < n-1-i; j++)
            if(a[j] > a[j+1]){ temp = a[j]; a[j] = a[j+1]; a[j+1] = temp; }
    for(i = 0; i < n; i++) printf("%d ", a[i]);
    return 0;
}

Create three nodes in a singly linked list

#include <stdio.h>
#include <stdlib.h>
struct node{ int data; struct node *next; };
int main(){
    struct node *n1 = malloc(sizeof *n1),
                *n2 = malloc(sizeof *n2),
                *n3 = malloc(sizeof *n3);
    n1->data = 10; n2->data = 20; n3->data = 30;
    n1->next = n2; n2->next = n3; n3->next = NULL;
    for(struct node *p = n1; p; p = p->next) printf("%d ", p->data);
    return 0;
}

Q6: Trace merge sort

67,41,11,22,40,85,57,14,26

Splits:
[67,41,11,22,40] | [85,57,14,26]
[67,41,11] | [22,40] and [85,57] | [14,26]
… down to singletons.

Merges (left to right):

[67] & [41] → [41,67]; then with [11] → [11,41,67]
[22] & [40] → [22,40] Merge → [11,22,40,41,67]
[85] & [57] → [57,85]
[14] & [26] → [14,26] Merge → [14,26,57,85]
Final merge → [11,14,22,26,40,41,57,67,85]

  • Q7. Short notes

  • Linear Search

    • Definition: A simple searching technique where each element of the list/array is compared with the target key sequentially.

    • Steps:

      1. Start from the first element.
      2. Compare the element with the target key.
      3. If found → return index; else continue.
      4. If the end is reached without a match → element not found.

    • Time Complexity:

      • Best case → O(1) (found at first position).
      • Worst case → O(n) (not found or at the last position).

    • Space Complexity: O(1)

    • Use Case: Works on both sorted and unsorted data.

Weighted Graph

  • Definition: A graph where each edge has a weight or cost associated with it.

  • Types:

    • Directed Weighted Graph → edges have direction & weight.

    • Undirected Weighted Graph → edges have weight but no direction.

  • Applications:

    • Shortest path algorithms (Dijkstra, Bellman-Ford).
    • Network routing, transportation, road maps.

  • Representation:

    • Adjacency Matrix with weights.

    • Adjacency List storing edge + weight pairs.

  • Adjacency Matrix — definition and structure:

    • If there’s an edge from vertex i to j, then A[i][j] = 1 (or the weight in weighted graphs).
    • If no edge, A[i][j] = 0.

  • Size: For n vertices → n × n matrix.

  • Advantages:

    • Fast edge lookup: O(1).
    • Easy to implement.

  • Disadvantages:

    • Uses O(n²) space, even for sparse graphs.

  • Example (3 vertices):

      0 1 2
0 0 1 0
1 0 0 1
2 1 0 0

Q8. Stack using switch (array implementation)

#include <stdio.h>
#define MAX 100
int stack[MAX], top = -1;

void push(int x){ if(top == MAX-1) puts("Overflow"); else stack[++top] = x; }
int pop(){ if(top == -1){ puts("Underflow"); return -1; } return stack[top--]; }
int peek(){ return (top == -1) ? -1 : stack[top]; }
void display(){ if(top == -1) puts("Empty");
                else for(int i = top; i >= 0; i--) printf("%d ", stack[i]), printf("\n"); }

int main(){
    int ch, x;
    do{
        printf("1.Push 2.Pop 3.Peek 4.Display 5.Exit\n");
        scanf("%d", &ch);
        switch(ch){
            case 1: scanf("%d", &x); push(x); break;
            case 2: x = pop(); if(x != -1) printf("Popped %d\n", x); break;
            case 3: x = peek(); if(x != -1) printf("Top=%d\n", x); break;
            case 4: display(); break;
        }
    } while(ch != 5);
    return 0;
}

Q9. Insert a node at the beginning of a singly linked list

#include <stdio.h>
#include <stdlib.h>
struct node{ int data; struct node *next; };

void push_front(struct node **head, int x){
    struct node *n = malloc(sizeof *n);
    n->data = x; n->next = *head; *head = n;
}
void print(struct node *p){ for(; p; p = p->next) printf("%d ", p->data); puts(""); }

int main(){
    struct node *head = NULL;
    push_front(&head, 30);
    push_front(&head, 20);
    push_front(&head, 10);   // list: 10->20->30
    print(head);
    return 0;
}

Q10. Selection sort trace

2, 81, 6, 45, 11, 21, 23, 41, 11

Pass-by-pass (select minimum from the unsorted suffix and swap with first of suffix):

  1. Min in a[0..8] = 2 → stays → 2, 81, 6, 45, 11, 21, 23, 41, 11
  2. Min in a[1..8] = 6 ↔ a[1] → 2, 6, 81, 45, 11, 21, 23, 41, 11
  3. Min in a[2..8] = 11 ↔ a[2] → 2, 6, 11, 45, 81, 21, 23, 41, 11
  4. Min in a[3..8] = 11 ↔ a[3] → 2, 6, 11, 11, 81, 21, 23, 41, 45
  5. Min in a[4..8] = 21 ↔ a[4] → 2, 6, 11, 11, 21, 81, 23, 41, 45
  6. Min in a[5..8] = 23 ↔ a[5] → 2, 6, 11, 11, 21, 23, 81, 41, 45
  7. Min in a[6..8] = 41 ↔ a[6] → 2, 6, 11, 11, 21, 23, 41, 81, 45
  8. Min in a[7..8] = 45 ↔ a[7] → 2, 6, 11, 11, 21, 23, 41, 45, 81
    Sorted result: 2, 6, 11, 11, 21, 23, 41, 45, 81