Time Left - 15:00 mins

# GATE 2022: Data Structure and Programming Quiz-11

Attempt now to get your rank among 363 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 __________

- 363 attempts
- 1 upvote
- 0 comments

Aug 1GATE & PSU CS

Posted by: