Data Structures Master Cheat Sheet: CC-104 Exam Prep

CC-104 Data Structures Master Cheat Sheet

1. High-Yield Formulas & Operations

• 2D Array Address (Row-Major):
  Address = Base + Size × (i × TotalColumns + j)
• 2D Array Address (Column-Major):
  Address = Base + Size × (j × TotalRows + i)
• Circular Queue Index Increment:
  rear = (rear + 1) % MAX;
• AVL Tree Balance Factor:
  Balance Factor = Height(Left Subtree) - Height(Right Subtree)
  (Valid values are strictly -1, 0, or 1. Anything else triggers rotation).
• 3-Step Postfix Conversion Shortcut (A + B * C):
  1. Bracket by precedence: (A + (B * C))
  2. Move operators right of brackets: (A (B C)*)+
  3. Remove brackets: A B C * +

2. Mandatory Comparison Tables

Array vs. Linked List

Quick Sort vs. Merge Sort

malloc() vs. calloc()

3. Syllabus Unit-Wise 1-Liners

Unit I: Arrays, Searching & Sorting

• Time-Space Tradeoff: Speeding up execution time generally increases memory consumption, and vice versa.
• Binary Search Prerequisite: Array must be sorted before executing binary search.
• Inorder Traversal Property: Performing Inorder traversal (Left, Root, Right) on a Binary Search Tree always outputs data in ascending sorted order.

Unit II: Linked Lists & Hashing

• Singly vs. Doubly Linked List: Singly lists have one forward pointer (next); Doubly lists have two pointers (prev and next).
• Hash Collision: Occurs when two distinct keys yield the exact same index from a hash function.
• Collision Solutions: Chaining (linked list at index) or Open Addressing (probing for the next empty array slot).

Unit III: Stacks, Queues & Recursion

• Stack (LIFO): Last-In, First-Out. Insert/Delete strictly at the top. Used for undo operations and recursion.
• Queue (FIFO): First-In, First-Out. Insert at rear, delete from front.
• Recursion Engine: Recursive function calls are tracked in memory using the system Call Stack. Must have a Base Case to prevent stack overflow.

Unit IV: Trees & Graphs

• Binary Tree Rule: Every node has at most 2 children.
• Strictly Binary Tree: Every node has either exactly 0 or 2 children.
• Graph vs. Tree: A tree is a connected graph with zero cycles.
• Graph Traversals: BFS uses a Queue; DFS uses a Stack (or recursion).

4. Essential C Code Templates

Linked List Node Creation

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

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

Stack Push & Pop Operations

// Push
if (s->top == MAX - 1) {
    printf("Stack Overflow\n");
} else {
    s->top++;
    s->items[s->top] = value;
}

// Pop
if (s->top == -1) {
    printf("Stack Underflow\n");
} else {
    int val = s->items[s->top];
    s->top--;
}

Binary Search Function

int binarySearch(int arr[], int size, int target) {
    int low = 0, high = size - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (arr[mid] == target) return mid;
        if (arr[mid] < target) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}

5. Paper Presentation Framework

To secure full marks for 5 and 8-mark questions, structure every long answer using this 4-step layout:

1. Definition & Core Concept: Write 1–2 crisp, authoritative sentences defining the term.
2. Visual Diagram: Draw a clean representation (e.g., node pointers, array memory blocks, or tree hierarchies).
3. Algorithm / Core Logic: Write the procedural steps or the core C code snippet.
4. Complexity Badge: Always write the time and space complexity at the bottom (e.g., Time Complexity: O(n), Space Complexity: O(1)).

6. Rapid Fire 1-Mark Questions

• Non-Linear Data Structure: Tree or Graph.
• Divide-and-Conquer Algorithm: Merge Sort or Quick Sort.
• Real-Life Singly Linked List: A digital music playlist or browser history.
• Hash Function Purpose: To map a large key to a small array index for instant O(1) searching.
• Binary Search Prerequisite: Array must be sorted.
• Binary Tree Maximum Children: At most 2.
• Strictly Binary Tree: Every node has exactly 0 or 2 children.
• Graph to Tree Conversion: A graph is a tree only when it is fully connected and has no cycles.
• Iterative Quick Sort Data Structure: Stack.

7. Detailed Long-Answer Notes

Memory Representation of 2D Arrays

Computer memory is 1D. To store a 2D array, the compiler flattens it using these formulas:

• Row-Major Order (Row by Row): Address = Base + Size * (i * TotalColumns + j)
• Column-Major Order (Column by Column): Address = Base + Size * (j * TotalRows + i)

Hashing and Collision Resolution

• Collision: Occurs when a Hash Function generates the same array index for two different keys.
• Chaining: Resolves collision by building a Linked List at that congested array index.
• Open Addressing: Resolves collision by probing the array for the next available empty slot.

Advanced Queue Data Structures

• Circular Queue: Uses modulo arithmetic (rear + 1) % MAX to wrap the pointer back to index 0, preventing memory waste.
• Double-Ended Queue (Deque): Allows insertion and deletion at both the front and the rear.
• Priority Queue: Elements are dequeued based on assigned priority rather than arrival time.

Trees: BST and AVL

• Binary Search Tree (BST): Left child is always smaller than the parent; right child is always greater. Inorder traversal gives sorted output.
• AVL Tree: A height-balanced BST. The Balance Factor Height(Left) - Height(Right) must strictly equal -1, 0, or 1 for every node.

Doubly Linked List Node Definition

struct Node {
    int data;
    struct Node* prev;  // Points backward
    struct Node* next;  // Points forward
};

GCD using Recursion

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}