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

1.	In a Propositional Directed Acyclic Graph Leaves maybe labelled with a boolean variable.(a) True(b) FalseWhat is the answer to this question? I'm confused
Answer» RIGHT choice is (a) True The explanation is: In a Propositional DIRECTED ACYCLIC Graph leaves maybe labelled with a boolean VARIABLE, T or ⊥.

Discussion

2.	What is the number of words that can be formed from the given Directed Acyclic Word Graph?(a) 2(b) 4(c) 12(d) 7Please answer it as soon as possible.
Answer» Right answer is (B) 4 The best I can explain: Words namely BATS, BOTS, BAT and BOT can be formed.

Discussion

3.	For any two different vertices u and v of an Acyclic Directed Graph if v is reachable from u, u is also reachable from v?(a) True(b) False
Answer» Correct option is (B) False Best explanation: If such VERTICES EXISTS it means that the graph CONTAINS a cycle which contradicts the first part of the statement.

Discussion

4.	Which of the following logical operation can’t be implemented by polynomial time graph manipulation algorithms using Binary Decision Diagrams?(a) Conjunction(b) Disjunction(c) Negation(d) Tautology CheckingI'd like to ask this question from Binary Decision Diagrams &And Inverter Graph in section Graph of Data Structures & Algorithms IThe question was asked in a job interview.
Answer» The correct answer is (d) Tautology CHECKING Explanation: In BINARY Decision DIAGRAM, Conjunction, Disjunction, Negotiation can be IMPLEMENTED in polynomial time whereas tautology checking can be implemented in linear time.

Discussion

5.	The And Inverter Graph representation of a Boolean function is more efficient than the Binary Decision Diagram.(a) True(b) FalseThis intriguing question originated from Binary Decision Diagrams &And Inverter Graph in section Graph of Data Structures & Algorithms IThis question was addressed to me in a national level competition.
Answer» CORRECT option is (a) True Easiest EXPLANATION - The CONVERSION from the network logic is FASTER and more scalable than in the case of the Binary DECISION Diagram.

Discussion

6.	And Inverter Graph is a type of __________(a) Multigraph(b) Cyclic Graph(c) Directed Acyclic Graph(d) Directed Acyclic Word GraphI want to ask this question from Binary Decision Diagrams &And Inverter Graph in chapter Graph of Data Structures & Algorithms IThis question was addressed to me in examination.
Answer» Right CHOICE is (c) DIRECTED Acyclic GRAPH To explain: And Inverter is a directed graph which is used to solve boolean EXPRESSIONS, hence have no loops.

Discussion

7.	Size of an And Inverter Graph is the number of _______ gates and the number of logic levels is number of ________ gates on the __________ path from a primary input to a primary output.(a) AND, AND, average(b) AND, OR, longest(c) OR, OR, shortest(d) AND, AND, longestMy enquiry is from Binary Decision Diagrams &And Inverter Graph in portion Graph of Data Structures & Algorithms IThis question was posed to me in an online quiz.
Answer» The correct OPTION is (d) AND, AND, longest Easiest explanation - The GIVEN statement FORMS the attributes of the And Inverter GRAPH.

Discussion

8.	Two or more And Inverter Graphs can represent same function.(a) True(b) FalseThis intriguing question originated from Binary Decision Diagrams &And Inverter Graph topic in portion Graph of Data Structures & Algorithms IThis question was addressed to me in homework.
Answer» The CORRECT choice is (a) True Easiest explanation - And INVERTER Graphs are not canonical in nature.

Discussion

9.	How many nodes are required to create a Binary Decision Tree having 4 variables?(a) 2^4(b) 2^4-1(c) 2^5(d) 2^5-1Asked question is from Binary Decision Diagrams &And Inverter Graph topic in portion Graph of Data Structures & Algorithms II got this question in quiz.
Answer» Correct option is (d) 2^5-1 The best EXPLANATION: Binary DECISION Trees are COMPLETE Binary Trees of level V + 1, here V is the number of VARIABLES.

Discussion

10.	In a Binary DecisionDiagrams 0 values by a _________ line and the 1 values are represented by a _________ line.(a) dashed, bold(b) bold, dashed(c) dotted, bold(d) dotted, dashedI want to ask this question from Binary Decision Diagrams &And Inverter Graph in chapter Graph of Data Structures & Algorithms IThe question was posed to me during an internship interview.
Answer» RIGHT option is (C) dotted, bold The best explanation: It is USED to distinguish between the 2 values without explicitly writing.

Discussion

11.	In a Binary Decision Diagram, how many types of terminal exists?(a) 1(b) 2(c) 3(d) 4Enquiry is from Binary Decision Diagrams &And Inverter Graph topic in portion Graph of Data Structures & Algorithms IThis question was posed to me in an interview.
Answer» Correct answer is (b) 2 To explain: In a BDD, 2 TERMINALS NAMELY terminal-0 and terminal-1 exists.

Discussion

12.	In which of the following case does a Binary Decision Diagram is used for?(a) Representation of Boolean Functions(b) String Matching(c) Searching(d) Sorting of numberMy doubt stems from Binary Decision Diagrams &And Inverter Graph in division Graph of Data Structures & Algorithms IThe question was posed to me in class test.
Answer» Correct CHOICE is (a) Representation of Boolean Functions Best explanation: A Binary DECISION Diagram is USED to represent a Boolean FUNCTION.

Discussion

13.	Binary Decision Diagram is a type of __________(a) Multigraph(b) Cyclic Graph(c) Directed Acyclic Graph(d) Directed Acyclic Word GraphI would like to ask this question from Binary Decision Diagrams &And Inverter Graph topic in chapter Graph of Data Structures & Algorithms IThe question was asked during an interview for a job.
Answer» The correct option is (c) Directed Acyclic GRAPH Explanation: An Inverter is a directed graph which is used to solve BOOLEAN EXPRESSIONS, hence have no loops.

Discussion

14.	MultiGraphs having self-loops are called PseudoGraphs?(a) True(b) FalseI need to ask this question from Multigraph and Hypergraph topic in division Graph of Data Structures & Algorithms II got this question in an interview for job.
Answer» The correct answer is (a) True Easiest explanation - All PsuedoGraphs are MULTIGRAPHS, but all MultiGraphs are not PSEUDOGRAPHS as all PseudoGraphs have self loop, but all MultiGraphs do not have self LOOPS.

Discussion

15.	Which of the following is a HyperGraph, where V is the set of vertices, E is the set of edges?(a) V = {v1, v2, v3} E = {e1, e2} = {{v2, v3} {v1, v3}}(b) V = {v1, v2} E = {e1} = {{v1, v2}}(c) V = {v1, v2, v3} E = {e1, e2, e3} = {{v2, v3}{v3, v1}{v2, v1}}(d) All of the mentionedThe origin of the question is Multigraph and Hypergraph topic in portion Graph of Data Structures & Algorithms IThe question was asked in an interview for job.
Answer» RIGHT choice is (d) All of the mentioned For EXPLANATION: In a UNIFORM Graph all the hyper-edges have the same cardinality.

Discussion

16.	Possible number of labelled simple Directed, Pseudo and Multigarphs exist having 2 vertices?(a) 3, Infinite, 4(b) 4, 3, Infinite(c) 4, Infinite, infinite(d) 4, Infinite, InfiniteMy enquiry is from Multigraph and Hypergraph in chapter Graph of Data Structures & Algorithms II had been asked this question by my school principal while I was bunking the class.
Answer» The correct option is (d) 4, Infinite, Infinite Best explanation: MULTIGRAPHS and PseudoGraphs may have infinite NUMBER of edges, while 4 POSSIBLE simple graphs exist.

Discussion

17.	All undirected Multigraphs contain eulerian cycles.(a) True(b) FalseThis intriguing question comes from Multigraph and Hypergraph in portion Graph of Data Structures & Algorithms II had been asked this question by my school teacher while I was bunking the class.
Answer» Right ANSWER is (a) True The explanation is: Only GRAPHS with EVERY vertex having even degree have eulerian circuits or cycles.

Discussion

18.	Every Binary Decision Diagram is also a Propositional Directed Acyclic Graph.(a) True(b) FalseThis interesting question is from Propositional and Directed Acyclic Word Graph in section Graph of Data Structures & Algorithms IThis question was posed to me in class test.
Answer» CORRECT choice is (a) True Explanation: Both BINARY Decision Diagram and Propositional Directed Acyclic Graph may be used to REPRESENT the same BOOLEAN function.

Discussion

19.	In which of the following case does a Propositional Directed Acyclic Graph is used for?(a) Representation of Boolean Functions(b) String Matching(c) Searching(d) Sorting of numberThe question is from Propositional and Directed Acyclic Word Graph topic in portion Graph of Data Structures & Algorithms II have been asked this question by my college director while I was bunking the class.
Answer» RIGHT ANSWER is (a) Representation of Boolean Functions To explain: A Propositional DIRECTED ACYCLIC Graph is used to represent a boolean function.

Discussion

20.	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?(a) O(S1)(b) O(S2)(c) O(S1+S2)(d) O(1)This interesting question is from Propositional and Directed Acyclic Word Graph topic in section Graph of Data Structures & Algorithms IThis question was posed to me during an online interview.
Answer» CORRECT option is (a) O(S1) Easiest explanation - For each CHECK of a word of lengthS1, we need to follow at most S1 EDGES.

Discussion

21.	Determine the longest string which is described by the given Directed Acyclic Word Graph.(a) BATS(b) BOATS(c) BOT(d) BATI'd like to ask this question from Propositional and Directed Acyclic Word Graph in chapter Graph of Data Structures & Algorithms IThe question was asked during an internship interview.
Answer» The correct option is (a) BATS The best I can explain: STARTING from the initial state and choosing B, A, T, S RESPECTIVELY.

Discussion

22.	In which of the following does a Directed Acyclic Word Graph finds its application in?(a) String Matching(b) Number Sorting(c) Manipulations on numbers(d) Pattern PrintingI want to ask this question from Propositional and Directed Acyclic Word Graph topic in chapter Graph of Data Structures & Algorithms II had been asked this question during a job interview.
Answer» The CORRECT answer is (a) String Matching To explain: A Directed Acyclic Word Graph is similar to SUFFIX TREE, it can be viewed as a Deterministic Finite AUTOMATA.

Discussion

23.	What is the value of the sum of the minimum in-degree and maximum out-degree of an Directed Acyclic Graph?(a) Depends on a Graph(b) Will always be zero(c) Will always be greater than zero(d) May be zero or greater than zeroThe above asked question is from Directed Acyclic Graph topic in section Graph of Data Structures & Algorithms II have been asked this question during an internship interview.
Answer» CORRECT answer is (B) Will always be zero Explanation: EVERY Directed Acyclic Graph has a source and a sink vertex.

Discussion

24.	Which of the given statement is true?(a) All the Cyclic Directed Graphs have topological sortings(b) All the Acyclic Directed Graphs have topological sortings(c) All Directed Graphs have topological sortings(d) All the cyclic directed graphs hace non topological sortingsAsked question is from Directed Acyclic Graph topic in division Graph of Data Structures & Algorithms II got this question at a job interview.
Answer» Right CHOICE is (d) All the cyclic directed graphs hace non TOPOLOGICAL sortings The BEST EXPLANATION: Cyclic Directed Graphs cannot be SORTED topologically.

Discussion

25.	What sequence would the BFS traversal of the given graph yield?(a) A F D B C E(b) C B A F E D(c) A B D C E F(d) E F D C B AI'd like to ask this question from Directed Acyclic Graph in portion Graph of Data Structures & Algorithms II had been asked this question in exam.
Answer» Right answer is (c) A B D C E F The best I can explain: In BFS NODES gets explored and then the NEIGHBORS of the current NODE gets explored, before moving on to the next levels.

Discussion

26.	If there are more than 1 topological sorting of a DAG is possible, which of the following is true.(a) Many Hamiltonian paths are possible(b) No Hamiltonian path is possible(c) Exactly 1 Hamiltonian path is possible(d) Given information is insufficient to comment anythingThe above asked question is from Directed Acyclic Graph topic in portion Graph of Data Structures & Algorithms IThis question was addressed to me in my homework.
Answer» CORRECT ANSWER is (b) No Hamiltonian path is possible The best explanation: 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.

Discussion

27.	The topological sorting of any DAG can be done in ________ time.(a) cubic(b) quadratic(c) linear(d) logarithmicI'm obligated to ask this question of Directed Acyclic Graph topic in division Graph of Data Structures & Algorithms IThis question was addressed to me during an interview.
Answer» The CORRECT choice is (c) linear To explain: Topological sorting can be done in O(V+E), here V and E REPRESENTS number of vertices and number of EDGES respectively.

Discussion

28.	With V(greater than 1) vertices, how many edges at most can a Directed Acyclic Graph possess?(a) (V(V-1))/2(b) (V(V+1))/2(c) (V+1)C2(d) (V-1)C2Enquiry is from Directed Acyclic Graph topic in division Graph of Data Structures & Algorithms IThe question was posed to me during an interview for a job.
Answer» The correct answer is (a) (V(V-1))/2 Easiest EXPLANATION - The first edge WOULD have an OUTGOING degree of atmost V-1, the next edge would have V-2 and so on, hence V-1 + V-2…. +1 equals (V(V-1))/2.

Discussion

29.	Which of the following is not a topological sorting of the given graph?(a) A B C D E F(b) A B F E D C(c) A B E C F D(d) A B C D F EQuery is from Directed Acyclic Graph topic in division Graph of Data Structures & Algorithms IThe question was asked in a national level competition.
Answer» Right choice is (d) A B C D F E Explanation: Topological sorting is a LINEAR arrangement of VERTICES such that for every directed edge UV from vertex u to vertex v, u comes before v in the ORDERING. In A B C D F E, F comes before E in ordering.

Discussion

30.	Every Directed Acyclic Graph has at least one sink vertex.(a) True(b) FalseQuery is from Directed Acyclic Graph in section Graph of Data Structures & Algorithms II have been asked this question in homework.
Answer» RIGHT answer is (a) True The best explanation: A sink vertex is a vertex which has an OUTGOING degree of ZERO.

Discussion

31.	What is the maximum number of edges present in a simple directed graph with 7 vertices if there exists no cycles in the graph?(a) 21(b) 7(c) 6(d) 49My doubt stems from Directed Graph topic in chapter Graph of Data Structures & Algorithms IThis question was posed to me in quiz.
Answer» The CORRECT CHOICE is (c) 6 For explanation: If the no cycles exists then the DIFFERENCE between the number of vertices and EDGES is 1.

Discussion

32.	All Graphs have unique representation on paper.(a) True(b) FalseMy question is from Directed Graph topic in division Graph of Data Structures & Algorithms II have been asked this question by my school teacher while I was bunking the class.
Answer» Right answer is (b) False Easiest explanation - Same GRAPH may be DRAWN in different WAYS on PAPER.

Discussion

33.	Floyd Warshall Algorithm used to solve the shortest path problem has a time complexity of __________(a) O(VV)(b) O(VVV)(c) O(EV)(d) O(E*E)This key question is from Directed Graph topic in section Graph of Data Structures & Algorithms IThe question was posed to me in examination.
Answer» Right choice is (b) O(VVV) The best explanation: The ALGORITHM uses Dynamic PROGRAMMING and checks for every POSSIBLE path.

Discussion

34.	What is the number of unlabeled simple directed graph that can be made with 1 or 2 vertices?(a) 2(b) 4(c) 5(d) 9My enquiry is from Directed Graph in section Graph of Data Structures & Algorithms IThe question was posed to me in a job interview.
Answer» CORRECT choice is (b) 4 Explanation: The NUMBER of UNLABELED simple directed GRAPH that can be made with 1 or 2 VERTICES is 4

Discussion

35.	A graph having an edge from each vertex to every other vertex is called a ___________(a) Tightly Connected(b) Strongly Connected(c) Weakly Connected(d) Loosely ConnectedThe query is from Directed Graph in division Graph of Data Structures & Algorithms IThe question was posed to me in an interview.
Answer» Right answer is (a) Tightly Connected Explanation: This is a PART of the NOMENCLATURE followed in GRAPH Theory.

Discussion

36.	Dijkstra’s Algorithm will work for both negative and positive weights?(a) True(b) FalseThe origin of the question is Directed Graph in division Graph of Data Structures & Algorithms IThe question was asked in examination.
Answer» Correct CHOICE is (b) False The explanation is: Dijkstra’s ALGORITHM ASSUMES all weights to be non-negative.

Discussion

37.	What would thetime complexity to check if an undirected graph with V vertices and E edges is Bipartite or not given its adjacency matrix?(a) O(EE)(b) O(VV)(c) O(E)(d) O(V)The origin of the question is Undirected Graph in portion Graph of Data Structures & Algorithms II have been asked this question during an interview for a job.
Answer» Correct answer is (B) O(V*V) The best I can explain: A graph can be checked for being Bipartite by seeing if it is 2-colorable or not, which can be obtained with the HELP of BFS.

Discussion

38.	In the given graph which edge should be removed to make it a Bipartite Graph?(a) A-C(b) B-E(c) C-D(d) D-EThis interesting question is from Undirected Graph in section Graph of Data Structures & Algorithms II got this question in final exam.
Answer» Correct choice is (a) A-C Easy EXPLANATION - The resultant graph would be a BIPARTITE Graph having {A,C,E} and{D, B} as its subgroups.

Discussion

39.	Which of the following graphs are isomorphic to each other?(a) fig 1 and fig 2(b) fig 2 and fig 3(c) fig 1 and fig 3(d) fig 1, fig 2 and fig 3My question is from Undirected Graph topic in section Graph of Data Structures & Algorithms II have been asked this question by my college professor while I was bunking the class.
Answer» Right answer is (d) fig 1, fig 2 and fig 3 The best explanation: All three GRAPHS are COMPLETE graphs with 4 VERTICES.

Discussion

40.	All trees with n vertices consists of n-1 edges.(a) True(b) FalseMy question is taken from Undirected Graph in division Graph of Data Structures & Algorithms II had been asked this question in an internship interview.
Answer» RIGHT CHOICE is (a) True To explain: A trees is ACYCLIC in NATURE.

Discussion

41.	What is the number of vertices of degree 2 in a path graph having n vertices,here n>2.(a) n-2(b) n(c) 2(d) 0I'm obligated to ask this question of Undirected Graph in portion Graph of Data Structures & Algorithms IThis question was posed to me in an international level competition.
Answer» RIGHT choice is (a) n-2 The explanation is: Only the first and the last VERTEX WOULD have degree 1, others would be of degree 2.

Discussion

42.	All paths and cyclic graphs are bipartite graphs.(a) True(b) FalseQuestion is taken from Undirected Graph in chapter Graph of Data Structures & Algorithms IThis question was addressed to me during an interview.
Answer» RIGHT choice is (b) False To EXPLAIN: Only PATHS and EVEN cycles are bipartite graphs.

Discussion

43.	Number of vertices with odd degrees in a graph having a eulerianwalk is ________(a) 0(b) Can’t be predicted(c) 2(d) either 0 or 2I would like to ask this question from Undirected Graph topic in portion Graph of Data Structures & Algorithms IThis question was addressed to me in an online quiz.
Answer» Right answer is (d) either 0 or 2 Explanation: If the START and END vertices for the path are same the answer WOULD be 0 otherwise 2.

Discussion

44.	Given a plane graph, G having 2 connected component, having 6 vertices, 7 edges and 4 regions. What will be the number of connected components?(a) 1(b) 2(c) 3(d) 4Origin of the question is Undirected Graph in chapter Graph of Data Structures & Algorithms II had been asked this question during an internship interview.
Answer» The correct option is (b) 2 Easiest EXPLANATION - EULER’s IDENTITY says V – E + R= 1+ NUMBER of connected components.

Discussion

45.	The number of possible undirected graphs which may have self loops but no multiple edges and have n verticesis ________(a) 2^((n(n-1))/2)(b) 2^((n(n+1))/2)(c) 2^((n-1)(n-1))/2)(d) 2^((nn)/2)This interesting question is from Undirected Graph in portion Graph of Data Structures & Algorithms IThe question was posed to me in an internship interview.
Answer» Correct option is (d) 2^((Nn)/2) The EXPLANATION is: There can be at most, nn EDGES in an undirected graph.

Discussion

46.	What would be the time complexity of the BFS traversal of agraph with n vertices and n^1.25 edges?(a) O(n)(b) O(n^1.25)(c) O(n^2.25)(d) O(n*n)This question is from Adjacency List topic in portion Graph of Data Structures & Algorithms II had been asked this question in semester exam.
Answer» Correct CHOICE is (b) O(N^1.25) To EXPLAIN: The TIME complexity for BFS is O(\|V\| + \|E\|) = O(n + n^1.25) = O(n^1.25).

Discussion

47.	To create an adjacency list C++’s map container can be used.(a) True(b) FalseThe question is from Adjacency List topic in section Graph of Data Structures & Algorithms II got this question during an interview for a job.
Answer» Correct answer is (a) True To EXPLAIN: We can create a mapping from string to a vector, where string would be the NAME of the vertex and vector would CONTAINS the name of the VERTICES to which it is connected.

Discussion

48.	In which case adjacency list is preferred in front of an adjacency matrix?(a) Dense graph(b) Sparse graph(c) Adjacency list is always preferred(d) Complete graphThis interesting question is from Adjacency List in division Graph of Data Structures & Algorithms IThe question was asked in class test.
Answer» Right answer is (B) Sparse graph Easy explanation - In case of sparse graph most of the ENTRIES in the ADJACENCY matrix would be 0, HENCE adjacency LIST would be preferred.

Discussion

49.	Space complexity for an adjacency list of an undirected graph having large values of V (vertices) and E (edges) is __________(a) O(V)(b) O(E*E)(c) O(E)(d) O(E+V)Enquiry is from Adjacency List topic in portion Graph of Data Structures & Algorithms IThe question was posed to me at a job interview.
Answer» Right answer is (c) O(E) The best 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

50.	Time complexity to find if there is an edge between 2 particular vertices is _________(a) O(V)(b) O(E)(c) O(1)(d) O(V+E)My question is taken from Adjacency List in portion Graph of Data Structures & Algorithms IThe question was asked in exam.
Answer» Correct OPTION is (a) O(V) For EXPLANATION: The maximum edges a VERTEX can have is V-1.

Discussion

Explore topic-wise InterviewSolutions in .

In a Propositional Directed Acyclic Graph Leaves maybe labelled with a boolean variable.(a) True(b) FalseWhat is the answer to this question? I'm confused

What is the number of words that can be formed from the given Directed Acyclic Word Graph?(a) 2(b) 4(c) 12(d) 7Please answer it as soon as possible.

For any two different vertices u and v of an Acyclic Directed Graph if v is reachable from u, u is also reachable from v?(a) True(b) False

Two or more And Inverter Graphs can represent same function.(a) True(b) FalseThis intriguing question originated from Binary Decision Diagrams &And Inverter Graph topic in portion Graph of Data Structures & Algorithms IThis question was addressed to me in homework.

How many nodes are required to create a Binary Decision Tree having 4 variables?(a) 2^4(b) 2^4-1(c) 2^5(d) 2^5-1Asked question is from Binary Decision Diagrams &And Inverter Graph topic in portion Graph of Data Structures & Algorithms II got this question in quiz.

In a Binary Decision Diagram, how many types of terminal exists?(a) 1(b) 2(c) 3(d) 4Enquiry is from Binary Decision Diagrams &And Inverter Graph topic in portion Graph of Data Structures & Algorithms IThis question was posed to me in an interview.

MultiGraphs having self-loops are called PseudoGraphs?(a) True(b) FalseI need to ask this question from Multigraph and Hypergraph topic in division Graph of Data Structures & Algorithms II got this question in an interview for job.

All undirected Multigraphs contain eulerian cycles.(a) True(b) FalseThis intriguing question comes from Multigraph and Hypergraph in portion Graph of Data Structures & Algorithms II had been asked this question by my school teacher while I was bunking the class.

Every Binary Decision Diagram is also a Propositional Directed Acyclic Graph.(a) True(b) FalseThis interesting question is from Propositional and Directed Acyclic Word Graph in section Graph of Data Structures & Algorithms IThis question was posed to me in class test.

What sequence would the BFS traversal of the given graph yield?(a) A F D B C E(b) C B A F E D(c) A B D C E F(d) E F D C B AI'd like to ask this question from Directed Acyclic Graph in portion Graph of Data Structures & Algorithms II had been asked this question in exam.

The topological sorting of any DAG can be done in ________ time.(a) cubic(b) quadratic(c) linear(d) logarithmicI'm obligated to ask this question of Directed Acyclic Graph topic in division Graph of Data Structures & Algorithms IThis question was addressed to me during an interview.

With V(greater than 1) vertices, how many edges at most can a Directed Acyclic Graph possess?(a) (V(V-1))/2(b) (V(V+1))/2(c) (V+1)C2(d) (V-1)C2Enquiry is from Directed Acyclic Graph topic in division Graph of Data Structures & Algorithms IThe question was posed to me during an interview for a job.

Which of the following is not a topological sorting of the given graph?(a) A B C D E F(b) A B F E D C(c) A B E C F D(d) A B C D F EQuery is from Directed Acyclic Graph topic in division Graph of Data Structures & Algorithms IThe question was asked in a national level competition.

Every Directed Acyclic Graph has at least one sink vertex.(a) True(b) FalseQuery is from Directed Acyclic Graph in section Graph of Data Structures & Algorithms II have been asked this question in homework.

What is the maximum number of edges present in a simple directed graph with 7 vertices if there exists no cycles in the graph?(a) 21(b) 7(c) 6(d) 49My doubt stems from Directed Graph topic in chapter Graph of Data Structures & Algorithms IThis question was posed to me in quiz.

All Graphs have unique representation on paper.(a) True(b) FalseMy question is from Directed Graph topic in division Graph of Data Structures & Algorithms II have been asked this question by my school teacher while I was bunking the class.

Floyd Warshall Algorithm used to solve the shortest path problem has a time complexity of __________(a) O(VV)(b) O(VV*V)(c) O(EV)(d) O(EE)This key question is from Directed Graph topic in section Graph of Data Structures & Algorithms IThe question was posed to me in examination.

What is the number of unlabeled simple directed graph that can be made with 1 or 2 vertices?(a) 2(b) 4(c) 5(d) 9My enquiry is from Directed Graph in section Graph of Data Structures & Algorithms IThe question was posed to me in a job interview.

A graph having an edge from each vertex to every other vertex is called a ___________(a) Tightly Connected(b) Strongly Connected(c) Weakly Connected(d) Loosely ConnectedThe query is from Directed Graph in division Graph of Data Structures & Algorithms IThe question was posed to me in an interview.

Dijkstra’s Algorithm will work for both negative and positive weights?(a) True(b) FalseThe origin of the question is Directed Graph in division Graph of Data Structures & Algorithms IThe question was asked in examination.

In the given graph which edge should be removed to make it a Bipartite Graph?(a) A-C(b) B-E(c) C-D(d) D-EThis interesting question is from Undirected Graph in section Graph of Data Structures & Algorithms II got this question in final exam.

All trees with n vertices consists of n-1 edges.(a) True(b) FalseMy question is taken from Undirected Graph in division Graph of Data Structures & Algorithms II had been asked this question in an internship interview.

What is the number of vertices of degree 2 in a path graph having n vertices,here n>2.(a) n-2(b) n(c) 2(d) 0I'm obligated to ask this question of Undirected Graph in portion Graph of Data Structures & Algorithms IThis question was posed to me in an international level competition.

All paths and cyclic graphs are bipartite graphs.(a) True(b) FalseQuestion is taken from Undirected Graph in chapter Graph of Data Structures & Algorithms IThis question was addressed to me during an interview.

Number of vertices with odd degrees in a graph having a eulerianwalk is ________(a) 0(b) Can’t be predicted(c) 2(d) either 0 or 2I would like to ask this question from Undirected Graph topic in portion Graph of Data Structures & Algorithms IThis question was addressed to me in an online quiz.

What would be the time complexity of the BFS traversal of agraph with n vertices and n^1.25 edges?(a) O(n)(b) O(n^1.25)(c) O(n^2.25)(d) O(n*n)This question is from Adjacency List topic in portion Graph of Data Structures & Algorithms II had been asked this question in semester exam.

To create an adjacency list C++’s map container can be used.(a) True(b) FalseThe question is from Adjacency List topic in section Graph of Data Structures & Algorithms II got this question during an interview for a job.

In which case adjacency list is preferred in front of an adjacency matrix?(a) Dense graph(b) Sparse graph(c) Adjacency list is always preferred(d) Complete graphThis interesting question is from Adjacency List in division Graph of Data Structures & Algorithms IThe question was asked in class test.

Space complexity for an adjacency list of an undirected graph having large values of V (vertices) and E (edges) is __________(a) O(V)(b) O(E*E)(c) O(E)(d) O(E+V)Enquiry is from Adjacency List topic in portion Graph of Data Structures & Algorithms IThe question was posed to me at a job interview.

Time complexity to find if there is an edge between 2 particular vertices is _________(a) O(V)(b) O(E)(c) O(1)(d) O(V+E)My question is taken from Adjacency List in portion Graph of Data Structures & Algorithms IThe question was asked in exam.

Explore topic-wise InterviewSolutions in .

In a Propositional Directed Acyclic Graph Leaves maybe labelled with a boolean variable.(a) True(b) FalseWhat is the answer to this question? I'm confused

What is the number of words that can be formed from the given Directed Acyclic Word Graph?(a) 2(b) 4(c) 12(d) 7Please answer it as soon as possible.

For any two different vertices u and v of an Acyclic Directed Graph if v is reachable from u, u is also reachable from v?(a) True(b) False

Two or more And Inverter Graphs can represent same function.(a) True(b) FalseThis intriguing question originated from Binary Decision Diagrams &And Inverter Graph topic in portion Graph of Data Structures & Algorithms IThis question was addressed to me in homework.

How many nodes are required to create a Binary Decision Tree having 4 variables?(a) 2^4(b) 2^4-1(c) 2^5(d) 2^5-1Asked question is from Binary Decision Diagrams &And Inverter Graph topic in portion Graph of Data Structures & Algorithms II got this question in quiz.

In a Binary Decision Diagram, how many types of terminal exists?(a) 1(b) 2(c) 3(d) 4Enquiry is from Binary Decision Diagrams &And Inverter Graph topic in portion Graph of Data Structures & Algorithms IThis question was posed to me in an interview.

MultiGraphs having self-loops are called PseudoGraphs?(a) True(b) FalseI need to ask this question from Multigraph and Hypergraph topic in division Graph of Data Structures & Algorithms II got this question in an interview for job.

All undirected Multigraphs contain eulerian cycles.(a) True(b) FalseThis intriguing question comes from Multigraph and Hypergraph in portion Graph of Data Structures & Algorithms II had been asked this question by my school teacher while I was bunking the class.

Every Binary Decision Diagram is also a Propositional Directed Acyclic Graph.(a) True(b) FalseThis interesting question is from Propositional and Directed Acyclic Word Graph in section Graph of Data Structures & Algorithms IThis question was posed to me in class test.

What sequence would the BFS traversal of the given graph yield?(a) A F D B C E(b) C B A F E D(c) A B D C E F(d) E F D C B AI'd like to ask this question from Directed Acyclic Graph in portion Graph of Data Structures & Algorithms II had been asked this question in exam.

The topological sorting of any DAG can be done in ________ time.(a) cubic(b) quadratic(c) linear(d) logarithmicI'm obligated to ask this question of Directed Acyclic Graph topic in division Graph of Data Structures & Algorithms IThis question was addressed to me during an interview.

Which of the following is not a topological sorting of the given graph?(a) A B C D E F(b) A B F E D C(c) A B E C F D(d) A B C D F EQuery is from Directed Acyclic Graph topic in division Graph of Data Structures & Algorithms IThe question was asked in a national level competition.

Every Directed Acyclic Graph has at least one sink vertex.(a) True(b) FalseQuery is from Directed Acyclic Graph in section Graph of Data Structures & Algorithms II have been asked this question in homework.

What is the maximum number of edges present in a simple directed graph with 7 vertices if there exists no cycles in the graph?(a) 21(b) 7(c) 6(d) 49My doubt stems from Directed Graph topic in chapter Graph of Data Structures & Algorithms IThis question was posed to me in quiz.

All Graphs have unique representation on paper.(a) True(b) FalseMy question is from Directed Graph topic in division Graph of Data Structures & Algorithms II have been asked this question by my school teacher while I was bunking the class.

Floyd Warshall Algorithm used to solve the shortest path problem has a time complexity of __________(a) O(V*V)(b) O(V*V*V)(c) O(E*V)(d) O(E*E)This key question is from Directed Graph topic in section Graph of Data Structures & Algorithms IThe question was posed to me in examination.

What is the number of unlabeled simple directed graph that can be made with 1 or 2 vertices?(a) 2(b) 4(c) 5(d) 9My enquiry is from Directed Graph in section Graph of Data Structures & Algorithms IThe question was posed to me in a job interview.

A graph having an edge from each vertex to every other vertex is called a ___________(a) Tightly Connected(b) Strongly Connected(c) Weakly Connected(d) Loosely ConnectedThe query is from Directed Graph in division Graph of Data Structures & Algorithms IThe question was posed to me in an interview.

Dijkstra’s Algorithm will work for both negative and positive weights?(a) True(b) FalseThe origin of the question is Directed Graph in division Graph of Data Structures & Algorithms IThe question was asked in examination.

In the given graph which edge should be removed to make it a Bipartite Graph?(a) A-C(b) B-E(c) C-D(d) D-EThis interesting question is from Undirected Graph in section Graph of Data Structures & Algorithms II got this question in final exam.

All trees with n vertices consists of n-1 edges.(a) True(b) FalseMy question is taken from Undirected Graph in division Graph of Data Structures & Algorithms II had been asked this question in an internship interview.

What is the number of vertices of degree 2 in a path graph having n vertices,here n>2.(a) n-2(b) n(c) 2(d) 0I'm obligated to ask this question of Undirected Graph in portion Graph of Data Structures & Algorithms IThis question was posed to me in an international level competition.

All paths and cyclic graphs are bipartite graphs.(a) True(b) FalseQuestion is taken from Undirected Graph in chapter Graph of Data Structures & Algorithms IThis question was addressed to me during an interview.

Number of vertices with odd degrees in a graph having a eulerianwalk is ________(a) 0(b) Can’t be predicted(c) 2(d) either 0 or 2I would like to ask this question from Undirected Graph topic in portion Graph of Data Structures & Algorithms IThis question was addressed to me in an online quiz.

What would be the time complexity of the BFS traversal of agraph with n vertices and n^1.25 edges?(a) O(n)(b) O(n^1.25)(c) O(n^2.25)(d) O(n*n)This question is from Adjacency List topic in portion Graph of Data Structures & Algorithms II had been asked this question in semester exam.

To create an adjacency list C++’s map container can be used.(a) True(b) FalseThe question is from Adjacency List topic in section Graph of Data Structures & Algorithms II got this question during an interview for a job.

In which case adjacency list is preferred in front of an adjacency matrix?(a) Dense graph(b) Sparse graph(c) Adjacency list is always preferred(d) Complete graphThis interesting question is from Adjacency List in division Graph of Data Structures & Algorithms IThe question was asked in class test.

Space complexity for an adjacency list of an undirected graph having large values of V (vertices) and E (edges) is __________(a) O(V)(b) O(E*E)(c) O(E)(d) O(E+V)Enquiry is from Adjacency List topic in portion Graph of Data Structures & Algorithms IThe question was posed to me at a job interview.

Time complexity to find if there is an edge between 2 particular vertices is _________(a) O(V)(b) O(E)(c) O(1)(d) O(V+E)My question is taken from Adjacency List in portion Graph of Data Structures & Algorithms IThe question was asked in exam.

Floyd Warshall Algorithm used to solve the shortest path problem has a time complexity of __________(a) O(VV)(b) O(VV*V)(c) O(EV)(d) O(EE)This key question is from Directed Graph topic in section Graph of Data Structures & Algorithms IThe question was posed to me in examination.