88 + Interview Questions in Graph in Data Structures & Algorithms I Page 2 InterviewSolution

51.	For some sparse graph an adjacency list is more space efficient against an adjacency matrix.(a) True(b) FalseEnquiry is from Adjacency List topic in portion Graph of Data Structures & Algorithms II got this question in my homework.
Answer» Right OPTION is (a) True Easiest explanation - SPACE COMPLEXITY for adjacency matrix is ALWAYS O(V*V) while space complexity for adjacency list in this case would be O(V).

Discussion

52.	Space complexity for an adjacency list of an undirected graph having large values of V (vertices) and E (edges) is ___________(a) O(E)(b) O(V*V)(c) O(E+V)(d) O(V)The question is from Adjacency List in section Graph of Data Structures & Algorithms IThis question was posed to me in an interview for job.
Answer» The correct OPTION is (c) O(E+V) Easiest explanation - In an adjacency LIST for every vertex there is a LINKED list which have the values of the edges to which it is CONNECTED.

Discussion

53.	If in a DAG N sink vertices and M source vertices exists, then the number of possible stacks in the Graph Structured Stack representation would come out to be N*M.(a) True(b) FalseAsked question is from Incidence Matrix and Graph Structured Stack in section Graph of Data Structures & Algorithms II had been asked this question during an internship interview.
Answer» CORRECT ANSWER is (b) False Explanation: The answer WOULD DEPEND on the intermediate vertices ALSO.

Discussion

54.	Graph Structured Stack finds its application in _____________(a) Bogo Sort(b) Tomita’s Algorithm(c) Todd–Coxeter algorithm(d) Heap SortMy question comes from Incidence Matrix and Graph Structured Stack in division Graph of Data Structures & Algorithms II had been asked this question during a job interview.
Answer» Right OPTION is (b) Tomita’s Algorithm Best EXPLANATION: Tomita’s is a parsing algorithm which USES Graph Structured STACK in its implementation.

Discussion

55.	If a Graph Structured Stack contains {1,2,3,4} {1,5,3,4} {1,6,7,4} and {8,9,7,4}, what would be the source and sink vertices of the DAC?(a) Source – 1, 8 Sink – 7,4(b) Source – 1 Sink – 8,4(c) Source – 1, 8 Sink – 4(d) Source – 4, Sink – 1,8I'm obligated to ask this question of Incidence Matrix and Graph Structured Stack in chapter Graph of Data Structures & Algorithms IThe question was posed to me during a job interview.
Answer» Right choice is (C) Source – 1, 8 Sink – 4 Explanation: EVERY STACK of the Graph Structured Stack represents a path, each path STARTS with the source vertex and ends with the sink vertex.

Discussion

56.	A Graph Structured Stack is a _____________(a) Undirected Graph(b) Directed Graph(c) Directed Acyclic Graph(d) Regular GraphAsked question is from Incidence Matrix and Graph Structured Stack topic in section Graph of Data Structures & Algorithms IThe question was posed to me in an online quiz.
Answer» The CORRECT option is (C) Directed ACYCLIC Graph The BEST explanation: A Graph Structured Stack is a Directed Acyclic Graph with each path representing a stack.

Discussion

57.	In the following DAG find out the number of required Stacks in order to represent it in a Graph Structured Stack.(a) 1(b) 2(c) 3(d) 4My enquiry is from Incidence Matrix and Graph Structured Stack in portion Graph of Data Structures & Algorithms IThe question was posed to me in final exam.
Answer» Right answer is (c) 3 Easiest EXPLANATION - PATH ADE, BDE and BCE are possible.

Discussion

58.	If a connected Graph (G) contains n vertices what would be the rank of its incidence matrix?(a) n-1(b) values greater than n are possible(c) values less than n-1 are possible(d) insufficient Information is givenMy question is taken from Incidence Matrix and Graph Structured Stack topic in section Graph of Data Structures & Algorithms IThis question was posed to me by my college professor while I was bunking the class.
Answer» The correct option is (a) n-1 The best I can explain: Every column of the incidence matrix may contain only +1 and -1 as NON zero ENTRIES RANK would be less than n.

Discussion

59.	Time complexity to check if an edge exists between two vertices would be ___________(a) O(V*V)(b) O(V+E)(c) O(1)(d) O(E)My doubt is from Incidence Matrix and Graph Structured Stack topic in portion Graph of Data Structures & Algorithms IThis question was posed to me during an online interview.
Answer» The CORRECT ANSWER is (d) O(E) Best explanation: We have to check for all edges, in the worst CASE the vertices will have no common edge.

Discussion

60.	The column sum in an incidence matrix for a directed graph having no self loop is __________(a) 0(b) 1(c) 2(d) equal to the number of edgesMy doubt is from Incidence Matrix and Graph Structured Stack topic in chapter Graph of Data Structures & Algorithms IThis question was posed to me in examination.
Answer» Correct choice is (a) 0 Easy explanation - Under EVERY EDGE COLUMN there would be either all 0 values or a pair of -1 and +1 VALUE exists.

Discussion

61.	What are the dimensions of an incidence matrix?(a) Number of edgesnumber of edges(b) Number of edgesnumber of vertices(c) Number of verticesnumber of vertices(d) Number of edges (^1⁄2 * number of vertices)This interesting question is from Incidence Matrix and Graph Structured Stack topic in division Graph of Data Structures & Algorithms II got this question in class test.
Answer» Right ANSWER is (b) Number of EDGES*number of VERTICES Easiest explanation - Columns may REPRESENT edges and vertices may be REPRESENTED by the rows.

Discussion

62.	The column sum in an incidence matrix for a simple graph is __________(a) depends on number of edges(b) always greater than 2(c) equal to 2(d) equal to the number of edgesThe above asked question is from Incidence Matrix and Graph Structured Stack in section Graph of Data Structures & Algorithms II have been asked this question in exam.
Answer» Right option is (c) equal to 2 Easy explanation - For every edge only the vertices with which it is connected WOULD have the value 1 in the matrix, as an edge connects two vertices sum will ALWAYS be 2.

Discussion

63.	Incidence matrix and Adjacency matrix of a graph will always have same dimensions?(a) True(b) FalseThe question is from Incidence Matrix and Graph Structured Stack topic in division Graph of Data Structures & Algorithms II got this question in examination.
Answer» Correct ANSWER is (B) False Easiest explanation - For a graph having V vertices and E edges, ADJACENCY MATRIX haveVV elements while Incidence matrix have VE elements.

Discussion

64.	If A[x+3][y+5] represents an adjacency matrix, which of these could be the value of x and y.(a) x=5, y=3(b) x=3, y=5(c) x=3, y=3(d) x=5, y=5The question is from Adjacency Matrix topic in chapter Graph of Data Structures & Algorithms II have been asked this question by my college director while I was bunking the class.
Answer» Correct CHOICE is (a) x=5, y=3 The BEST I can EXPLAIN: All adjacency MATRICES are square matrices.

Discussion

65.	Given an adjacency matrix A = [ [0, 1, 1], [1, 0, 1], [1, 1, 0] ], The total no. of ways in which every vertex can walk to itself using 2 edges is ________(a) 2(b) 4(c) 6(d) 8I need to ask this question from Adjacency Matrix topic in division Graph of Data Structures & Algorithms IThis question was addressed to me in an international level competition.
Answer» RIGHT CHOICE is (c) 6 Easy explanation - A^2 = [ [2, 1, 1], [1, 2, 1], [1, 1, 2] ], all the 3 vertices can reach to themselves in 2 ways, hence a total of 3*2, 6 ways.

Discussion

66.	Which of these adjacency matrices represents a simple graph?(a) [ [1, 0, 0], [0, 1, 0], [0, 1, 1] ](b) [ [1, 1, 1], [1, 1, 1], [1, 1, 1] ](c) [ [0, 0, 1], [0, 0, 0], [0, 0, 1] ](d) [ [0, 0, 1], [1, 0, 1], [1, 0, 0] ]My enquiry is from Adjacency Matrix in portion Graph of Data Structures & Algorithms IThe question was posed to me in an international level competition.
Answer» Correct ANSWER is (d) [ [0, 0, 1], [1, 0, 1], [1, 0, 0] ] The EXPLANATION is: A SIMPLE graph MUST have no-self LOOPS, should be undirected.

Discussion

67.	In the given connected graph G, what is the value of rad(G) and diam(G)?(a) 2, 3(b) 3, 2(c) 2, 2(d) 3, 3I need to ask this question from Adjacency Matrix in division Graph of Data Structures & Algorithms IThe question was posed to me in my homework.
Answer» Right ANSWER is (a) 2, 3 For explanation: Value of ECCENTRICITY for vertices A, C is 2 whereas for F, B, D, E it is 3.

Discussion

68.	On which of the following statements does the time complexity of checking if an edge exists between two particular vertices is not, depends?(a) Depends on the number of edges(b) Depends on the number of vertices(c) Is independent of both the number of edges and vertices(d) It depends on both the number of edges and verticesAsked question is from Adjacency Matrix topic in division Graph of Data Structures & Algorithms IThe question was asked by my college professor while I was bunking the class.
Answer» CORRECT option is (c) Is independent of both the NUMBER of edges and vertices 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.

Discussion

69.	What is the maximum number of possible non zero values in an adjacency matrix of a simple graph with n vertices?(a) (n(n-1))/2(b) (n(n+1))/2(c) n(n-1)(d) n(n+1)Query is from Adjacency Matrix in section Graph of Data Structures & Algorithms II had been asked this question in examination.
Answer» CORRECT option is (C) n(n-1) For explanation: Out of nn possible VALUES for a simple graph the DIAGONAL values will always be zero.

Discussion

70.	For the adjacency matrix of a directed graph the row sum is the _________ degree and the column sum is the ________ degree.(a) in, out(b) out, in(c) in, total(d) total, outI need to ask this question from Adjacency Matrix in portion Graph of Data Structures & Algorithms IThis question was addressed to me in unit test.
Answer» CORRECT option is (b) out, in The best I can explain: Row NUMBER of the MATRIX represents the tail, while Column number represents the head of the edge.

Discussion

71.	The time complexity to calculate the number of edges in a graph whose information in stored in form of an adjacency matrix is ____________(a) O(V)(b) O(E^2)(c) O(E)(d) O(V^2)This intriguing question originated from Adjacency Matrix in division Graph of Data Structures & Algorithms IThis question was posed to me by my college professor while I was bunking the class.
Answer» The CORRECT option is (d) O(V^2) Explanation: As V entries are 0, a TOTAL of V^2-V entries are to be examined.

Discussion

72.	Adjacency matrix of all graphs are symmetric.(a) False(b) TrueI want to ask this question from Adjacency Matrix in portion Graph of Data Structures & Algorithms II had been asked this question during an online exam.
Answer» CORRECT ANSWER is (a) False The best EXPLANATION: Only undirected graphs produce symmetric adjacency matrices.

Discussion

73.	What would be the number of zeros in the adjacency matrix of the given graph?(a) 10(b) 6(c) 16(d) 0My question is from Adjacency Matrix in section Graph of Data Structures & Algorithms IThe question was posed to me in an interview for job.
Answer» Correct choice is (b) 6 The best I can explain: Total number of values in the MATRIX is 4*4=16, out of which 6 ENTRIES are NON zero.

Discussion

74.	The number of elements in the adjacency matrix of a graph having 7 vertices is __________(a) 7(b) 14(c) 36(d) 49Origin of the question is Adjacency Matrix in portion Graph of Data Structures & Algorithms II have been asked this question during a job interview.
Answer» CORRECT option is (d) 49 To explain: There are N*n elements in the ADJACENCY MATRIX of a GRAPH with n vertices.

Discussion

75.	Which of the following ways can be used to represent a graph?(a) Adjacency List and Adjacency Matrix(b) Incidence Matrix(c) Adjacency List, Adjacency Matrix as well as Incidence Matrix(d) No way to representMy question is taken from Graph in portion Graph of Data Structures & Algorithms II have been asked this question in semester exam.
Answer» The correct choice is (C) Adjacency List, Adjacency Matrix as well as INCIDENCE Matrix The best I can EXPLAIN: Adjacency Matrix, Adjacency List and Incidence Matrix are USED to REPRESENT a graph.

Discussion

76.	A graph with all vertices having equal degree is known as a __________(a) Multi Graph(b) Regular Graph(c) Simple Graph(d) Complete GraphMy enquiry is from Graph in section Graph of Data Structures & Algorithms II had been asked this question in an international level competition.
Answer» RIGHT choice is (B) Regular Graph The best EXPLANATION: The given statement is the DEFINITION of regular graphs.

Discussion

77.	For which of the following combinations of the degrees of vertices would the connected graph be eulerian?(a) 1,2,3(b) 2,3,4(c) 2,4,5(d) 1,3,5I'm obligated to ask this question of Graph in chapter Graph of Data Structures & Algorithms IThis question was posed to me in my homework.
Answer» RIGHT OPTION is (a) 1,2,3 Easiest EXPLANATION - A graph is eulerian if either all of its vertices are even or if only TWO of its vertices are odd.

Discussion

78.	For a given graph G having v vertices and e edges which is connected and has no cycles, which of the following statements is true?(a) v=e(b) v = e+1(c) v + 1 = e(d) v = e-1My doubt is from Graph topic in portion Graph of Data Structures & Algorithms II had been asked this question in an international level competition.
Answer» Correct answer is (b) v = e+1 For EXPLANATION: For any CONNECTED GRAPH with no CYCLES the equation holds true.

Discussion

79.	Which of the following is true?(a) A graph may contain no edges and many vertices(b) A graph may contain many edges and no vertices(c) A graph may contain no edges and no vertices(d) A graph may contain no vertices and many edgesThe query is from Graph in portion Graph of Data Structures & Algorithms II got this question during an internship interview.
Answer» RIGHT answer is (b) A GRAPH MAY CONTAIN many EDGES and no vertices Best explanation: A graph must contain at least one vertex.

Discussion

80.	Which of the following properties does a simple graph not hold?(a) Must be connected(b) Must be unweighted(c) Must have no loops or multiple edges(d) Must have no multiple edgesMy question is based upon Graph topic in portion Graph of Data Structures & Algorithms II got this question in homework.
Answer» Right choice is (a) MUST be CONNECTED The BEST EXPLANATION: A SIMPLE graph maybe connected or disconnected.

Discussion

81.	If a simple graph G, contains n vertices and m edges, the number of edges in the Graph G'(Complement of G) is___________(a) (nn-n-2m)/2(b) (nn+n+2m)/2(c) (nn-n-2m)/2(d) (nn-n+2m)/2My query is from Graph topic in section Graph of Data Structures & Algorithms IThis question was addressed to me in my homework.
Answer» RIGHT choice is (a) (nn-n-2m)/2 For EXPLANATION: The union of G and G’ would be a COMPLETE GRAPH so, the number ofedges in G’= number of EDGES in the complete form of G(nC2)-edges in G(m).

Discussion

82.	A connected planar graph having 6 vertices, 7 edges contains _____________ regions.(a) 15(b) 3(c) 1(d) 11My question comes from Graph topic in portion Graph of Data Structures & Algorithms IThe question was posed to me in exam.
Answer» CORRECT option is (B) 3 The EXPLANATION is: By euler’s FORMULA the relation between vertices(N), edges(q) andregions(r) is given by n-q+r=2.

Discussion

83.	In a simple graph, the number of edges is equal to twice the sum of the degrees of the vertices.(a) True(b) FalseThe question is from Graph in section Graph of Data Structures & Algorithms IThis question was addressed to me in an interview.
Answer» Right choice is (B) False Easiest explanation - The sum of the DEGREES of the vertices is equal to TWICE the NUMBER of EDGES.

Discussion

84.	The given Graph is regular.(a) True(b) FalseQuestion is from Graph topic in section Graph of Data Structures & Algorithms IThis question was addressed to me in my homework.
Answer» Correct ANSWER is (a) True The EXPLANATION is: In a REGULAR GRAPH, degrees of all the vertices are equal. In the givengraph the degree of every vertex is 3.

Discussion

85.	What is the number of edges present in a complete graph having n vertices?(a) (n(n+1))/2(b) (n(n-1))/2(c) n(d) Information given is insufficientThe origin of the question is Graph topic in portion Graph of Data Structures & Algorithms IThis question was addressed to me in an interview.
Answer» Right answer is (b) (N*(n-1))/2 Easy explanation - Number of WAYS in which every VERTEX can be connected to each other is nC2.

Discussion

86.	For the given graph(G), which of the following statements is true?(a) G is a complete graph(b) G is not a connected graph(c) The vertex connectivity of the graph is 2(d) The edge connectivity of the graph is 1My query is from Graph topic in chapter Graph of Data Structures & Algorithms IThis question was addressed to me in my homework.
Answer» Right CHOICE is (c) The VERTEX connectivity of the GRAPH is 2 To EXPLAIN: After removing vertices B and C, the graph becomes disconnected.

Discussion

87.	In the given graph identify the cut vertices.(a) B and E(b) C and D(c) A and E(d) C and BMy doubt is from Graph topic in portion Graph of Data Structures & Algorithms IThis question was addressed to me in an interview.
Answer» Correct answer is (d) C and B The BEST I can explain: After REMOVING EITHER B or C, the graph BECOMES disconnected.

Discussion

88.	Which of the following statements for a simple graph is correct?(a) Every path is a trail(b) Every trail is a path(c) Every trail is a path as well as every path is a trail(d) Path and trail have no relationEnquiry is from Graph topic in section Graph of Data Structures & Algorithms IThis question was posed to me in a job interview.
Answer» The CORRECT answer is (a) Every path is a TRAIL Best EXPLANATION: In a walk if the vertices are distinct it is called a path, WHEREAS if the edges are distinct it is called a trail.

Discussion

Explore topic-wise InterviewSolutions in .

For some sparse graph an adjacency list is more space efficient against an adjacency matrix.(a) True(b) FalseEnquiry is from Adjacency List topic in portion Graph of Data Structures & Algorithms II got this question in my homework.

A Graph Structured Stack is a _____________(a) Undirected Graph(b) Directed Graph(c) Directed Acyclic Graph(d) Regular GraphAsked question is from Incidence Matrix and Graph Structured Stack topic in section Graph of Data Structures & Algorithms IThe question was posed to me in an online quiz.

In the following DAG find out the number of required Stacks in order to represent it in a Graph Structured Stack.(a) 1(b) 2(c) 3(d) 4My enquiry is from Incidence Matrix and Graph Structured Stack in portion Graph of Data Structures & Algorithms IThe question was posed to me in final exam.

Time complexity to check if an edge exists between two vertices would be ___________(a) O(V*V)(b) O(V+E)(c) O(1)(d) O(E)My doubt is from Incidence Matrix and Graph Structured Stack topic in portion Graph of Data Structures & Algorithms IThis question was posed to me during an online interview.

Incidence matrix and Adjacency matrix of a graph will always have same dimensions?(a) True(b) FalseThe question is from Incidence Matrix and Graph Structured Stack topic in division Graph of Data Structures & Algorithms II got this question in examination.

In the given connected graph G, what is the value of rad(G) and diam(G)?(a) 2, 3(b) 3, 2(c) 2, 2(d) 3, 3I need to ask this question from Adjacency Matrix in division Graph of Data Structures & Algorithms IThe question was posed to me in my homework.

What is the maximum number of possible non zero values in an adjacency matrix of a simple graph with n vertices?(a) (n*(n-1))/2(b) (n*(n+1))/2(c) n*(n-1)(d) n*(n+1)Query is from Adjacency Matrix in section Graph of Data Structures & Algorithms II had been asked this question in examination.

Adjacency matrix of all graphs are symmetric.(a) False(b) TrueI want to ask this question from Adjacency Matrix in portion Graph of Data Structures & Algorithms II had been asked this question during an online exam.

What would be the number of zeros in the adjacency matrix of the given graph?(a) 10(b) 6(c) 16(d) 0My question is from Adjacency Matrix in section Graph of Data Structures & Algorithms IThe question was posed to me in an interview for job.

The number of elements in the adjacency matrix of a graph having 7 vertices is __________(a) 7(b) 14(c) 36(d) 49Origin of the question is Adjacency Matrix in portion Graph of Data Structures & Algorithms II have been asked this question during a job interview.

A graph with all vertices having equal degree is known as a __________(a) Multi Graph(b) Regular Graph(c) Simple Graph(d) Complete GraphMy enquiry is from Graph in section Graph of Data Structures & Algorithms II had been asked this question in an international level competition.

For which of the following combinations of the degrees of vertices would the connected graph be eulerian?(a) 1,2,3(b) 2,3,4(c) 2,4,5(d) 1,3,5I'm obligated to ask this question of Graph in chapter Graph of Data Structures & Algorithms IThis question was posed to me in my homework.

Which of the following properties does a simple graph not hold?(a) Must be connected(b) Must be unweighted(c) Must have no loops or multiple edges(d) Must have no multiple edgesMy question is based upon Graph topic in portion Graph of Data Structures & Algorithms II got this question in homework.

A connected planar graph having 6 vertices, 7 edges contains _____________ regions.(a) 15(b) 3(c) 1(d) 11My question comes from Graph topic in portion Graph of Data Structures & Algorithms IThe question was posed to me in exam.

In a simple graph, the number of edges is equal to twice the sum of the degrees of the vertices.(a) True(b) FalseThe question is from Graph in section Graph of Data Structures & Algorithms IThis question was addressed to me in an interview.

The given Graph is regular.(a) True(b) FalseQuestion is from Graph topic in section Graph of Data Structures & Algorithms IThis question was addressed to me in my homework.

What is the number of edges present in a complete graph having n vertices?(a) (n*(n+1))/2(b) (n*(n-1))/2(c) n(d) Information given is insufficientThe origin of the question is Graph topic in portion Graph of Data Structures & Algorithms IThis question was addressed to me in an interview.

In the given graph identify the cut vertices.(a) B and E(b) C and D(c) A and E(d) C and BMy doubt is from Graph topic in portion Graph of Data Structures & Algorithms IThis question was addressed to me in an interview.

What is the maximum number of possible non zero values in an adjacency matrix of a simple graph with n vertices?(a) (n(n-1))/2(b) (n(n+1))/2(c) n(n-1)(d) n(n+1)Query is from Adjacency Matrix in section Graph of Data Structures & Algorithms II had been asked this question in examination.

What is the number of edges present in a complete graph having n vertices?(a) (n(n+1))/2(b) (n(n-1))/2(c) n(d) Information given is insufficientThe origin of the question is Graph topic in portion Graph of Data Structures & Algorithms IThis question was addressed to me in an interview.