Data Structure II Mock Test 5

10%

Question 1 of 10

1. Which of the following is the greedy best first search?

Both A* and B*

Pure Heuristic Search

Question 1 of 10

Question 2 of 10

2. Find the maximum flow from the following graph.

Question 2 of 10

Question 3 of 10

3. Bellmann Ford algorithm is used to indicate whether the graph has negative weight cycles or not.

True

False

Question 3 of 10

Question 4 of 10

4. In the given graph, what is the minimum cost to travel from vertex 1 to vertex 3?

-3

Question 4 of 10

Question 5 of 10

5. Which of the following is an NP complete problem?

Finding maximum element in an array

Calculating chromatic number of graph

Hamiltonian cycle

Travelling salesman problem

Question 5 of 10

Question 6 of 10

6. Which of the following is false about Prim’s algorithm?

It never accepts cycles in the MST

It is a greedy algorithm

It constructs MST by selecting edges in increasing order of their weights

It can be implemented using the Fibonacci heap

Question 6 of 10

Question 7 of 10

7. What is the running time of Karger’s algorithm to find the minimum cut in a graph?

O(|V|²)

O(|E|)

O(E)

O(V)

Question 7 of 10

Question 8 of 10

8. Consider the following statements.
S1. Kruskal’s algorithm might produce a non-minimal spanning tree.
S2. Kruskal’s algorithm can efficiently implemented using the disjoint-set data structure.

Both S1 and S2 are true

Both S1 and S2 are false

S1 is true but S2 is false

S2 is true but S1 is false

Question 8 of 10

Question 9 of 10

9. Which of the following is false in the case of a spanning tree of a graph G?

It includes every vertex of the G

It is tree that spans G

It can be either cyclic or acyclic

It is a subgraph of the G

Question 9 of 10

Question 10 of 10

10. What will be the chromatic number for a line graph having n vertices?

Question 10 of 10