MCS-208 — Data Structures & Algorithms Quick Revision (75 Questions + Answers)

UNIT-1: Introduction to Data Structures & Algorithms (Q1–15)

1. What is a Data Structure?

A way of organizing and storing data efficiently for operations like searching, insertion, and deletion.

2. What is an Algorithm?

Step-by-step procedure to solve a specific problem.

3. Characteristics of a good algorithm

Correctness, efficiency, simplicity, finiteness, determinism.

4. What is Time Complexity?

It measures execution time as a function of input size.

5. What is Space Complexity?

Memory required by an algorithm based on input size.

6. Big-O Notation?

Represents worst-case time complexity.

7. Best, Average, Worst Cases

They indicate performance variations based on different input scenarios.

8. Example complexities

9. What is Asymptotic Analysis?

Analysis of algorithm performance when input size grows large.

10. Types of Data Structures

Primitive and Non-primitive (Linear and Non-Linear).

11. What is ADT?

Abstract Data Type: Specifies what operations but not implementation.

12. Static vs Dynamic Data Structures

Static size fixed (arrays), dynamic resizable (linked list).

13. What is Recursion?

Function calling itself until base condition.

14. Tail Recursion

Recursive call appears at the end of function.

15. Advantages of Recursion

Simple implementation for problems like factorial, tree traversal.

UNIT-2: Arrays, Strings & Searching (Q16–30)

16. What is Array?

Sequential memory storage of same-type elements.

17. Advantages of arrays

Fast access using index.

18. Disadvantages of arrays

Fixed size and costly insert/delete.

19. What is 2D array?

Matrix-like memory structure.

20. Linear Search complexity

Worst case: O(n)

21. Binary Search requirement

Array must be sorted.

22. Binary Search time complexity

O(log n)

23. What is String?

Array of characters with null terminator (in C-style) or object (in OOP languages).

24. Sparse Matrix

Matrix mostly filled with zeros.

25. How to store sparse matrices?

Triplet format or linked list representation.

26. Circular Array?

Array in which last index connects to first index.

27. What is Searching?

Finding an element in a collection.

28. What is Sorting?

Arranging data in ascending/descending order.

29. Stable Sorting Algorithm

Maintains order of equal keys (e.g., Merge Sort, Bubble Sort).

30. Unstable Sorting Algorithm

Does not guarantee order (e.g., Quick Sort, Heap Sort).

UNIT-3: Linked Lists, Stacks, Queues (Q31–50)

31. What is Linked List?

Dynamic structure of nodes linked using pointers.

32. Types of Linked List

Singly, Doubly, Circular.

33. Node structure example

data + pointer

34. Advantage of linked list

Efficient insertion/deletion.

35. Disadvantage

Slow access (sequential).

36. Stack

LIFO structure.

37. Applications of Stack

Function calls, undo operations, expression evaluation.

38. Stack overflow

Push when stack is full.

39. Queue

FIFO structure.

40. Applications of Queue

Scheduling, buffering, printers.

41. Circular Queue

Front and rear wrap around.

42. Priority Queue

Elements served based on priority.

43. Deque

Double-ended queue (insert/delete at both ends).

44. Expression Types

Infix, Postfix, Prefix.

45. Convert infix to postfix

Use stack and precedence rules.

46. Postfix Evaluation

Uses stack.

47. Polynomial representation

Array or linked list.

48. Linked List vs Array

Dynamic vs fixed size.

49. Stack implementation

Array or linked list.

50. Queue implementation

Array or linked list.

UNIT-4: Trees & Graphs (Q51–65)

51. What is a Tree?

Non-linear hierarchical data structure.

52. Binary Tree

Each node has up to two children.

53. Full Binary Tree

All nodes have 0 or 2 children.

54. Complete Binary Tree

All levels filled except last left-to-right.

55. Binary Search Tree (BST)

Left < Root>

56. BST Search Complexity

O(log n) average.

57. Tree Traversal Methods

• Inorder (LNR)

• Preorder (NLR)

• Postorder (LRN)

58. AVL Tree

Self-balancing BST.

59. B-Tree

Balanced tree used in disk storage.

60. Heap

Complete binary tree useful for priority queue.

61. Graph

Nodes (vertices) + connections (edges).

62. Directed vs Undirected Graph

Edges have direction or not.

63. Graph Representation

Adjacency matrix or adjacency list.

64. BFS

Breadth-first search using queue.

65. DFS

Depth-first search using stack/recursion.

UNIT-5: Advanced Topics & Sorting Algorithms (Q66–75)

66. Selection Sort

Repeatedly selects smallest element.
Time: O(n²)

67. Bubble Sort

Repeated adjacent swaps.
Time: O(n²)

68. Insertion Sort

Builds sorted list one element at a time.
Time: O(n²) (best case O(n))

69. Merge Sort

Divide and conquer.
Time: O(n log n) (stable)

70. Quick Sort

Pivot-based divide and conquer.
Average: O(n log n), worst: O(n²).

71. Heap Sort

Uses heap structure.
Performance: O(n log n).

72. Hashing

Uses hash function for fast searching.

73. Collision Handling Methods

Chaining, open addressing.

74. Floyd–Warshall algorithm

Used for shortest path in weighted graph.

75. Dijkstra’s Algorithm

Finds shortest path from a source to all nodes in weighted graph.