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