Data Structures and Algorithms

1. Basics of Data Structures

  • Definition: Way to organize, manage, and store data.
  • Types:
    • Linear → Array, Linked List, Stack, Queue.
    • Non-Linear → Tree, Graph, Hash Table.

2. Array

  • Fixed size; stored in contiguous memory.
  • Operations: Access O(1), Search O(n), Insert/Delete O(n).
  • Uses: Searching, sorting, simple data storage.

3. Linked List

  • Collection of nodes (data + pointer).
  • Types:
    • Singly → forward only.
    • Doubly → forward + backward.
    • Circular → last connects to first.
  • Uses: Dynamic memory, implementing stacks/queues.

4. Stack

  • LIFO (Last In, First Out).
  • Operations: Push, Pop, Peek/Top.
  • Uses: Undo (Ctrl+Z), recursion, expression evaluation.

5. Queue

  • FIFO (First In, First Out).
  • Types: Simple, Circular, Priority.
  • Uses: Scheduling, buffering (e.g., printers, CPU tasks).

6. Hashing

  • Maps keys → values, access O(1).
  • Collision Handling:
    • Chaining (linked list).
    • Open addressing (linear/quadratic probing).
  • Uses: Database indexing, caching, symbol tables.

7. Trees

  • Hierarchical (root → children).
  • Types:
    • Binary Tree → max 2 children.
    • BST → Left < Root < Right.
    • AVL Tree → Self-balancing BST.
    • Heap →
      • Min-Heap: Parent ≤ Child.
      • Max-Heap: Parent ≥ Child.
  • Uses: Searching, parsing expressions, heapsort.

8. Graphs

  • Vertices (nodes) + Edges (connections).
  • Representation: Adjacency List, Adjacency Matrix.
  • Traversal:
    • BFS → level-wise.
    • DFS → depth-wise.
  • Uses: Networking, shortest paths, social networks.

9. Searching Algorithms

  • Linear Search → O(n).
  • Binary Search → O(log n), works only on sorted arrays.

10. Sorting Algorithms

  • Slow (O(n²)) → Bubble, Selection, Insertion.
  • Fast (O(n log n)) → Merge Sort, Quick Sort (avg), Heap Sort.

11. Divide & Conquer

  • Break → Solve → Combine.
  • Examples: Merge Sort, Quick Sort, Binary Search.

12. Dynamic Programming (DP)

  • Solve problems with overlapping subproblems.
  • Examples: Fibonacci, Knapsack, Longest Common Subsequence.

13. Greedy Algorithms

  • Local best choice → global solution.
  • Examples:
    • Prim’s & Kruskal’s → Minimum Spanning Tree.
    • Dijkstra’s → Shortest Path.

14. Backtracking

  • Try → Backtrack if fail.
  • Examples: N-Queens, Sudoku, Maze solving.

15. Important Algorithms

  • KMP → Pattern matching.
  • Bellman-Ford → Shortest path (handles negative edges).
  • Floyd-Warshall → All-pairs shortest path.
  • A* → Pathfinding.
  • Disjoint Set (Union-Find) → Cycle detection in graphs.

16. Complexity Analysis (Big-O)

  • O(1) → Constant.
  • O(log n) → Logarithmic (Binary Search).
  • O(n) → Linear (Linear Search).
  • O(n²) → Quadratic (Bubble Sort).
  • O(2ⁿ) → Exponential (Backtracking, brute force).

🔑 Quick Revision (Exam Cheatsheet)

  • Linear DS → Array, Linked List, Stack, Queue.
  • Non-Linear DS → Tree, Graph, Hash Table.
  • Searching → Linear O(n), Binary O(log n).
  • Sorting → Merge/Quick/Heap → O(n log n).
  • Algorithms → DP (Knapsack, LCS), Greedy (Prim, Kruskal, Dijkstra), Backtracking (N-Queens).
  • Complexity → Constant < Log < Linear < Quadratic < Exponential.

MCQ

Q1. Which of the following is the correct time complexity for accessing an element in an array by index?
a) O(n)
b) O(log n)
c) O(1)
d) O(n²)

c

Q2. In a sorted array, which searching algorithm is more efficient?
a) Linear Search
b) Binary Search
c) Hashing
d) Depth First Search

b

Q3. What is the minimum time complexity of sorting an array?
a) O(log n)
b) O(n log n)
c) O(n²)
d) O(n³)

b

Q4. What is the time complexity of inserting a node at the beginning of a singly linked list?
a) O(1)
b) O(n)
c) O(log n)
d) O(n²)

a

Q5. Which of the following data structures is more suitable for implementing a stack?
a) Array
b) Linked List
c) Queue
d) Graph

b

Q6. How many pointers are needed to represent a node in a doubly linked list?
a) 1
b) 2
c) 3
d) 4

b

Q7. Which data structure works on the principle of LIFO?
a) Queue
b) Stack
c) Tree
d) Graph

b

Q8. Which of the following applications can be implemented using a stack?
a) Expression evaluation
b) Breadth-first search
c) Priority Queue
d) None of the above

a

Q9. What is the postfix expression of (A + B) * (C - D)?
a) AB + CD - *
b) AB + * CD -
c) A + B * C - D
d) A B C D - + *

a

Q10. A queue follows which principle?
a) LIFO
b) FIFO
c) Random Order
d) Priority Order

b

Q11. What is the time complexity for enqueuing or dequeuing in a simple queue?
a) O(1)
b) O(log n)
c) O(n)
d) O(n²)

a

Q12. Which data structure is used to implement a circular queue?
a) Array
b) Linked List
c) Both
d) None

c

Q13. In a binary search tree, which traversal outputs data in sorted order?
a) Preorder
b) Inorder
c) Postorder
d) Level order

b

Q14. What is the height of a full binary tree with n nodes?
a) log₂(n+1)
b) log₂(n)
c) 2n
d) n

a

Q15. In a max-heap, the parent node is:
a) Smaller than its child nodes
b) Greater than or equal to its child nodes
c) Equal to its left child only
d) None of the above

b

Q16. What is the time complexity of Breadth-First Search (BFS) for a graph with V vertices and E edges?
a) O(V + E)
b) O(V²)
c) O(E log V)
d) O(V³)

a

Q17. Which graph representation uses adjacency lists?
a) Linked List
b) Array
c) Queue
d) Stack

a

Q18. Prim’s algorithm is used to find:
a) Shortest path
b) Minimum spanning tree
c) Maximum flow
d) Topological sorting

b

Q19. Which of the following sorting algorithms has the best average-case time complexity?
a) Bubble Sort
b) Quick Sort
c) Merge Sort
d) Insertion Sort

c

Q20. Linear search is best suited for:
a) Large unsorted lists
b) Small unsorted lists
c) Sorted lists only
d) None of the above

b

Q21. Which method is used to handle hash collisions?
a) Chaining
b) Open Addressing
c) Both a and b
d) None of the above

c

Q22. What is the load factor in a hash table?
a) Total size of hash table.
b) Number of elements divided by table size.
c) Number of collisions.
d) None of the above.

b

Q23. The time complexity of Binary Search is:
a) O(1)
b) O(log n)
c) O(n)
d) O(n²)

b

Q24. Which algorithm has the worst-case time complexity of O(n²)?
a) Bubble Sort
b) Quick Sort
c) Merge Sort
d) Heap Sort

a

Q25. Which problem is solved using dynamic programming?
a) Longest Common Subsequence
b) N-Queens Problem
c) Dijkstra’s Algorithm
d) Depth-First Search

a

Q26. Which property is required for dynamic programming?
a) Greedy choice
b) Optimal substructure and overlapping subproblems
c) Divide and Conquer
d) Backtracking

b

Q27. Which of the following is NOT an application of backtracking?
a) Sudoku Solver
b) N-Queens Problem
c) Minimum Spanning Tree
d) Crossword Puzzle

c

Q28. Dijkstra’s algorithm does NOT work with:
a) Positive edge weights
b) Negative edge weights
c) Directed graphs
d) Undirected graphs

b