Data Structures Exam Preparation Guide

DETAILED TOPICS (Main Questions)

1. MULTIDIMENSIONAL ARRAY

Definition: A multidimensional array is an array of arrays, where elements are arranged in multiple dimensions (rows, columns, and beyond).

Types:

• 2D Array (Matrix): Array with rows and columns

• 3D Array: Array with depth, rows, and columns

• nD Array: Array with n dimensions

Memory Representation:

• Row-Major Order: Elements stored row by row

  • Address = Base + [(i × n) + j] × size

• Column-Major Order: Elements stored column by column

  • Address = Base + [(j × m) + i] × size

Example (2D Array Declaration):

int matrix[3][4]; // 3 rows, 4 columns

Applications: Matrix operations, image processing, game boards, scientific computations

---

2. SPARSE MATRIX

Definition: A matrix where most elements are zero (typically >60% zeros).

Why Use Special Representation?

• Saves memory space

• Reduces computation time

• Avoids storing unnecessary zeros

Representations:

a) Triplet/3-Tuple Form:

Row | Column | Value
----|--------|------
 0  |   0    |  15
 1  |   3    |  22
 2  |   1    |  11

b) Linked List Representation:

• Each non-zero element is a node

• Nodes contain: row, column, value, next pointer

Operations: Addition, Subtraction, Multiplication, Transpose

---

3. LINKED LIST

SINGLY LINKED LIST

Structure:

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

INSERTION FUNCTIONS:

a) Insert at Beginning:

void insertBegin(struct Node** head, int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = *head;
    *head = newNode;
}

b) Insert at End:

void insertEnd(struct Node** head, 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;
}

c) Insert at Middle (After a Given Node):

void insertMiddle(struct Node* prevNode, int data) {
    if (prevNode == NULL) {
        printf("Previous node cannot be NULL");
        return;
    }

    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = prevNode->next;
    prevNode->next = newNode;
}

DELETION FUNCTIONS:

a) Delete from Beginning:

void deleteBegin(struct Node** head) {
    if (*head == NULL) {
        printf("List is empty");
        return;
    }

    struct Node* temp = *head;
    *head = (*head)->next;
    free(temp);
}

b) Delete from End:

void deleteEnd(struct Node** head) {
    if (*head == NULL) {
        printf("List is empty");
        return;
    }

    if ((*head)->next == NULL) {
        free(*head);
        *head = NULL;
        return;
    }

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

c) Delete from Middle (Delete a Specific Node):

void deleteMiddle(struct Node** head, int key) {
    struct Node* temp = *head;
    struct Node* prev = NULL;

    if (temp != NULL && temp->data == key) {
        *head = temp->next;
        free(temp);
        return;
    }

    while (temp != NULL && temp->data != key) {
        prev = temp;
        temp = temp->next;
    }

    if (temp == NULL) return;

    prev->next = temp->next;
    free(temp);
}

---

DOUBLY LINKED LIST (VVIP)

Structure:

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

INSERTION FUNCTIONS:

a) Insert at Beginning:

void insertBegin(struct Node** head, int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->prev = NULL;
    newNode->next = *head;

    if (*head != NULL) {
        (*head)->prev = newNode;
    }
    *head = newNode;
}

b) Insert at End:

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

    if (*head == NULL) {
        newNode->prev = NULL;
        *head = newNode;
        return;
    }

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

c) Insert at Middle (After a Given Node):

void insertMiddle(struct Node* prevNode, int data) {
    if (prevNode == NULL) {
        printf("Previous node cannot be NULL");
        return;
    }

    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = prevNode->next;
    newNode->prev = prevNode;

    if (prevNode->next != NULL) {
        prevNode->next->prev = newNode;
    }
    prevNode->next = newNode;
}

DELETION FUNCTIONS:

a) Delete from Beginning:

void deleteBegin(struct Node** head) {
    if (*head == NULL) {
        printf("List is empty");
        return;
    }

    struct Node* temp = *head;
    *head = (*head)->next;

    if (*head != NULL) {
        (*head)->prev = NULL;
    }
    free(temp);
}

b) Delete from End:

void deleteEnd(struct Node** head) {
    if (*head == NULL) {
        printf("List is empty");
        return;
    }

    struct Node* temp = *head;

    if (temp->next == NULL) {
        free(temp);
        *head = NULL;
        return;
    }

    while (temp->next != NULL) {
        temp = temp->next;
    }
    temp->prev->next = NULL;
    free(temp);
}

c) Delete from Middle:

void deleteMiddle(struct Node** head, int key) {
    if (*head == NULL) return;

    struct Node* temp = *head;

    while (temp != NULL && temp->data != key) {
        temp = temp->next;
    }

    if (temp == NULL) return;

    if (temp->prev != NULL) {
        temp->prev->next = temp->next;
    } else {
        *head = temp->next;
    }

    if (temp->next != NULL) {
        temp->next->prev = temp->prev;
    }
    free(temp);
}

---

4. STACK

Definition: A linear data structure following LIFO (Last In First Out) principle.

A) STACK USING ARRAY

Structure:

#define MAX 100
struct Stack {
    int arr[MAX];
    int top;
};

PUSH Algorithm:

1. Check if stack is full (top == MAX-1)
2. If full, print "Stack Overflow"
3. Else, increment top
4. Insert element at arr[top]

PUSH Function:

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

POP Algorithm:

1. Check if stack is empty (top == -1)
2. If empty, print "Stack Underflow"
3. Else, get element at arr[top]
4. Decrement top
5. Return the element

POP Function:

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

PEEK Algorithm:

1. Check if stack is empty (top == -1)
2. If empty, print "Stack is empty"
3. Else, return arr[top] without removing

PEEK Function:

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

---

B) STACK USING LINKED LIST

Structure:

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

PUSH Algorithm:

1. Create new node
2. Assign data to new node
3. Point new node's next to current top
4. Make new node as top

PUSH Function:

void push(struct Stack* stack, int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = stack->top;
    stack->top = newNode;
    printf("%d pushed to stack\n", data);
}

POP Algorithm:

1. Check if top is NULL (stack empty)
2. If empty, print "Stack Underflow"
3. Else, store top node in temp
4. Get data from temp
5. Move top to next node
6. Free temp
7. Return data

POP Function:

int pop(struct Stack* stack) {
    if (stack->top == NULL) {
        printf("Stack Underflow\n");
        return -1;
    }
    struct Node* temp = stack->top;
    int popped = temp->data;
    stack->top = stack->top->next;
    free(temp);
    return popped;
}

PEEK Algorithm:

1. Check if top is NULL
2. If empty, print "Stack is empty"
3. Else, return top->data

PEEK Function:

int peek(struct Stack* stack) {
    if (stack->top == NULL) {
        printf("Stack is empty\n");
        return -1;
    }
    return stack->top->data;
}

---

5. QUEUE

Definition: A linear data structure following FIFO (First In First Out) principle.

Structure (Array Implementation):

#define MAX 100
struct Queue {
    int arr[MAX];
    int front, rear;
};

INSERT (Enqueue) Algorithm:

1. Check if queue is full (rear == MAX-1)
2. If full, print "Queue Overflow"
3. If queue is empty (front == -1), set front = 0
4. Increment rear
5. Insert element at arr[rear]

INSERT Function:

void enqueue(struct Queue* queue, int data) {
    if (queue->rear == MAX - 1) {
        printf("Queue Overflow\n");
        return;
    }
    if (queue->front == -1) {
        queue->front = 0;
    }
    queue->arr[++queue->rear] = data;
    printf("%d inserted to queue\n", data);
}

DELETE (Dequeue) Algorithm:

1. Check if queue is empty (front == -1 or front > rear)
2. If empty, print "Queue Underflow"
3. Get element at arr[front]
4. If front == rear (only one element), reset front and rear to -1
5. Else, increment front
6. Return the element

DELETE Function:

int dequeue(struct Queue* queue) {
    if (queue->front == -1 || queue->front > queue->rear) {
        printf("Queue Underflow\n");
        return -1;
    }
    int data = queue->arr[queue->front];
    if (queue->front == queue->rear) {
        queue->front = queue->rear = -1;
    } else {
        queue->front++;
    }
    return data;
}

---

6. CIRCULAR QUEUE

Definition: A queue where the last position is connected back to the first position, forming a circle. This overcomes the limitation of linear queue where space is wasted.

Advantages:

• Better memory utilization

• No wasted space after dequeue operations

• Both front and rear can wrap around

Structure:

#define MAX 5
struct CircularQueue {
    int arr[MAX];
    int front, rear;
};

Operations:

Insert:

void enqueue(struct CircularQueue* queue, int data) {
    if ((queue->rear + 1) % MAX == queue->front) {
        printf("Queue is full\n");
        return;
    }
    if (queue->front == -1) {
        queue->front = 0;
    }
    queue->rear = (queue->rear + 1) % MAX;
    queue->arr[queue->rear] = data;
}

Delete:

int dequeue(struct CircularQueue* queue) {
    if (queue->front == -1) {
        printf("Queue is empty\n");
        return -1;
    }
    int data = queue->arr[queue->front];
    if (queue->front == queue->rear) {
        queue->front = queue->rear = -1;
    } else {
        queue->front = (queue->front + 1) % MAX;
    }
    return data;
}

---

7. RECURSION (VVIP)

Definition: A function that calls itself directly or indirectly to solve a problem by breaking it into smaller subproblems.

Components:

1. Base Case: Stopping condition

2. Recursive Case: Function calling itself with modified parameters

Example: Factorial

int factorial(int n) {
    // Base case
    if (n == 0 || n == 1) {
        return 1;
    }
    // Recursive case
    return n * factorial(n - 1);
}

Example Execution (factorial(4)):

factorial(4) = 4 × factorial(3)
             = 4 × 3 × factorial(2)
             = 4 × 3 × 2 × factorial(1)
             = 4 × 3 × 2 × 1
             = 24

---

TYPES OF RECURSION (VVIP)

1. DIRECT RECURSION: A function calls itself directly.

void directRecursion(int n) {
    if (n > 0) {
        printf("%d ", n);
        directRecursion(n - 1);  // Calls itself
    }
}

2. INDIRECT RECURSION: A function calls another function which eventually calls the first function.

void functionA(int n);
void functionB(int n);

void functionA(int n) {
    if (n > 0) {
        printf("%d ", n);
        functionB(n - 1);  // Calls functionB
    }
}

void functionB(int n) {
    if (n > 1) {
        printf("%d ", n);
        functionA(n / 2);  // Calls functionA
    }
}

3. TAIL RECURSION: The recursive call is the last operation in the function. No operations after the recursive call.

void tailRecursion(int n) {
    if (n > 0) {
        printf("%d ", n);
        tailRecursion(n - 1);  // Last operation
    }
}

Advantage: Can be optimized by compiler to use constant stack space.

4. NON-TAIL RECURSION: There are operations to be performed after the recursive call returns.

int nonTailRecursion(int n) {
    if (n == 0) {
        return 1;
    }
    return n * nonTailRecursion(n - 1);  // Multiplication after recursive call
}

Comparison Table:

---

8. TOWER OF HANOI PROBLEM

Problem Statement: Transfer n disks from source peg to destination peg using an auxiliary peg, following rules:

1. Only one disk can be moved at a time

2. A larger disk cannot be placed on a smaller disk

3. Only the top disk can be moved

Algorithm:

1. If n == 1, move disk from source to destination
2. Else:
   a) Move (n-1) disks from source to auxiliary using destination
   b) Move nth disk from source to destination
   c) Move (n-1) disks from auxiliary to destination using source

Recursive Solution:

void towerOfHanoi(int n, char source, char destination, char auxiliary) {
    if (n == 1) {
        printf("Move disk 1 from %c to %c\n", source, destination);
        return;
    }

    // Move n-1 disks from source to auxiliary
    towerOfHanoi(n - 1, source, auxiliary, destination);

    // Move nth disk from source to destination
    printf("Move disk %d from %c to %c\n", n, source, destination);

    // Move n-1 disks from auxiliary to destination
    towerOfHanoi(n - 1, auxiliary, destination, source);
}

Example (3 disks):

Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C

Complexity:

• Time Complexity: O(2^n)

• Number of Moves: 2^n - 1

---

1 MARK QUESTIONS

1. Self Referential Pointer/Self Referential Structure

A structure that contains a pointer to the same structure type as one of its members.

struct Node {
    int data;
    struct Node* next;  // Pointer to same structure type
};

Use: Creating linked lists, trees, and graphs.

---

2. What is Circular List

A linked list where the last node points back to the first node instead of NULL, forming a circle.

Types:

• Circular Singly Linked List (last→next = first)

• Circular Doubly Linked List (last→next = first, first→prev = last)

Advantage: Can traverse entire list from any node.

---

3. What is Peek Operation

An operation that returns the top element of a stack without removing it. It allows viewing the top element while keeping the stack unchanged.

int peek(struct Stack* stack) {
    if (stack->top == -1) {
        return -1;  // Stack empty
    }
    return stack->arr[stack->top];
}

---

4. What is Recursion

A programming technique where a function calls itself to solve a problem by breaking it into smaller, similar subproblems. It requires a base case to stop and a recursive case to continue.

Example: factorial(n) = n × factorial(n-1)

---

5. What is Priority Queue

A special type of queue where each element has a priority value. Elements with higher priority are dequeued before elements with lower priority, regardless of insertion order.

Types:

• Ascending Priority Queue (lowest priority first)

• Descending Priority Queue (highest priority first)

Applications: CPU scheduling, Dijkstra's algorithm, Huffman coding.

---

6. Differences Between Structure and Union

Example:

struct Student {
    int id;      // 4 bytes
    char name[20]; // 20 bytes
    float marks; // 4 bytes
};  // Total: 28 bytes

union Data {
    int i;    // 4 bytes
    float f;  // 4 bytes
    char c;   // 1 byte
};  // Total: 4 bytes (largest member)

---

7. Difference Between Stack and Queue (5 marks)

Key Difference:

• Stack: Last element added is first to be removed (like a stack of books)

• Queue: First element added is first to be removed (like a waiting line)

---

8. Evaluation of Postfix Expression

Method:

1. Scan expression from left to right

2. If operand, push to stack

3. If operator, pop two operands, apply operator, push result

4. Final stack value is the answer

Example: 5 3 + 2 × (equivalent to (5+3)×2)

Answer: 16

Algorithm:

1. Create empty stack
2. For each character in expression:
   a) If operand: push to stack
   b) If operator:
      - Pop two operands (op2, op1)
      - Calculate: op1 operator op2
      - Push result to stack
3. Return top of stack

---

9. Conversion from Infix to Postfix

Rules:

1. Scan infix expression left to right

2. If operand, add to output

3. If '(', push to stack

4. If ')', pop until '(' and add to output

5. If operator:

   • Pop operators with higher/equal precedence

   • Push current operator

6. Pop all remaining operators

Precedence: ^ > ×,/ > +,-

Example: A + B × C

Result: ABC×+

Algorithm:

1. Initialize empty stack and output string
2. For each character:
   - If operand: append to output
   - If '(': push to stack
   - If ')': pop and append until '('
   - If operator:
     * Pop operators with ≥ precedence
     * Push current operator
3. Pop remaining operators to output

---

10. Examples of Infix, Prefix, Postfix Expressions

Infix Notation: Operator between operands (how we normally write)

• Example: A + B

• Example: (A + B) × C

• Example: A + B × C

Prefix Notation: Operator before operands (Polish Notation)

• Example: + A B

• Example: × + A B C

• Example: + A × B C

Postfix Notation: Operator after operands (Reverse Polish Notation)

• Example: A B +

• Example: A B + C ×

• Example: A B C × +

Comparison Table:

Advantages:

• Infix: Easy for humans to read

• Prefix: No need for parentheses, easy to evaluate right-to-left

• Postfix: No need for parentheses, easy to evaluate left-to-right, used in calculators and compilers

---