Design and Analysis of Algorithms MCQs with Answers
Practice important Design and Analysis of Algorithms MCQs with answers and explanations.
Multiple Choice Questions
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
View Answer
B
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
View Answer
C
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)
View Answer
A
Q234: In depth-first search, what data structure is commonly used?
- A: Queue
- B: Stack
- C: Array
- D: Linked list
View Answer
B
Q235: Which of the following is not a type of graph?
- A: Undirected graph
- B: Cyclic graph
- C: Cubic graph
- D: Weighted graph
View Answer
C
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
View Answer
B
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
View Answer
A
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
View Answer
B
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
View Answer
C
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
View Answer
B