1Which data structure is primarily used to implement Breadth-First Search (BFS)?
A.Hash Table
B.Priority Queue
C.Queue
D.Stack
Correct Answer: Queue
Explanation:
BFS explores the neighbor nodes first before moving to the next level neighbors, which follows the First-In-First-Out (FIFO) principle handled by a Queue.
Incorrect! Try again.
2Which data structure is primarily used to implement Depth-First Search (DFS)?
A.Queue
B.Linked List
C.Stack
D.Heap
Correct Answer: Stack
Explanation:
DFS explores as far as possible along each branch before backtracking, which follows the Last-In-First-Out (LIFO) principle handled by a Stack (or recursion stack).
Incorrect! Try again.
3What is the time complexity of BFS for a graph represented using an adjacency list with V vertices and E edges?
A.O(V * E)
B.O(V)
C.O(E)
D.O(V + E)
Correct Answer: O(V + E)
Explanation:
In BFS using an adjacency list, every vertex is enqueued once and every edge is inspected once, resulting in O(V + E).
Incorrect! Try again.
4What is the time complexity of DFS for a graph represented using an adjacency matrix with V vertices?
A.O(V)
B.O(log V)
C.O(V + E)
D.O(V^2)
Correct Answer: O(V^2)
Explanation:
With an adjacency matrix, finding the neighbors of the current vertex requires checking all V entries in the row, leading to O(V^2) total time.
Incorrect! Try again.
5Which algorithm is best suited for finding the shortest path in an unweighted graph?
A.Kruskal's Algorithm
B.DFS
C.Prim's Algorithm
D.BFS
Correct Answer: BFS
Explanation:
BFS explores nodes level by level. In an unweighted graph, the first time a node is reached during BFS, it is via the shortest path.
Incorrect! Try again.
6Dijkstra’s Algorithm is based on which algorithmic paradigm?
A.Divide and Conquer
B.Greedy Approach
C.Backtracking
D.Dynamic Programming
Correct Answer: Greedy Approach
Explanation:
Dijkstra's algorithm makes a locally optimal choice at each step (selecting the unvisited node with the smallest tentative distance) to find the global optimum.
Incorrect! Try again.
7What is the main limitation of Dijkstra’s Algorithm?
A.It cannot handle cycles.
B.It is slower than Bellman-Ford.
C.It cannot handle negative weight edges.
D.It only works on directed graphs.
Correct Answer: It cannot handle negative weight edges.
Explanation:
Dijkstra’s algorithm assumes that once a node is processed, its distance is final. Negative edges can contradict this assumption by providing a shorter path later.
Incorrect! Try again.
8What is the time complexity of Dijkstra’s Algorithm using a binary heap (priority queue)?
A.O(V log E)
B.O(E log V)
C.O(V^2)
D.O(E + V log V)
Correct Answer: O(E log V)
Explanation:
With a binary heap, extracting the minimum takes O(log V) and is done V times. Decreasing the key takes O(log V) and can occur E times. Often simplified to O(E log V) or O((E+V)log V).
Incorrect! Try again.
9Which algorithm can detect a negative weight cycle in a graph?
A.Prim's Algorithm
B.Bellman-Ford Algorithm
C.BFS
D.Dijkstra’s Algorithm
Correct Answer: Bellman-Ford Algorithm
Explanation:
Bellman-Ford can detect negative cycles if, after V-1 iterations, a further relaxation step can still reduce the distance to a vertex.
Incorrect! Try again.
10How many iterations does the Bellman-Ford algorithm run to guarantee shortest paths in a graph with V vertices?
A.V
B.E
C.V + 1
D.V - 1
Correct Answer: V - 1
Explanation:
In a graph with V vertices, the longest simple path can have at most V-1 edges. Therefore, V-1 iterations are sufficient to propagate weights.
Incorrect! Try again.
11What is the time complexity of the Bellman-Ford algorithm?
A.O(VE)
B.O(V + E)
C.O(V^2)
D.O(E log V)
Correct Answer: O(VE)
Explanation:
The algorithm iterates V-1 times, and in each iteration, it relaxes all E edges. Thus, the complexity is O(VE).
Incorrect! Try again.
12The Floyd Warshall algorithm is used to solve which problem?
A.Minimum Spanning Tree
B.Network Flow
C.Single-Source Shortest Path
D.All-Pairs Shortest Path
Correct Answer: All-Pairs Shortest Path
Explanation:
Floyd Warshall computes the shortest paths between every pair of vertices in the graph.
Incorrect! Try again.
13What is the time complexity of the Floyd Warshall algorithm?
A.O(E^2)
B.O(V^2)
C.O(VE)
D.O(V^3)
Correct Answer: O(V^3)
Explanation:
The algorithm uses three nested loops (source, destination, and intermediate node), each iterating up to V times.
Incorrect! Try again.
14Floyd Warshall algorithm uses which algorithmic paradigm?
A.Divide and Conquer
B.Branch and Bound
C.Dynamic Programming
D.Greedy Approach
Correct Answer: Dynamic Programming
Explanation:
It builds the solution by considering intermediate vertices incrementally, using previously computed shortest paths.
Incorrect! Try again.
15In the relaxation step if (d[u] + c(u, v) < d[v]), what does d[v] represent?
A.The number of edges from source to v
B.The current known shortest distance from source to v
C.The shortest distance from u to v
D.The weight of edge (u, v)
Correct Answer: The current known shortest distance from source to v
Explanation:
d[v] stores the tentative shortest distance found so far from the source vertex to vertex v.
Incorrect! Try again.
16Which traversal is most appropriate for topological sorting?
A.DFS
B.Floyd Warshall
C.BFS
D.Dijkstra
Correct Answer: DFS
Explanation:
Topological sorting is typically implemented using DFS by pushing a node to a stack only after all its adjacent nodes have been visited.
Incorrect! Try again.
17If a graph is disconnected, which traversal will fail to visit all vertices if started from a single source?
A.Both BFS and DFS
B.BFS only
C.DFS only
D.Neither
Correct Answer: Both BFS and DFS
Explanation:
Standard BFS and DFS only traverse the component containing the source node. To visit all vertices in a disconnected graph, an outer loop iterating over all vertices is required.
Incorrect! Try again.
18In Dijkstra's algorithm, what is the initial distance value assigned to the source vertex?
A.-1
B.0
C.Infinity
D.1
Correct Answer: 0
Explanation:
The distance from the source to itself is always 0.
Incorrect! Try again.
19What does A[i][j] represent in the final matrix of the Floyd Warshall algorithm?
A.Boolean indicating if i and j are connected
B.Number of edges between i and j
C.Shortest distance from i to j
D.Length of the longest path from i to j
Correct Answer: Shortest distance from i to j
Explanation:
The final matrix contains the weight of the shortest path between every pair of vertices (i, j).
Incorrect! Try again.
20Which algorithm is strictly faster for sparse graphs when finding the single-source shortest path with non-negative weights?
A.Matrix Multiplication
B.Floyd Warshall
C.Bellman-Ford
D.Dijkstra (with Heap)
Correct Answer: Dijkstra (with Heap)
Explanation:
Dijkstra is O(E log V). For sparse graphs (E ~ V), this is much faster than Bellman-Ford (O(VE)) or Floyd Warshall (O(V^3)).
Incorrect! Try again.
21During DFS, if we encounter an edge to a vertex that is currently in the recursion stack, what does this indicate?
A.A disconnected component
B.A bridge
C.A cycle
D.A shortest path
Correct Answer: A cycle
Explanation:
An edge pointing back to an ancestor in the DFS tree (a node currently in the recursion stack) is called a back-edge and indicates a cycle.
Incorrect! Try again.
22Bellman-Ford works on which type of graphs?
A.Trees only
B.DAGs only
C.Undirected graphs with positive weights only
D.Directed graphs with negative weights (no negative cycles)
Correct Answer: Directed graphs with negative weights (no negative cycles)
Explanation:
Bellman-Ford is specifically designed to handle directed graphs that may contain negative weight edges, provided there are no negative weight cycles.
Incorrect! Try again.
23What is the space complexity of the Floyd Warshall algorithm?
A.O(V^3)
B.O(V)
C.O(V^2)
D.O(E)
Correct Answer: O(V^2)
Explanation:
It requires a 2D matrix of size V x V to store the distances between all pairs.
Incorrect! Try again.
24Which algorithm calculates the shortest path from a single source to all other vertices?
A.Kruskal's Algorithm
B.Johnson's Algorithm
C.Dijkstra's Algorithm
D.Floyd Warshall
Correct Answer: Dijkstra's Algorithm
Explanation:
Dijkstra's (and Bellman-Ford) are Single-Source Shortest Path algorithms. Floyd Warshall is All-Pairs.
Incorrect! Try again.
25In BFS, nodes are visited in an order based on their:
A.Distance from the source
B.Alphabetical order
C.Weight
D.Finish time
Correct Answer: Distance from the source
Explanation:
BFS visits nodes layer by layer, which corresponds to their unweighted distance (number of edges) from the source.
Incorrect! Try again.
26In the context of Bellman-Ford, what happens if the graph contains a negative weight cycle?
A.The algorithm converts negative weights to positive.
B.The algorithm loops infinitely.
C.The algorithm returns the correct shortest path.
D.The algorithm can report the existence of the cycle.
Correct Answer: The algorithm can report the existence of the cycle.
Explanation:
Bellman-Ford can detect the cycle by performing one extra relaxation pass after the (V-1)th iteration. If distances change, a negative cycle exists.
Incorrect! Try again.
27The recurrence relation D[i][j] = min(D[i][j], D[i][k] + D[k][j]) belongs to which algorithm?
A.Floyd Warshall
B.Dijkstra
C.Bellman-Ford
D.DFS
Correct Answer: Floyd Warshall
Explanation:
This logic checks if going from i to j via intermediate node k is cheaper than the direct path (or previously calculated path) from i to j.
Incorrect! Try again.
28Which of the following is an application of DFS?
A.Finding the shortest path in unweighted graphs
B.Broadcasting in a network
C.GPS Navigation systems
D.Solving the maze problem
Correct Answer: Solving the maze problem
Explanation:
DFS is ideal for maze solving as it explores one path deeply before backtracking, effectively simulating a strategy of 'keep going until you hit a wall'.
Incorrect! Try again.
29If we use an adjacency matrix to represent a graph for Dijkstra's algorithm, the time complexity becomes:
A.O(E log V)
B.O(E + V)
C.O(V^3)
D.O(V^2)
Correct Answer: O(V^2)
Explanation:
Without a priority queue (using a linear search for the min distance node), Dijkstra takes O(V^2), which is actually better for dense graphs (where E ~ V^2).
Incorrect! Try again.
30What is the maximum number of edges in a connected undirected graph with V vertices?
A.V
B.V - 1
C.V^2
D.V(V-1)/2
Correct Answer: V(V-1)/2
Explanation:
In a complete undirected graph, every vertex is connected to every other vertex.
Incorrect! Try again.
31Which traversal algorithm uses less memory (space complexity) for a very deep but narrow tree?
A.Bellman-Ford
B.Dijkstra
C.DFS
D.BFS
Correct Answer: BFS
Explanation:
BFS must store all nodes at the current level in the queue, which can be up to V/2 in the worst case. DFS only stores the current path.
Incorrect! Try again.
32Which of the following algorithms can handle directed graphs with negative edges?
A.Bellman-Ford
B.Dijkstra
C.Prim
D.Kruskal
Correct Answer: Bellman-Ford
Explanation:
Bellman-Ford is specifically capable of handling negative weights, unlike Dijkstra or the MST algorithms.
Incorrect! Try again.
33What is the initial state of the distance array in Dijkstra's algorithm for all vertices except the source?
A.1
B.Infinity
C.Undefined
D.0
Correct Answer: Infinity
Explanation:
All nodes are initialized to Infinity to represent that they are currently unreachable, except the source which is 0.
Incorrect! Try again.
34In a Dense Graph (where E is close to V^2), which algorithm is generally preferred for Single Source Shortest Path?
A.Bellman-Ford
B.Floyd Warshall
C.Dijkstra using Priority Queue
D.Dijkstra using Array
Correct Answer: Dijkstra using Array
Explanation:
Using an array (linear search) gives O(V^2). Using a binary heap gives O(E log V) which becomes O(V^2 log V) in a dense graph. O(V^2) is better.
Incorrect! Try again.
35A 'Cross Edge' is a concept encountered in which algorithm?
A.BFS
B.Floyd Warshall
C.DFS
D.Bellman-Ford
Correct Answer: DFS
Explanation:
In DFS classification of edges, a cross edge connects two nodes where neither is an ancestor of the other in the DFS tree.
Incorrect! Try again.
36To reconstruct the shortest path after running Dijkstra’s or Bellman-Ford, what additional information must be stored?
A.The edge weights
B.The degree of nodes
C.The visit time
D.The parent (predecessor) of each node
Correct Answer: The parent (predecessor) of each node
Explanation:
By storing the predecessor node that successfully relaxed the distance, one can backtrack from the destination to the source to find the path.
C.Yes, if a diagonal element distance becomes negative.
D.Only if the graph is undirected.
Correct Answer: Yes, if a diagonal element distance becomes negative.
Explanation:
Normally the distance from a node to itself is 0. If dist[i][i] becomes negative, it implies a path from i to i with negative total weight (a cycle).
Incorrect! Try again.
38Which algorithm calculates the Transitive Closure of a graph?
A.Bellman-Ford
B.Dijkstra
C.Prim
D.Floyd Warshall
Correct Answer: Floyd Warshall
Explanation:
Floyd Warshall can be adapted to find the transitive closure (reachability) by using boolean AND/OR operations instead of min/add.
Incorrect! Try again.
39In BFS, what are the colors usually associated with nodes during processing?
A.0, 1, 2
B.Red, Green, Blue
C.True, False, Null
D.White, Gray, Black
Correct Answer: White, Gray, Black
Explanation:
Standard CLRS notation uses White (unvisited), Gray (visiting/in queue), and Black (visited/processed).
Incorrect! Try again.
40Dijkstra's algorithm can be implemented efficiently using:
A.Max-Priority Queue
B.Stack
C.Min-Priority Queue
D.Queue
Correct Answer: Min-Priority Queue
Explanation:
A Min-Priority Queue efficiently retrieves the vertex with the smallest tentative distance.
Incorrect! Try again.
41If you need to find the shortest path between two specific nodes (u, v), which algorithm is typically stopped early?
A.Dijkstra
B.Kruskal
C.Bellman-Ford
D.Floyd Warshall
Correct Answer: Dijkstra
Explanation:
Dijkstra's algorithm can be terminated as soon as the destination node v is extracted from the priority queue.
Incorrect! Try again.
42Which algorithm is capable of handling a graph with cycles?
A.BFS
B.Dijkstra
C.DFS
D.All of the above
Correct Answer: All of the above
Explanation:
All these algorithms utilize a mechanism (like a visited array or distance check) to handle cycles and prevent infinite loops.
Incorrect! Try again.
43The process of updating the distance of a vertex v using a neighbor u is called:
A.Initialization
B.Relaxation
C.Exploration
D.Visitation
Correct Answer: Relaxation
Explanation:
Relaxation is the step where we check if a path through u offers a shorter route to v than the currently known path.
Incorrect! Try again.
44What is the minimum number of edges required to connect a graph with N vertices?
A.N - 1
B.N
C.0
D.N / 2
Correct Answer: N - 1
Explanation:
A tree is a minimally connected graph, and a tree with N vertices has N-1 edges.
Incorrect! Try again.
45Which algorithm is most sensitive to the order of edges processed if not using a specific data structure?
A.BFS
B.Bellman-Ford
C.Floyd Warshall
D.None
Correct Answer: Bellman-Ford
Explanation:
While the final result is the same, the speed of convergence in Bellman-Ford can vary depending on the order edges are relaxed, though the worst-case complexity remains O(VE).
Incorrect! Try again.
46In a graph where edge weights represent probabilities of success, how do we transform the problem to use Shortest Path algorithms?
A.Use 1/weight
B.Use 1 - weight
C.Use -log(weight)
D.Use weight^2
Correct Answer: Use -log(weight)
Explanation:
To maximize product of probabilities (P1 * P2...), we minimize sum of negative logs (-log(P1) + -log(P2)...).
Incorrect! Try again.
47Breadth-First Search is equivalent to Level-Order Traversal in which data structure?
A.Tree
B.Graph
C.Array
D.Stack
Correct Answer: Tree
Explanation:
BFS on a tree starting from the root visits nodes level by level, exactly like Level-Order Traversal.
Incorrect! Try again.
48Which graph representation is most space-efficient for sparse graphs?
A.Adjacency List
B.Incidence Matrix
C.Adjacency Matrix
D.2D Array
Correct Answer: Adjacency List
Explanation:
Adjacency List uses O(V + E) space, whereas Adjacency Matrix uses O(V^2). For sparse graphs (E << V^2), the list is much smaller.
Incorrect! Try again.
49In the classification of edges in DFS, what is a 'Forward Edge'?
A.An edge from a node to its ancestor
B.The edge connecting parent to child in the DFS tree
C.An edge to a previously visited node in a different branch
D.An edge from a node to a descendant that is not a child
Correct Answer: An edge from a node to a descendant that is not a child
Explanation:
A forward edge connects a vertex to one of its descendants in the DFS tree (skipping levels).
Incorrect! Try again.
50Why is Bellman-Ford not preferred over Dijkstra for graphs with non-negative weights?
A.Bellman-Ford is harder to implement
B.Bellman-Ford requires more space
C.Bellman-Ford has a higher time complexity
D.Bellman-Ford gives incorrect results for positive weights
Correct Answer: Bellman-Ford has a higher time complexity
Explanation:
Bellman-Ford is O(VE) while Dijkstra is O(E log V). For most graphs, Dijkstra is significantly faster.
Incorrect! Try again.
Did this save you a night before the exam?
LPU Notes is free, and it stays free. Ads cover part of the server bill.
The rest comes out of a student's own pocket: the domain, the storage,
and keeping the site up through the weeks everyone needs it at once.
The payment button didn't load. An ad blocker or a filtered network is the usual reason.
to try again.
Nothing here is ever locked, and nothing unlocks. Chip in only if it was worth it.
What it pays for →