Data Structures and Algorithms

1. Basics of Data Structures

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

2. Array

  • Fixed-size collection of elements, stored in contiguous memory.
  • Key Operations: Access (O(1)), Search (O(n)), Insert/Delete (O(n)).
  • Applications: Searching, sorting.

3. Linked List

  • Collection of nodes connected via pointers.
  • Types:
    • Singly Linked List: Forward navigation.
    • Doubly Linked List: Forward and backward navigation.
    • Circular Linked List: Last node points to the first.
  • Applications: Dynamic memory allocation, implementation of stacks/queues.

4. Stack

  • LIFO (Last In, First Out) data structure.
  • Operations:
    • Push: Add element.
    • Pop: Remove element.
    • Peek/Top: View top element.
  • Applications: Expression evaluation, backtracking.

5. Queue

  • FIFO (First In, First Out) data structure.
  • Types:
    • Simple Queue: Linear order.
    • Circular Queue: Reuse memory.
    • Priority Queue: Elements served based on priority.
  • Applications: Scheduling, buffering.

6. Hashing

  • Maps keys to values for quick access (O(1)).
  • Collision Handling:
    • Chaining (linked list).
    • Open Addressing (linear/quadratic probing).
  • Applications: Database indexing, caching.

7. Trees

  • Hierarchical data structure with root and nodes.
  • Binary Tree: Max 2 children per node.
    • Binary Search Tree (BST): Left < Root < Right.
    • AVL Tree: Self-balancing BST.
    • Heap:
      • Min-Heap: Parent <= Child.
      • Max-Heap: Parent >= Child.
  • Applications: Searching, expression parsing.

8. Graphs

  • Set of vertices (nodes) and edges.
  • Representations:
    • Adjacency Matrix.
    • Adjacency List.
  • Traversals:
    • BFS (Breadth-First Search): Level-wise.
    • DFS (Depth-First Search): Depth-wise.
  • Applications: Networking, shortest path algorithms.

9. Searching Algorithms

  • Linear Search: O(n).
  • Binary Search: O(log n) (Array must be sorted).

10. Sorting Algorithms

  • Bubble Sort: Compare adjacent elements (O(n²)).
  • Selection Sort: Select smallest element (O(n²)).
  • Insertion Sort: Insert element in sorted subarray (O(n²)).
  • Merge Sort: Divide-and-conquer (O(n log n)).
  • Quick Sort: Partitioning (O(n log n) on average).
  • Heap Sort: Based on heap structure (O(n log n)).

11. Divide and Conquer

  • Break problem into smaller sub-problems, solve recursively.
  • Examples: Merge Sort, Quick Sort, Binary Search.

12. Dynamic Programming

  • Solve complex problems by breaking them into overlapping sub-problems.
  • Examples:
    • Knapsack Problem.
    • Longest Common Subsequence.
    • Fibonacci Sequence.

13. Greedy Algorithms

  • Make locally optimal choices to find the global solution.
  • Examples:
    • Prim’s Algorithm (MST).
    • Kruskal’s Algorithm (MST).
    • Dijkstra’s Algorithm (Shortest Path).

14. Backtracking

  • Explore all solutions by building a solution incrementally.
  • Examples:
    • N-Queens Problem.
    • Sudoku Solver.

15. Important Algorithms

  • KMP Algorithm: Pattern matching.
  • Bellman-Ford Algorithm: Shortest path (handles negative weights).
  • Floyd-Warshall Algorithm: All-pairs shortest path.
  • A Algorithm*: Pathfinding.
  • Disjoint Set (Union-Find): Detect cycles in graphs.

16. Complexity Analysis

  • Big O Notation:
    • O(1): Constant.
    • O(log n): Logarithmic.
    • O(n): Linear.
    • O(n²): Quadratic.
    • O(2ⁿ): 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