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.

On which of the following statements does the time complexity of check

1.	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

No Comment Found

Related InterviewSolutions

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
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.
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.
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.
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.
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 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.

Discussion

No Comment Found

Related InterviewSolutions

Reply to Comment