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

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 :

Now consider the following graph and find the index of element "D" in the array if array starts from 0 __________

• 463 attempts
• 1 upvote