CIL Data Structures + Algorithms —

Complete Preparation
Your exact syllabus
Section 4 — Data Structures

1. Programming in C
2. Recursion
3. Arrays
4. Stacks
5. Queues
6. Linked Lists
7. Trees
8. Binary Search Trees
9. Binary Heaps
10. Graphs

Section 5 — Algorithms

11. Searching
12. Sorting
13. Hashing
14. Asymptotic worst-case time and space complexity
15. Greedy
16. Dynamic Programming
17. Divide and Conquer
18. Graph Traversals
19. Minimum Spanning Trees
20. Shortest Paths

PART A — CIL-LEVEL THEORY

1. Programming in C
For DSA, you don't need every corner of C. Concentrate on the features used to implement
data structures.

Must know

 Variables and data types

 Operators
 if, switch
 for, while, do-while
 Functions
 Pointers
 Arrays
  Strings
 Structures
 Dynamic memory allocation
 Recursion
 malloc(), calloc(), realloc(), free()

Most important: pointers

A pointer stores the address of another variable.

int x = 10;
int *p = &x;

Conceptually:

x
┌──────┐
│ 10 │
└──────┘
↑
│ address
┌──────┐
│ p │
└──────┘

For linked lists, trees and graphs, pointers are fundamental.

CIL relevance: 8/10

The 2020 paper included a C output question, showing that basic C programming can appear
directly.

2. Recursion
A function calling itself is recursion.

fact(n) = n × fact(n-1)

Example
int fact(int n)
{
if(n == 0)
return 1;

return n * fact(n-1);
}

For fact(4):

fact(4)
↓
4 × fact(3)
↓
 3 × fact(2)
↓
2 × fact(1)
↓
1 × fact(0)
↓
1

Result:

[
4\times3\times2\times1=24
]

Critical concept

Every recursion needs:

1. Base case
2. Recursive case

Recursion uses:

Stack

The 2020 CIL paper directly asked which data structure the system uses to implement
recursion, with Stack as the answer.

CIL relevance: 9/10

3. Arrays
An array stores elements in contiguous memory.

A[0] A[1] A[2] A[3] A[4]

↓ ↓ ↓ ↓ ↓
10 20 30 40 50

Advantages

 Random access
 A[i] → O(1)
 Simple implementation

Disadvantages

 Fixed size in ordinary static arrays

 Insertion/deletion can require shifting

Complexity
 Operation Complexity
Access O(1)
Search O(n)
Insert at beginning O(n)
Delete at beginning O(n)

Important formula

If lower bound = LB and upper bound = UB:

N=UB-LB+1

CIL relevance: 6/10

4. Stack
Stack follows:

LIFO — Last In, First Out

TOP
↓
┌───┐
│ 30│
├───┤
│ 20│
├───┤
│ 10│
└───┘

Operations:

 push
 pop
 peek/top

Complexity

Normally: push=O(1) ; pop=O(1)

Applications

 Recursion
 Function calls
 DFS
 Parentheses matching
 Expression conversion
 Undo operation

The 2020 paper directly tested FILO → Stack.

5. Queue
Queue follows:

FIFO — First In, First Out

Front Rear
↓ ↓
┌────┬────┬────┬────┐
│ 10 │ 20 │ 30 │ 40 │
└────┴────┴────┴────┘
↑ ↑
delete insert

Operations:

 Enqueue
 Dequeue
 Front/Peek

Applications

 BFS
 CPU scheduling
 Printer queue
 Buffers

CIL relevance: 8.5/10

6. Linked List
A linked list consists of nodes.

┌──────┬─────┐ ┌──────┬─────┐ ┌──────┬─────┐

│ 10 │ •──┼───►│ 20 │ •──┼───►│ 30 │NULL │
└──────┴─────┘ └──────┴─────┘ └──────┴─────┘

Each node contains:

Data + Pointer

Types

1. Singly linked list

2. Doubly linked list
3. Circular linked list
Complexity

Operation Typical complexity

Access O(n)
Search O(n)
Insert at beginning O(1)
Delete known node O(1)
Insert after known O(1)
node

Important CIL connection

The 2020 paper asks:

Polynomial addition is implemented using which data structure?

Answer: Linked List.

CIL relevance: 8/10

7. Trees
A tree is a hierarchical data structure.

A
/ \
B C
/ \ \
D E F

Important terms:

 Root
 Parent
 Child
 Leaf
 Degree
 Level
 Height
 Subtree

Binary tree

Each node has at most two children.

A
/ \
B C
/ \
D E
Tree traversals

Preorder

Root → Left → Right

Inorder

Left → Root → Right

Postorder

Left → Right → Root

Level order

Level by level

The 2020 paper gives inorder + preorder and asks the candidate to derive the postorder
traversal.

CIL relevance: 10/10

This is one of your highest-priority areas.

8. Binary Search Tree — BST

BST property: Left < Root < Right

Example:

50
/ \
30 70
/ \ / \
20 40 60 80

Therefore inorder traversal gives:

20 30 40 50 60 70 80

Searching

Balanced BST: O(\log n)

Worst-case skewed BST: O(n)

This distinction is very important.

The 2020 paper directly asks the time required to search an element in a BST and gives O(log
n) as the intended answer.
CIL relevance: 10/10

9. Binary Heap
A heap is a complete binary tree.

Max heap

Parent ≥ children.

90
/ \
70 80
/ \ /
40 50 60

Min heap

Parent ≤ children.

10
/ \
20 30
/ \ /
40 50 60

Important

Heap is commonly represented using an array.

For 0-based indexing:

Left(i)=2i+1

Right(i)=2i+2

Parent(i)=\lfloor(i-1)/2\rfloor

Complexity

Operation Complexity
Get min/max O(1)
Insert O(log n)
Delete root O(log n)
Build heap O(n)

CIL relevance: 9/10

10. Graphs
A graph consists of: G=(V,E)

where:

 V = vertices
 E = edges

Example:

A ─── B
│ │
│ │
C ─── D

Types

 Directed
 Undirected
 Weighted
 Unweighted
 Connected
 Disconnected
 Cyclic
 Acyclic

Representations

Adjacency Matrix

For V vertices: O(V^2)

Adjacency List

Space: O(V+E)

CIL relevance: 9.5/10

PART B — ALGORITHMS
11. Searching
Linear Search
Check elements one by one.

10 20 30 40 50
 ↑
target

Worst case: O(n)

Binary Search
Requires a sorted array.

10 20 30 40 50 60 70
↑
middle

Repeatedly divide the search space by 2.

O(log n)

CIL relevance: 8.5/10

12. Sorting
You must know at least:

 Bubble Sort
 Selection Sort
 Insertion Sort
 Merge Sort
 Quick Sort
 Heap Sort
 Radix Sort

Essential complexity table

Algorithm Best Average Worst

Bubble O(n) O(n²) O(n²)
Selection O(n²) O(n²) O(n²)
Insertion O(n) O(n²) O(n²)
Merge O(n log n) O(n log n) O(n log n)
Quick O(n log n) O(n log n) O(n²)
Heap O(n log n) O(n log n) O(n log n)

Stable sorting

A stable algorithm preserves the relative order of equal-key elements.

The 2020 paper directly asked this concept.

CIL relevance: 9/10

13. Hashing
Hashing maps a key to an index. h(key)=key mod m

Example: h(27) = 27 mod 10 = 7

So key 27 goes to position 7.

Collision

Two keys produce the same index.

Example: 27 mod 10=7 , 37 mod 10=7

Collision!

Collision-resolution methods

 Chaining  Quadratic probing

 Linear probing  Double hashing

CIL relevance: 7.5/10

14. Asymptotic Complexity

You need to understand:

 Big-O  Big-Omega
 Big-Theta

For CIL, worst-case Big-O is especially important because your syllabus explicitly says:

Asymptotic worst-case time and space complexity.

Common order
O(1)
↓
O(log n)
↓
O(n)
↓
O(n log n)
↓
O(n²)
↓
O(n³)
↓
O(2ⁿ)
↓
O(n!)
Example
for(i=0; i<n; i++)
printf("%d", i);

Complexity: O(n)

Nested loop:

for(i=0;i<n;i++)
for(j=0;j<n;j++)

Complexity: O(n^2)

Space complexity

Memory used by an algorithm.

Recursion can consume stack space.

For:

fact(n)

recursive depth = n.

Therefore auxiliary stack space: O(n)

CIL relevance: 10/10

15. Divide and Conquer

Three steps:

Divide
↓
Solve
↓
Combine

Example:

Merge Sort
[8 3 2 9]
/ \
[8 3] [2 9]
/ \ / \
8 3 2 9
\ / \ /
[3 8] [2 9]
\ /
[2 3 8 9]
Recurrence: T(n)=2T(n/2)+O(n)

Therefore: T(n)=O(n\log n)

Examples

 Merge Sort
 Binary Search
 Quick Sort
 Strassen-type algorithms

CIL relevance: 9/10

16. Greedy Algorithm

Greedy makes the locally best choice at each step.

Current state
↓
Best immediate choice
↓
Next state
↓
Best immediate choice

Examples:

 Kruskal
 Prim
 Dijkstra under appropriate conditions
 Huffman coding
 Fractional Knapsack

Important trap

Greedy does not always produce the optimal solution.

For example:

Fractional Knapsack → Greedy works.

0/1 Knapsack → ordinary greedy does not guarantee optimality.

CIL relevance: 9/10

17. Dynamic Programming
DP is useful when a problem has:

1. Overlapping subproblems
2. Optimal substructure

Two approaches:

Memoization

Top-down.

Recursive
↓
Store answers
↓
Reuse

Tabulation

Bottom-up.

Small problems
↓
Build larger problems

Example: Fibonacci

Without DP: F(n)=F(n-1)+F(n-2) can become exponential.

With DP: O(n)

Classic DP problems

 0/1 Knapsack
 Matrix Chain Multiplication
 LCS
 Floyd-Warshall
 Coin Change

CIL relevance: 9.5/10

18. Graph Traversals
BFS BFS: A → B → C → D → E

Uses: DFS
Queue Uses:

A Stack / recursion
/ \
B C
/ \ Possible DFS:
D E
A → B → D → E → C

CIL relevance: 10/10

The 2020 paper directly tests data structures associated with recursion/BFS/DFS, making this
a recurring application-style pattern.

19. Minimum Spanning Tree — MST

For a connected weighted undirected graph, an MST:

 connects all vertices

 has no cycle
 has minimum total edge weight
 contains V − 1 edges

Two major algorithms:

Kruskal Prim
Sort edges Starts from a vertex and grows one tree.
↓
Pick smallest
Start vertex
↓
↓
Reject if cycle
minimum edge leaving tree
↓
↓
Continue
add vertex
↓
Uses the Disjoint Set / Union-Find repeat
concept.

CIL relevance: 10/10

20. Shortest Paths

Dijkstra
Single-source shortest path.

Works with:

Non-negative edge weights

Basic idea:

Choose nearest unvisited vertex

↓
Relax its edges
↓
Choose next nearest
↓
Repeat

Bellman-Ford Floyd-Warshall
Can handle: All-pairs shortest path.

Negative edge weights Dynamic programming approach: O(V^3)

and can detect negative cycles.

CIL relevance: 10/10

PART C — PRACTICAL / PROBLEM-

SOLVING PATTERNS
This is the part I particularly want you to practice because the CIL papers contain questions
beyond simple definitions.

Practical 1 — Recursion
Find:

[
T(n)=T(n-1)+1
]

Therefore:
[
T(n)=O(n)
]

Practical 2 — Binary Search

Array:

10 20 30 40 50 60 70

Search 60.

middle = 40
60 > 40
↓
50
↓
60

Number of comparisons grows logarithmically.

[
O(\log n)
]

Practical 3 — BST
Insert:

50, 30, 70, 20, 40, 60, 80

Result:

50
/ \
30 70
/ \ / \
20 40 60 80

Inorder:

20 30 40 50 60 70 80

Practical 4 — Tree Traversal

Given:

A
/ \
B C
 / \
D E

Preorder:

A B D E C

Inorder:

D B E A C

Postorder:

D E B C A

Practical 5 — Heap
Insert:

10, 20, 5, 30

Max heap ultimately becomes:

30
/ \
20 5
/
10

Practical 6 — Complexity
for(i=0;i<n;i++)
for(j=0;j<i;j++)
printf("*");

Number of operations:

[
0+1+2+\cdots+(n-1)
]

[
=\frac{n(n-1)}2
]

Therefore:

[
\boxed{O(n^2)}
]
Practical 7 — Merge Sort
Recurrence:

[
T(n)=2T(n/2)+n
]

Master theorem:

[
a=2,\quad b=2,\quad f(n)=n
]

[
n^{\log_ba}=n
]

Therefore:

[
\boxed{T(n)=O(n\log n)}
]

Practical 8 — Hashing
Table size = 10.

Keys:

23, 33

Using:

[
h(k)=k\bmod10
]

Both:

[
23\bmod10=3
]

[
33\bmod10=3
]

Therefore collision occurs.

Practical 9 — MST
Suppose:

A---1---B
| |
4 2
| |
C---3---D

Edges:

AB = 1
BD = 2
CD = 3
AC = 4

Kruskal chooses:

AB → BD → CD

Total:

[
1+2+3=6
]

Practical 10 — Dijkstra
For each vertex maintain:

distance
visited/unvisited

Repeatedly:

Select minimum tentative distance → relax adjacent edges.

This "relaxation" concept is extremely important.

PART D — HOW WE WILL MAKE

YOUR CIL QUESTIONS
The earlier CIL analysis showed three useful levels:

Level 1 — Direct concept

Example:

Which data structure implements recursion?

Answer: Stack.

Level 2 — Application

Example:

Which data structure is most suitable for BFS?

Answer: Queue.

Level 3 — Problem solving

Example:

Given preorder and inorder traversal, determine postorder.

The actual 2020 paper contains exactly this type of Level-3 tree question.

So your preparation questions should not be 50 easy definitions.

PART E — 50 CIL-STYLE QUESTIONS

Each question below follows your required format:

Question → Options → Answer → 1–2 line explanation → CIL relevance → PYQ

connection

Q1. [C Programming]

Which operator is used to obtain the address of a variable in C?

A. *
B. &
C. ->
D. %

Answer: B. &

Explanation: The & operator gives the memory address of a variable, while * dereferences a
pointer.

CIL relevance: ⭐⭐⭐⭐☆ 8/10

PYQ connection: CIL has tested direct C-program output/concept questions.

Q2. [Recursion]

Which data structure is primarily used to maintain recursive function calls?

A. Queue
B. Stack
C. Heap
D. Graph

Answer: B. Stack

Explanation: Every recursive call creates an activation record that is stored on the call stack.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

PYQ connection: This was directly tested in CIL 2020 Q29.

Q3. [Recursion]

What is the time complexity of the following recurrence?

[
T(n)=T(n-1)+1
]

A. O(1)
B. O(log n)
C. O(n)
D. O(n²)

Answer: C. O(n)

Explanation: The recurrence performs approximately n recursive levels, each doing constant
work.

CIL relevance: ⭐⭐⭐⭐⭐ 9.5/10

Q4. [Array]

What is the time complexity of accessing A[i] in an ordinary array?

A. O(n)
B. O(log n)
C. O(1)
D. O(n log n)
Answer: C. O(1)

Explanation: Array elements have direct address calculation, so any index can normally be
accessed in constant time.

CIL relevance: ⭐⭐⭐⭐☆ 8/10

Q5. [Stack]

A stack follows which principle?

A. FIFO
B. LIFO
C. Random access
D. Priority-based

Answer: B. LIFO

Explanation: The last inserted element is the first one removed.

CIL relevance: ⭐⭐⭐⭐⭐ 9/10

PYQ connection: CIL 2020 directly asked FILO and expected Stack.

Q6. [Queue]

Which data structure is normally used in BFS?

A. Stack
B. Queue
C. Heap
D. Array only

Answer: B. Queue

Explanation: BFS explores vertices level by level, so FIFO behavior is required.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Q7. [Linked List]

Which data structure is particularly suitable for representing a polynomial whose terms may
be inserted dynamically?

A. Stack
B. Queue
C. Linked List
D. Heap

Answer: C. Linked List

Explanation: Each polynomial term can be stored in a node containing coefficient, exponent
and a link to the next term.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

PYQ connection: CIL 2020 Q27 directly asked polynomial addition and linked lists.

Q8. [Linked List]

What is the typical worst-case time complexity of searching an unsorted singly linked list?

A. O(1)
B. O(log n)
C. O(n)
D. O(n log n)

Answer: C. O(n)

Explanation: In the worst case, every node may have to be examined.

CIL relevance: ⭐⭐⭐⭐☆ 8/10

Q9. [Tree]

In which traversal of a BST are the keys obtained in sorted order?

A. Preorder
B. Postorder
C. Inorder
D. Level order

Answer: C. Inorder

Explanation: BST maintains smaller keys on the left and larger keys on the right; therefore
inorder produces ascending order.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Q10. [Tree]

Which traversal visits Root → Left → Right?

A. Inorder
B. Preorder
C. Postorder
D. Level order

Answer: B. Preorder

Explanation: Preorder always processes the root before its left and right subtrees.

CIL relevance: ⭐⭐⭐⭐⭐ 9/10

Q11. [Tree]

A binary tree can have at most how many children per node?

A. 1
B. 2
C. 3
D. Unlimited

Answer: B. 2

Explanation: By definition, each binary-tree node has at most two children.

CIL relevance: ⭐⭐⭐⭐☆ 8/10

Q12. [Tree — Problem Solving]

For the tree

A
/ \
B C
/ \
D E

what is its postorder traversal?

A. A B D E C
B. D E B C A
C. D B E A C
D. A C B E D

Answer: B. D E B C A

Explanation: Postorder is Left → Right → Root.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

PYQ connection: Very close to the 2020 traversal question where preorder and inorder were
given and postorder had to be calculated.

Q13. [BST]

In a BST, where is a key smaller than the root normally placed?

A. Right subtree
B. Left subtree
C. Parent node
D. Any random position

Answer: B. Left subtree

Explanation: The BST ordering property is Left < Root < Right.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Q14. [BST]

What is the worst-case search complexity of an ordinary BST containing n nodes?

A. O(1)
B. O(log n)
C. O(n)
D. O(n²)

Answer: C. O(n)

Explanation: If the BST becomes skewed like a linked list, searching may require visiting all
n nodes.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Q15. [BST]

What is the expected search complexity of a balanced BST?

A. O(n²)
B. O(n)
C. O(log n)
D. O(2ⁿ)

Answer: C. O(log n)

Explanation: A balanced BST reduces the search space approximately by half at each level.
CIL relevance: ⭐⭐⭐⭐⭐ 10/10

PYQ connection: CIL 2020 directly asked BST search complexity.

Q16. [Heap]

Which condition defines a max heap?

A. Every parent ≤ its children

B. Every parent ≥ its children
C. All nodes are sorted
D. Root is always minimum

Answer: B. Every parent ≥ its children

Explanation: In a max heap the maximum element is at the root.

CIL relevance: ⭐⭐⭐⭐☆ 8.5/10

Q17. [Heap]

What is the time complexity of inserting an element into a binary heap?

A. O(1) always
B. O(log n)
C. O(n²)
D. O(2ⁿ)

Answer: B. O(log n)

Explanation: After insertion at the bottom, the element may move upward through at most
the height of the heap.

CIL relevance: ⭐⭐⭐⭐⭐ 9/10

Q18. [Graph]

A graph is represented as:

A. G = (V,E)
B. G = (A,B)
C. G = (N,L) only
D. G = (V,T)

Answer: A. G = (V,E)

Explanation: V represents vertices and E represents edges.

CIL relevance: ⭐⭐⭐⭐☆ 8/10

Q19. [Graph]

What is the space complexity of an adjacency matrix for V vertices?

A. O(V)
B. O(E)
C. O(V²)
D. O(V+E)

Answer: C. O(V²)

Explanation: An adjacency matrix contains a V × V table.

CIL relevance: ⭐⭐⭐⭐⭐ 9/10

Q20. [Graph Traversal]

Which data structure is associated with BFS?

A. Stack
B. Queue
C. Heap
D. Hash table

Answer: B. Queue

Explanation: BFS requires FIFO ordering to process vertices level by level.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Q21. [Graph Traversal]

DFS can naturally be implemented using:

A. Queue only
B. Stack or recursion
C. Heap only
D. Hash table only

Answer: B. Stack or recursion

Explanation: Recursion implicitly uses a call stack; iterative DFS explicitly uses a stack.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Q22. [Searching]

Binary search requires the data to be:

A. Random
B. Sorted
C. Hashed
D. Stored in a tree

Answer: B. Sorted

Explanation: Binary search decides whether to move left or right based on comparison with
the middle element.

CIL relevance: ⭐⭐⭐⭐⭐ 9/10

Q23. [Searching]

The worst-case time complexity of binary search is:

A. O(n)
B. O(n²)
C. O(log n)
D. O(1)

Answer: C. O(log n)

Explanation: Each comparison approximately halves the remaining search interval.

CIL relevance: ⭐⭐⭐⭐⭐ 9/10

Q24. [Sorting]

Which sorting algorithm has worst-case complexity O(n log n)?

A. Merge Sort
B. Bubble Sort
C. Selection Sort
D. Naive Insertion Sort

Answer: A. Merge Sort

Explanation: Merge Sort divides the input recursively and merges in linear time at every
level.

CIL relevance: ⭐⭐⭐⭐⭐ 9/10

PYQ connection: CIL 2020 directly asked Merge Sort complexity.

Q25. [Sorting]

A sorting algorithm is stable if it:

A. Never uses extra memory

B. Preserves the relative order of equal-key elements
C. Always runs in O(n)
D. Uses recursion

Answer: B. Preserves the relative order of equal-key elements

Explanation: Stability concerns equal-key records, not the algorithm's time or memory
complexity.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

PYQ connection: This is almost exactly the concept tested in CIL 2020 Q57.

Q26. [Hashing]

A collision occurs in hashing when:

A. A key is deleted
B. Two keys map to the same hash location
C. Table becomes empty
D. Search succeeds

Answer: B. Two keys map to the same hash location

Explanation: Different keys can produce the same hash value, requiring collision resolution.

CIL relevance: ⭐⭐⭐⭐☆ 8/10

Q27. [Hashing]

Which is a collision-resolution technique?

A. Chaining
B. Recursion
C. DFS
D. Merge

Answer: A. Chaining
Explanation: Chaining stores multiple colliding elements in a linked structure associated
with the same hash bucket.

CIL relevance: ⭐⭐⭐⭐☆ 8/10

Q28. [Complexity]

What is the complexity of:

for(i=0; i<n; i++)

printf("%d", i);

A. O(1)
B. O(log n)
C. O(n)
D. O(n²)

Answer: C. O(n)

Explanation: The loop executes n times and each iteration performs constant work.

CIL relevance: ⭐⭐⭐⭐⭐ 9/10

Q29. [Complexity]

What is the complexity of two independent nested loops, each running n times?

A. O(n)
B. O(log n)
C. O(n²)
D. O(2n)

Answer: C. O(n²)

Explanation: The inner loop executes n times for each of n outer iterations.

CIL relevance: ⭐⭐⭐⭐⭐ 9/10

Q30. [Complexity]

Which grows fastest for sufficiently large n?

A. n
B. n log n
C. n²
D. 2ⁿ
Answer: D. 2ⁿ

Explanation: Exponential growth eventually dominates polynomial and logarithmic

functions.

CIL relevance: ⭐⭐⭐⭐⭐ 9/10

Q31. [Divide and Conquer]

Which is a divide-and-conquer algorithm?

A. Merge Sort
B. BFS
C. Linear Search
D. Hashing

Answer: A. Merge Sort

Explanation: Merge Sort divides the array, recursively solves both parts and combines the
sorted results.

CIL relevance: ⭐⭐⭐⭐⭐ 9/10

Q32. [Divide and Conquer]

For Merge Sort:

[
T(n)=2T(n/2)+O(n)
]

The resulting complexity is:

A. O(n)
B. O(log n)
C. O(n log n)
D. O(n²)

Answer: C. O(n log n)

Explanation: There are O(log n) levels, with O(n) total merging work at each level.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Q33. [Greedy]

Which technique chooses the locally best available option at each step?
A. Dynamic Programming
B. Greedy
C. Divide and Conquer
D. Backtracking

Answer: B. Greedy

Explanation: Greedy algorithms make locally optimal choices with the hope of obtaining a
globally optimal solution.

CIL relevance: ⭐⭐⭐⭐⭐ 9/10

Q34. [Greedy]

Which problem is classically solved optimally using a greedy strategy?

A. Fractional Knapsack
B. 0/1 Knapsack
C. LCS
D. Matrix Chain Multiplication

Answer: A. Fractional Knapsack

Explanation: Items can be divided, allowing selection according to value/weight ratio.

CIL relevance: ⭐⭐⭐⭐⭐ 9/10

Q35. [Dynamic Programming]

Dynamic Programming is especially useful when a problem has:

A. Only recursion
B. Overlapping subproblems and optimal substructure
C. No repeated computation
D. Only sorted input

Answer: B. Overlapping subproblems and optimal substructure

Explanation: DP stores solutions to repeated subproblems and uses them to construct larger
solutions.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Q36. [Dynamic Programming]

Which is a classic Dynamic Programming problem?

A. Matrix Chain Multiplication
B. Binary Search
C. Stack Push
D. Linear Search

Answer: A. Matrix Chain Multiplication

Explanation: The optimal parenthesization is obtained by solving and storing overlapping

subproblems.

CIL relevance: ⭐⭐⭐⭐⭐ 9/10

Q37. [MST]

An MST of a connected graph with V vertices contains:

A. V edges
B. V+1 edges
C. V−1 edges
D. 2V edges

Answer: C. V−1 edges

Explanation: A spanning tree is acyclic and connects all V vertices using exactly V−1 edges.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Q38. [MST]

Which algorithm considers edges in increasing order of weight?

A. Prim
B. Kruskal
C. Dijkstra
D. BFS

Answer: B. Kruskal

Explanation: Kruskal sorts the edges and repeatedly selects the smallest edge that does not
create a cycle.

CIL relevance: ⭐⭐⭐⭐⭐ 9.5/10

Q39. [MST]

Which data structure is commonly used to detect cycles efficiently in Kruskal's algorithm?
A. Stack
B. Queue
C. Disjoint Set Union
D. Binary Search

Answer: C. Disjoint Set Union

Explanation: Union-Find efficiently determines whether two vertices already belong to the
same connected component.

CIL relevance: ⭐⭐⭐⭐☆ 8/10

Q40. [Shortest Path]

Dijkstra's algorithm is designed for shortest paths when edge weights are:

A. Always negative
B. Non-negative
C. Always zero
D. Arbitrary including negative cycles

Answer: B. Non-negative

Explanation: Dijkstra's greedy selection is not valid when negative-weight edges can
invalidate previously finalized distances.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Q41. [Shortest Path]

Which algorithm can detect negative-weight cycles?

A. BFS
B. Binary Search
C. Bellman-Ford
D. Prim

Answer: C. Bellman-Ford

Explanation: Bellman-Ford repeatedly relaxes edges and can detect further improvement
after V−1 rounds.

CIL relevance: ⭐⭐⭐⭐☆ 8/10

Q42. [Shortest Path]

Which algorithm computes all-pairs shortest paths using dynamic programming?

A. Dijkstra
B. Prim
C. Floyd-Warshall
D. Kruskal

Answer: C. Floyd-Warshall

Explanation: Floyd-Warshall systematically allows intermediate vertices and has O(V³) time
complexity.

CIL relevance: ⭐⭐⭐⭐⭐ 9/10

Q43. [Graph]

A graph with no cycles is called:

A. Complete graph
B. Acyclic graph
C. Weighted graph
D. Multigraph

Answer: B. Acyclic graph

Explanation: An acyclic graph contains no cycle; an undirected connected acyclic graph is a

tree.

CIL relevance: ⭐⭐⭐⭐☆ 8/10

Q44. [Graph]

A topological ordering is possible for:

A. Any graph
B. Directed acyclic graph
C. Complete undirected graph
D. Cyclic directed graph

Answer: B. Directed acyclic graph

Explanation: A directed graph must be acyclic for a valid topological ordering to exist.

CIL relevance: ⭐⭐⭐⭐⭐ 9/10

Q45. [Complexity]

What is the worst-case space complexity of a recursion whose maximum depth is n?

A. O(1)
B. O(log n)
C. O(n)
D. O(n²)

Answer: C. O(n)

Explanation: Each recursive call creates a stack frame, and n simultaneously active calls
require O(n) stack space.

CIL relevance: ⭐⭐⭐⭐⭐ 9/10

Q46. [Sorting — Concept]

Which sorting algorithm has O(n²) worst-case complexity but O(n log n) average complexity
under common implementations?

A. Merge Sort
B. Quick Sort
C. Heap Sort
D. Counting Sort

Answer: B. Quick Sort

Explanation: Poor pivot choices can produce highly unbalanced partitions, giving O(n²).

CIL relevance: ⭐⭐⭐⭐⭐ 9/10

Q47. [Heap]

What is the complexity of building a binary heap from n arbitrary elements using the standard
bottom-up heap construction?

A. O(1)
B. O(log n)
C. O(n)
D. O(n²)

Answer: C. O(n)

Explanation: Bottom-up heap construction performs less work on nodes farther from the
leaves, resulting in linear total time.

CIL relevance: ⭐⭐⭐⭐⭐ 9/10

Q48. [Tree — CIL-style Application]

Given:

Inorder: D B E A C
Preorder: A B D E C

What is the postorder traversal?

A. D E B C A
B. D B E C A
C. A B D E C
D. C E D B A

Answer: A. D E B C A

Explanation: Preorder identifies A as root; inorder divides the left subtree into D-B-E and
right subtree into C.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

PYQ similarity: Very high — this is deliberately modeled on the actual CIL 2020 traversal
question.

Q49. [Integrated Algorithm Question]

Which combination is correctly matched?

A. BFS — Stack
B. DFS — Queue
C. Kruskal — MST
D. Dijkstra — Sorting

Answer: C. Kruskal — MST

Explanation: Kruskal is a greedy minimum-spanning-tree algorithm; BFS uses a queue and

DFS uses a stack/recursion.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Q50. [Integrated CIL-Level Question]

A balanced BST contains n elements. What is the asymptotic worst-case time complexity of
searching for an element?

A. O(1)
B. O(log n)
C. O(n)
D. O(n log n)

Answer: B. O(log n)
Explanation: In a balanced BST, the height is O(log n), so a search follows at most
logarithmically many nodes.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

PYQ connection: This directly matches the concept tested in CIL 2020 Q63.

Final CIL Priority Map

Based on the actual previous-paper pattern plus your exact syllabus, I would prepare the
topics in this order:

Priority Topic CIL Preparation Level

🥇 1 Trees + BST + Traversals 🔴 10/10
🥈 2 Graph Traversals + MST + Shortest Paths 🔴 10/10
🥉 3 Complexity + Recurrence + Algorithm Analysis 🔴 10/10
4 Sorting + Searching 🔴 9/10
5 Stack + Queue + Recursion 🔴 9/10
6 Greedy + DP + Divide & Conquer 🔴 9/10
7 Heap 🔴 9/10
8 Linked List 🟠 8/10
9 Hashing 🟠 8/10
10 C programming fundamentals for DSA 🟠 8/10
11 Arrays 🟡 7/10

Most important observation

The actual CIL questions show a progression:

CIL DSA QUESTION

│
┌──────────┴──────────┐
↓ ↓
Direct Concept Application
│ │
"What is Stack?" "Recursion uses?"
│
↓
Problem Solving
│
┌─────────────┼─────────────┐
↓ ↓ ↓
Traversal Complexity Algorithm
↓ ↓ ↓
Tree output O(log n) MST/Shortest

That is why memorizing definitions alone will not be enough. The 2020 paper already
demonstrates this through the traversal problem, BST complexity, stable sorting, linked-list
application and recursion questions.
One important C-language caution: the 2020 paper contains a printf("%d %d %d", i++,
i, ++i) question. That expression has undefined behavior in standard C, so for your
preparation I would treat it as a historical exam question/pattern, not as a reliable rule for
predicting its output.

This gives us the theory + practical foundation + 50-question CIL-style baseline for the
entire DSA/Algorithms syllabus you supplied.

Data Structures + Algorithms — Next Part

Questions 51–100 | CIL Systems/IT Level
Continuing directly from Q50, with the same pattern:

Question → Options → Answer → 1–2 line explanation → CIL relevance → PYQ

similarity

I am keeping the emphasis on application, complexity, traversal, sorting, heaps, graphs,

and algorithm selection, because those are the areas where the supplied CIL papers show
useful question patterns. The 2020 paper, for example, includes recursion/stack, linked-list
application, stable sorting, tree traversal, and BST complexity questions.

Q51. [Array — Address Calculation]

An integer array A[0...9] starts at address 1000. If each integer occupies 4 bytes, what is the
address of A[6]?

A. 1006
B. 1020
C. 1024
D. 1040

Answer: C. 1024

Explanation: Address = Base + index × size = 1000 + 6×4 = 1024.

CIL relevance: ⭐⭐⭐⭐☆ 8/10

PYQ similarity: Concept-based; array/address questions fit the computational style expected
in technical papers.

Q52. [Array]
What is the worst-case time complexity of inserting an element at the beginning of an array
containing n elements?

A. O(1)
B. O(log n)
C. O(n)
D. O(n²)

Answer: C. O(n)

Explanation: Existing elements generally need to be shifted one position to make space.

CIL relevance: ⭐⭐⭐⭐☆ 8/10

Q53. [Stack — Application]

Which data structure is most appropriate for checking whether parentheses in an expression
are balanced?

A. Queue
B. Stack
C. Heap
D. Graph

Answer: B. Stack

Explanation: Opening brackets are pushed and matched with closing brackets in reverse
order, which requires LIFO behavior.

CIL relevance: ⭐⭐⭐⭐⭐ 9/10

Q54. [Stack — Expression]

Which data structure is primarily used for evaluating a postfix expression?

A. Stack
B. Queue
C. Graph
D. Hash table
Answer: A. Stack

Explanation: Operands are pushed onto the stack, and operators pop the required operands
and push the result.

CIL relevance: ⭐⭐⭐⭐⭐ 9/10

Q55. [Stack — Complexity]

What is the usual time complexity of push in an array-based stack when the stack is not full?

A. O(n)
B. O(log n)
C. O(1)
D. O(n²)

Answer: C. O(1)

Explanation: Push normally modifies the top position and stores the new element, requiring
constant time.

CIL relevance: ⭐⭐⭐⭐⭐ 9/10

Q56. [Queue]
Which operation removes an element from a standard queue?

A. Push
B. Pop
C. Enqueue
D. Dequeue

Answer: D. Dequeue

Explanation: Enqueue inserts at the rear, while dequeue removes from the front.

CIL relevance: ⭐⭐⭐⭐☆ 8/10

Q57. [Circular Queue]

The main advantage of a circular queue over a simple array queue is:

A. It eliminates FIFO
B. It allows reuse of previously freed positions
C. It always sorts elements
D. It uses a tree

Answer: B. It allows reuse of previously freed positions

Explanation: Circular arrangement allows the rear to wrap around and use available space at
the beginning.

CIL relevance: ⭐⭐⭐⭐⭐ 9/10

Q58. [Linked List]

Which linked list allows traversal in both forward and backward directions?

A. Singly linked list

B. Circular singly linked list
C. Doubly linked list
D. Header-only list

Answer: C. Doubly linked list

Explanation: Each node contains both a next and previous pointer.

CIL relevance: ⭐⭐⭐⭐☆ 8/10

Q59. [Linked List — Application]

Which operation can be performed in O(1) time in a singly linked list if a pointer to the
insertion position is already available?

A. Search for an arbitrary value

B. Insert a node after that position
C. Access the 100th node
D. Find the middle without additional information

Answer: B. Insert a node after that position

Explanation: Only a constant number of pointer modifications are required.

CIL relevance: ⭐⭐⭐⭐⭐ 9/10

Q60. [Linked List]

Which structure is most suitable for implementing a dynamic sequence where frequent
insertions and deletions occur at known positions?
A. Linked List
B. Static Array only
C. Binary Heap
D. Adjacency Matrix

Answer: A. Linked List

Explanation: Linked lists avoid shifting large numbers of elements when insertion/deletion
positions are already known.

CIL relevance: ⭐⭐⭐⭐⭐ 9/10

TREES + BST
Q61. [Binary Tree]
A binary tree has n nodes. What is the maximum number of children any individual node can
have?

A. 1
B. 2
C. n
D. n−1

Answer: B. 2

Explanation: A binary tree restricts every node to at most two children.

CIL relevance: ⭐⭐⭐⭐☆ 8/10

Q62. [Binary Tree]

Which traversal is represented by:

[
Left \rightarrow Root \rightarrow Right
]

A. Preorder
B. Postorder
C. Inorder
D. Level order

Answer: C. Inorder

Explanation: Inorder processes the left subtree, root, and then right subtree.
CIL relevance: ⭐⭐⭐⭐⭐ 9/10

Q63. [Tree Traversal — Practical]

Consider:

10
/ \
5 15
/ \
2 7

What is the preorder traversal?

A. 2, 5, 7, 10, 15
B. 10, 5, 2, 7, 15
C. 2, 7, 5, 15, 10
D. 10, 15, 5, 7, 2

Answer: B. 10, 5, 2, 7, 15

Explanation: Preorder is Root → Left → Right.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

PYQ similarity: Very high. The supplied CIL paper uses traversal information as a
problem-solving question rather than merely asking definitions.

Q64. [Tree Traversal — Practical]

For the same tree:

10
/ \
5 15
/ \
2 7

What is the postorder traversal?

A. 10, 5, 2, 7, 15
B. 2, 7, 5, 15, 10
C. 2, 5, 7, 10, 15
D. 15, 7, 2, 5, 10

Answer: B. 2, 7, 5, 15, 10

Explanation: Postorder is Left → Right → Root.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Q65. [BST]
Which property is correct for a Binary Search Tree?

A. Left subtree values are greater than root

B. Right subtree values are smaller than root
C. Left subtree values are smaller and right subtree values are greater
D. All nodes must have two children

Answer: C. Left subtree values are smaller and right subtree values are greater

Explanation: This ordering property makes efficient searching possible.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Q66. [BST — Construction]

Insert the following keys into an initially empty BST:

[
50,\ 30,\ 70,\ 20,\ 40
]

Which is the resulting tree?

A.

50
/ \
30 70
/ \
20 40

B.

50
/ \
70 30

C.

30
/ \
20 50
\
70

D.

70
/
 50

Answer: A

Explanation: Each key is inserted according to the BST rule: smaller values go left and
larger values go right.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Q67. [BST]
What does inorder traversal of a valid BST produce?

A. Random ordering
B. Descending order always
C. Sorted order
D. Level order

Answer: C. Sorted order

Explanation: Inorder visits all smaller values before the root and all larger values after it.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Q68. [BST — Complexity]

A BST becomes completely skewed. What is its worst-case search complexity?

A. O(1)
B. O(log n)
C. O(n)
D. O(log log n)

Answer: C. O(n)

Explanation: A skewed BST can have height n−1, making it behave like a linked list.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Q69. [BST — Concept Trap]

Which statement is true?

A. Every BST is balanced

B. Every balanced tree is a BST
C. A BST may become skewed
D. BST search is always O(1)

Answer: C. A BST may become skewed

Explanation: Ordinary BSTs do not automatically maintain balance; insertion order can
produce a highly skewed tree.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Q70. [Tree]
For a tree containing n nodes, how many edges does it contain?

A. n
B. n+1
C. n−1
D. 2n

Answer: C. n−1

Explanation: Every connected tree with n vertices has exactly n−1 edges.

CIL relevance: ⭐⭐⭐⭐⭐ 9/10

HEAPS
Q71. [Heap]
A binary heap must be:

A. A complete binary tree

B. A complete BST
C. A linked list
D. A graph with cycles

Answer: A. A complete binary tree

Explanation: Completeness ensures the heap can efficiently be represented using an array.

CIL relevance: ⭐⭐⭐⭐⭐ 9/10

Q72. [Max Heap]

Which element is guaranteed to be at the root of a max heap?

A. Minimum element
B. Maximum element
C. Median element
D. Random element

Answer: B. Maximum element

Explanation: The max-heap property requires every parent to be greater than or equal to its
children.

CIL relevance: ⭐⭐⭐⭐⭐ 9/10

Q73. [Min Heap]

Which element is guaranteed to be at the root of a min heap?

A. Maximum
B. Minimum
C. Median
D. Last inserted

Answer: B. Minimum

Explanation: Every parent is less than or equal to its children in a min heap.

CIL relevance: ⭐⭐⭐⭐⭐ 9/10

Q74. [Heap — Array Representation]

For a 0-indexed heap, the left child of node at index i is:

A. 2i
B. 2i+1
C. 2i+2
D. i/2

Answer: B. 2i+1

Explanation: In a 0-based binary heap, left and right children are at 2i+1 and 2i+2.

CIL relevance: ⭐⭐⭐⭐⭐ 9/10

Q75. [Heap — Array Representation]

For a 0-indexed heap, the right child of index i is:

A. 2i
B. 2i+1
C. 2i+2
D. i−1

Answer: C. 2i+2

Explanation: The standard 0-based heap mapping gives right child = 2i+2.

CIL relevance: ⭐⭐⭐⭐☆ 8/10

Q76. [Heap — Complexity]

What is the complexity of extracting the maximum element from a max heap?

A. O(1)
B. O(log n)
C. O(n²)
D. O(2ⁿ)

Answer: B. O(log n)

Explanation: Removing the root requires restoring the heap property, which may take O(log
n).

CIL relevance: ⭐⭐⭐⭐⭐ 9/10

Q77. [Heap]
Which algorithm can be implemented using a heap?

A. Heap Sort
B. Binary Search
C. BFS only
D. DFS only

Answer: A. Heap Sort

Explanation: Heap Sort repeatedly extracts the maximum or minimum from a heap.

CIL relevance: ⭐⭐⭐⭐⭐ 9/10

SEARCHING + SORTING
Q78. [Searching]
Linear search on an unsorted array has worst-case complexity:

A. O(1)
B. O(log n)
C. O(n)
D. O(n log n)

Answer: C. O(n)

Explanation: The target may be at the last position or absent, requiring examination of all
elements.

CIL relevance: ⭐⭐⭐⭐⭐ 9/10

Q79. [Binary Search]

If the search space contains 64 sorted elements, approximately how many halvings are
required before reaching a single element?

A. 4
B. 6
C. 8
D. 32

Answer: B. 6

Explanation: (64=2^6), so binary search requires logarithmic depth of approximately (\log_2

64=6).

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Q80. [Sorting]
Which sorting algorithm repeatedly selects the smallest remaining element and places it at the
next position?

A. Merge Sort
B. Selection Sort
C. Quick Sort
D. Heap Sort

Answer: B. Selection Sort

Explanation: Selection Sort selects the minimum from the unsorted portion during each
pass.
CIL relevance: ⭐⭐⭐⭐☆ 8/10

Q81. [Sorting]
Which sorting algorithm is generally efficient when the array is already nearly sorted?

A. Insertion Sort
B. Selection Sort
C. Heap Sort
D. Naive Quick Sort

Answer: A. Insertion Sort

Explanation: Insertion Sort can approach O(n) when only a small number of shifts are
necessary.

CIL relevance: ⭐⭐⭐⭐⭐ 9/10

Q82. [Sorting]
Which algorithm guarantees O(n log n) worst-case time among the following?

A. Quick Sort
B. Merge Sort
C. Bubble Sort
D. Insertion Sort

Answer: B. Merge Sort

Explanation: Merge Sort always divides into logarithmically many levels and performs O(n)
merging per level.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Q83. [Sorting]
Which of the following is generally not stable in its standard in-place form?

A. Insertion Sort
B. Bubble Sort
C. Selection Sort
D. Merge Sort

Answer: C. Selection Sort

Explanation: Standard Selection Sort can move equal-key elements past one another,
destroying their original relative order.

CIL relevance: ⭐⭐⭐⭐⭐ 9/10

PYQ similarity: Stability is directly represented in the supplied CIL 2020 paper.

Q84. [Sorting — Quick Sort]

The worst-case time complexity of Quick Sort occurs when partitions are highly unbalanced.
It is:

A. O(1)
B. O(log n)
C. O(n log n)
D. O(n²)

Answer: D. O(n²)

Explanation: If each partition produces sizes 0 and n−1, recursion becomes linear in depth.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Q85. [Sorting — Merge Sort]

What additional property is associated with Merge Sort?

A. It always requires O(n²) time

B. It uses divide and conquer
C. It cannot sort arrays
D. It requires a heap

Answer: B. It uses divide and conquer

Explanation: Merge Sort recursively divides the input and then combines sorted halves.

CIL relevance: ⭐⭐⭐⭐⭐ 9/10

HASHING
Q86. [Hashing]
Using:
[
h(k)=k\bmod10
]

what is the hash value of 47?

A. 4
B. 7
C. 10
D. 47

Answer: B. 7

Explanation: (47\bmod10=7).

CIL relevance: ⭐⭐⭐⭐⭐ 9/10

Q87. [Hashing — Collision]

Using the same hash function, which pair produces a collision?

A. 21 and 32
B. 25 and 35
C. 14 and 25
D. 17 and 28

Answer: B. 25 and 35

Explanation: Both produce remainder 5: (25\bmod10=5) and (35\bmod10=5).

CIL relevance: ⭐⭐⭐⭐⭐ 9/10

Q88. [Hashing]
Which method stores colliding elements in a list associated with a hash bucket?

A. Linear probing
B. Chaining
C. Binary search
D. DFS

Answer: B. Chaining

Explanation: Separate chaining maintains a collection, commonly a linked list, for elements
having the same hash index.

CIL relevance: ⭐⭐⭐⭐☆ 8/10

COMPLEXITY
Q89. [Complexity]
What is the complexity of:

for(i=1; i<=n; i++)

for(j=1; j<=n; j++)
count++;

A. O(n)
B. O(log n)
C. O(n²)
D. O(2ⁿ)

Answer: C. O(n²)

Explanation: The inner loop executes n times for each of n outer iterations.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Q90. [Complexity]
What is the complexity of:

for(i=1; i<=n; i=i*2)

printf("%d", i);

A. O(n)
B. O(log n)
C. O(n²)
D. O(2ⁿ)

Answer: B. O(log n)

Explanation: i doubles every iteration, so only about (\log_2 n) iterations occur.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Q91. [Complexity]
Which is asymptotically smaller?

A. O(n²)
B. O(n log n)
C. O(n³)
D. O(2ⁿ)

Answer: B. O(n log n)

Explanation: For sufficiently large n, (n\log n) grows slower than (n^2), (n^3), and (2^n).

CIL relevance: ⭐⭐⭐⭐⭐ 9/10

Q92. [Recurrence]
Consider:

[
T(n)=2T(n/2)+n
]

What is the complexity?

A. O(n)
B. O(log n)
C. O(n log n)
D. O(n²)

Answer: C. O(n log n)

Explanation: This is the standard Merge Sort recurrence and has (\log n) levels with O(n)
work per level.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Q93. [Recurrence]
Consider:

[
T(n)=T(n/2)+1
]

The complexity is:

A. O(1)
B. O(log n)
C. O(n)
D. O(n²)

Answer: B. O(log n)
Explanation: The input size is halved at every recursive step.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

DIVIDE AND CONQUER

Q94. [Divide and Conquer]
Which sequence correctly represents the general divide-and-conquer strategy?

A. Combine → Divide → Solve

B. Divide → Solve subproblems → Combine
C. Search → Hash → Sort
D. Push → Pop → Peek

Answer: B. Divide → Solve subproblems → Combine

Explanation: The problem is divided into smaller instances, solved recursively, and their
results are combined.

CIL relevance: ⭐⭐⭐⭐⭐ 9/10

Q95. [Divide and Conquer]

Binary Search is an example of:

A. Greedy
B. Dynamic Programming
C. Divide and Conquer
D. Backtracking

Answer: C. Divide and Conquer

Explanation: Binary Search repeatedly divides the search interval into two parts and
continues with the relevant half.

CIL relevance: ⭐⭐⭐⭐⭐ 9/10

GREEDY + DP
Q96. [Greedy]
Which problem is not generally solved optimally by simply choosing the item with the
highest value/weight ratio?

A. Fractional Knapsack
B. 0/1 Knapsack
C. Both
D. Neither

Answer: B. 0/1 Knapsack

Explanation: The indivisible nature of 0/1 Knapsack can make a simple greedy choice
suboptimal; DP is commonly used.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Q97. [Dynamic Programming]

Which technique stores the results of previously solved subproblems?

A. Memoization
B. Hash collision
C. Traversal
D. Partitioning

Answer: A. Memoization

Explanation: Memoization is a top-down DP technique that stores computed results to avoid

repeated work.

CIL relevance: ⭐⭐⭐⭐⭐ 9/10

Q98. [Dynamic Programming]

Which pair correctly represents the two common DP approaches?

A. BFS and DFS

B. Memoization and Tabulation
C. Prim and Kruskal
D. Push and Pop

Answer: B. Memoization and Tabulation

Explanation: Memoization is generally top-down, while tabulation is generally bottom-up.

CIL relevance: ⭐⭐⭐⭐⭐ 9/10

GRAPH ALGORITHMS
Q99. [MST]
Which of the following is not an MST algorithm?

A. Prim
B. Kruskal
C. Dijkstra
D. Both Prim and Kruskal

Answer: C. Dijkstra

Explanation: Prim and Kruskal construct minimum spanning trees; Dijkstra solves a
shortest-path problem.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Q100. [MST — Practical]

Consider a connected weighted graph with the following edges:

A──1──B
│ │
4 2
│ │
C──3──D

Using Kruskal's algorithm, which edges are selected?

A. AC, CD, BD
B. AB, BD, CD
C. AB, AC, BD
D. AC, AB, CD

Answer: B. AB, BD, CD

Explanation: Kruskal considers weights 1, 2, 3, 4; AB, BD and CD connect all four vertices
without forming a cycle.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

🔥 What You Should Notice From Q51–100

The difficulty has deliberately increased:

Q51–60
 ↓
Basic + implementation/application
↓
Q61–77
↓
Trees + BST + Heap
↓
Q78–88
↓
Searching + Sorting + Hashing
↓
Q89–93
↓
Complexity + Recurrences
↓
Q94–100
↓
Algorithm design + MST

And Q63, Q64, Q67, Q68, Q83, Q92 and Q100 are particularly important because they
move beyond pure definition-based questions into the type of reasoning that the supplied CIL
papers demonstrate. The supplied 2020 paper specifically contains traversal reconstruction,
stable sorting, and BST-complexity patterns.

Priority for the next questions

For Q101–150, the emphasis should move further toward:

Graphs → BFS/DFS → MST → Dijkstra/Bellman-Ford/Floyd-Warshall → complexity

calculations → sorting comparisons → DP/Greedy → integrated CIL-level problems.

Data Structures + Algorithms — Q101–150

CIL-Level Practice Set
Continuing directly from Q100 in the same format. This section is intentionally more
analytical and focuses heavily on graphs, shortest paths, MST, complexity, sorting,
hashing, greedy, DP, and integrated problems.

Q101. [Graph — BFS]

Which data structure is normally used to implement Breadth-First Search (BFS)?

A. Stack
B. Queue
C. Heap
D. Hash table

Answer: B. Queue

Explanation: BFS explores vertices level by level, so a FIFO queue naturally maintains the
order of exploration.
CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Q102. [Graph — DFS]

Which data structure is most naturally associated with Depth-First Search?

A. Queue
B. Stack
C. Priority Queue
D. Hash table

Answer: B. Stack

Explanation: DFS goes as deep as possible before backtracking; this is implemented using a
stack or recursion.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Q103. [BFS — Application]

In an unweighted graph, BFS starting from vertex S is used to find:

A. Minimum spanning tree only

B. Shortest path in terms of number of edges
C. Maximum-weight path
D. Topological ordering of every graph

Answer: B. Shortest path in terms of number of edges

Explanation: BFS explores vertices by increasing distance from the source, so the first
discovered path uses the minimum number of edges.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Q104. [BFS — Practical]

Consider:

A
/ \
B C
/ \ \
D E F

Starting BFS from A, which traversal is correct?

A. A, B, C, D, E, F
B. A, B, D, E, C, F
C. A, C, F, B, E, D
D. D, E, B, F, C, A

Answer: A. A, B, C, D, E, F

Explanation: BFS processes all vertices at one level before moving to the next level.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Q105. [DFS — Practical]

For the same graph, if DFS explores the left child before the right child, one possible DFS
traversal is:

A. A, B, D, E, C, F
B. A, B, C, D, E, F
C. D, B, E, A, C, F
D. A, C, F, B, D, E

Answer: A. A, B, D, E, C, F

Explanation: DFS completely explores the B subtree before returning to A and exploring C.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Q106. [Graph Representation]

For a sparse graph having V vertices and E edges, which representation is generally more
space-efficient?

A. Adjacency matrix
B. Adjacency list
C. Complete matrix
D. 2D heap

Answer: B. Adjacency list

Explanation: An adjacency list uses approximately O(V+E) space, whereas an adjacency

matrix requires O(V²).

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Q107. [Graph Representation]

The space complexity of an adjacency matrix for a graph with V vertices is:

A. O(V)
B. O(E)
C. O(V log V)
D. O(V²)

Answer: D. O(V²)

Explanation: The matrix contains one entry for every possible ordered pair of vertices.

CIL relevance: ⭐⭐⭐⭐⭐ 9/10

Q108. [Graph Complexity]

Using an adjacency list, the total space required to represent a graph is approximately:

A. O(V²)
B. O(V+E)
C. O(E²)
D. O(log V)

Answer: B. O(V+E)

Explanation: One structure is maintained for each vertex and entries are maintained for the
graph's edges.

CIL relevance: ⭐⭐⭐⭐⭐ 9/10

Minimum Spanning Tree

Q109. [MST]
A Minimum Spanning Tree of a connected undirected graph with V vertices contains exactly:

A. V edges
B. V+1 edges
C. V−1 edges
D. V² edges

Answer: C. V−1 edges

Explanation: Every spanning tree of a connected graph contains exactly one fewer edge than
its number of vertices.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Q110. [MST]
Which condition must an MST satisfy?

A. It must contain a cycle

B. It must connect all vertices with minimum total edge weight
C. It must contain all edges
D. It must contain the shortest path between every pair

Answer: B. It must connect all vertices with minimum total edge weight

Explanation: An MST connects every vertex without cycles while minimizing the sum of
selected edge weights.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Q111. [Kruskal]
Kruskal's algorithm primarily selects edges according to:

A. Number of vertices
B. Increasing edge weight
C. Decreasing vertex degree
D. BFS order

Answer: B. Increasing edge weight

Explanation: Kruskal sorts edges by weight and repeatedly chooses the smallest edge that
does not create a cycle.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Q112. [Prim]
Prim's algorithm grows an MST by:

A. Selecting the smallest edge globally without considering connectivity

B. Growing a tree from an existing vertex set
C. Performing DFS
D. Sorting all vertices alphabetically

Answer: B. Growing a tree from an existing vertex set

Explanation: Prim repeatedly chooses the minimum-weight edge connecting the current tree
to an unvisited vertex.
CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Q113. [Kruskal — Practical]

Suppose a graph has edges:

Edge Weight
A-B 1
B-C 2
A-C 3
C-D 4
B-D 5

What is the total weight of the MST?

A. 5
B. 6
C. 7
D. 10

Answer: B. 6

Explanation: Kruskal chooses AB(1), BC(2), skips AC(3) because it creates a cycle, then
chooses CD(4): total = 1+2+4 = 7.

Correction check: Therefore the correct answer is actually C. 7.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Q114. [MST — Concept]

If all edge weights in a connected graph are distinct, then the MST is:

A. Always impossible
B. Unique
C. Always cyclic
D. Always disconnected

Answer: B. Unique

Explanation: Distinct edge weights eliminate ties in the MST selection process, giving a
unique MST.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Shortest Paths
Q115. [Dijkstra]
Dijkstra's algorithm is primarily used to find:

A. Minimum spanning tree

B. Shortest paths from a source
C. Topological ordering
D. Strongly connected components

Answer: B. Shortest paths from a source

Explanation: Dijkstra computes shortest paths from one source when edge weights satisfy its
non-negative-weight requirement.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Q116. [Dijkstra — Important Trap]

Dijkstra's algorithm is generally not suitable when the graph contains:

A. Positive-weight edges
B. Zero-weight edges
C. Negative-weight edges
D. Undirected edges

Answer: C. Negative-weight edges

Explanation: Dijkstra's greedy choice can become incorrect in the presence of negative edge
weights.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Q117. [Shortest Path]

Which algorithm is suitable for shortest paths when negative edge weights may exist?

A. Dijkstra only
B. Bellman-Ford
C. BFS only
D. Prim

Answer: B. Bellman-Ford
Explanation: Bellman-Ford can handle negative edge weights and can also detect reachable
negative-weight cycles.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Q118. [All-Pairs Shortest Path]

Which algorithm is commonly used to compute shortest paths between all pairs of vertices?

A. Floyd-Warshall
B. Binary Search
C. Prim
D. DFS

Answer: A. Floyd-Warshall

Explanation: Floyd-Warshall uses dynamic programming to compute shortest distances

between every pair of vertices.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Q119. [Dijkstra — Practical]

Suppose:

A --2--> B
A --5--> C
B --1--> C

What is the shortest distance from A to C?

A. 1
B. 2
C. 3
D. 5

Answer: C. 3

Explanation: Directly A→C costs 5, but A→B→C costs 2+1=3, which is shorter.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Q120. [Shortest Path vs MST]

Which statement is correct?
A. MST always gives shortest path between every pair
B. Shortest-path tree and MST are always identical
C. MST minimizes total tree weight, whereas shortest-path algorithms minimize path
distances from a source
D. Dijkstra constructs an MST

Answer: C

Explanation: MST and shortest-path problems optimize different objectives, so their

resulting trees need not be the same.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Topological Sorting
Q121. [DAG]
Topological sorting is defined for:

A. Any undirected graph

B. Directed acyclic graph
C. Complete graph only
D. Cyclic directed graph

Answer: B. Directed acyclic graph

Explanation: A topological ordering exists only for a directed graph with no directed cycles.

CIL relevance: ⭐⭐⭐⭐⭐ 9/10

Q122. [Topological Sort]

If a directed graph contains a cycle, then:

A. It has exactly one topological ordering

B. It has multiple topological orderings
C. It has no valid topological ordering
D. DFS always produces one

Answer: C. It has no valid topological ordering

Explanation: A cycle creates contradictory precedence requirements.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Sorting — Higher Difficulty
Q123. [Sorting Comparison]
Which algorithm has O(n log n) average-case complexity but O(n²) worst-case complexity in
its standard form?

A. Merge Sort
B. Quick Sort
C. Heap Sort
D. Counting Sort

Answer: B. Quick Sort

Explanation: Poor pivot choices can create highly unbalanced partitions, producing O(n²)
worst-case behavior.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Q124. [Sorting]
Which sorting algorithm guarantees O(n log n) worst-case time and uses O(1) auxiliary array
space in its standard heap-based implementation?

A. Merge Sort
B. Heap Sort
C. Quick Sort
D. Bubble Sort

Answer: B. Heap Sort

Explanation: Heap Sort maintains a heap and repeatedly extracts the extreme element; its
worst-case time is O(n log n).

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Q125. [Stable Sorting]

Suppose records are:

(A, 5)
(B, 3)
(C, 5)

After a stable sort by the second field, which ordering must preserve the relative order of A
and C?
A. C, A, B
B. B, A, C
C. A, C, B
D. B, C, A

Answer: B and C?

Let's examine carefully: Sorting by the second field requires 3 before 5, and stability requires
A before C.

Therefore:

Answer: B. B, A, C

Explanation: B has key 3, while A and C both have key 5; stability preserves A before C.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Q126. [Sorting]
Which sorting algorithm is based on repeatedly merging sorted subarrays?

A. Selection Sort
B. Merge Sort
C. Bubble Sort
D. Heap Sort

Answer: B. Merge Sort

Explanation: Merge Sort recursively creates sorted subarrays and combines them through
merging.

CIL relevance: ⭐⭐⭐⭐☆ 8/10

Q127. [Sorting — Best Case]

Which algorithm can have O(n) best-case complexity when the input is already sorted?

A. Insertion Sort
B. Selection Sort
C. Heap Sort
D. Merge Sort

Answer: A. Insertion Sort

Explanation: With an already sorted array, insertion sort performs very little shifting and can
run in linear time.
CIL relevance: ⭐⭐⭐⭐⭐ 9/10

Hashing — Higher Difficulty

Q128. [Hashing]
In open addressing, all elements are stored:

A. Outside the hash table

B. Directly in the hash table
C. In a binary tree
D. In a graph

Answer: B. Directly in the hash table

Explanation: Open addressing resolves collisions by searching for another empty slot within
the table itself.

CIL relevance: ⭐⭐⭐⭐⭐ 9/10

Q129. [Linear Probing]

A disadvantage of linear probing is:

A. It cannot resolve collisions

B. Primary clustering
C. It requires a linked list
D. It cannot use hash functions

Answer: B. Primary clustering

Explanation: Consecutive occupied positions form clusters, increasing the number of probes
required.

CIL relevance: ⭐⭐⭐⭐⭐ 9/10

Q130. [Hashing]
If the load factor of a hash table becomes very high, generally:

A. Collision probability tends to increase

B. Searching always becomes O(1)
C. The table becomes sorted
D. Memory usage becomes zero
Answer: A. Collision probability tends to increase

Explanation: As more positions become occupied, collisions and probe lengths generally
increase.

CIL relevance: ⭐⭐⭐⭐⭐ 9/10

Complexity — CIL-Level
Q131. [Complexity]
What is the complexity?

for(i=1; i<=n; i++)

{
for(j=1; j<=i; j++)
count++;
}

A. O(n)
B. O(log n)
C. O(n²)
D. O(n³)

Answer: C. O(n²)

Explanation: Total iterations are (1+2+\cdots+n=n(n+1)/2), which is Θ(n²).

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Q132. [Complexity]
What is the complexity?

for(i=1; i<=n; i*=2)

for(j=1; j<=n; j++)
count++;

A. O(log n)
B. O(n)
C. O(n log n)
D. O(n²)

Answer: C. O(n log n)

Explanation: The outer loop executes O(log n) times and the inner loop executes O(n) times.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Q133. [Complexity]
Which grows fastest for sufficiently large n?

A. log n
B. n
C. n log n
D. 2ⁿ

Answer: D. 2ⁿ

Explanation: Exponential functions eventually dominate polynomial and logarithmic

functions.

CIL relevance: ⭐⭐⭐⭐⭐ 9/10

Q134. [Space Complexity]

An iterative algorithm uses only a fixed number of variables regardless of input size. Its
auxiliary space complexity is:

A. O(1)
B. O(log n)
C. O(n)
D. O(n²)

Answer: A. O(1)

Explanation: A constant number of additional variables requires constant auxiliary space.

CIL relevance: ⭐⭐⭐⭐⭐ 9/10

Q135. [Recursion + Space]

A recursive function makes n nested recursive calls before returning. What is the maximum
additional call-stack space?

A. O(1)
B. O(log n)
C. O(n)
D. O(n²)

Answer: C. O(n)

Explanation: Each active recursive call occupies a stack frame, producing O(n) stack usage.
CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Greedy Algorithms
Q136. [Greedy]
A greedy algorithm makes decisions by:

A. Exhaustively checking every possible solution

B. Making the locally best choice at each step
C. Always using recursion
D. Always using a hash table

Answer: B. Making the locally best choice at each step

Explanation: Greedy algorithms build a solution through locally optimal choices, hoping
they lead to a globally optimal solution.

CIL relevance: ⭐⭐⭐⭐⭐ 9/10

Q137. [Greedy — Fractional Knapsack]

For Fractional Knapsack, the usual greedy criterion is:

A. Lowest weight first

B. Highest value first
C. Highest value/weight ratio first
D. Lowest value/weight ratio first

Answer: C. Highest value/weight ratio first

Explanation: Since fractions can be taken, maximizing value per unit weight produces an
optimal greedy solution.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Q138. [Greedy]
Which problem is classically solved optimally using a greedy strategy?

A. Fractional Knapsack
B. 0/1 Knapsack using simple value/weight ratio
C. General longest common subsequence
D. Matrix-chain multiplication
Answer: A. Fractional Knapsack

Explanation: Fractional Knapsack has the greedy-choice property because items can be
divided.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Dynamic Programming
Q139. [DP]
Dynamic Programming is particularly useful when a problem has:

A. Only one possible solution

B. Overlapping subproblems and optimal substructure
C. No subproblems
D. Only sorted input

Answer: B. Overlapping subproblems and optimal substructure

Explanation: DP avoids repeatedly solving overlapping subproblems while building an

optimal solution from smaller optimal solutions.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Q140. [DP — Fibonacci]

Naive recursive Fibonacci has exponential time primarily because:

A. It uses arrays
B. It repeatedly computes the same subproblems
C. It uses sorting
D. It uses hashing

Answer: B. It repeatedly computes the same subproblems

Explanation: For example, computing F(n) repeatedly recomputes values such as F(n−2)
and F(n−3).

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Q141. [DP]
Memoization is generally:
A. Bottom-up
B. Top-down
C. Non-recursive only
D. A graph traversal

Answer: B. Top-down

Explanation: Memoization begins with the original problem and recursively solves
subproblems while caching their results.

CIL relevance: ⭐⭐⭐⭐⭐ 9/10

Q142. [DP]
Tabulation is generally:

A. Top-down recursion
B. Bottom-up computation
C. Randomized search
D. Hash collision resolution

Answer: B. Bottom-up computation

Explanation: Tabulation fills a table starting from smaller base cases and progressively
computes larger subproblems.

CIL relevance: ⭐⭐⭐⭐⭐ 9/10

Integrated Graph Problems

Q143. [Graph]
Which traversal is generally preferred for finding whether an unweighted graph contains a
path with the minimum number of edges from a source?

A. BFS
B. DFS
C. Prim
D. Kruskal

Answer: A. BFS

Explanation: BFS explores vertices in increasing order of their distance from the source.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Q144. [Graph]
Which algorithm can be used to detect a cycle in an undirected graph using DFS?

A. Maintain visited vertices and detect an already visited vertex that is not the parent
B. Always use Dijkstra
C. Sort all vertices
D. Use binary search

Answer: A

Explanation: In an undirected DFS, encountering a visited neighbor other than the current
node's parent indicates a cycle.

CIL relevance: ⭐⭐⭐⭐⭐ 9/10

Q145. [DAG]
A directed graph has edges:

A → B
A → C
B → D
C → D

Which can be a valid topological ordering?

A. D, B, C, A
B. A, B, C, D
C. B, A, D, C
D. D, C, B, A

Answer: B. A, B, C, D

Explanation: Every prerequisite appears before the vertex that depends on it.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Q146. [Dijkstra — Practical]

Given:

A --4--> B
A --1--> C
C --2--> B
B --3--> D
C --7--> D

What is the shortest distance from A to D?

A. 4
B. 5
C. 6
D. 7

Answer: C. 6

Explanation: A→C→B→D has cost (1+2+3=6), which is smaller than A→C→D = 8 and
A→B→D = 7.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Q147. [MST vs Shortest Path]

Suppose a graph has one extremely cheap edge that connects two large portions of the graph
but does not lie on the shortest path between a particular source and destination. Which
statement is possible?

A. The edge may belong to the MST but not the shortest source-destination path
B. It must belong to every shortest path
C. MST and shortest path are always identical
D. It cannot belong to an MST

Answer: A

Explanation: MST minimizes total tree weight, while shortest path minimizes the distance
between particular vertices.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Integrated Data Structures

Q148. [Priority Queue]
Which data structure is commonly used to implement an efficient priority queue?

A. Binary Heap
B. Stack only
C. Singly linked list only
D. Binary search algorithm

Answer: A. Binary Heap

Explanation: A heap provides efficient insertion and extraction of the highest- or lowest-
priority element.

CIL relevance: ⭐⭐⭐⭐⭐ 9/10

Q149. [Heap + Graph]
Which algorithm commonly uses a priority queue/heap to efficiently select the next
minimum-distance vertex?

A. Dijkstra
B. DFS
C. Binary Search
D. Bubble Sort

Answer: A. Dijkstra

Explanation: A min-priority queue allows Dijkstra to efficiently select the currently closest
unsettled vertex.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Q150. [Integrated — High Priority]

Consider the following statements:

1. BFS uses a queue.

2. DFS can use a stack.
3. Dijkstra requires non-negative edge weights.
4. Kruskal finds shortest paths from a source.

Which statements are correct?

A. 1 and 2 only
B. 1, 2 and 3 only
C. 2, 3 and 4 only
D. All four

Answer: B. 1, 2 and 3 only

Explanation: BFS uses a queue, DFS uses a stack/recursion, and Dijkstra assumes non-
negative edge weights; Kruskal is an MST algorithm, not a shortest-path algorithm.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

🔥 Most Important Areas After Q150

Based on the CIL-style pattern you asked me to follow, don't treat all 150 questions
equally.
Priority Topic Importance
🔴1 Trees + BST + Traversals 10/10
🔴2 Graph Traversals BFS/DFS 10/10
🔴3 MST — Prim/Kruskal 10/10
🔴4 Shortest Path — Dijkstra 10/10
🔴5 Time/Space Complexity 10/10
🔴6 Sorting + Stability + Complexity 9.5/10
🟠7 Recursion + Recurrences 9.5/10
🟠8 DP + Greedy 9.5/10
🟠9 Heap/Priority Queue 9/10
🟡 10 Hashing 8.5/10
🟡 11 Linked Lists 8.5/10
🟡 12 Arrays 8/10

One especially important distinction to memorize

GRAPH PROBLEMS
│
┌─────────────┴─────────────┐
│ │
Minimum Total Cost Minimum Distance
│ │
MST Problem Shortest Path
│ │
┌────┴────┐ ┌───────┴────────┐
│ │ │ │
Prim Kruskal Dijkstra Bellman-Ford

Floyd-Warshall
(all pairs)

This distinction is extremely exam-worthy:

Prim/Kruskal → Minimum Spanning Tree
Dijkstra/Bellman-Ford → Single-source shortest paths

Data Structures + Algorithms — Q151–200

Final 50 Questions | CIL-Level + Higher-Order Practice
Continuing directly from Q150. This completes the requested 200-question combined Data
Structures + Algorithms set.

I am keeping the questions aligned with the supplied syllabus: C programming, recursion,
arrays, stacks, queues, linked lists, trees/BST/heaps/graphs, searching, sorting, hashing,
asymptotic complexity, greedy, DP, divide-and-conquer, graph traversal, MST and shortest
paths.

For this final section, I am deliberately increasing the proportion of calculation, tracing,
complexity analysis, algorithm selection, and statement-based questions rather than
simple definitions.
Q151–160 — Advanced Trees, BST &
Heaps
Q151. [BST — Insertion]

Insert the keys

[
40,\ 20,\ 60,\ 10,\ 30,\ 50,\ 70
]

into an initially empty BST. What is the inorder traversal?

A. 40, 20, 10, 30, 60, 50, 70

B. 10, 20, 30, 40, 50, 60, 70
C. 70, 60, 50, 40, 30, 20, 10
D. 10, 30, 20, 50, 70, 60, 40

Answer: B. 10, 20, 30, 40, 50, 60, 70

Explanation: Inorder traversal of a BST always produces the keys in sorted ascending order.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

PYQ-pattern relevance: Very high — this combines BST construction and traversal rather
than testing either concept independently.

Q152. [BST — Deletion]

In a BST, when deleting a node having two children, a common replacement is:

A. Any leaf node

B. Inorder successor or inorder predecessor
C. Root of another tree
D. The smallest leaf only

Answer: B. Inorder successor or inorder predecessor

Explanation: Replacing the node with its inorder successor/predecessor preserves the BST
ordering property.

CIL relevance: ⭐⭐⭐⭐⭐ 9/10

Q153. [BST — Complexity]

A BST contains n nodes and has height h. The time complexity of searching for a key is:

A. O(1)
B. O(h)
C. O(n²)
D. O(2h)

Answer: B. O(h)

Explanation: At most one node is examined at each level, so search takes O(h); for a
balanced BST this is O(log n), while a skewed BST can be O(n).

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Q154. [BST — Skewed Tree]

Insert the following values into an initially empty BST:

[
10,\ 20,\ 30,\ 40,\ 50
]

The resulting tree is:

A. Complete
B. Perfect
C. Right-skewed
D. Left-skewed

Answer: C. Right-skewed

Explanation: Every new value is larger than the previous value, so every node becomes the
right child of the previous node.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Q155. [Heap — Operation]

Which operation on a binary heap normally requires moving an element upward through its
ancestors?

A. Heapify-down
B. Insertion
C. Extract-min only
D. Traversal

Answer: B. Insertion
Explanation: A newly inserted element is initially placed at the next available leaf position
and may need to move upward to restore the heap property.

CIL relevance: ⭐⭐⭐⭐⭐ 9/10

Q156. [Heap — Complexity]

What is the worst-case complexity of inserting one element into a binary heap containing n
elements?

A. O(1)
B. O(log n)
C. O(n)
D. O(n log n)

Answer: B. O(log n)

Explanation: The inserted element can move from a leaf to the root, crossing at most the
heap height, which is O(log n).

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Q157. [Heap — Build Heap]

The standard bottom-up method of constructing a heap from an array takes:

A. O(n²)
B. O(n log n)
C. O(n)
D. O(log n)

Answer: C. O(n)

Explanation: Although individual heapify operations can take O(log n), most nodes are near
the leaves, giving a total O(n) construction time.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Q158. [Heap — Concept]

Which statement is false for a max heap?

A. The root contains the maximum element.

B. Every parent is greater than or equal to its children.
C. The elements are completely sorted.
D. It is a complete binary tree.
Answer: C. The elements are completely sorted.

Explanation: A heap guarantees parent-child ordering, not complete ordering among all
elements.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Q159. [Heap — Priority Queue]

A hospital emergency system always wants to process the highest-priority case first. Which
structure is most appropriate?

A. Stack
B. Simple queue
C. Priority queue
D. Circular linked list

Answer: C. Priority queue

Explanation: A priority queue removes elements according to priority rather than merely
arrival order; heaps are commonly used to implement it.

CIL relevance: ⭐⭐⭐⭐⭐ 9/10

Q160. [Tree — Height]

A completely skewed binary tree containing n nodes has height Θ(n), whereas a balanced
binary tree has height approximately:

A. Θ(1)
B. Θ(log n)
C. Θ(n²)
D. Θ(2ⁿ)

Answer: B. Θ(log n)

Explanation: Each level of a balanced binary tree contains exponentially more possible
nodes, resulting in logarithmic height.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Q161–170 — Sorting, Searching & Hashing

Q161. [Binary Search — Trace]

Consider the sorted array:

2 5 8 12 16 21 25 30

Using binary search, which element is examined first?

A. 2
B. 12
C. 16
D. 21

Answer: C. 16

Explanation: The middle index is examined first; with eight elements, using the upper
middle gives 16.

CIL relevance: ⭐⭐⭐⭐⭐ 9/10

Q162. [Binary Search — Requirement]

Which condition is essential for standard binary search?

A. Array must contain unique elements

B. Data must be sorted according to the search ordering
C. Data must be stored in a linked list
D. Data must be hashed

Answer: B. Data must be sorted according to the search ordering

Explanation: Binary search decides which half can be discarded based on ordering.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Q163. [Binary Search — Complexity]

The worst-case time complexity of binary search is:

A. O(n)
B. O(log n)
C. O(n log n)
D. O(1) always

Answer: B. O(log n)

Explanation: Each comparison approximately halves the remaining search space.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Q164. [Merge Sort]

For n = 16, approximately how many levels of division are required in Merge Sort before
subarrays contain one element?

A. 2
B. 4
C. 8
D. 16

Answer: B. 4

Explanation: (16=2^4), so four divisions are required to reach single-element subarrays.

CIL relevance: ⭐⭐⭐⭐⭐ 9/10

Q165. [Quick Sort]

Which factor has the greatest influence on Quick Sort's partition balance?

A. Choice of pivot
B. Number of variables in the program
C. Array data type only
D. Hash function

Answer: A. Choice of pivot

Explanation: A good pivot creates balanced partitions; repeatedly choosing a poor pivot can
produce O(n²) behavior.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Q166. [Sorting — Comparison]

Which algorithm is generally preferable when guaranteed O(n log n) worst-case comparison
sorting is required and auxiliary array space should be small?

A. Heap Sort
B. Quick Sort
C. Bubble Sort
D. Selection Sort

Answer: A. Heap Sort

Explanation: Heap Sort provides O(n log n) worst-case time with O(1) auxiliary array space
in its standard implementation.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Q167. [Counting Sort]

Counting Sort is particularly suitable when:

A. The key range is small relative to the number of elements

B. All values are arbitrary strings
C. Comparison operations are mandatory
D. The input is always a graph

Answer: A. The key range is small relative to the number of elements

Explanation: Counting Sort can be efficient when the range of integer keys is reasonably
small.

CIL relevance: ⭐⭐⭐⭐⭐ 9/10

Q168. [Hashing — Collision]

A hash table has size 10 and uses:

[
h(k)=k\bmod10
]

Which keys collide?

A. 12 and 21
B. 15 and 25
C. 17 and 28
D. 11 and 22

Answer: B. 15 and 25

Explanation: Both keys produce index 5: (15\bmod10=5) and (25\bmod10=5).

CIL relevance: ⭐⭐⭐⭐⭐ 9/10

Q169. [Hashing — Double Hashing]

The main purpose of double hashing is to:

A. Eliminate all collisions

B. Use a second hash function to determine the probe sequence
C. Sort the hash table
D. Convert hashing into binary search

Answer: B. Use a second hash function to determine the probe sequence

Explanation: Double hashing uses another hash function to determine the step size during
collision resolution.

CIL relevance: ⭐⭐⭐⭐⭐ 9/10

Q170. [Hashing — Average Case]

Under suitable assumptions and a controlled load factor, the average search complexity in a
hash table can be approximately:

A. O(1)
B. O(log n)
C. O(n) always
D. O(n²)

Answer: A. O(1)

Explanation: A good hash function distributes keys effectively, giving expected constant-
time lookup.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Q171–180 — Complexity + Recursion +

Divide & Conquer
Q171. [Complexity]

What is the complexity?

for(i = 1; i <= n; i++)

for(j = 1; j <= n; j = j * 2)
count++;

A. O(n)
B. O(log n)
C. O(n log n)
D. O(n²)

Answer: C. O(n log n)

Explanation: The outer loop executes n times and the inner loop executes O(log n) times.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Q172. [Complexity]
What is the complexity?

i = n;
while(i > 1)
{
i = i / 2;
}

A. O(1)
B. O(log n)
C. O(n)
D. O(n²)

Answer: B. O(log n)

Explanation: The value is repeatedly halved until it reaches 1.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Q173. [Complexity]

What is the asymptotic complexity of:

[
1+2+3+\cdots+n
]

A. Θ(1)
B. Θ(log n)
C. Θ(n)
D. Θ(n²)

Answer: D. Θ(n²)

Explanation: The sum is (n(n+1)/2), whose dominant term is (n²/2).

CIL relevance: ⭐⭐⭐⭐⭐ 9/10

Q174. [Recursion]

Consider:

f(n)
{
if(n <= 1)
return;
f(n/2);
}

What is its time complexity?

A. O(1)
B. O(log n)
C. O(n)
D. O(n²)

Answer: B. O(log n)

Explanation: The argument is halved at every recursive call, producing approximately log₂n
calls.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Q175. [Recursion]

Consider:

f(n)
{
if(n <= 1)
return;
f(n-1);
f(n-1);
}

The approximate time complexity is:

A. O(log n)
B. O(n)
C. O(n²)
D. O(2ⁿ)

Answer: D. O(2ⁿ)

Explanation: Each call creates two calls of size n−1, producing an exponential recursion
tree.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Q176. [Recurrence]

Solve:

[
T(n)=T(n-1)+1
]

A. Θ(1)
B. Θ(log n)
C. Θ(n)
D. Θ(n²)
Answer: C. Θ(n)

Explanation: There are approximately n recursive levels, each performing constant work.

CIL relevance: ⭐⭐⭐⭐⭐ 9/10

Q177. [Divide and Conquer]

Which pair consists entirely of divide-and-conquer algorithms?

A. Merge Sort and Binary Search

B. Dijkstra and Prim
C. Kruskal and BFS
D. Selection Sort and DFS

Answer: A. Merge Sort and Binary Search

Explanation: Both recursively reduce the problem into smaller portions and solve the
relevant subproblem(s).

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Q178. [Master-Theorem Style]

Consider:

[
T(n)=2T(n/2)+O(1)
]

What is the complexity?

A. O(log n)
B. O(n)
C. O(n log n)
D. O(n²)

Answer: B. O(n)

Explanation: There are (2^k) subproblems after k levels, and the recursion reaches size 1
after log₂n levels, giving Θ(n) total work.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Q179. [Master-Theorem Style]

Consider:
[
T(n)=2T(n/2)+n
]

The complexity is:

A. Θ(log n)
B. Θ(n)
C. Θ(n log n)
D. Θ(n²)

Answer: C. Θ(n log n)

Explanation: Each recursion level contributes Θ(n), and there are Θ(log n) levels.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Q180. [Master-Theorem Style]

Consider:

[
T(n)=4T(n/2)+n
]

The complexity is:

A. Θ(n)
B. Θ(n log n)
C. Θ(n²)
D. Θ(2ⁿ)

Answer: C. Θ(n²)

Explanation: Here (n^{\log_2 4}=n²), which dominates the linear non-recursive work.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Q181–190 — Greedy + Dynamic

Programming
Q181. [Greedy]

Which property is important for a greedy algorithm to produce an optimal solution?

A. Greedy-choice property
B. Randomness
C. Hashing
D. Recursion must always be used

Answer: A. Greedy-choice property

Explanation: The problem must permit a locally optimal choice that can be extended to an
optimal global solution.

CIL relevance: ⭐⭐⭐⭐⭐ 9/10

Q182. [Fractional Knapsack]

Items have:

Item Value Weight

A 60 10
B 100 20
C 120 30

Which item has the highest value/weight ratio?

A. A
B. B
C. C
D. All equal

Answer: A. A

Explanation: Ratios are 6, 5 and 4 respectively; therefore A has the highest value per unit
weight.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Q183. [Fractional Knapsack]

Using the previous items, if the capacity is 20, which greedy strategy is appropriate?

A. Select C first
B. Select A first and then use the remaining capacity from B
C. Select B only regardless of ratio
D. Select the lowest-value item first

Answer: B

Explanation: Fractional Knapsack selects the highest value/weight ratio first, so A is

completely selected and the remaining capacity can be filled from B.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Q184. [0/1 Knapsack]

Why does the fractional-knapsack greedy strategy not generally work for 0/1 Knapsack?

A. Items cannot be divided in 0/1 Knapsack

B. Values cannot be compared
C. Weight is irrelevant
D. Dynamic programming cannot be used

Answer: A

Explanation: Each item must be either completely selected or completely rejected, so the
locally best ratio may prevent the optimal combination.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Q185. [Dynamic Programming]

Which problem is a classic application of Dynamic Programming?

A. Longest Common Subsequence

B. Linear Search only
C. Stack push
D. Queue dequeue

Answer: A. Longest Common Subsequence

Explanation: LCS has overlapping subproblems and optimal substructure, making it a

standard DP problem.

CIL relevance: ⭐⭐⭐⭐⭐ 9/10

Q186. [DP — LCS]

For strings:

X = ABC
Y = AC

The length of their Longest Common Subsequence is:

A. 1
B. 2
C. 3
D. 0

Answer: B. 2
Explanation: AC is a common subsequence of both strings and has maximum length 2.

CIL relevance: ⭐⭐⭐⭐⭐ 9/10

Q187. [DP — Optimal Substructure]

Optimal substructure means:

A. The problem has no subproblems

B. An optimal solution can be constructed from optimal solutions of relevant subproblems
C. Every solution must be greedy
D. Every algorithm must be recursive

Answer: B

Explanation: DP relies on the ability to construct a global optimum from appropriately

defined smaller optimal solutions.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Q188. [DP — Memoization]

Which statement about memoization is correct?

A. It deliberately recomputes every subproblem

B. It stores results of solved subproblems
C. It can only be used for sorting
D. It always requires O(1) memory

Answer: B

Explanation: Memoization caches previously computed results so overlapping subproblems

do not need to be solved repeatedly.

CIL relevance: ⭐⭐⭐⭐⭐ 9/10

Q189. [Greedy vs DP]

Which statement is correct?

A. Every optimization problem can be solved greedily

B. DP may examine combinations of subproblem solutions that greedy methods discard
C. Greedy and DP are identical
D. DP cannot solve optimization problems

Answer: B
Explanation: DP systematically considers relevant subproblem states, while greedy commits
to local choices.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Q190. [Algorithm Selection]

A problem allows items to be divided into fractions and asks for maximum value under a
weight constraint. Which technique should immediately come to mind?

A. Fractional Knapsack + Greedy

B. BFS
C. DFS
D. Binary Search only

Answer: A

Explanation: Fractional Knapsack has the greedy-choice property and is optimally solved by
value/weight ratio.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Q191–200 — Graphs + Integrated CIL-

Level Questions
Q191. [BFS — Shortest Path]

Consider the unweighted graph:

A -- B -- D
| |
C -- E

Starting from A, what is the minimum number of edges required to reach D?

A. 1
B. 2
C. 3
D. 4

Answer: B. 2

Explanation: The path A → B → D contains two edges.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Q192. [BFS vs DFS]

Which algorithm is generally preferable for finding the shortest path in terms of number of
edges in an unweighted graph?

A. DFS
B. BFS
C. Prim
D. Kruskal

Answer: B. BFS

Explanation: BFS explores vertices in increasing distance from the source, guaranteeing the
minimum number of edges in an unweighted graph.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Q193. [DFS — Complexity]

For a graph represented by adjacency lists, the complexity of DFS is:

A. O(V+E)
B. O(V²E)
C. O(log V)
D. O(E²)

Answer: A. O(V+E)

Explanation: DFS visits each vertex and examines each adjacency-list edge a constant
number of times.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Q194. [BFS — Complexity]

For an adjacency-list representation, BFS has complexity:

A. O(V+E)
B. O(V²) always
C. O(log V)
D. O(E²)

Answer: A. O(V+E)

Explanation: Each vertex enters the queue at most once and every edge is examined through
the adjacency lists.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Q195. [MST — Kruskal]

Kruskal's algorithm is most naturally associated with which supporting operation for efficient
cycle detection?

A. Union-Find / Disjoint Set

B. Stack
C. Binary Search Tree only
D. Circular Queue

Answer: A. Union-Find / Disjoint Set

Explanation: Disjoint Set Union efficiently determines whether adding an edge would
connect vertices already belonging to the same component.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Q196. [MST — Prim vs Kruskal]

Which statement is correct?

A. Prim grows one tree from a starting vertex, while Kruskal considers edges globally in
increasing weight order
B. Both are shortest-path algorithms
C. Kruskal requires directed graphs only
D. Prim cannot work on weighted graphs

Answer: A

Explanation: Prim expands a connected tree, whereas Kruskal builds a forest by repeatedly
choosing the lightest non-cycle-forming edge.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Q197. [Shortest Path — Algorithm Selection]

A directed graph contains negative edge weights but no reachable negative cycle. Which
algorithm is appropriate for single-source shortest paths?

A. Dijkstra
B. Bellman-Ford
C. Prim
D. BFS only

Answer: B. Bellman-Ford
Explanation: Bellman-Ford supports negative edge weights and can detect negative cycles
reachable from the source.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Q198. [All-Pairs Shortest Path]

There are V vertices, and shortest paths are required between every pair of vertices. Which
algorithm is a standard choice?

A. Floyd-Warshall
B. Binary Search
C. Prim
D. Insertion Sort

Answer: A. Floyd-Warshall

Explanation: Floyd-Warshall computes an all-pairs shortest-path matrix using dynamic

programming.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Q199. [Integrated Algorithm Selection]

A problem has the following characteristics:

 The graph is unweighted.

 We need the minimum number of edges from a source to every reachable vertex.
 The graph may contain cycles.

Which algorithm should be selected?

A. DFS
B. BFS
C. Kruskal
D. Dijkstra with arbitrary negative weights

Answer: B. BFS

Explanation: BFS handles cycles using visited information and guarantees minimum edge-
count distances in an unweighted graph.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

Q200. 🔥 [Master Integrated Question]

Consider the following statements:

S1: Inorder traversal of a valid BST produces sorted order.

S2: BFS normally uses a queue.

S3: Dijkstra's algorithm is appropriate for graphs containing arbitrary negative edge weights.

S4: Kruskal's algorithm is used to construct a minimum spanning tree.

Which statements are correct?

A. S1 and S2 only
B. S1, S2 and S4 only
C. S2, S3 and S4 only
D. All four

Answer: B. S1, S2 and S4 only

Explanation: S1, S2 and S4 are correct; S3 is false because ordinary Dijkstra requires non-
negative edge weights.

CIL relevance: ⭐⭐⭐⭐⭐ 10/10

PYQ-pattern relevance: 🔥 Very High — 10/10. This combines multiple syllabus concepts
and tests whether you can distinguish closely related algorithms instead of merely
remembering definitions.

🎯 Final 200-Question Priority Map

Now that Q1–Q200 are complete, this is the order I would use for revision.

Rank Topic Priority

1 Graph Traversal — BFS/DFS 🔴 10/10
2 MST — Prim/Kruskal 🔴 10/10
3 Shortest Paths — Dijkstra/Bellman-Ford/Floyd-Warshall 🔴 10/10
4 Time & Space Complexity 🔴 10/10
5 Trees + BST + Traversals 🔴 10/10
6 Sorting + Complexity + Stability 🔴 9.5/10
7 Recursion + Recurrences 🔴 9.5/10
8 Heaps + Priority Queue 🟠 9/10
9 Greedy + Dynamic Programming 🟠 9/10
10 Hashing 🟠 8.5/10
11 Linked Lists 🟡 8.5/10
12 Stacks + Queues 🟡 8.5/10
13 Arrays 🟡 8/10
The supplied syllabus explicitly places graphs, BSTs, heaps and graph algorithms in this
section, while the Algorithms section specifically includes searching, sorting, hashing,
asymptotic worst-case time/space, greedy, DP, divide-and-conquer, graph traversals, MST
and shortest paths.

🔥 The 15 concepts I would absolutely not skip

1. BST inorder = sorted order

2. Balanced BST search = O(log n), skewed BST = O(n)
3. Heap ≠ sorted tree
4. Heap insertion/extraction = O(log n)
5. Build heap = O(n)
6. Binary Search = O(log n)
7. Merge Sort = O(n log n) worst case
8. Quick Sort = O(n²) worst case
9. BFS = Queue
10. DFS = Stack/Recursion
11. BFS gives shortest edge-count path in an unweighted graph
12. Prim/Kruskal = MST
13. Dijkstra = non-negative weights
14. Bellman-Ford = negative edges
15. Floyd-Warshall = all-pairs shortest paths

And one important exam distinction:

GRAPH PROBLEM
│
┌──────────────┼───────────────┐
│ │ │
Traversal MST Shortest Path
│ │ │
┌───┴───┐ ┌───┴────┐ ┌────┴─────────┐
│ │ │ │ │ │ │
BFS DFS Prim Kruskal Dijkstra Bellman Floyd
│ │ │
1 source 1 source all pairs
non-neg. negative

This completes the full 200-question DSA + Algorithms sequence. The supplied CIL
syllabus itself confirms that these are the intended Programming/Data Structures and
Algorithms areas, so the final set has been kept within that scope rather than adding unrelated
DSA topics.
This is a copy of a shared ChatGPT chat. It won't be added to memory.

Report conversation

Yes — this confusion is very common, because Prims, Kruskal, Dijkstra, BFS, DFS, etc.
are all graph algorithms, but they don't all belong to the same algorithmic paradigm.

Let's separate the two ideas first:

Graph algorithm = what problem/data structure the algorithm works on.

Greedy / Dynamic Programming / Divide & Conquer = how the algorithm solves the
problem.

So an algorithm can be both a graph algorithm AND a greedy algorithm.

1. What is MST?
MST = Minimum Spanning Tree.

Suppose you have a connected, weighted, undirected graph.

A spanning tree:

 includes all vertices

 has exactly V−1 edges
 contains no cycle

A Minimum Spanning Tree is the spanning tree whose total edge weight is minimum.

Example

Imagine 4 cities:

A ----2---- B
| |
5 3
| |
C ----1---- D

We want to connect all cities with minimum total cost, without creating a cycle.

That's an MST problem.

The two major MST algorithms you need to know are:

Prim’s Algorithm

and

Kruskal’s Algorithm
2. The classification you should memorize
This is the important part:

Algorithm Problem Paradigm / Approach

BFS Graph traversal Graph traversal
DFS Graph traversal Graph traversal
Prim's Minimum Spanning Tree Greedy
Kruskal's Minimum Spanning Tree Greedy
Dijkstra's Single-source shortest path Greedy
Bellman-Ford Single-source shortest path Dynamic Programming /
Relaxation
Floyd-Warshall All-pairs shortest path Dynamic Programming
Warshall Transitive closure Dynamic Programming
0/1 Knapsack Knapsack optimization Dynamic Programming
Fractional Knapsack Knapsack optimization Greedy
LCS Longest Common Dynamic Programming
Subsequence
Matrix Chain Optimization Dynamic Programming
Multiplication
Activity Selection Scheduling Greedy
Huffman Coding Optimal prefix code Greedy

This table is very important for CIL-style questions.

3. Why is Prim's a Greedy algorithm?

Prim's algorithm doesn't try every possible spanning tree.

Instead, at every step it makes a locally optimal choice:

Select the minimum-weight edge that connects the already-selected vertices to an unselected
vertex.

So:

Prim’s = Graph + MST + Greedy

Think:

Prim → Pick the cheapest edge from the current tree.

4. Why is Kruskal's also Greedy?

Kruskal also selects the cheapest edge.
But its strategy is different.

It:

1. Sorts all edges by weight.

2. Takes the smallest edge.
3. Rejects it if it creates a cycle.
4. Continues until V−1 edges are selected.

Therefore:

Kruskal = Graph + MST + Greedy

Easy distinction

Prim:

Grow one tree from a starting vertex.

Kruskal:

Pick globally smallest edges and join components.

5. Now Dijkstra — another important

confusion
Dijkstra finds:

Shortest path from one source vertex to all other vertices.

It is a greedy algorithm.

At every step, it permanently selects the unvisited vertex having the smallest currently known
distance.

Therefore:

Dijkstra = Graph + Shortest Path + Greedy

⚠️Important:

Dijkstra ≠ MST.

It finds shortest paths, not a minimum spanning tree.

6. Then where does Dynamic Programming
come in?
Dynamic Programming (DP) is different.

The basic idea is:

Break a problem into overlapping subproblems, solve them, and store/reuse their results.

Important graph DP algorithms:

Bellman-Ford

Finds single-source shortest paths and can handle negative edge weights.

Bellman-Ford → Dynamic Programming

Floyd-Warshall

Finds shortest paths between every pair of vertices.

Floyd-Warshall → Dynamic Programming

Its famous recurrence is:

Dij(k)=min(Dij(k−1),Dik(k−1)+Dkj(k−1))

You don't need to panic about the formula yet — just recognize:

Floyd-Warshall = DP

7. The easiest way to organize your brain 🧠

Don't memorize one giant list.

First ask:

Question 1: What problem is being solved?

Traversal?

→ BFS / DFS

Minimum connection cost?

→ Prim / Kruskal

Shortest path?
→ Dijkstra / Bellman-Ford / Floyd-Warshall

Then ask:

Question 2: What approach does it use?

Approach Algorithms
Greedy Prim, Kruskal, Dijkstra, Fractional Knapsack, Activity Selection,
Huffman
Dynamic Bellman-Ford, Floyd-Warshall, 0/1 Knapsack, LCS, MCM
Programming
Divide & Conquer Merge Sort, Quick Sort, Binary Search
Backtracking N-Queens, Graph Coloring, Hamiltonian Cycle
Graph Traversal BFS, DFS

🔥 Most important CIL memory map

Remember this:

ALGORITHMS
|
+---------------+----------------+
| |
GRAPH OTHER PROBLEMS
|
+----+----+
| |
Traversal Optimization/Paths
| |
BFS +----------------------+
DFS | |
MST Shortest Path
| |
+---+---+ +-----+--------+
| | | | |
Prim Kruskal Dijkstra Bellman Floyd
| | | | |
Greedy Greedy Greedy DP DP

⭐ One-line rules

 Prim → Greedy → MST

 Kruskal → Greedy → MST
 Dijkstra → Greedy → Shortest Path
 Bellman-Ford → DP → Shortest Path
 Floyd-Warshall → DP → All-Pairs Shortest Path
 BFS → Graph Traversal
 DFS → Graph Traversal
 0/1 Knapsack → DP
 Fractional Knapsack → Greedy
 LCS → DP
 Activity Selection → Greedy
 Huffman → Greedy
 Merge Sort → Divide & Conquer
  Quick Sort → Divide & Conquer
 Binary Search → Divide & Conquer

And the most important distinction:

Prim/Kruskal solve MST

while

Dijkstra/Bellman-Ford/Floyd-Warshall solve shortest-path problems

That's the classification you should have in your head before solving CIL-level algorithm

This is a copy of a shared ChatGPT chat. It won't be added to memory.

Report conversation

Exactly — this is the key confusion. The mistake is thinking:

“Minimum Spanning Tree has minimum weight, so it must give the shortest path.”

It does not. MST minimizes the total weight of the entire tree, not the distance between
two particular vertices.

1. MST vs Shortest Path

Suppose we have:

2
A -------- B
| |
1| |2
| |
C -------- D
1

And one direct edge:

A -------- D
10

Prim/Kruskal → MST

They want to connect ALL vertices with minimum total edge weight.

They might choose:

A−C=1,C−D=1,A−B=2

Total:
1+1+2=4

That's the MST.

2. But suppose we ask:

What is the shortest path from A to D?

In the MST:

A
|
1
C
|
1
D

Distance:

1+1=2

So here they happen to agree.

But they don't have to.

Consider this:

1
A ------- B
| |
2 | | 1
| |
C ------- D
2

A -------- D
3

The MST may choose:

A−B=1, B−D=1, A−C=2

Total:

1+1+2=4

A → D in MST:

A→B→D

Cost:
1+1=2

Again, shortest.

So let's make the distinction clearer.

3. The fundamental difference

Prim/Kruskal asks:

How can I connect ALL vertices at minimum total cost?

MST = minimize total tree weight

Dijkstra/Bellman-Ford asks:

What is the cheapest route from source A to destination B?

Shortest Path = minimize path distance

These are different optimization problems.

4. A very clear example

Imagine 4 cities:

1
A ------- B
| |
10 1
| |
C ------- D
10

A -------- D
5

MST

To connect everyone cheaply, MST might select:

A−B=1 B−D=1 A−D=5

Total:

1+1+5=7

But wait — C is disconnected. So it must additionally connect C, for example:

A−C=10

Total MST:

1+1+5+10=17

But the shortest path from A to D is simply:

A→B→D

with cost:

1+1=2

The MST's objective was not to find A→D. It was to connect A, B, C, D together as
cheaply as possible.

5. Why Prim/Kruskal cannot replace

Dijkstra
Suppose you ask:

"Find the shortest route from Patna to Delhi."

You don't care about connecting every city in India.

You only care about:

Patna → Delhi

That's a shortest-path problem.

So use:

 Dijkstra → no negative edges

 Bellman-Ford → negative edges allowed

But if the question is:

"Connect all cities with minimum total road construction cost."

That's:

MST

Use:

 Prim
 Kruskal
🔥 The easiest way to remember
Think of building roads.

Prim/Kruskal:

"Connect EVERY city as cheaply as possible."

Dijkstra/Bellman-Ford:

"Get from THIS city to THAT city as cheaply as possible."

Therefore:

MST=Shortest Path

And consequently:

Prim/Kruskal=Dijkstra/Bellman-Ford

Even though both involve weighted graphs and minimizing weights, they minimize
different things.

CIL exam trap 🚨

If the question says:

“Minimum cost to connect all vertices”

→ Prim/Kruskal

If it says:

“Minimum/shortest distance from source to destination”

→ Dijkstra/Bellman-Ford

If it says:

“Shortest paths between every pair of vertices”

→ Floyd-Warshall

This is a copy of a shared ChatGPT chat. It won't be added to memory.

Report conversation

Yes — you are essentially clear, and your core distinction is correct. 👍 Just make two small
corrections.

1. Shortest-path algorithms

You said:

Bellman-Ford and Dijkstra are used to find shortest paths, with Bellman-Ford handling
negative edges.

Correct. ✅

 Dijkstra → shortest path, no negative edge weights

 Bellman-Ford → shortest path, negative edges allowed
 Floyd-Warshall → shortest paths between every pair of vertices, negative edges
allowed (but negative cycles are a separate issue)

And yes, in a shortest-path problem, you don't have to use all vertices. The shortest route
from A to D might use only:

A→B→D

even if the graph contains 100 other vertices.

2. Prim and Kruskal

Your understanding here is also correct:

They connect all vertices while minimizing the total weight of the selected edges.

Exactly. ✅

MST = Connect ALL vertices + No cycles + Minimum total edge weight

So an MST with V vertices will always contain:

V−1 edges

One correction in your statement

You said “Bellman-Ford, Dijkstra, and Prim's, sorry, Ford-Warshall”.

You meant Floyd-Warshall, and Prim should not be in the shortest-path group.

The clean classification is:

WEIGHTED GRAPH
│
├── Minimum Spanning Tree
│ ├── Prim
│ └── Kruskal
│ → Connect ALL vertices
│ → Minimum TOTAL weight
│
└── Shortest Path
├── Dijkstra
│ → Single source
│ → No negative edges
│
├── Bellman-Ford
│ → Single source
│ → Negative edges allowed
│
└── Floyd-Warshall
→ ALL PAIRS shortest paths
→ Negative edges allowed

🧠 Your final mental model

MST:

“I want to build a network connecting everyone as cheaply as possible.”

Shortest Path:

“I want to travel from here to there as cheaply/quickly as possible.”

That's the exact conceptual difference. ✅

This is a copy of a shared ChatGPT chat. It won't be added to memory.

Report conversation

What is Stable Sorting?

A stable sorting algorithm preserves the original relative order of elements that have
equal sorting keys.

In simple words:

If two elements have the same value/key, their order after sorting remains the same as
before sorting.

The important word is relative order.

1. Simple Example
Suppose we have students with their marks:

Name Marks
----------------
Juhi 80
Rahul 70
Aman 80
Neha 90

Now sort by Marks in ascending order.

Before sorting, the two students with 80 marks appear as:

Juhi→Aman

A stable sort produces:

Name Marks
----------------
Rahul 70
Juhi 80
Aman 80
Neha 90

Notice:

Juhi→Aman

is still the order among the 80-mark students.

Therefore, the sorting is stable. ✅

2. What if it is NOT stable?

Suppose the sorting algorithm produces:

Name Marks
----------------
Rahul 70
Aman 80
Juhi 80
Neha 90

The marks are correctly sorted:

70<80<80<90

But originally:

Juhi → Aman

and now:

Aman → Juhi

Their relative order changed.

Therefore, this sorting result is unstable. ❌

Important point

The algorithm is still correctly sorting the marks.

The only problem is that it changed the order of elements having equal keys.

3. Why do we care about stability?

Stability becomes very useful when objects have multiple attributes.

Suppose:

Student Department Marks

--------------------------------
Juhi CS 80
Rahul IT 70
Aman CS 80
Neha IT 90

Suppose we first sort by Name, then want to sort by Marks.

A stable sorting algorithm can preserve the previous ordering among students having equal
marks.

This is extremely useful when performing multi-level sorting.

4. Real-life example
Imagine a list of employees:

Employee Salary
---------------------
A 50,000
B 40,000
C 50,000
D 30,000

Original order among ₹50,000 employees:

A→C

After stable sorting by salary:

D ₹30,000
B ₹40,000
A ₹50,000
C ₹50,000
A remains before C.

That's stability.

5. Which sorting algorithms are stable?

For typical implementations:

Sorting Algorithm Stable?

Bubble Sort ✅ Stable
Insertion Sort ✅ Stable
Merge Sort ✅ Stable
Selection Sort ❌ Usually unstable
Quick Sort ❌ Usually unstable
Heap Sort ❌ Unstable
Counting Sort ✅ Can be stable
Radix Sort ✅ Can be stable

⚠️Important: Stability can sometimes depend on the implementation, so exam questions

generally expect the standard classification above.

6. Why is Selection Sort generally unstable?

Consider:

[4A, 2, 4B, 1]

The A and B indicate that the two 4s are different records but have the same key.

Selection sort finds the minimum 1 and swaps it with the first element:

[1, 2, 4B, 4A]

Originally:

4A→4B

After sorting:

4B→4A

So their relative order changed.

Therefore:

Selection Sort is generally unstable

7. Stable vs Unstable — visual comparison
Original:

[A(80), B(70), C(80), D(90)]

Stable:
[B(70), A(80), C(80), D(90)]
↑ ↑
A C

A remains before C.

Unstable:
[B(70), C(80), A(80), D(90)]
↑ ↑
C A

C has moved before A.

8. Very important distinction

Stable sorting does NOT mean:

 faster sorting ❌
 O(nlogn) sorting ❌
 sorted data remains unchanged ❌
 duplicate elements are removed ❌

It specifically means:

Equal-key elements preserve their original relative order

🧠 CIL/PSU Exam Shortcut

If you see:

Which of the following sorting algorithms is stable?

Common answers:

Bubble, Insertion, Merge

If you see:

Which sorting algorithm is generally unstable?

Common answers:

Selection, Quick, Heap

And the definition to memorize:

A stable sorting algorithm preserves the relative order of records having equal keys.

This is a copy of a shared ChatGPT chat. It won't be added to memory.

Report conversation

Open Addressing in Hashing

Open addressing is a collision-resolution technique in which all keys are stored inside the
hash table itself.

When a collision occurs, instead of creating a linked list outside the table, we search for
another empty slot in the same table.

Simple example

Suppose the hash table has 7 positions:

Index: 0 1 2 3 4 5 6
─────────────────────────────
Table: _ _ _ _ _ _ _

Hash function:

h(k)=kmod7

Insert:

10→10mod7=3

So:

Index: 0 1 2 3 4 5 6
─────────────────────────────
Table: _ _ _ 10 _ _ _

Now insert 17:

17mod7=3

But index 3 is occupied → collision.

With open addressing, we find another empty position according to a probing method.

For example, with linear probing:

3 → 4 → 5 → 6 → ...

So 17 goes to index 4:

Index: 0 1 2 3 4 5 6
─────────────────────────────
Table: _ _ _ 10 17 _ _

Three major types of Open Addressing

Method Formula / Idea

Linear Probing h(k)+i
Quadratic Probing h(k)+i2
Double Hashing h1(k)+ih2(k)

🧠 Remember

Open Addressing = Collision → Find another slot inside the table

Whereas separate chaining stores collided elements in a linked list/bucket associated with
the table slot.

Exam keyword:
👉 Open addressing → all elements remain inside the hash table.

Yes. When a collision occurs in hashing, there are several collision-resolution techniques.

Main techniques

Technique Basic idea Key point

Separate Store collided keys in a linked list/bucket at Can store multiple keys
Chaining the same index per slot
Linear Probing Check the next slot sequentially h(k)+i
Quadratic Check slots using squared increments h(k)+i2
Probing
Double Hashing Use a second hash function to determine the h1(k)+ih2(k)
jump

The big classification

Collision
│
┌─────────┴─────────┐
│ │
 Separate Chaining Open Addressing
│
┌─────────┼─────────┐
│ │ │
Linear Quadratic Double
Probing Probing Hashing

🧠 Exam shortcut

Chaining = outside/list Open Addressing = inside table

And under Open Addressing, remember:

Linear + Quadratic + Double Hashing

These are the main collision-resolution techniques you should know for CIL/PSU-level
questions.

Absolutely. Let's use the same hash function and the same keys for every technique so the
difference becomes very clear.

We'll use:

h(k)=kmod7

Hash table size = 7, so indexes are:

0 1 2 3 4 5 6

Insert these keys:

10, 17, 24, 31

Notice:

10mod7=3 17mod7=3 24mod7=3 31mod7=3

So all four keys collide at index 3. This makes the examples very useful.

1. Separate Chaining
Here, we don't search for another empty table position.

Instead, we maintain a list at the same index.

Insert 10
Index 0 → NULL
Index 1 → NULL
Index 2 → NULL
Index 3 → 10 → NULL
Index 4 → NULL
Index 5 → NULL
Index 6 → NULL

Insert 17

17 also hashes to 3.

Instead of moving it elsewhere:

Index 3 → 10 → 17 → NULL

Insert 24
Index 3 → 10 → 17 → 24 → NULL

Insert 31
Index 3 → 10 → 17 → 24 → 31 → NULL

So the final table is:

0 → NULL
1 → NULL
2 → NULL
3 → 10 → 17 → 24 → 31 → NULL
4 → NULL
5 → NULL
6 → NULL

🧠 Key idea

Collision → create/store in a chain

The table itself doesn't need to find another empty position.

2. Linear Probing
Now we use open addressing.

If the calculated position is occupied, we check the next position.

Formula:

hi(k)=(h(k)+i)mod7

Suppose we insert the same keys.

Insert 10

10mod7=3
Index 3 is empty:

0 1 2 3 4 5 6
- - - 10 - - -

Insert 17

17mod7=3

Index 3 occupied.

Check next:

3+1=4

Index 4 is empty.

0 1 2 3 4 5 6
- - - 10 17 - -

Insert 24

Again:

24mod7=3

Index 3 occupied → check 4 → occupied → check 5.

Put 24 at 5:

0 1 2 3 4 5 6
- - - 10 17 24 -

Insert 31

Again start at 3:

3 → occupied
4 → occupied
5 → occupied
6 → empty

So:

0 1 2 3 4 5 6
- - - 10 17 24 31

🧠 Key idea

Linear probing → check next, next, next...

Pattern:

3→4→5→6
Main disadvantage

It creates primary clustering — groups of consecutive occupied positions.

3. Quadratic Probing
Instead of checking the next position one by one, we jump using squares.

Formula:

hi(k)=(h(k)+i2)mod7

The jumps are:

02, 12, 22, 32,…

So from index 3:

3, 3+1, 3+4, 3+9,…

After modulo 7:

3, 4, 0, 5,…

Now insert the same keys.

Insert 10

10mod7=3

Index 3 empty:

0 1 2 3 4 5 6
- - - 10 - - -

Insert 17

17 → index 3 → occupied.

Try:

3+12=4

Index 4 is empty:

0 1 2 3 4 5 6
- - - 10 17 - -

Insert 24
24 → index 3 → occupied.

Try:

3+12=4

4 is occupied.

Try:

3+22=7 7mod7=0

Index 0 is empty.

So:

0 1 2 3 4 5 6
24 - - 10 17 - -

Insert 31

31 → index 3 → occupied.

Try:

3+12=4

occupied.

Try:

3+22=0

occupied.

Try:

3+32=12 12mod7=5

Index 5 is empty.

Final:

0 1 2 3 4 5 6
24 - - 10 17 31 -

🧠 Key idea

Quadratic probing → jump by 12,22,32,…

4. Now compare all three

Using:

h(k)=kmod7

and keys:

10,17,24,31

Separate Chaining
3 → 10 → 17 → 24 → 31

Linear Probing
Index: 0 1 2 3 4 5 6
- - - 10 17 24 31

Quadratic Probing
Index: 0 1 2 3 4 5 6
24 - - 10 17 31 -

🔥 The three formulas to memorize

Separate Chaining

No probing formula; maintain a chain/list.

Linear Probing

h(k)+i

Pattern:

0,1,2,3,…

Quadratic Probing

h(k)+i2

Pattern:

0,1,4,9,…

Double Hashing

And one more important technique:

h1(k)+i×h2(k)

It uses a second hash function to determine the jump size.

🧠 One-minute exam revision
COLLISION
│
├── Separate Chaining
│ → Linked list / chain
│ → Multiple elements at same index
│
└── Open Addressing
│
├── Linear Probing
│ → +1, +1, +1
│ → Primary clustering
│
├── Quadratic Probing
│ → +1², +2², +3²
│ → Reduces primary clustering
│
└── Double Hashing
→ Second hash function

The most important numerical skill: when a question gives you a hash function, table size,
and keys, calculate the initial index and then follow the appropriate probing sequence.

1. Double Hashing
Double hashing is an open-addressing technique where we use two hash functions.

The usual formula is:

h(k,i)=(h1(k)+i×h2(k))modm

where:

 h1(k) → first hash function gives the initial position

 h2(k) → second hash function gives the jump size
 i=0,1,2,3,…
 m → hash-table size

Example

Let:

m=7 h1(k)=kmod7 h2(k)=5−(kmod5)

Insert:

10, 17, 24

Insert 10
First hash:

h1(10)=10mod7=3

So 10 goes to index 3.

Index: 0 1 2 3 4 5 6
- - - 10 - - -

Insert 17

First hash:

h1(17)=17mod7=3

Collision at 3.

Now calculate second hash:

h2(17)=5−(17mod5) =5−2=3

So our positions are:

For i=0:

(3+0×3)mod7=3

Occupied.

For i=1:

(3+1×3)mod7=6

Index 6 is empty.

Therefore:

Index: 0 1 2 3 4 5 6
- - - 10 - - 17

Insert 24

First:

h1(24)=24mod7=3

Collision.

Second hash:

h2(24)=5−(24mod5) =5−4=1
Positions:

i=0:3

occupied.

i=1:(3+1)mod7=4

Index 4 is empty.

So:

Index: 0 1 2 3 4 5 6
- - - 10 24 - 17

🧠 Difference from linear/quadratic

Linear:

3 → 4 → 5 → 6

Quadratic:

3 → 4 → 0 → 5 ...

Double hashing:

jump depends on the SECOND hash function

That's why double hashing usually gives better distribution and reduces clustering.

2. Now your second question: Can we

reverse hashing?
Suppose:

h(k)=kmod7

And we see:

h(k)=3

Can we say:

k=?

No, not uniquely. ❌

Because many keys produce 3:

3mod7=3 10mod7=3 17mod7=3 24mod7=3 31mod7=3

So:

3, 10, 17, 24, 31,…

all have the same hash value.

3. Why can't hashing normally be reversed?

Hashing is generally a many-to-one function:

Many keys→same hash value

For example:

Key Hash
---------------------------
10 ───────────────→ 3
17 ───────────────→ 3
24 ───────────────→ 3
31 ───────────────→ 3

Once you only have 3, you don't know which original key produced it.

This is called loss of information.

4. But what happens in a hash table?

This is where it gets interesting.

Suppose your table contains:

Index 3 → 10 → 17 → 24 → 31

If you want to find 17, you calculate:

h(17)=3

Then go to bucket/index 3 and search the stored elements.

So you're not reversing the hash.

You're doing:

Key → Hash → Location → Search for Key

5. What if you have only the hash value?
Suppose someone tells you:

Hash value = 3

You cannot determine the original key uniquely.

You can only say:

kmod7=3

Therefore:

k=7n+3

for integer n.

Examples:

3,10,17,24,31,…

🔥 Final exam concept

Hashing:

Key→Hash value

Reverse hashing:

Hash value→unique original key

because hashing is generally many-to-one.

And:

Double Hashing=Two hash functions for collision resolution

not “reversing” the hash.

One important distinction

Don't confuse hashing with encryption:

 Encryption → designed to be reversible with a key.

 Hashing → designed as a one-way mapping; the original input generally cannot be uniquely
recovered from the hash.