Time Left - 15:00 mins
GATE 2022: Data Structure and Programming Quiz-11
Attempt now to get your rank among 463 students!
Question 1
G is an undirected graph with vertex set {v1, v2, v3, v4, v5, v6, v7} and edge set {v1v2, v1v3, v1v4, v2v4, v2v5, v3v4, 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?
Question 2
One of the application of DFT is to check whether a vertex is articulation point or not. So in a graph with V vertices and E edges, what is the time taken to check whether a specific vertex is articulation point or not :
Question 3
Consider the following undirected graph with 8 nodes .
Now consider the following traversals made on the graph :
I. ABCDHEFG
II. ACBDHFGE
III. ADBCHGFE
IV. HBDEGACF
Which of the above traversals are valid Breadth First traversals ?
Now consider the following traversals made on the graph :
I. ABCDHEFG
II. ACBDHFGE
III. ADBCHGFE
IV. HBDEGACF
Which of the above traversals are valid Breadth First traversals ?
Question 4
Consider the following undirected graph with 8 nodes .
Now consider the following traversals made on the graph :
I. ABHEFGDC
II. ACBHEDFG
III. HEFGDCAB
IV. CBDAHEFG
Which of the above traversals are valid Depth First traversals ?
Now consider the following traversals made on the graph :
I. ABHEFGDC
II. ACBHEDFG
III. HEFGDCAB
IV. CBDAHEFG
Which of the above traversals are valid Depth First traversals ?
Question 5
Apply DFT on the graph given below and find the minimum number of times backtracking required (start from A).
Question 6
We want to store a graph in an array such that the children are stored immediately after the parent.
Example :
Example :
Now consider the following graph and find the index of element "D" in the array if array starts from 0 __________
- 463 attempts
- 1 upvote
- 0 comments
Aug 1GATE & PSU CS
