Mena Sargios
Quiz by , created more than 1 year ago

Algorithms and Data Structures | Test 3 Review | CSCI-3110-002 MTSU

41
1
0
Mena Sargios
Created by Mena Sargios over 7 years ago
Close

15. Graph Spanning Tree

Question 1 of 12

1

How do you know if a connected undirected graph does not contain a cycle?

Select one of the following:

  • A connected undirected graph that has EXACTLY n-1 edges, with n being the number of nodes in the graph, cannot contain a cycle.

  • none

Explanation

Question 2 of 12

1

A connected undirected graph with 17 nodes has 20 edges.
Is it a spanning tree? If so, why?

Select one of the following:

  • A) No.

  • B) Not enough information is presented to reach a conclusion.

  • C) Yes; any connected but undirected graph is a spanning tree.

  • D) Yes; a spanning tree is a connected graph with at least (N + 1)
    edges.

Explanation

Question 3 of 12

1

How do you get the minimum spanning tree?

Select one of the following:

  • Prim's Algorithm

  • none

Explanation

Question 4 of 12

1

What is a spanning tree?

Select one of the following:

  • A.graph that has two cycles

  • B.graph that has one cycle

  • C.graph that has no cycle

  • D.none of the above

Explanation

Question 5 of 12

1

What is a Spannning three?

Select one of the following:

  • A. Connected graph

  • B. Undirected graph without cycles

  • C. All the above.

Explanation

Question 6 of 12

1

What results from a Depth-First Search?

Select one of the following:

  • A) 2-3 Tree

  • B) Binary Tree

  • C) Balanced Binary Tree

  • D) Spanning Tree

Explanation

Question 7 of 12

1

A connected __ digraph with n vertices and ___ n-1 degrees ___ a cycle

Select one of the following:

  • a.directed, exactly, must contain ;undirected, more than, cannot contain

  • b.undirected, more than, must contain ;undirected, exactly, cannot contain

  • c.undirected, exactly, cannot contain ;directed, more than, must contain

  • d.directed, more than, must contain ;directed, exactly, cannot contain

  • e. None of the above

Explanation

Question 8 of 12

1

What aglorithm is used to find the minimum spanning tree for a graph?

Select one of the following:

  • A. Depth First Search

  • B. Bubble Sort

  • C. Dijkstra's Algorithm

  • D. Prim's Algorithm

Explanation

Question 9 of 12

1

Which of the following is NOT a way to find a spanning tree?

Select one of the following:

  • A. DFS

  • B. BFS

  • C. Prim's

  • D. Dijkstra's

Explanation

Question 10 of 12

1

Which of the following are correct concerning spanning trees?

Select one of the following:

  • A. all trees are graphs, but not all graphs are trees, and it is a connected, undirected graph without cycles

  • B. all trees are not graphs, but all graphs are trees, and it is a connected, undirected graph without cycles

  • C. all trees are graphs, but not all graphs are trees, and it is an unconnected, undirected graph without cycles

  • D. all trees are not graphs, but all graphs are trees, and it is an unconnected, undirected graph without cycles

Explanation

Question 11 of 12

1

A graph with that is not connected will not have a spanning tree?

Select one of the following:

  • True
  • False

Explanation

Question 12 of 12

1

A connected undirected graph that has n vertices and exactly n - 1 edges must contain at least one cycle.

Select one of the following:

  • True
  • False

Explanation

Previous
Check answer
Next