Final

Question 1

Which data structure is used in BFS?

Answer 1

Queue

Question 2

Is BFS suitable for finding the shortest path in an unweighted graph?

Answer 2

Yes

Question 3

What is the time complexity of BFS in terms of V and E?

Answer 3

O(V + E)

Question 4

Does BFS visit all nodes in a disconnected graph?

Answer 4

No

Question 5

Which data structure is used in DFS (iterative)?

Answer 5

Stack

Question 6

DFS can be used to detect cycles in which type of graph?

Answer 6

Both directed and undirected graphs

Question 7

In DFS

Answer 7

what can be used to find articulation points and bridges?

Question 8

What is the time complexity of DFS?

Answer 8

O(V + E)

Question 9

Topological sorting applies to which type of graph?

Answer 9

Directed Acyclic Graph (DAG)

Question 10

Which algorithms can perform topological sort?

Answer 10

Kahn’s Algorithm (BFS) and DFS-based

Question 11

What is the order of nodes in topological sort useful for?

Answer 11

Task scheduling / dependency resolution

Question 12

Topological sort is not possible if the graph has a

Answer 12

Cycle

Question 13

A spanning tree must include all

Answer 13

Vertices with minimum number of edges

Question 14

Number of edges in a spanning tree with n vertices is

Answer 14

n - 1

Question 15

Can a graph have more than one spanning tree?

Answer 15

Yes

Question 16

What is a minimum spanning tree?

Answer 16

A spanning tree with minimum total edge weight

Question 17

What is an articulation point in a graph?

Answer 17

A vertex whose removal increases the number of connected components

Question 18

Which algorithm is commonly used to find articulation points?

Answer 18

DFS with low-link values

Question 19

Articulation points exist only in

Answer 19

Connected undirected graphs

Question 20

Can a leaf node be an articulation point?

Answer 20

No

Question 21

What are two common algorithms to find MST?

Answer 21

Prim’s and Kruskal’s

Question 22

Can an MST exist in a disconnected graph?

Answer 22

No

Question 23

Is MST unique for every graph?

Answer 23

No

Question 24

Prim’s algorithm grows the MST by adding

Answer 24

The smallest edge connecting the tree to an outside vertex

Question 25

Which data structure is used to improve Prim's efficiency?

Answer 25

Priority Queue (Min Heap)

Question 26

Time complexity of Prim's using min-heap and adjacency list

Answer 26

O(E log V)

Question 27

Kruskal’s algorithm uses which data structure to detect cycles?

Answer 27

Disjoint Set (Union-Find)

Question 28

Kruskal’s sorts all edges based on

Answer 28

Weight

Question 29

Kruskal’s is best suited for

Answer 29

Sparse graphs

Question 30

Dijkstra’s algorithm works only when all edge weights are

Answer 30

Non-negative

Question 31

What is the time complexity using a binary heap?

Answer 31

O((V + E) log V)

Question 32

Does Dijkstra’s algorithm guarantee shortest paths?

Answer 32

Yes

Question 33

Bellman-Ford can handle

Answer 33

Graphs with negative weights

Question 34

Time complexity of Bellman-Ford is

Answer 34

O(V × E)

Question 35

It can detect

Answer 35

Negative weight cycles

Question 36

Floyd-Warshall is used for

Answer 36

All-pairs shortest paths

Question 37

It works with

Answer 37

Negative weights

Question 38

Time complexity of Floyd-Warshall

Answer 38

O(V³)