topic - solutions adda

Graphs-and-Tree

Please wait while the activity loads.
If this activity does not load, try refreshing your browser. Also, this page requires javascript. Please visit using a browser with javascript enabled.

If loading fails, click here to try again

Question 1

Consider the following statements.
S₁:The sequence of procedure calls corresponds to a preorder traversal of the activation tree.
S₂:The sequence of procedure returns corresponds to a postorder traversal of the activation tree.
Which one of the following options is correct?

A	S₁is false and S₂is false
B	S₁is true and S₂is true
C	S₁is true and S₂is false
D	S₁is false and S₂is true

Data-StructuresGraphs-and-TreeGATE 2021 CS-Set-1Video-Explanation

Question 1 Explanation:

The given statements are true, they are well known facts.

The sequence of procedure calls corresponds to a preorder traversal of the activation tree.
The sequence of returns corresponds to a postorder traversal of the activation tree.

Question 2

Let G = (V,E) be a directed, weighted graph with weight function w:E → R. For some function f:V → R, for each edge (u,v) ∈ E, define w'(u,v) as w(u,v) + f(u) - f(v).
Which one of the options completes the following sentence so that it is TRUE?

“The shortest paths in G under w are shortest paths under w’ too, _______”.

A	if and only if f(u) is the distance from s to u in the graph obtained by adding a new vertex s to G and edges of zero weight from s to every vertex of G
B	if and only if ∀u ∈ V, f(u) is positive
C	if and only if ∀u ∈ V, f(u) is negative
D	for every f: V→R

Data-StructuresGraphs-and-TreeGATE 2020Video-Explanation

Question 2 Explanation:

Question 3

Consider the following directed graph:

Which of the following is/are correct about the graph?

A	For each pair of vertices u and v, there is a directed path from u to v.
B	The graph does not have a strongly connected component.
C	The graph does not have a topological order.
D	A depth-first traversal staring at vertex S classifies three directed edges as back edges.

Data-StructuresGraphs-and-TreeGATE 2021 CS-Set-2Video-Explanation

Question 3 Explanation:

Option-1: FALSE: There is no path from top right corner vertex to any other vertex

Option-2: FALSE: A directed graph is called strongly connected if there is a path in each direction between each pair of vertices of the graph. As there is no path from the above vertex then this statement is wrong.

Option-3: TRUE: This graph does have directed cycles, thus topological order can not be possible for according to topological definition.

Question 4

G is an undirected graph with vertex set { v1, v2, v3, v4, v5, v6, v7} and edge set {v1v2, v1v3, v1v4, v2v4, v2v5, v4v4, v4v5, v4v6, v5v6, v6v7}. A breadth first search of the graph is performed with v1 as the root node. Which of the following is a tree edge?

A	v2v4
B	v1v4
C	v4v5
D	v3v4

Data-StructuresGraphs-and-TreeISRO CS 2020Video-Explanation

Question 5

A_____takes a directed ______ graph G and produce a linear ordering of all its vertices such that for every directed edge in G, the vertex v comes before the vertex w in the ordering.

A	Breadth first search; acyclic
B	Topological sort; acyclic
C	Breadth first search; cyclic
D	Topological sort; cyclic

Data-StructuresGraphs-and-TreeCIL Part - B

Question 5 Explanation:

Topological sorting of vertices of a Directed Acyclic Graph is an ordering of the vertices V1,v2,...vn in such a way, that if there is an edge directed towards vertex vj from vertex vi , then vi comes before vj

Question 6

Which one of the following is blind search?

A	Breadth first search
B	Depth first search
C	Breadth first search and Depth first search
D	None of the given options

Data-StructuresGraphs-and-TreeAPPSC-2016-DL-CA

Question 6 Explanation:

Blind search algorithms have no additional information on the goal node other than the one provided in the problem definition. The plans to reach the goal state from the start state differ only by the order and/or length of actions.
Examples of blind search algorithms are:
1. Depth First Search
2. Breadth First Search
3. Uniform Cost Search

Question 7

Breadth first traversal is a method to traverse

A	All successor of a visited node before any successors of any of those successors
B	A single path of the graph as far it can go
C	Graph using shortest path
D	None of these

Data-StructuresGraphs-and-TreeTNPSC-2012-Polytechnic-CS

Question 7 Explanation:

Breadth first traversal is a method to traverse all successor of a visited node before any successors of any of those successors.

There are 7 questions to complete.

Access quiz wise question and answers by becoming as a solutions adda PRO SUBSCRIBER with Ad-Free content

If you have registered and made your payment please contact solutionsadda.in@gmail.com to get access