Top 150+ Solved Design and Analysis of Algorithms MCQ Questions Answer
Q. The main time taking step in fractional knapsack problem is
a. breaking items into fraction
b. adding items into knapsack
c. sorting
d. looping through sorted items
Q. Find the maximum value output assuming items to be divisible and nondivisible respectively.
a. 100, 80
b. 110, 70
c. 130, 110
d. 110, 80
Q. Given G is a bipartite graph and the bipartitions of this graphs are U and V respectively. What is the relation between them?
a. number of vertices in u = number of vertices in v
b. sum of degrees of vertices in u = sum of degrees of vertices in v
c. number of vertices in u > number of vertices in v
d. nothing can be said
Q. A k-regular bipartite graph is the one in which degree of each vertices is k for all the vertices in the graph. Given that the bipartitions of this graph are U and V respectively. What is the relation between them?
a. number of vertices in u=number of vertices in v
b. number of vertices in u not equal to number of vertices in v
c. number of vertices in u always greater than the number of vertices in v
d. nothing can be said
Q. When is a graph said to be bipartite?
a. if it can be divided into two independent sets a and b such that each edge connects a vertex from to a to b
b. if the graph is connected and it has odd number of vertices
c. if the graph is disconnected
d. if the graph has at least n/2 vertices whose degree is greater than n/2
Q. Are trees bipartite?
a. yes
b. no
c. yes if it has even number of vertices
d. no if it has odd number of vertices
Q. A graph has 20 vertices. The maximum number of edges it can have is? (Given it is bipartite)
a. 100
b. 140
c. 80
d. 20
Q. Can there exist a graph which is both eulerian and is bipartite?
a. yes
b. no
c. yes if it has even number of edges
d. nothing can be said
Q. A graph is found to be 2 colorable. What can be said about that graph?
a. the given graph is eulerian
b. the given graph is bipartite
c. the given graph is hamiltonian
d. the given graph is planar