Design And Analysis Of Algorithms Set 13

On This Page

This set of Design and Analysis of Algorithms Multiple Choice Questions & Answers (MCQs) focuses on Design And Analysis Of Algorithms Set 13

Q1 | Fractional knapsack problem can be solved in time O(n).
  • true
  • false
Q2 | Find the maximum value output assuming items to be divisible.
  • 60
  • 80 c) 100
  • d) 40
Q3 | The result of the fractional knapsack is greater than or equal to 0/1 knapsack.
  • true
  • false
Q4 | The main time taking step in fractional knapsack problem is                        
  • breaking items into fraction
  • adding items into knapsack
  • sorting
  • looping through sorted items
Q5 | Find the maximum value output assuming items to be divisible and nondivisible respectively.
  • 100, 80
  • 110, 70
  • 130, 110
  • 110, 80
Q6 | Given G is a bipartite graph and the bipartitions of this graphs are U and V respectively. What is the relation between them?
  • number of vertices in u = number of vertices in v
  • sum of degrees of vertices in u = sum of degrees of vertices in v
  • number of vertices in u > number of vertices in v
  • nothing can be said
Q7 | 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?
  • number of vertices in u=number of vertices in v
  • number of vertices in u not equal to number of vertices in v
  • number of vertices in u always greater than the number of vertices in v
  • nothing can be said
Q8 | A complete bipartite graph is a one in which each vertex in set X has an edge with set Y. Let n be the total number of vertices. For maximum number of edges, the total number of vertices hat should be present on set X is?
  • n
  • n/2
  • n/4
  • data insufficient
Q9 | When is a graph said to be bipartite?
  • if it can be divided into two independent sets a and b such that each edge connects a vertex from to a to b
  • if the graph is connected and it has odd number of vertices
  • if the graph is disconnected
  • if the graph has at least n/2 vertices whose degree is greater than n/2
Q10 | Are trees bipartite?
  • yes
  • no
  • yes if it has even number of vertices
  • no if it has odd number of vertices
Q11 | A graph has 20 vertices. The maximum number of edges it can have is? (Given it is bipartite)
  • 100
  • 140
  • 80
  • 20
Q12 | Given that a graph contains no odd cycle. Is it enough to tell that it is bipartite?
  • yes
  • no
Q13 | Can there exist a graph which is both eulerian and is bipartite?
  • yes
  • no
  • yes if it has even number of edges
  • nothing can be said
Q14 | A graph is found to be 2 colorable. What can be said about that graph?
  • the given graph is eulerian
  • the given graph is bipartite
  • the given graph is hamiltonian
  • the given graph is planar
Q15 | Which type of graph has no odd cycle in it?
  • bipartite
  • histogram
  • cartesian
  • pie
Q16 | What type of graph has chromatic number less than or equal to 2?
  • histogram
  • bipartite
  • cartesian
  • tree
Q17 | Which of the following is the correct type of spectrum of the bipartite graph?
  • symmetric
  • anti – symmetric
  • circular
  • exponential
Q18 | Which of the following is not a property of the bipartite graph?
  • no odd cycle
  • symmetric spectrum
  • chromatic number is less than or equal to 2
  • asymmetric spectrum
Q19 | Which one of the following is the chromatic number of bipartite graph?
  • 1
  • 4
  • 3
  • 5
Q20 | Which graph has a size of minimum vertex cover equal to maximum matching?
  • cartesian
  • tree
  • heap
  • bipartite
Q21 | Which theorem gives the relation between the minimum vertex cover and maximum matching?
  • konig’s theorem
  • kirchhoff’s theorem
  • kuratowski’s theorem
  • kelmans theorem
Q22 | Which of the following is not a property of perfect graph?
  • compliment of line graph of bipartite graph
  • compliment of bipartite graph
  • line graph of bipartite graph
  • line graph
Q23 | Which of the following has maximum clique size 2?
  • perfect graph
  • tree
  • histogram
  • cartesian
Q24 | What is the chromatic number of compliment of line graph of bipartite graph?
  • 0
  • 1
  • 2
  • 3
Q25 | What is the clique size of the line graph of bipartite graph?
  • 0
  • 1
  • 2
  • 3