Graphs-and-Tree

Question 1
 Consider the following statements.
S1:The sequence of procedure calls corresponds to a preorder traversal of the activation tree.
S2:The sequence of procedure returns corresponds to a postorder traversal of the activation tree.
Which one of the following options is correct?
A
S1is false and S2is false
B
S1is true and S2is true
C
S1is true and S2is false
D
S1is false and S2is true
Data-StructuresGraphs-and-TreeGATE 2021 CS-Set-1Video-Explanation
Question 1 Explanation: 

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

  1. The sequence of procedure calls corresponds to a preorder traversal of the activation tree.
  2. 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
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 4 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 5
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 5 Explanation: 
Breadth first traversal is a method to traverse all successor of a visited node before any successors of any of those successors.
Question 6
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 7

A flow graph F with entry node (1) and exit node (11) is shown below:



What is the cyclomatic complexity of flowgraph F
A
2
B
3
C
4
D
5
Data-StructuresGraphs-and-TreeUGC-NET DEC-2019 Part-2
Question 7 Explanation: 
To find cyclomatic complexity we have 3 formulas
1. The number of regions(R) corresponds to the cyclomatic complexity. Total number of regions(R) are 4.
2. V(G),Flow graph is defined as V(G)=E-N+2 where E is the number of flow graph edges, and N is the number of flow graph nodes.
Predicates are 3+1=4
3. V(G),Flow graph is defined as V(G)=P+1 where p is the number of predicate nodes contained in the flow graph G.
Edges(E)-Nodes(N)+2
= 11-9+2
= 2+2
= 4
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