Name: 
 

Python Data Structures 20 Q Sample Test



True/False
Indicate whether the statement is true or false.
 

 1. 

Mathematically, a graph is a set V of vertices and a set E of edges, such that each edge in E connects three of the vertices in V.
 

 2. 

Vertices and edges can be labeled or unlabeled.
 

 3. 

Two adjacent vertices are also called neighbors.
 

 4. 

A vertex is reachable from another vertex if and only if there is a path between the two.
 

 5. 

The weight of a path is the number of edges on the path.
 

 6. 

A child of a given graph consists of a subset of that graph’s vertices and the edges connecting those vertices.
 

 7. 

A simple path is a path that does not pass through the same vertex more than once.
 

 8. 

A loop is a path that begins and ends at the same vertex.
 

 9. 

Each edge in a digraph is called a directed edge.
 

 10. 

Lists and trees are special cases of undirected graphs.
 

Multiple Choice
Identify the choice that best completes the statement or answers the question.
 

 11. 

We can use the term ____ as a synonym for vertex.
a.
node
c.
index
b.
element
d.
bucket
 

 12. 

When the edges are labeled with numbers, the graph is said to be a(n) ____ graph.
a.
directed
c.
weighted
b.
undirected
d.
labeled
 

 13. 

One vertex is ____ to another vertex if there is an edge connecting the two vertices.
a.
contiguous
c.
parent
b.
related
d.
adjacent
 

 14. 

A ____ is a sequence of edges that allows one vertex to be reached from another vertex in a graph.
a.
route
c.
link
b.
path
d.
chain
 

 15. 

A graph is ____ if there is a path from each vertex to every other vertex.
a.
directed
c.
weighted
b.
connected
d.
complete
 

 16. 

A graph is ____ if there is an edge from each vertex to every other vertex.
a.
directed
c.
weighted
b.
connected
d.
complete
 

 17. 

The ____ of a vertex is equal to the number of edges connected to it.
a.
degree
c.
label
b.
weight
d.
level
 

 18. 

A ____ is a subgraph consisting of the set of vertices that are reachable from a given vertex.
a.
cycle
c.
connected component
b.
digraph
d.
child
 

 19. 

The edges of a(n) ____ have no direction.
a.
simple graph
c.
cycle
b.
undirected graph
d.
digraph
 

 20. 

The edges in a(n) ____ specify an explicit direction.
a.
simple graph
c.
cycle
b.
undirected graph
d.
digraph
 



 
Check Your Work     Start Over