Related InterviewSolutions

• Which of the following is an advantage of adjacency list representation over adjacency matrix representation of a graph?(A) In adjacency list representation, space is saved for sparse graphs.(B) DFS and BSF can be done in O(V + E) time for adjacency list representation. These operations take O(V^2) time in adjacency matrix representation. Here is V and E are number of vertices and edges respectively.(C) Adding a vertex in adjacency list representation is easier than adjacency matrix representation.(D) All of the above
• Consider an undirected random graph of eight vertices. The probability that there is an edge between a pair of vertices is 1/2. What is the expected number of unordered cycles of length three?(A) 1/8(B) 1(C) 7(D) 8
• How many undirected graphs (not necessarily connected) can be constructed out of a given set V= {V 1, V 2,…V n} of n vertices ?(A) n(n-l)/2(B) 2^n(C) n!(D) 2^(n(n-1)/2)
• Given an undirected graph G with V vertices and E edges, the sum of the degrees of all vertices is(A) E(B) 2E(C) V(D) 2V
• Which of the following statements is/are TRUE for an undirected graph?P: Number of odd degree vertices is evenQ: Sum of degrees of all vertices is even(A) P Only(B) Q Only(C) Both P and Q(D) Neither P nor Q
• Consider an undirected unweighted graph G. Let a breadth-first traversal of G be done starting from a node r. Let d(r, u) and d(r, v) be the lengths of the shortest paths from r to u and v respectively, in G. lf u is visited before v during the breadth-first traversal, which of the following statements is correct? (GATE CS 2001)(A) d(r, u) < d (r, v)(B) d(r, u) > d(r, v)(C) d(r, u) <= d (r, v)(D) None of the above
• The most efficient algorithm for finding the number of connected components in an undirected graph on n vertices and m edges has time complexity.(A) (n)(B) (m)(C) (m + n)(D) (mn)(A) A(B) B(C) C(D) D