Design and Analysis of Algorithms MCQs with Answers
Practice important Design and Analysis of Algorithms MCQs with answers and explanations.
Chapter: 8
Q261:
A fill-in-the-blank for the DFS algorithm states: When we first discover a vertex, we store a counter in ______.
A. d[u]
B. f[u]
C. color[u]
D. none of the above
Correct Answer:
A
Chapter: 8
Q262:
The time stamp "2/5" indicates that a vertex was discovered at time ______ and finished processing at time ______.
A. 2 and 5
B. 5 and 2
C. 1 and 10
D. None of the above
Correct Answer:
A
Chapter: 8
Q263:
In the precedence constraint graph for CS courses, what does an edge from C2 to C4 represent?
A. Course C2 must be taken before C4
B. Course C4 must be taken before C2
C. Courses are unrelated
D. None of the above
Correct Answer:
A
Chapter: 8
Q264:
For undirected graphs, edges are typically classified as ______.
A. Tree edges only
B. Back edges only
C. Forward edges only
D. Back edges (by convention)
Correct Answer:
D
Chapter: 8
Q265:
What is a digraph?
A. An undirected graph
B. A directed graph
C. A weighted graph
D. A cyclic graph
Correct Answer:
B
Chapter: 8
Q266:
A digraph is strongly connected if ______.
A. Every vertex can reach every other vertex
B. At least one vertex can reach another vertex
C. There are no isolated vertices
D. All vertices have the same degree
Correct Answer:
A
Chapter: 8
Q267:
The strongly connected components of a digraph can be found using which algorithm?
A. Depth-First Search
B. Prim's Algorithm
C. Kruskal's Algorithm
D. None of the above
Correct Answer:
A
Chapter: 8
Q268:
In a strongly connected digraph, every vertex must appear in ______.
A. The same DFS tree
B. A different DFS tree
C. Any tree structure
D. Only one tree
Correct Answer:
A
Chapter: 8
Q269:
When merging vertices in a strong component, the resulting graph is called ______.
A. Component digraph
B. Directed acyclic graph
C. Equivalence graph
D. Adjacency list
Correct Answer:
A
Chapter: 8
Q270:
The maximum finish times of components in a digraph are related to ______.
A. The component DAG
B. Graph colorings
C. Spanning trees
D. Cycle detection
Correct Answer:
A
Chapter: 8
Q271:
Which of the following is true regarding the finish times in DFS?
A. They are always in increasing order
B. They are always in decreasing order
C. They can be in any order
D. They depend on the graph structure
Correct Answer:
C
Chapter: 8
Q272:
To find strong components, we must first compute ______. The adjacency matrix
A. The reversed topological order
B. The component DAG
C. The spanning tree
Correct Answer:
C
Chapter: 8
Q273:
Kruskal's and Prim's algorithms are used to find ______. Strong components
A. Minimum spanning trees
B. Shortest paths
C. Connected components
Correct Answer:
B
Chapter: 8
Q274:
The weight of a minimum spanning tree is the ______. Total cost of edges included in the tree
A. Total number of vertices in the graph
B. Number of edges minus one
C. Total number of paths in the graph
Correct Answer:
A
Chapter: 8
Q275:
What happens when an edge is added to a free tree?
A. It creates a cycle
B. It connects all components
C. It increases the tree size
D. Nothing happens
Correct Answer:
A
Chapter: 8
Q276:
A minimum spanning tree is a tree of ______. Maximum weight
A. Minimum weight
B. Average weight
C. Total weight
Correct Answer:
B
Chapter: 8
Q277:
Which algorithm always selects the cheapest option at each stage?
A. Greedy algorithm
B. Brute force algorithm
C. Backtracking algorithm
D. None of the above
Correct Answer:
A
Chapter: 8
Q278:
The execution of the strong components algorithm operates in ______ time. Θ(V + E)
A. Θ(V^2)
B. Θ(E^2)
C. Θ(VE)
Correct Answer:
A
Chapter: 8
Q279:
What does Prim's algorithm primarily focus on adding to the minimum spanning tree?
A. Edges
B. Vertices
C. Leaves
D. Cycles
Correct Answer:
C
Chapter: 8
Q280:
In Prim's algorithm, what is used to store the lightest edge weights?
A. Priority queue
B. Stack
C. Array
D. Linked list
Correct Answer:
A