Design and Analysis of Algorithms MCQs with Answers
Practice important Design and Analysis of Algorithms MCQs with answers and explanations.
Chapter: 7
Q221:
The solution to the fractional knapsack problem can be visualized as filling a knapsack with which of the following?
A. Whole items only
B. Fractions of items only
C. Whole and fractional items
D. Neither A nor B
Correct Answer:
C
Chapter: 8
Q222:
What is a graph primarily used to model?
A. Static data
B. Linear equations
C. Connections between objects
D. Complex algorithms
Correct Answer:
C
Chapter: 8
Q223:
In graph theory, what does a vertex represent?
A. A connection between objects
B. A set of edges
C. A point of intersection
D. An object in a graph
Correct Answer:
C
Chapter: 8
Q224:
What is the term for a graph without cycles?
A. Acyclic graph
B. Cyclic graph
C. Directed graph
D. Weighted graph
Correct Answer:
A
Chapter: 8
Q225:
In a directed graph, what is the out-degree of a vertex?
A. The number of edges coming into the vertex
B. The number of edges going out of the vertex
C. The total number of edges
D. The number of vertices connected to it
Correct Answer:
B
Chapter: 8
Q226:
How is an adjacency matrix defined?
A. A binary tree structure
B. A list of vertices
C. A square matrix representing edges between vertices
D. A collection of edges
Correct Answer:
C
Chapter: 8
Q227:
What does an adjacency list contain?
A. A list of all vertices in the graph
B. An array of edges for each vertex
C. A matrix of vertex connections
D. A list of weights for each edge
Correct Answer:
B
Chapter: 8
Q228:
In a connected graph, what can be said about the vertices?
A. Some vertices cannot be reached from others
B. All vertices can reach every other vertex
C. Only one vertex is reachable from any other vertex
D. All vertices have the same degree
Correct Answer:
B
Chapter: 8
Q229:
Which traversal algorithm uses a queue for implementation?
A. Depth-first search
B. Breadth-first search
C. Graph traversal
D. Topological sort
Correct Answer:
B
Chapter: 8
Q230:
What is the purpose of the predecessor pointer in shortest path algorithms?
A. To keep track of the longest path
B. To store the distance to each vertex
C. To trace back the shortest path
D. To store unvisited vertices
Correct Answer:
C
Chapter: 8
Q231:
What is the characteristic of a Hamiltonian cycle?
A. It visits every edge exactly once
B. It visits every vertex exactly once
C. It is a directed cycle
D. It contains no loops
Correct Answer:
B
Chapter: 8
Q232:
What does the term 'degree of a vertex' refer to in an undirected graph?
A. The number of vertices connected to it
B. The total number of edges in the graph
C. The number of edges incident on the vertex
D. The maximum distance to any other vertex
Correct Answer:
C
Chapter: 8
Q233:
What is the worst-case time complexity of breadth-first search in a graph?
A. O(V + E)
B. O(E)
C. O(V^2)
D. O(E log V)
Correct Answer:
A
Chapter: 8
Q234:
In depth-first search, what data structure is commonly used?
A. Queue
B. Stack
C. Array
D. Linked list
Correct Answer:
B
Chapter: 8
Q235:
Which of the following is not a type of graph?
A. Undirected graph
B. Cyclic graph
C. Cubic graph
D. Weighted graph
Correct Answer:
C
Chapter: 8
Q236:
What does it mean for a graph to be 'directed'?
A. The edges have no direction
B. The edges point from one vertex to another
C. The graph has no loops
D. The graph is fully connected
Correct Answer:
B
Chapter: 8
Q237:
What is represented by the adjacency list for vertex v?
A. The vertices adjacent to v
B. All vertices in the graph
C. Only the starting vertex
D. The degree of vertex v
Correct Answer:
A
Chapter: 8
Q238:
What type of graph traversal algorithm visits vertices in bands from the source vertex?
A. Depth-first search
B. Breadth-first search
C. Graph traversal
D. Shortest path algorithm
Correct Answer:
B
Chapter: 8
Q239:
Which of the following statements about cycles in a directed graph is true?
A. A cycle must have exactly one vertex
B. A cycle can exist without edges
C. A Hamiltonian cycle visits every vertex exactly once
D. A cycle cannot exist in a directed graph
Correct Answer:
C
Chapter: 8
Q240:
A graph is said to be disconnected if:
A. There are no edges
B. Some vertices cannot reach others
C. Every vertex can reach every other vertex
D. There are cycles present
Correct Answer:
B