/* */ 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 ____________

O(V)
O(E2)
O(E)
O(V2)

Answer:- (D).
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

in,out
out,in
in,total
total,out

Answer:- (B).
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?

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

Answer:- (C).
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.

Answer:- (B).
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?

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

Answer:- (C).
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

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

Answer:- (B).
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.

Answer:- (B).
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?

Answer:- (D).
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?

O(S1)
O(S2)
O(S1+S2)
O(1)

Answer:- (A).
Explanations :For each check of a word of length S1, we need to follow at most S1 edges.

Q10.What is the maximum number of edges in a bipartite graph having 10 vertices?

Answer:- (C).
Explanations :Let one set have n vertices another set would contain 10-n vertices. Total number of edges would be n*(10-n), differentiating with respect to n, would yield the answer.

« PREVIOUS PAGE NEXT PAGE »