Data Structures carry 6-7 questions in CCAT Section B. While that may seem fewer than C programming, these questions are often conceptual and can be quickly solved if you know the fundamentals. Combined with C programming, mastering data structures helps you dominate Section B.
In This Article
Time Complexity — The Foundation
Understanding time complexity is essential because many CCAT questions ask you to identify the complexity of an algorithm or compare algorithms.
| Complexity | Name | Example |
|---|---|---|
| O(1) | Constant | Array access by index |
| O(log n) | Logarithmic | Binary Search |
| O(n) | Linear | Linear Search |
| O(n log n) | Linearithmic | Merge Sort, Quick Sort (avg) |
| O(n²) | Quadratic | Bubble Sort, Selection Sort |
Sorting Algorithms
Sorting is the most important DS topic for CCAT. Know how each algorithm works and its complexity.
| Algorithm | Best | Average | Worst | Stable? |
|---|---|---|---|---|
| Selection Sort | O(n²) | O(n²) | O(n²) | No |
| Bubble Sort | O(n) | O(n²) | O(n²) | Yes |
| Insertion Sort | O(n) | O(n²) | O(n²) | Yes |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | Yes |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | No |
Key Points to Remember
- Merge Sort always gives O(n log n) but requires extra space O(n)
- Quick Sort is fastest on average but degrades to O(n²) for sorted arrays
- Bubble Sort with optimization (flag-based) has best case O(n)
- Know the step-by-step process for each algorithm
Searching Algorithms
Linear Search
- Time: O(n) — checks each element sequentially
- Works on unsorted arrays
Binary Search
- Time: O(log n) — divides the search space in half each time
- Requires a sorted array
- Know iterative and recursive implementations
Linked Lists
Linked List questions focus on types, operations, and time complexity comparisons with arrays.
Types of Linked Lists
- Singly Linear: Each node points to the next, last node points to NULL
- Doubly Linear: Each node has previous and next pointers
- Singly Circular: Last node points back to the first node
- Doubly Circular: Doubly linked + circular (last node's next = first, first node's prev = last)
Important Operations
| Operation | Array | Linked List |
|---|---|---|
| Access by index | O(1) | O(n) |
| Insert at beginning | O(n) | O(1) |
| Insert at end | O(1) amortized | O(n) or O(1) with tail |
| Delete by value | O(n) | O(n) |
| Search | O(n) | O(n) |
Stack & Queue
Stack (LIFO)
- Operations: push, pop, peek/top — all O(1)
- Applications: Expression evaluation, parenthesis matching, recursion, undo operations
- Know infix to postfix conversion
Queue (FIFO)
- Operations: enqueue, dequeue, front, rear — all O(1)
- Types: Simple Queue, Circular Queue, Priority Queue, Deque
- Applications: CPU scheduling, BFS traversal, printer spooling
Trees & Traversals
Tree Terminology
Root, Parent, Child, Leaf, Sibling, Height, Depth, Level, Degree — know each definition clearly.
Binary Tree Types
- Full Binary Tree: Every node has 0 or 2 children
- Complete Binary Tree: All levels filled except possibly the last (filled left to right)
- Perfect Binary Tree: All internal nodes have 2 children, all leaves at same level
- Binary Search Tree (BST): Left child < Parent < Right child
Tree Traversals — Very Important
- In-order (LNR): Left → Node → Right — gives sorted order for BST
- Pre-order (NLR): Node → Left → Right — used for copying trees
- Post-order (LRN): Left → Right → Node — used for deleting trees
Graphs
Graph questions in CCAT are usually limited to basic terminology. Know these concepts:
- Directed vs Undirected graphs
- Weighted vs Unweighted graphs
- Adjacency Matrix vs Adjacency List representation
- BFS (Breadth-First Search) — uses Queue
- DFS (Depth-First Search) — uses Stack
- Spanning Tree — minimum spanning tree concepts
Test Your Data Structures Knowledge
Practice topic-wise MCQs and take timed mock tests
Take a Mock TestFrequently Asked Questions
How many data structure questions are asked in CCAT?
Section B typically has 6-7 data structure questions out of 50. They focus on sorting algorithms, linked lists, trees, and time complexity analysis.
Which data structures are most important for CCAT?
Sorting algorithms (with time complexity), Linked Lists (types and operations), Trees (traversals), and Stack/Queue operations are most frequently asked.
Should I learn implementation or just theory?
For CCAT, focus on understanding concepts and output prediction. You do not need to write code. Know how algorithms work step by step and their time complexity.