DSGT_ Unit 5 Quiz

Which of the following is true for a tree?

• It contains cycles

• It is always disconnected

• It is connected and acyclic

• It has more edges than vertices

A leaf node in a tree is a node with:

• No parent

• One child

• Two children

• No children

A spanning tree of a graph is:

• A tree with the smallest number of edges

• A subgraph that includes all vertices and is acyclic

• A tree with the largest number of edges

• None of the above

In a tree with 15 vertices, how many edges are there?

• 14

• 15

• 13

• 16

In preorder traversal, the sequence of traversal is:

• Left → Root → Right

• Root → Left → Right

• Left → Right → Root

• Right → Left → Root

In which traversal is the root visited between the left and right subtrees?

• Preorder

• Inorder

• Postorder

• Level order

What is the first node visited in level order traversal?

• Leftmost leaf

• Left child

• Root

• Rightmost leaf

What is the output of preorder traversal of the tree: A / \ B C / \ \ D E F

• A B D E C F

• D B E A F C

• D E B F C A

• A B C D E F

In Prim's algorithm, we always add the edge with:

• The maximum weight

• The minimum weight that connects to the already selected vertices

• The minimum weight in the whole graph

• The edge with the lowest vertex number

In Kruskal's algorithm, we add edges in the order of:

• Increasing vertex labels

• Decreasing weights

• Increasing weights

• Random selection