In-Semester (Mid-Sem)

Data Structures and Algorithms

May 2023 Examination

11/30/2025
•
5 min read

Total Marks

30

Duration

1 hour

Semester

semester3

Year/Branch

SE IT

Instructions:

Attempt any THREE questions from the following.

Question 1

10 marks
1.a)5 marks

Define a linked list. What are the advantages of linked lists over arrays?

Answer

A linked list is a linear data structure where elements are stored in nodes. Each node contains data and a reference (pointer) to the next node in the sequence.

Advantages over arrays:

  • Dynamic size - can grow or shrink at runtime
  • Efficient insertion/deletion - O(1) if position is known
  • No memory wastage - allocates memory as needed
1.b)5 marks

Write a C program to reverse a singly linked list.

Answer

Program to reverse a singly linked list:

reverse_linked_list.c
struct Node* reverse(struct Node* head) {
    struct Node* prev = NULL;
    struct Node* current = head;
    struct Node* next = NULL;
    
    while (current != NULL) {
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }
    
    return prev;
}

// Time Complexity: O(n)
// Space Complexity: O(1)

Attempt any one

Choose one of the following questions

Question 2

10 marks
2)10 marks

Explain binary search tree with its properties. Write an algorithm to search for an element in BST.

Answer

Binary Search Tree (BST)

A Binary Search Tree is a binary tree with the following properties:

  1. Left subtree of a node contains only nodes with keys less than the node's key
  2. Right subtree contains only nodes with keys greater than the node's key
  3. Both left and right subtrees must also be binary search trees

Search Algorithm

struct Node* search(struct Node* root, int key) {
    // Base cases: root is null or key is present at root
    if (root == NULL || root->data == key)
        return root;
    
    // Key is greater than root's key
    if (root->data < key)
        return search(root->right, key);
    
    // Key is smaller than root's key
    return search(root->left, key);
}

// Time Complexity: O(h) where h is height
// Best case: O(log n) for balanced BST
// Worst case: O(n) for skewed BST
OR

Question 3

10 marks
3.a)5 marks

What is a stack? Explain its applications with examples.

Answer

Stack: A stack is a linear data structure that follows the Last In First Out (LIFO) principle. Elements can only be inserted and removed from one end called the top.

Applications:

  1. Expression Evaluation: Converting infix to postfix, evaluating postfix expressions
  2. Function Calls: Managing function call stack in recursion
  3. Undo/Redo: Text editors, Photoshop operations
  4. Browser History: Back button functionality
3.b)5 marks

Implement stack using array in C with push and pop operations.

Answer
stack_array.c
#define MAX 100

struct Stack {
    int arr[MAX];
    int top;
};

void initialize(struct Stack* s) {
    s->top = -1;
}

int isFull(struct Stack* s) {
    return s->top == MAX - 1;
}

int isEmpty(struct Stack* s) {
    return s->top == -1;
}

void push(struct Stack* s, int value) {
    if (isFull(s)) {
        printf("Stack Overflow\n");
        return;
    }
    s->arr[++s->top] = value;
    printf("%d pushed to stack\n", value);
}

int pop(struct Stack* s) {
    if (isEmpty(s)) {
        printf("Stack Underflow\n");
        return -1;
    }
    return s->arr[s->top--];
}

int peek(struct Stack* s) {
    if (isEmpty(s)) {
        printf("Stack is empty\n");
        return -1;
    }
    return s->arr[s->top];
}

Question 4

10 marks
4)10 marks

Write a program to implement Bubble Sort. Explain its time complexity for best and worst cases with suitable examples.

Answer

Bubble Sort Implementation

bubble_sort.c
void bubbleSort(int arr[], int n) {
    int i, j, temp;
    int swapped;
    
    for (i = 0; i < n - 1; i++) {
        swapped = 0;
        
        // Last i elements are already sorted
        for (j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // Swap arr[j] and arr[j+1]
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = 1;
            }
        }
        
        // If no swap happened, array is sorted
        if (swapped == 0)
            break;
    }
}

Time Complexity Analysis

Best Case: O(n)

Example: Array [1, 2, 3, 4, 5] - Already sorted

Only one pass is needed, no swaps occur, loop breaks early.

Worst Case: O(n²)

Example: Array [5, 4, 3, 2, 1] - Reverse sorted

Every comparison results in a swap. For n elements, total comparisons = n(n-1)/2 ≈ O(n²)

Average Case: O(n²)

Space Complexity: O(1) - In-place sorting algorithm

SPPU | Last updated: 11/30/2025