Algorithms MCQs (Set-3)

What problem does Dijkstra's algorithm solve?

A Minimum spanning tree
B All pairs connectivity only
C Single source shortest paths
D String pattern search

What edge weight condition does Dijkstra require?

A Nonnegative weights
B All weights equal one
C Negative weights only
D No weighted edges

Which algorithm supports negative edge weights?

A Dijkstra
B Bellman Ford
C Kruskal
D Binary search

What does Floyd Warshall compute?

A One minimum spanning tree
B Single pattern match
C Only unweighted reachability
D All pairs shortest paths

What is edge relaxation?

A Delete a heavy edge
B Try improving a known distance
C Reverse a graph path
D Mark a vertex visited

What does a minimum spanning tree minimize?

A Number of vertices
B Total edge weight
C Longest path length
D Maximum vertex degree

How does Kruskal's algorithm select edges?

A Decreasing weight with cycles
B Breadth first by distance
C Increasing weight without cycles
D Randomly until connected

Which structure helps Kruskal detect components?

A Stack
B Disjoint set union
C Trie
D Circular queue

How does Prim's algorithm grow a spanning tree?

A Sorts all vertices by name
B DFS from every edge
C Removes the lightest vertex
D Adds light crossing edge

What does topological sorting require?

A Undirected cycle
B Directed acyclic graph
C Complete weighted graph
D Binary search tree

What does indegree count?

A Outgoing paths only
B All reachable vertices
C Distinct graph components
D Incoming directed edges

Which traversal is useful for topological sorting?

A Binary search
B Heap sort
C Depth first search
D Linear probing

What is a strongly connected directed graph?

A Every edge has equal weight
B It has no cycles
C Every vertex reaches every other
D It contains one source only

What does Kosaraju's algorithm find?

A Minimum spanning tree
B Negative weight cycles
C Strongly connected components
D String prefixes

What does A star prioritize?

A Only number of vertices
B Largest edge weight
C Random priority values
D Path cost plus heuristic

What does an admissible A star heuristic guarantee?

A Never overestimates remaining cost
B Always equals exact cost
C Can be negative only
D Ignores goal distance

What does breadth first search find shortest paths for?

A Graphs with negative weights
B All weighted graphs
C Only directed cycles
D Unweighted graphs

What does depth first search commonly help detect?

A Cycles and connectivity
B Sorted numeric order
C Minimum weights only
D Hash collisions

What is a bridge in an undirected graph?

A Edge whose removal disconnects graph
B Edge in every cycle
C Vertex with no neighbors
D Minimum weight edge

What is an articulation vertex?

A Vertex of maximum degree
B Vertex whose removal disconnects graph
C Vertex with no outgoing edges
D A source in every path

What is an Euler circuit?

A Path visiting every vertex once
B Cycle with minimum weight
C Walk using every vertex twice
D Closed walk, each edge once

What is a Hamiltonian cycle?

A Cycle visiting every vertex once
B Cycle using every edge once
C Shortest weighted path
D A tree with every leaf

What is transitive closure of a graph?

A Reachability relation between vertices
B Minimum spanning edge set
C Sorted adjacency list
D Shortest path tree only

What does a negative cycle allow in shortest path problems?

A Path cost decreases indefinitely
B Every path becomes unique
C All distances become positive
D The graph becomes acyclic

What does a graph cut separate?

A Edges by weight only
B Cycles from paths
C Vertices into two groups
D Source code into modules