7137374
Description
Quiz by Mena Sargios, updated more than 1 year ago
|
Created by Mena Sargios
over 7 years ago
|
|
Question 1
Question
How do you know if a connected undirected graph does not contain a cycle?
Answer
-
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
Question 2
Question
A connected undirected graph with 17 nodes has 20 edges.
Is it a spanning tree? If so, why?
Answer
-
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.
Question 3
Question
How do you get the minimum spanning tree?
Answer
-
Prim's Algorithm
-
none
Question 4
Question
What is a spanning tree?
Answer
-
A.graph that has two cycles
-
B.graph that has one cycle
-
C.graph that has no cycle
-
D.none of the above
Question 5
Question
What is a Spannning three?
Answer
-
A. Connected graph
-
B. Undirected graph without cycles
-
C. All the above.
Question 6
Question
What results from a Depth-First Search?
Answer
-
A) 2-3 Tree
-
B) Binary Tree
-
C) Balanced Binary Tree
-
D) Spanning Tree
Question 7
Question
A connected __ digraph with n vertices and ___ n-1 degrees ___ a cycle
Answer
-
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
Question 8
Question
What aglorithm is used to find the minimum spanning tree for a graph?
Answer
-
A. Depth First Search
-
B. Bubble Sort
-
C. Dijkstra's Algorithm
-
D. Prim's Algorithm
Question 9
Question
Which of the following is NOT a way to find a spanning tree?
Answer
-
A. DFS
-
B. BFS
-
C. Prim's
-
D. Dijkstra's
Question 10
Question
Which of the following are correct concerning spanning trees?
Answer
-
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
Question 11
Question
A graph with that is not connected will not have a spanning tree?
Answer
- True
- False
Question 12
Question
A connected undirected graph that has n vertices and exactly n - 1 edges must contain at least one cycle.
Answer
- True
- False
Want to create your own Quizzes for free with GoConqr? Learn more.