Learn Data Structure Graph Multiple Choice Questions and Answers with explanations. Practice Data Structure Graph MCQs Online Quiz Mock Test For Objective Interview.

1. What is the maximum number of possible non zero values in an adjacency matrix of a simple graph with n vertices?
### Answer & Explanation

### Workspace

### Report Error

Answer: Option C

Explanation:

Out of n*n possible values for a simple graph the diagonal values will always be zero.

2. On which of the following statements does the time complexity of checking if an edge exists between two particular vertices is not, depends?
### Answer & Explanation

### Workspace

### Report Error

Answer: Option C

Explanation:

To check if there is an edge between to vertices i and j, it is enough to see if the value of A[i][j] is 1 or 0, here A is the adjacency matrix.

3. If there are more than 1 topological sorting of a DAG is possible, which of the following is true.
### Answer & Explanation

### Workspace

### Report Error

Answer: Option B

Explanation:

For a Hamiltonian path to exist all the vertices must be connected with a path, had that happened there would have been a unique topological sort.

4. Assuming value of every weight to be greater than 10, in which of the following cases the shortest path of a directed weighted graph from 2 vertices u and v will never change?
### Answer & Explanation

### Workspace

### Report Error

Answer: Option C

Explanation:

In case of addition or subtraction the shortest path may change because the number of edges between different paths may be different, while in case of multiplication path wont change.

5. A connected planar graph having 6 vertices, 7 edges contains _____________ regions.
### Answer & Explanation

### Workspace

### Report Error

Answer: Option B

Explanation:

By eulerâ€™s formula the relation between vertices(n), edges(q) and regions(r) is given by n-q+r=2.