MAD101_Practice_PT3

Given a graph G as shown below.

What is the order of vertices traversed by Depth First Search algorithm from the vertex a?

• a, b, c, e, g, h, d, f

• a, b, c, d, e, g, h, f

• a, b, c, e, f, d, g, h

• a, b, c, d, e, f, g, h

• (i)

• (ii)

• (iii)

• None of the other choices is correct

If using preorder traversal to visit the vertices of the given rooted tree, what is the position of vertex d?

• None of the other choices is correct

• 4th

• 13th

• 11th

• 7th

How many edges must be removed from the graph to get a spanning tree?

• 5

• 1

• 2

• 3

• 4

Which of the following statements are correct?

(i) If a simple graph is connected, then it has a spanning tree.

(ii) If a simple graph is not connected, then it does not have a spanning tree.

(iii) If a simple graph does not have a spanning tree, then it is not connected.

• Only (i)

• Only (ii)

• Only (iii)

• None of them

• All of (i), (ii) and (iii)

How many edges must be removed from the graph to get a spanning tree?

• 9

• 7

• 11

• 10

• 12

Find the first vertices when using Dijkstra's algorithm to find the shortest path from A to Z.

• A-B-C

• None of the other choices is correct

• A-B-D

• A-B-E

• A-B-Z

Find the postorder traveral of the tree.

• a-c-f-g-e-b-i-j-k-n-m-o-p-l-h-d

• None of the other choices is correct

• d-b-a-c-e-f-g-h-i-l-j-m-k-n-o-p

• a-b-c-f-e-g-d-i-h-j-l-k-m-n-o-p

Apply the Dijkstra algorithm to find the shortest path from A to Z. What is the next vertex chosen after E?

• C

• D

• Z

• None of the other choices is correct

How many cut vertices and cut edges in this graph?

• 2 and 1

• 2 and 2

• 3 and 2

• 1 and 1

• 1 and 3