Deck 13: Sets and Maps

Question 1

An undirected graph is a graph where the pairings representing the edges are _____________.

A) Unordered
B) Ordered
C) Sorted
D) None of the above

Answer 1

Unordered

Question 2

Two vertices in a graph are ___________ if there is an edge connecting them.

A) Connected
B) Adjacent
C) Ordered
D) None of the above

Answer 2

Adjacent

Question 3

An undirected graph is considered complete if it has the maximum number of edges connecting vertices.

A) Connected
B) Adjacent
C) Complete
D) Full

Answer 3

Complete

Question 4

A _________ is a sequence of edges that connects two vertices in a graph.

A) Connection
B) Path
C) Set
D) Cycle

Question 5

A ________ is a path in which the first and last vertices are the same and none of the edges are repeated.

A) Connection
B) Path
C) Set
D) Cycle

Question 6

An undirected tree is a connected, acyclic, undirected graph with one element designated as the _______.

A) Starting point
B) Root
C) Leaf
D) Cycle

Question 7

A directed graph, sometimes referred as a digraph, is a graph where the edges are _________ pairs of vertices.

A) Unordered
B) Ordered
C) Sorted
D) None of the above

Question 8

A path in a directed graph is a sequence of directed edges that connects two _________ in a graph.

A) Vertices
B) Trees
C) Edges
D) None of the above

Question 9

A ________, or a weighted graph, is a graph with weights or costs associated with each edge.

A) Tree
B) Graph
C) Network
D) None of the above

Question 10

The only difference between a depth-first traversal of a graph and a breadth-first traversal is the use of a _________ instead of a queue to manage the traversal.

A) Stack
B) Tree
C) List
D) Heap

Question 11

A graph is connected if and only if the number of vertices in the __________ traversal is the same as the number of vertices in the graph regardless of the starting vertex.

A) Depth-first
B) Breadth-first
C) Level-order
D) None of the above

Question 12

A __________ tree is a tree that includes all of the vertices of a graph and some, but possibly not all, of the edges.

A) Directed
B) Undirected
C) Spanning
D) None of the above

Question 13

A minimum spanning tree is a spanning tree where the sum of the weights of the edges is ____________ to the sum of the weights for any other spanning tree for the same graph.

A) Less than or equal
B) Greater than or equal
C) Equal
D) None of the above

Question 14

An ______ graph is a graph where the pairings representing the edges are unordered.

Question 15

Two vertices in a graph are adjacent if there is an edge ______ them.

Question 16

An undirected graph is considered complete if it has the ______ number of edges connecting vertices.

Question 17

A ______ is a sequence of edges that connects two vertices in a graph.

Question 18

A cycle is a path in which the first and last vertices are ______ and none of the edges are repeated.

Question 19

An undirected tree is a connected, ______, undirected graph with one element designated as the root.

Question 20

A ______, sometimes referred as a digraph, is a graph where the edges are ordered pairs of vertices.

Question 21

A path in a directed graph is a sequence of ______ edges that connects two vertices in a graph.

Question 22

A ______, or a weighted graph, is a graph with weights or costs associated with each edge.

Question 23

The only difference between a depth-first traversal of a graph and a breadth-first traversal is the use of a stack instead of a ______ to manage the traversal.

Question 24

A graph is ______ if and only if the number of vertices in the breadth-first traversal is the same as the number of vertices in the graph regardless of the starting vertex.

Question 25

A spanning tree is a tree that includes all of the ______ of a graph and some, but possibly not all, of the ______.

Question 26

A ______ is a spanning tree where the sum of the weights of the edges is less than or equal to the sum of the weights for any other spanning tree for the same graph.

Question 27

An undirected graph is a graph where the pairings representing the edges are unordered.

Question 28

Two vertices in a graph are adjacent if there is an edge connecting them.

Question 29

An undirected graph is considered complete if it has the maximum number of edges connecting vertices.

Question 30

A path is a sequence of edges that connects two vertices in a graph.

Question 31

A cycle is a path in which the first and last vertices are the same and only one of the edges are repeated.

Question 32

An undirected tree is a connected, cyclic, undirected graph with one element designated as the root.

Question 33

A directed graph, sometimes referred as a digraph, is a graph where the edges are ordered pairs of vertices.

Question 34

A path in a directed graph is a sequence of undirected edges that connects two vertices in a graph.

Question 35

A network, or a weighted graph, is a graph with weights or costs associated with each edge.

Question 36

The only difference between a depth-first traversal of a graph and a breadth-first traversal is the use of a queue instead of a stack to manage the traversal.

Question 37

A graph is connected if and only if the number of vertices in the breadth-first traversal is the same as the number of vertices in the graph regardless of the starting vertex.

Question 38

A spanning tree is a tree that includes all of the edges of a graph and some, but possibly not all, of the vertices.

Question 39

A minimum spanning tree is a spanning tree where the sum of the weights of the edges is greater than or equal to the sum of the weights for any other spanning tree for the same graph.

Question 40

What is the difference between a graph and a tree?

Question 41

What is an undirected graph?

Question 42

What is a directed graph?

Question 43

What does it mean to say that a graph is complete?

Question 44

What is the maximum number of edges for an undirected graph? A directed graph?

Question 45

What is the definition of path? Of cycle?

Question 46

What is the difference between a network and a graph?

Question 47

What is a spanning tree? A minimum spanning tree?