/* */ Click to Join Live Class with Shankar sir Call 9798158723

# Data Structure MCQ - Graph

Q1.The time complexity to calculate the number of edges in a graph whose information instored in form of an adjacency matrix is ____________
1. O(V)
2. O(E2)
3. O(E)
4. O(V2)

Explanations :As V entries are 0, a total of V^2-V entries are to be examined
Q2.For the adjacency matrix of a directed graph the row sum is the _________ degree andthe column sum is the ________ degree
1. in,out
2. out,in
3. in,total
4. total,out

Explanations :Row number of the matrix represents the tail, while Column number representsthe head of the edge
Q3. What is the maximum number of possible non zero values in an adjacency matrix of a simple graph with n vertices?
1. (n*(n-1))/2
2. (n*(n+1))/2
3. n*(n-1)
4. n*(n+1)

Explanations :Out of n*n possible values for a simple graph the diagonal values will always be zero.
Q4.A connected planar graph having 6 vertices, 7 edges contains _____________ regions.
1. 15
2. 3
3. 1
4. 11

Explanations :By euler’s formula the relation between vertices(n), edges(q) and regions(r) is given by n-q+r=2.
Q5.On which of the following statements does the time complexity of checking if an edge exists between two particular vertices is not, depends?
1. Depends on the number of edges
2. Depends on the number of vertices
3. Is independent of both the number of edges and vertices
4. It depends on both the number of edges and vertices

Explanations :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.
Q6.If there are more than 1 topological sorting of a DAG is possible, which of the following is true
1. Many Hamiltonian paths are possible
2. No Hamiltonian path is possible
3. Exactly 1 Hamiltonian path is possible
4. Given information is insufficient to comment anything

Explanations :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.
Q7.A connected planar graph having 6 vertices, 7 edges contains _____________ regions.
1. 15
2. 3
3. 1
4. 13

Explanations :By euler's formula the relation between vertices(n), edges(q) and regions(r) is given by n-q+r=2.
Q8.What is the maximum possible number of edges in a directed graph with no self loop shaving vertices?
1. 28
2. 64
3. 256
4. 56

Explanations : If a graph has V vertices than every vertex can be connected to apossible of V-1 vertices
Q9.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? 1. O(S1)
2. O(S2)
3. O(S1+S2)
4. O(1)