Introduction to Programming Using Python, Y. Daniel Liang

Many questions in this edition have been updated in the new edition. Please check with the publisher on the newest edition.

This quiz is for students to practice. A large number of additional quiz is available for instructors using Quiz Generator from the Instructor's Resource Website. Videos for Java, Python, and C++ can be found at https://yongdanielliang.github.io/revelvideos.html.

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