Design And Analysis Of Algorithms Set 13 MCQs

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