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
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
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.
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
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
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
Question 7
Consider a weighted directed graph. The current shortest distance from source S to node x is represented by d[x]. Let d[u] = 15, w[u, v] = 12. What is the updated value of d[u] based on current information
A
29
B
27
C
25
D
17
There are 7 questions to complete.

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

Register Now

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