Questions and answers for exam Preparation

MCQs

Total Questions : 9

Question 1. A connected planar graph having 6 vertices, 7 edges contains _____________ regions.

Discuss Question

Answer: Option B. -> 3

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

Question 2. 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?

add all values by 10
subtract 10 from all the values
multiply all values by 10
In both the cases of multiplying and adding by 10

Discuss Question

Answer: Option C. -> multiply all values by 10

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.

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

Many Hamiltonian paths are possible
No Hamiltonian path is possible
Exactly 1 Hamiltonian path is possible
Given information is insufficient to comment anything

Discuss Question

Answer: Option B. -> No Hamiltonian path is possible

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.

Question 4. On which of the following statements does the time complexity of checking if an edge exists between two particular vertices is not, depends?

Depends on the number of edges
Depends on the number of vertices
Is independent of both the number of edges and vertices
It depends on both the number of edges and vertices

Discuss Question

Answer: Option C. -> Is independent of both the number of edges and vertices

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.

Question 5. What is the maximum number of possible non zero values in an adjacency matrix of a simple graph with n vertices?

(n*(n-1))/2
(n*(n+1))/2
n*(n-1)
n*(n+1)

Discuss Question

Answer: Option C. -> n*(n-1)

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

Question 6. If a connected Graph (G) contains n vertices what would be the rank of its incidence matrix?

n-1
values greater than n are possible
values less than n-1 are possible
Insufficient Information is given

Discuss Question

Answer: Option A. -> n-1

Every column of the incidence matrix may contain only +1 and -1 as non zero entries rank would be less than n.

Question 7. What is time complexity to check if a string(length S1) is a substring of another string(length S2) stored in a Directed Acyclic Word Graph, given S2 is greater than S1?