Data Structure II Mock Test 5

10%

Question 1 of 10

1. What is the total number of iterations used in a maximum- matching algorithm?

[n/2]+n

[n/3]

[n/2]+1

[n/2]

Question 1 of 10

Question 2 of 10

2. The problem of maximizing the sum of weights on edges connecting matched pairs of vertices is?

Maximum weight matching

Maximum node matching

Maximum- mass matching

Maximum bipartite matching

Question 2 of 10

Question 3 of 10

3. What happens when a free man approaches a married woman?

She accepts his proposal

She simply replaces her mate with him

She goes through her preference list and accordingly, she replaces her current mate with him

She simply rejects him

Question 3 of 10

Question 4 of 10

4. Consider a complete graph G with 4 vertices. The graph G has ____ spanning trees.

Question 4 of 10

Question 5 of 10

5. Consider the following graph. Using Kruskal’s algorithm, which edge will be selected first?

Question 5 of 10

Question 6 of 10

6. Which one of the following is not an application of max-flow min-cut algorithm?

bipartite matching

closest pair

network connectivity

network reliability

Question 6 of 10

Question 7 of 10

7. Under what condition can a vertex combine and distribute flow in any manner?

It may violate edge capacities

The vertex should be a sink vertex

It should maintain flow conservation

The vertex should be a source vertex

Question 7 of 10

Question 8 of 10

8. What is the condition for proper edge coloring of a graph?

Two vertices having a common edge should not have same color

No two incident edges should have different color

Two vertices having a common edge should always have same color

No two incident edges should have the same color

Question 8 of 10

Question 9 of 10

9. An optimal solution satisfying men’s preferences is said to be?

Man optimal

Pair optimal

Best optimal

Woman optimal

Question 9 of 10

Question 10 of 10

10. Who was the first person to solve the maximum matching problem?

Hopcroft

Karp

Claude Berge

Jack Edmonds

Question 10 of 10