Introduction to Programming Using Python, Y. Daniel Liang

This quiz is for students to practice. A large number of additional quiz is available for instructors from the Instructor's Resource Website.

Chapter 22 Graphs and Applications

Section 22.2 Basic Graph Terminologies
22.1  A ____ is an edge that links a vertex to itself.
A. loop
B. parallel edge
C. weighted edge
D. directed edge

22.2  If two vertices are connected by two or more edges, these edges are called ______.
A. loop
B. parallel edge
C. weighted edge
D. directed edge

22.3  A _________ is the one in which every two pairs of vertices are connected.
A. complete graph
B. weighted graph
C. directed graph

22.4  What is the number of edges in a complete graph of n vertices?
A. n
B. n - 1
C. n(n-1)/2
D. n*n

22.5  What is the number of edges in a tree of n vertices?
A. n
B. n - 1
C. n(n-1)/2
D. n*n

Sections 22.3-22.10
22.6  The _______ search of a graph first visits a vertex, then it recursively visits all the vertices adjacent to that vertex.
A. depth-first
B. breadth-first

22.7  The _______ the breadth-first search of a graph first visits a vertex, then all its adjacent vertices, then all the vertices adjacent to those vertices, and so on.
A. depth-first
B. breadth-first

22.8  The time complexity of the DFS algorithm is O(|E| + |V|).
A. true
B. false

22.9  The time complexity of the BFS algorithm is O(|E| + |V|).
A. true
B. false