Data Structure II Practice Test 5

1. Breadth First Search is equivalent to which of the traversal in the Binary Trees?

Pre-order Traversal

Level-order Traversal

In-order Traversal

Post-order Traversal

2. A simple acyclic path between source and sink which pass through only positive weighted edges is called?

residual path

augmenting path

maximum path

critical path

3. Consider the following graph. What is the minimum cost to travel from node A to node C?

4. If there are n couples who would prefer each other to their actual marriage partners, then the assignment is said to be unstable.

True

False

5. A graph is said to have a negative weight cycle when?

The total weight of the graph is negative

The graph has 1 negative weighted edge

The graph has 1 or more negative weighted edges

The graph has a cycle

6. What is the simplest method to prove that a graph is bipartite?

It does not have a cycle of an odd length

Both odd and even cycles are formed

It has a cycle of an odd length

It does not have cycles

7. Which of the following is not a branch and bound strategy to generate branches?

FIFO branch and bound

LIFO branch and bound

Lowest cost branch and bound

Highest cost branch and bound

8. A matching that matches all the vertices of a graph is called?

Good matching

Simplex matching

Cardinality matching

Perfect matching

9. Given pseudo code of Dijkstra's Algorithm.

//Initialise single source(G,s)
S=0
Q=V[G]
While Q != 0
    Do u=extract-min(Q)
        S=S union {u}
	    For each vertex v in adj[u]
	        Do relax(u,v,w)

What happens when "While Q != 0" is changed to "while Q>1"?

While loop does not get executed

While loop gets executed for v times

While loop gets executed for v-1 times

While loop gets executed only once

10. How many solution/solutions are available for a graph having negative weight cycle?

Two solutions

No solution

One solution

Infinite solutions